sudoku-solver/main.go

104 lines
1.8 KiB
Go

package main
import (
"fmt"
"time"
)
var grid = [9][9]int{
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9},
}
func draw() {
for _, row := range grid {
fmt.Println(row)
}
fmt.Println()
}
func canPut(x int, y int, value int) bool {
return !alreadyInVertical(x, y, value) &&
!alreadyInHorizontal(x, y, value) &&
!alreadyInSquare(x, y, value)
}
func alreadyInVertical(x int, y int, value int) bool {
for i := range [9]int{} {
if grid[i][x] == value {
return true
}
}
return false
}
func alreadyInHorizontal(x int, y int, value int) bool {
for i := range [9]int{} {
if grid[y][i] == value {
return true
}
}
return false
}
func alreadyInSquare(x int, y int, value int) bool {
sx, sy := int(x/3)*3, int(y/3)*3
for dy := range [3]int{} {
for dx := range [3]int{} {
if grid[sy+dy][sx+dx] == value {
return true
}
}
}
return false
}
func next(x int, y int) (int, int) {
nextX, nextY := (x+1)%9, y
if nextX == 0 {
nextY = y + 1
}
return nextX, nextY
}
func solve(x int, y int) bool {
if y == 9 {
return true
}
if grid[y][x] != 0 {
return solve(next(x, y))
} else {
for i := range [9]int{} {
var v = i + 1
if canPut(x, y, v) {
grid[y][x] = v
if solve(next(x, y)) {
return true
}
grid[y][x] = 0
}
}
return false
}
}
func main() {
fmt.Println("Grid to be completed:")
draw()
startSolving := time.Now()
if solve(0, 0) {
stopSolving := time.Since(startSolving)
fmt.Printf("I found a solution (in %v):\n", stopSolving)
draw()
} else {
fmt.Println("I did not find a solution...")
}
}