Sudoku checker

March 20, 2023

Name: Moch Lutfi
Twitter: @kaptenupi

Problem

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.

Implement an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable.

Example

For

grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '1', '.', '.', '.', '.', '.', '.'], ['.', '6', '7', '.', '.', '.', '.', '.', '9'], ['.', '.', '.', '.', '.', '.', '8', '1', '.'], ['.', '3', '.', '.', '.', '.', '.', '.', '6'], ['.', '.', '.', '.', '.', '7', '.', '.', '.'], ['.', '.', '.', '5', '.', '.', '.', '7', '.']]

the output should be solution(grid) = true;
For

grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'], ['.', '.', '.', '.', '6', '.', '.', '.', '.'], ['7', '1', '.', '.', '7', '5', '.', '.', '.'], ['.', '7', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '8', '3', '.', '.', '.'], ['.', '.', '8', '.', '.', '7', '.', '6', '.'], ['.', '.', '.', '.', '.', '2', '.', '.', '.'], ['.', '1', '.', '2', '.', '.', '.', '.', '.'], ['.', '2', '.', '.', '3', '.', '.', '.', '.']]

the output should be solution(grid) = false.

The given grid is not correct because there are two 1s in the second column. Each column, each row, and each 3 × 3 subgrid can only contain the numbers 1 through 9 one time.

Solution

Before solving the problem we must find out how to check the valid condition of sudoku board.

No duplicate number in same row and column
No duplicate number in 3x3 subgrid

Which data structure to check the duplicate number? Yes we can use map ( Don't forget with Dora The explorer vibes lol).

Here the step by step solution:

Create map map[string]bool to store checker and prepare template string
Iterate through all grid, continue if the grid contains dot if not empty add current value to map in row, column, and subgrid.
If same number occurred in one of row, column and subgrid return false, otherwise continue until finish then return true.

package main
import (
	"fmt"
	"testing"
)
func solution(grid [][]string) bool {
	n := len(grid)
	set := make(map[string]bool)
	const (
		templateRow     = "%s in row %d"
		templateCol     = "%s in col %d"
		templateSubgrid = "%s in square %d %d"
	)
	for row := 0; row < n; row++ {
		for col := 0; col < n; col++ {
			if grid[row][col] == "." {
				continue
			}
			if !set[fmt.Sprintf(templateRow, grid[row][col], row)] {
				set[fmt.Sprintf(templateRow, grid[row][col], row)] = true
			} else {
				return false
			}
			if !set[fmt.Sprintf(templateCol, grid[row][col], col)] {
				set[fmt.Sprintf(templateCol, grid[row][col], col)] = true
			} else {
				return false
			}
			if !set[fmt.Sprintf(templateSubgrid, grid[row][col], row/3, col/3)] {
				set[fmt.Sprintf(templateSubgrid, grid[row][col], row/3, col/3)] = true
			} else {
				return false
			}
		}
	}
	return true
}
func TestSudoku(t *testing.T) {
	tests := []struct {
		grid [][]string
		want bool
	}{
		{
			grid: [][]string{
				{".", ".", ".", ".", "2", ".", ".", "9", "."},
				{".", ".", ".", ".", "6", ".", ".", ".", "."},
				{"7", "1", ".", ".", "7", "5", ".", ".", "."},
				{".", "7", ".", ".", ".", ".", ".", ".", "."},
				{".", ".", ".", ".", "8", "3", ".", ".", "."},
				{".", ".", "8", ".", ".", "7", ".", "6", "."},
				{".", ".", ".", ".", ".", "2", ".", ".", "."},
				{".", "1", ".", "2", ".", ".", ".", ".", "."},
				{".", "2", ".", ".", "3", ".", ".", ".", "."},
			},
			want: false,
		},
		{
			grid: [][]string{
				{".", ".", ".", ".", ".", ".", ".", ".", "."},
				{".", ".", "2", ".", ".", ".", ".", ".", "."},
				{".", ".", ".", ".", ".", "2", "7", "1", "."},
				{".", ".", ".", ".", ".", ".", ".", ".", "."},
				{".", "2", ".", ".", ".", ".", ".", ".", "."},
				{".", "5", ".", ".", ".", ".", ".", ".", "."},
				{".", ".", ".", ".", "9", ".", ".", ".", "8"},
				{".", ".", ".", ".", ".", "1", "6", ".", "."},
				{".", ".", ".", ".", "6", ".", ".", ".", "."}},
			want: true,
		},
	}
	for _, tt := range tests {
		if got := solution(tt.grid); got != tt.want {
			t.Errorf("Sudoku(%v) = %v, want %v", tt.grid, got, tt.want)
		}
	}
}

Try it yourself https://go.dev/play/p/5fwka6bk1vv?v=gotip (opens in a new tab)

Build Directed Graph Implementing a Priority Queue Using Heap in Go