sudoku-solver/main.go

528 lines
9.3 KiB
Go
Raw Permalink Normal View History

package main
import (
"fmt"
"log"
"math"
"os"
"runtime"
"sync/atomic"
"time"
)
const eliminatedCounterEnabled = true
const size = 25
const blocks = 5
const blockSize = size / blocks
const maskZero = (1 << size) - 1
const guessChanSize = 1 << 20
const eliminatedChanSize = 1 << 15
// can't be constant, because go is strange
var errorGuessChanUsage = int(math.Round(0.8 * float64(guessChanSize)))
var warningEliminatedChanUsage = int(math.Round(0.8 * float64(eliminatedChanSize)))
type field [size][size][]int
var guesses = make(chan field, guessChanSize)
var solution = make(chan field, 1)
var eliminatedChan = make(chan int, eliminatedChanSize)
// 1 because of the first guess = starting point
var possibilities int64 = 1
var globalEliminated int64 = 0
func eliminate(field *field) *int {
eliminated := 0
// columns
for x := 0; x < size; x++ {
bitfield := maskZero
for y := 0; y < size; y++ {
if len(field[x][y]) == 1 {
mask := 1 << (field[x][y][0] - 1)
if bitfield&mask == 0 {
// duplicate number
return nil
}
bitfield &= mask ^ maskZero
}
}
for y := 0; y < size; y++ {
if len(field[x][y]) != 1 {
length := len(field[x][y])
for i := 0; i < length; i++ {
if (bitfield & (1 << (field[x][y][i] - 1))) == 0 {
eliminated++
field[x][y][i] = field[x][y][length-1]
field[x][y] = field[x][y][:length-1]
length--
i--
}
}
if length == 0 {
return nil
}
}
}
}
// rows
for y := 0; y < size; y++ {
bitfield := maskZero
for x := 0; x < size; x++ {
if len(field[x][y]) == 1 {
mask := 1 << (field[x][y][0] - 1)
if bitfield&mask == 0 {
// duplicate number
return nil
}
bitfield &= mask ^ maskZero
}
}
for x := 0; x < size; x++ {
if len(field[x][y]) != 1 {
length := len(field[x][y])
for i := 0; i < length; i++ {
if (bitfield & (1 << (field[x][y][i] - 1))) == 0 {
eliminated++
field[x][y][i] = field[x][y][length-1]
field[x][y] = field[x][y][:length-1]
length--
i--
}
}
if length == 0 {
return nil
}
}
}
}
// blocks
for sx := 0; sx < blocks; sx++ {
for sy := 0; sy < blocks; sy++ {
bitfield := maskZero
for x := sx * blockSize; x < (sx+1)*blockSize; x++ {
for y := sy * blockSize; y < (sy+1)*blockSize; y++ {
if len(field[x][y]) == 1 {
mask := 1 << (field[x][y][0] - 1)
if bitfield&mask == 0 {
// duplicate number
return nil
}
bitfield &= mask ^ maskZero
}
}
}
for x := sx * blockSize; x < (sx+1)*blockSize; x++ {
for y := sy * blockSize; y < (sy+1)*blockSize; y++ {
if len(field[x][y]) != 1 {
length := len(field[x][y])
for i := 0; i < length; i++ {
if (bitfield & (1 << (field[x][y][i] - 1))) == 0 {
eliminated++
field[x][y][i] = field[x][y][length-1]
field[x][y] = field[x][y][:length-1]
length--
i--
}
}
if length == 0 {
return nil
}
}
}
}
}
}
return &eliminated
}
type result int
const (
unsolved result = iota
solved
wrong
)
func check(field *field) result {
for _, column := range field {
for _, row := range column {
switch len(row) {
case 0:
return wrong
case 1:
// check next
default:
return unsolved
}
}
}
return solved
}
func copyField(fieldToCopy field) field {
var fieldCopy field
for x := 0; x < size; x++ {
for y := 0; y < size; y++ {
fieldCopy[x][y] = make([]int, len(fieldToCopy[x][y]))
copy(fieldCopy[x][y], fieldToCopy[x][y])
}
}
return fieldCopy
}
func addGuesses(field field) {
hasGuess := false
minX := 0
minY := 0
minLength := size + 1
for x := 0; x < size; x++ {
for y := 0; y < size; y++ {
length := len(field[x][y])
if length > 1 && length < minLength {
hasGuess = true
minX = x
minY = y
minLength = length
}
}
}
if hasGuess {
for _, value := range field[minX][minY] {
newField := copyField(field)
newField[minX][minY] = []int{value}
atomic.AddInt64(&possibilities, 1)
guesses <- newField
}
}
}
func removePossibility() {
if atomic.AddInt64(&possibilities, -1) <= 0 {
fmt.Println("no solution found")
os.Exit(1)
}
}
func worker() {
workerLoop:
for {
field := <-guesses
eliminateLoop:
for {
eliminated := eliminate(&field)
if eliminated == nil {
removePossibility()
continue workerLoop
} else if *eliminated == 0 {
break eliminateLoop
} else {
if eliminatedCounterEnabled {
eliminatedChan <- *eliminated
}
}
}
switch check(&field) {
case wrong:
removePossibility()
continue workerLoop
case solved:
solution <- field
// we don't need the worker anymore
break workerLoop
case unsolved:
addGuesses(field)
removePossibility()
continue workerLoop
}
}
}
func all() []int {
var list []int
for i := 0; i < size; i++ {
list = append(list, i+1)
}
return list
}
func readField(input string) field {
var field field
x := 0
y := 0
for _, c := range input {
inc := false
if c == ' ' || c == '-' {
field[x][y] = all()
inc = true
} else if c >= '0' && c <= '9' {
field[x][y] = []int{int(c - '0')}
inc = true
} else if c >= 'a' && c <= 'z' {
field[x][y] = []int{int(c - 'a' + 10)}
inc = true
} else if c >= 'A' && c <= 'Z' {
field[x][y] = []int{int(c - 'A' + 10)}
inc = true
} else {
// ignore
}
if inc {
x++
if x >= size {
x = 0
y++
}
if y >= size {
break
}
}
}
for x = 0; x < size; x++ {
for y = 0; y < size; y++ {
if field[x][y] == nil {
log.Fatal("not all cells filled")
} else {
for _, value := range field[x][y] {
if value < 1 || value > size {
log.Fatalf("cell range exceeded (%d, %d, %d)", x, y, value)
}
}
}
}
}
return field
}
func printField(field field) {
for y := 0; y < size; y++ {
for x := 0; x < size; x++ {
if len(field[x][y]) == 0 {
fmt.Print("#")
} else if len(field[x][y]) == 1 {
value := field[x][y][0]
if value < 10 {
fmt.Printf("%c", rune(value+'0'))
} else {
fmt.Printf("%c", rune(value-10+'a'))
}
} else {
fmt.Print(" ")
}
}
fmt.Print("\n")
}
}
func eliminiatedCounter() {
for {
eliminiated := <-eliminatedChan
globalEliminated += int64(eliminiated)
}
}
/*const wikipedia = `
53--7----
6--195---
-98----6-
8---6---3
4--8-3--1
7---2---6
-6----28-
---419--5
----8--79
`
const medium = `
47-53----
-9-----8-
-1--2--5-
1--7--5-4
--39--1--
---65-9-3
95--172-6
28------1
7---64-9-
`
const hard = `
---29--4-
--31-5-26
--96-----
2----83--
1----98-5
-57------
768-----4
----6-2-9
----4---3
`
const veryDifficult = `
-21-6-4--
---5---9-
4----2--1
84--5----
1-------2
----4--75
7--6----4
-3---9---
--8-3-61-
`
const hardest = `
8--------
--36-----
-7--9-2--
-5---7---
----457--
---1---3-
--1----68
--85---1-
-9----4--
`*/
const test16x16 = `
c3-8---g7f---4-e
---ac-3-----g2-7
-b-d--8-5-9---f-
-9-4--2---gdb-53
--f-----27b---4-
4--------5-g9-7c
---e3----c--85--
-c951--e8-a4f---
---g48-56--a1ed-
--d9--b----c5---
5a-6f-e--------b
-e---7d2-----8--
a2-f85---g--4-e-
-4---a-3-2--6-1-
g-5c-----4-e2---
6-e---gfa---3-c5
`
const test25x25 = `
7B---6C--F29-----E----M-K
-J-9-K---38--7-I-A--O-G--
---P6-2--A----I----KF----
-K-1--J4-EO-D5-6L-P--N--8
-HEG-P----FKC--58---4---L
---2B--J---N8-9H--4----3O
---4-O--A87--2-3-P-------
H------E---A--F-GC-I----6
---O---2I----C----M---E--
------6-K-H-M-3----A1----
B2-5--MC4---O8-----3-6JL9
-F1--8-H--L--J---B--E-K27
E-G--DA3N-9--P6F157HB8---
M-A-O-E9-6D-5---I2--C4H--
---ND--5--3----LC6--GF---
P4-3F2H-GD-M---N-9-J---B-
N-B-8--A1-4I-LGP37--2--F-
--7C5-NF------8---HBL----
--2--9I-8-J---B-O-65NG-7-
------K-M4----5-A8-E-I1--
--LFE---D---3I---N----P6C
D6--3--7----J-H-BL-P---1-
A-NI1-O---MC-------9K-48F
85--JC---1A-L--DF-G2I-3-H
97----------K41--I-O-2-5-
`
func main() {
field := readField(test25x25)
printField(field)
guesses <- field
fmt.Println()
threads := runtime.GOMAXPROCS(0)
fmt.Printf("number of threads: %d\n", threads)
for x := 0; x < threads; x++ {
go worker()
}
if eliminatedCounterEnabled {
go eliminiatedCounter()
}
eliminatedChanSizeWarningShowed := false
guessChanSizeWarningShowed := false
for {
time.Sleep(10 * time.Millisecond)
fmt.Printf("queued: %10d, remaining: %10d", len(guesses), possibilities)
if eliminatedCounterEnabled {
fmt.Printf(", eliminated: %d (+ %d) ", globalEliminated, len(eliminatedChan))
}
fmt.Print("\r")
if len(guesses) >= errorGuessChanUsage {
if len(guesses) == guessChanSize {
fmt.Println()
fmt.Printf("error: guessChan full, deadlock; increase guessChanSize (current value: %d)\n", guessChanSize)
os.Exit(1)
} else if !guessChanSizeWarningShowed {
fmt.Println()
fmt.Printf("warning: guessChan is nearly full; increase guessChanSize (current value: %d)\n", guessChanSize)
guessChanSizeWarningShowed = true
}
}
if !eliminatedChanSizeWarningShowed && len(eliminatedChan) >= warningEliminatedChanUsage {
2021-01-04 20:41:39 +00:00
fmt.Println()
fmt.Printf(
"warning: eliminated chan is nearly full, might slow down workers; increase eliminatedChanSize (current value: %d)\n",
eliminatedChanSize)
eliminatedChanSizeWarningShowed = true
2021-01-04 20:41:39 +00:00
}
if len(solution) > 0 {
break
}
}
solution := <-solution
fmt.Println()
fmt.Println()
fmt.Println()
fmt.Println("solved")
printField(solution)
}