Every good side project comes from a simple question. What if I could do it better? This project is no different. I was inspired by my Mother and her love of Sudoku, the question this time was. "Sure Mom you can solve a few puzzles in an afternoon but what if I could solve all of the Sudoku puzzles in an afternoon?
We'll start by importing the nessessary modules as we do with all Golang projects
package main
import (
"fmt"
)Now comes the basis of the puzzle, our main function containing the unsolved puzzle in a 9x9 matrix
func main() {
grid := [9][9]int{
{0, 0, 9, 0, 0, 0, 6, 0, 0},
{3, 0, 0, 0, 0, 8, 9, 0, 1},
{0, 1, 0, 0, 4, 0, 0, 0, 0},
{9, 0, 0, 2, 0, 0, 7, 8, 0},
{1, 0, 0, 0, 8, 0, 0, 0, 6},
{0, 6, 8, 0, 0, 9, 0, 0, 5},
{0, 0, 0, 0, 2, 0, 0, 4, 0},
{4, 0, 7, 5, 0, 0, 0, 0, 8},
{0, 0, 3, 0, 0, 0, 5, 0, 0},
}The meat of our program will by a function "WalkGrid()" which will recursively traverse each row a column until it finds an empty space which we denoted "0". Once found the function will call a helper function IsSafe() which takes 4 parameters: the current state of our grid, the x and y coordinates and the current number aka the current iteration of our partial solution. If this is a success we will recursively call WalkGrid() again until there are no more spaces to traverse in which case we know we have found the solution.
func WalkGrid(grid [9][9]int) bool {
// Look for the next unassigned number;
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if grid[i][j] == 0 {
for num := 1; num < 10; num++ {
if IsSafe(grid, i, j, num) == true {
grid[i][j] = num
if WalkGrid(grid) == true {
return true
}
grid[i][j] = 0
}
}
return false
}
}
}
// Print the solution;
for k := 0; k < 9; k++ {
fmt.Println(grid[k])
}
return true
}To complete our helper function IsSafe() it should be able to perform safety checks in 3 directions: Current row, Current Column, and Current 3x3 subgrid. We will call three more helper functions IsRowSafe(), IsColSafe(), IsBoxSafe()IsRowSafe() and IsColSafe() will take 2 parameters: the current row as a slice [9]int, and the candidate number.
func IsSafe(grid [9][9]int, i, j, num int) bool {
// Check if the grid is safe or not;
// Check Rows
if IsRowSafe(grid[i], num) == false {
return false
}
// Check Cols
col := [9]int{grid[0][j], grid[1][j], grid[2][j], grid[3][j], grid[4][j],
grid[5][j], grid[6][j], grid[7][j], grid[8][j]}
if IsColSafe(col, num) == false {
return false
}
// Check Boxes
if IsBoxSafe(grid, (i - (i % 3)), (j - (j % 3)), num) == false {
return false
}
return true
}The code for the helper functions is pretty straight forward.
func IsRowSafe(row [9]int, num int) bool {
for i := 0; i < 9; i++ {
if row[i] == num {
return false
}
}
return true
}
func IsColSafe(col [9]int, num int) bool {
for i := 0; i < 9; i++ {
if col[i] == num {
return false
}
}
return true
}IsBoxSafe will take 4 parameters similar to IsSafe(): the current state of the matrix, the current row, current col and again the candidate number.
func IsBoxSafe(grid [9][9]int, row, col, num int) bool {
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if grid[i + row][j + col] == num {
return false
}
}
}
return true
}As seen each function will return a boolean indicating their success. Finally we need to modify main() to alert the user of our success.
func main() {
grid := [9][9]int{
{0, 0, 9, 0, 0, 0, 6, 0, 0},
{3, 0, 0, 0, 0, 8, 9, 0, 1},
{0, 1, 0, 0, 4, 0, 0, 0, 0},
{9, 0, 0, 2, 0, 0, 7, 8, 0},
{1, 0, 0, 0, 8, 0, 0, 0, 6},
{0, 6, 8, 0, 0, 9, 0, 0, 5},
{0, 0, 0, 0, 2, 0, 0, 4, 0},
{4, 0, 7, 5, 0, 0, 0, 0, 8},
{0, 0, 3, 0, 0, 0, 5, 0, 0},
}
if WalkGrid(grid) == true {
fmt.Println("Solution Found")
} else {
fmt.Println("Sudoku has no solution")
}
}Our completed script should look like the following and out output will produce the solution and a status message.
package main
import (
"fmt"
)
func IsRowSafe(row [9]int, num int) bool {
for i := 0; i < 9; i++ {
if row[i] == num {
return false
}
}
return true
}
func IsColSafe(col [9]int, num int) bool {
for i := 0; i < 9; i++ {
if col[i] == num {
return false
}
}
return true
}
func IsBoxSafe(grid [9][9]int, row, col, num int) bool {
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if grid[i + row][j + col] == num {
return false
}
}
}
return true
}
func IsSafe(grid [9][9]int, i, j, num int) bool {
// Check if the grid is safe or not;
// Check Rows
if IsRowSafe(grid[i], num) == false {
return false
}
// Check Cols
col := [9]int{grid[0][j], grid[1][j], grid[2][j], grid[3][j], grid[4][j],
grid[5][j], grid[6][j], grid[7][j], grid[8][j]}
if IsColSafe(col, num) == false {
return false
}
// Check Boxes
if IsBoxSafe(grid, (i - (i % 3)), (j - (j % 3)), num) == false {
return false
}
return true
}
func WalkGrid(grid [9][9]int) bool {
// Look for the next unassigned number;
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if grid[i][j] == 0 {
for num := 1; num < 10; num++ {
if IsSafe(grid, i, j, num) == true {
grid[i][j] = num
if WalkGrid(grid) == true {
return true
}
grid[i][j] = UNASSIGNED
}
}
return false
}
}
}
for k := 0; k < 9; k++ {
fmt.Println(grid[k])
}
return true
}
func main() {
grid := [9][9]int{
{0, 0, 9, 0, 0, 0, 6, 0, 0},
{3, 0, 0, 0, 0, 8, 9, 0, 1},
{0, 1, 0, 0, 4, 0, 0, 0, 0},
{9, 0, 0, 2, 0, 0, 7, 8, 0},
{1, 0, 0, 0, 8, 0, 0, 0, 6},
{0, 6, 8, 0, 0, 9, 0, 0, 5},
{0, 0, 0, 0, 2, 0, 0, 4, 0},
{4, 0, 7, 5, 0, 0, 0, 0, 8},
{0, 0, 3, 0, 0, 0, 5, 0, 0},
}
if WalkGrid(grid) == true {
fmt.Println("Solution Found")
} else {
fmt.Println("Sudoku has no solution")
}
}