Sudoku checker
March 20, 2023
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 two1
s in the second column. Each column, each row, and each3 × 3
subgrid can only contain the numbers1
through9
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 thegrid
containsdot
if not empty add current value to map in row, column, and subgrid. - If same number occurred in one of
row
,column
andsubgrid
return false, otherwise continue until finish then return true.
package mainimport ( "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)