In this article, I will discuss an assignment about determining if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated. I will use the TDD to solve this assignment with two solutions.
Click to become a medium member and read unlimited stories!
Assignment Description
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board partially filled could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit1-9or'.'.
Tests
As the above assignment description is clear, I use the example data as the test cases directly based on that. And I also will add another sudoku as the third test case. I completed the test file content, the following code is the content of the file impl_test.go.
package sudoku
import "testing"
func TestIsValidSudoku(t *testing.T) {
tests := []struct {
name string
board [][]byte
want bool
}{
{
name: "Example 1",
board: [][]byte{
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
},
want: true,
},
{
name: "Example 2",
board: [][]byte{
{'8', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
},
want: false,
},
{
name: "Example 3",
board: [][]byte{
{'6', '.', '.', '.', '.', '2', '5', '.', '.'},
{'.', '1', '7', '5', '.', '.', '.', '.', '.'},
{'4', '.', '.', '.', '.', '.', '.', '2', '.'},
{'.', '7', '.', '.', '2', '3', '.', '6', '.'},
{'.', '.', '.', '.', '1', '.', '3', '.', '.'},
{'.', '.', '2', '.', '.', '5', '7', '.', '.'},
{'.', '.', '.', '4', '.', '.', '.', '.', '.'},
{'.', '9', '5', '.', '.', '.', '.', '3', '.'},
{'1', '.', '8', '.', '.', '.', '9', '.', '.'},
},
want: true,
},
// Additional test cases can be added here
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := isValidSudoku(tt.board)
if got != tt.want {
t.Errorf("isValidSudoku() = %v, want %v", got, tt.want)
}
})
}
}
In the above test content, the reflect.DeepEqual is used to compare the slices. The tests iterate over each test case using a for loop. For each test case, a subtest is created using t.Run(). This allows each test case to be run independently and provides a clear output for which tests pass or fail. I also provide an additional test case in the above.
Let’s run the above tests after I implement the isValidSudoku function.
Solution 1
To solve this problem, the first way I check each number on the Sudoku board is to ensure it does not repeat in its row, column, or 3×3 sub-grid. I use of separate functions for the main validation and rule checking makes the code organized and easier to understand. The solution is in the following content, the file named impl.go.
package sudoku
func isValidSudoku(board [][]byte) bool {
for j := 0; j < 9; j++ {
for i := 0; i < 9; i++ {
if board[i][j] != '.' {
if !validRule(board, i, j) {
return false
}
}
}
}
return true
}
func validRule(board [][]byte, row int, col int) bool {
num := board[row][col]
// Check if the number is valid in the row
for i := 0; i < 9; i++ {
if i != col && board[row][i] == num {
return false
}
}
// Check if the number is valid in the column
for j := 0; j < 9; j++ {
if j != row && board[j][col] == num {
return false
}
}
// Check if the number is valid in the 3x3 grid
startRow, startCol := row/9, col/9
for i := startRow; i < startRow+3; i++ {
for j := startCol; j < startCol+3; j++ {
if (i != row || j != col) && board[i][j] == num {
return false
}
}
}
return true
}
In the above code, I provide two functions. The function isValidSudoku iterates over each cell in the 9*9 Sudoku board. For each cell, it checks if the cell is not empty. If the cell contains a number, it calls the validRule function to check if the current number placement follows Sudoku rules. The function validRule is called with the board and the row and column indices of the current cell. It first retrieves the number (num) from the current cell. It checks all cells in the same row. If any other cell in the row contains the same number (num), it returns false. It also checks all cells in the same column. If any other cell in the column contains the same number, it returns false. It identifies the top-left cell of the 3*3 sub-grid in which the current cell is located. It then checks all cells in this 3*3 grid. If any cell contains the same number, it returns false.
In this solution, if it is a standard 9×9 Sudoku, the time complexity is O(n). In a generalized case for an n x n board, both complexities would be the time complexity is O(n²). And the space complexity is O(1). In the example, n equals 9.
Let’s execute the test using the command “go test . -v” .
Solution 2
In this solution, I provide an optimised solution. The code is in the following content, the file named impl.go.
package sudoku
func isValidSudoku(board [][]byte) bool {
var row, col, box [9][9]bool
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
// This is to convert the character '1'-'9' to an integer 0-8, suitable for indexing arrays.
num := board[i][j] - '1'
boxIndex := (i/3)*3 + j/3
if row[i][num] || col[j][num] || box[boxIndex][num] {
return false
}
row[i][num], col[j][num], box[boxIndex][num] = true, true, true
}
}
}
return true
}
In the above code, I use three 9*9 boolean arrays to keep track of the constraints for each row, column, and 3×3 sub-box. I will explain how it works in below.
Three 9*9 boolean arrays row, col, and box are initialized. Each array is used to track whether a number (1-9) has already been used in the corresponding row, column, or 3*3 sub-box. After that, the function iterates over each cell in the 9*9 Sudoku board using two nested loops. If the cell contains a number, it calculates the value num by subtracting ‘1' from the byte value of the cell. This is to convert the character ‘1’-’9′ to an integer 0–8, suitable for indexing arrays. And then, the function calculates boxIndex, the index of the 3*3 sub-box to which the cell belongs. This is done by dividing the row and column indices by 3, multiplying the row index by 3, and adding the column index. This ensures that each 3×3 sub-box gets a unique index from 0 to 8. Then, the function checks if the number num has already been seen in the current row, column, or 3*3 sub-box. If any of these checks return true, it means the number has already been used in that context, violating Sudoku rules. The function then returns false. If the number hasn’t been used in the same row, column, or box, the function marks it as used by setting row[i][num], col[j][num], and box[boxIndex][num] to true.
This solution’s time complexity is O(n²), where n is the size of one dimension of the Sudoku board. Since the board is 9×9, n is 9. The space complexity is also O(n²), because the solution uses three 9*9 boolean arrays (row, col, and box) to keep track of the numbers used in each row, column, and 3*3 sub-box. Each array has 81 elements (9*9), and since there are three such arrays, the total space used is 3 * 81 = 243, which is constant for a standard Sudoku puzzle. In terms of n, this would be 3 * n², but since the size of the Sudoku board is fixed and does not scale, it’s often considered O(1).
Let’s execute the test using the command “go test . -v” .
Conclusion
In summary, the first solution does not use any additional data structures that grow with the size of the input. The space used for variables and the call stack is constant, regardless of the size of the Sudoku board. The second solution efficiently validates a Sudoku board by using additional space (three 9*9 boolean arrays) to keep track of the constraints. It avoids redundant checks and provides a clear and concise way to ensure that each number appears only once per row, column, and 3*3 sub-box. For a standard 9*9 Sudoku board, both the time and space complexities are effectively constant, O(1), due to the fixed size of the board. However, in a generalized case for an n x n board, both complexities would be O(n²).