--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/solve.go Sun Oct 16 09:41:57 2016 +0200
@@ -0,0 +1,375 @@
+package takuzu
+
+import (
+ "fmt"
+ "log"
+ "runtime"
+ "sync"
+ "time"
+
+ "github.com/pkg/errors"
+)
+
+var verbosity int
+var schrodLvl uint
+
+// SetVerbosityLevel initializes the verbosity level of the resolution
+// routines.
+func SetVerbosityLevel(level int) {
+ verbosity = level
+}
+
+// SetSchrodingerLevel initializes the "Schrödinger" level (0 means disabled)
+// It must be called before any board generation or reduction.
+func SetSchrodingerLevel(level uint) {
+ schrodLvl = level
+}
+
+func (b Takuzu) guessPos(l, c int) int {
+ if b.Board[l][c].Defined {
+ return b.Board[l][c].Value
+ }
+
+ bx := b.Clone()
+ bx.Set(l, c, 0)
+ bx.FillLineColumn(l, c)
+ if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {
+ return 1
+ }
+ Copy(&b, &bx)
+ bx.Set(l, c, 1)
+ bx.FillLineColumn(l, c)
+ if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {
+ return 0
+ }
+
+ return -1 // dunno
+}
+
+// TrivialHint returns the coordinates and the value of the first cell that
+// can be guessed using trivial methods.
+// It returns {-1, -1, -1} if none can be found.
+func (b Takuzu) TrivialHint() (line, col, value int) {
+ for line = 0; line < b.Size; line++ {
+ for col = 0; col < b.Size; col++ {
+ if b.Board[line][col].Defined {
+ continue
+ }
+ if value = b.guessPos(line, col); value != -1 {
+ return
+ }
+ }
+ }
+ value, line, col = -1, -1, -1
+ return
+}
+
+// trySolveTrivialPass does 1 pass over the takuzu board and tries to find
+// values using simple guesses.
+func (b Takuzu) trySolveTrivialPass() (changed bool) {
+ for line := 0; line < b.Size; line++ {
+ for col := 0; col < b.Size; col++ {
+ if b.Board[line][col].Defined {
+ continue
+ }
+ if guess := b.guessPos(line, col); guess != -1 {
+ b.Set(line, col, guess)
+ if verbosity > 3 {
+ log.Printf("Trivial: Setting [%d,%d] to %d", line, col, guess)
+ }
+ changed = true // Ideally remember l,c
+ }
+ }
+ }
+ return changed
+}
+
+// TrySolveTrivial tries to solve the takuzu using a loop over simple methods
+// It returns true if all cells are defined, and an error if the grid breaks the rules.
+func (b Takuzu) TrySolveTrivial() (bool, error) {
+ for {
+ changed := b.trySolveTrivialPass()
+ if verbosity > 3 {
+ var status string
+ if changed {
+ status = "ongoing"
+ } else {
+ status = "stuck"
+ }
+ log.Println("Trivial resolution -", status)
+ }
+ if !changed {
+ break
+ }
+
+ if verbosity > 3 {
+ b.DumpBoard()
+ fmt.Println()
+ }
+ }
+ full, err := b.Validate()
+ if err != nil {
+ return full, errors.Wrap(err, "the takuzu looks wrong")
+ }
+ return full, nil
+}
+
+// TrySolveRecurse tries to solve the takuzu recursively, using trivial
+// method first and using guesses if it fails.
+func (b Takuzu) TrySolveRecurse(allSolutions *[]Takuzu, timeout time.Duration) (*Takuzu, error) {
+
+ var solutionsMux sync.Mutex
+ var singleSolution *Takuzu
+ var solutionMap map[string]*Takuzu
+
+ var globalSearch bool
+ // globalSearch doesn't need to use a mutex and is more convenient
+ // to use than allSolutions.
+ if allSolutions != nil {
+ globalSearch = true
+ solutionMap = make(map[string]*Takuzu)
+ }
+
+ startTime := time.Now()
+
+ var recurseSolve func(level int, t Takuzu, errStatus chan<- error) error
+
+ recurseSolve = func(level int, t Takuzu, errStatus chan<- error) error {
+
+ reportStatus := func(failure error) {
+ // Report status to the caller's channel
+ if errStatus != nil {
+ errStatus <- failure
+ }
+ }
+
+ // In Schröndinger mode we check concurrently both values for a cell
+ var schrodinger bool
+ concurrentRoutines := 1
+ if level < int(schrodLvl) {
+ schrodinger = true
+ concurrentRoutines = 2
+ }
+
+ var status [2]chan error
+ status[0] = make(chan error)
+ status[1] = make(chan error)
+
+ for {
+ // Try simple resolution first
+ full, err := t.TrySolveTrivial()
+ if err != nil {
+ reportStatus(err)
+ return err
+ }
+
+ if full { // We're done
+ if verbosity > 1 {
+ log.Printf("{%d} The takuzu is correct and complete.", level)
+ }
+ solutionsMux.Lock()
+ singleSolution = &t
+ if globalSearch {
+ solutionMap[t.ToString()] = &t
+ }
+ solutionsMux.Unlock()
+
+ reportStatus(nil)
+ return nil
+ }
+
+ if verbosity > 2 {
+ log.Printf("{%d} Trivial resolution did not complete.", level)
+ }
+
+ // Trivial method is stuck, let's use recursion
+
+ changed := false
+
+ // Looking for first empty cell
+ var line, col int
+ firstClear:
+ for line = 0; line < t.Size; line++ {
+ for col = 0; col < t.Size; col++ {
+ if !t.Board[line][col].Defined {
+ break firstClear
+ }
+ }
+ }
+
+ if line == t.Size || col == t.Size {
+ break
+ }
+
+ if verbosity > 2 {
+ log.Printf("{%d} GUESS - Trying values for [%d,%d]", level, line, col)
+ }
+
+ var val int
+ err = nil
+ errCount := 0
+
+ for testval := 0; testval < 2; testval++ {
+ if !globalSearch && t.Board[line][col].Defined {
+ // No need to "guess" here anymore
+ break
+ }
+
+ // Launch goroutines for cell values of 0 and/or 1
+ for testCase := 0; testCase < 2; testCase++ {
+ if schrodinger || testval == testCase {
+ tx := t.Clone()
+ tx.Set(line, col, testCase)
+ go recurseSolve(level+1, tx, status[testCase])
+ }
+ }
+
+ // Let's collect the goroutines' results
+ for i := 0; i < concurrentRoutines; i++ {
+ if schrodinger && verbosity > 1 { // XXX
+ log.Printf("{%d} Schrodinger waiting for result #%d for cell [%d,%d]", level, i, line, col)
+ }
+ select {
+ case e := <-status[0]:
+ err = e
+ val = 0
+ case e := <-status[1]:
+ err = e
+ val = 1
+ }
+
+ if schrodinger && verbosity > 1 { // XXX
+ log.Printf("{%d} Schrodinger result #%d/2 for cell [%d,%d]=%d - err=%v", level, i+1, line, col, val, err)
+ }
+
+ if err == nil {
+ if !globalSearch {
+ reportStatus(nil)
+ if i+1 < concurrentRoutines {
+ // Schröndinger mode and we still have one status to fetch
+ <-status[1-val]
+ }
+ return nil
+ }
+ continue
+ }
+ if timeout > 0 && level > 2 && time.Since(startTime) > timeout {
+ if errors.Cause(err).Error() != "timeout" {
+ if verbosity > 0 {
+ log.Printf("{%d} Timeout, giving up", level)
+ }
+ err := errors.New("timeout")
+ reportStatus(err)
+ if i+1 < concurrentRoutines {
+ // Schröndinger mode and we still have one status to fetch
+ <-status[1-val]
+ }
+ // XXX actually can't close the channel and leave, can I?
+ return err
+ }
+ }
+
+ // err != nil: we can set a value -- unless this was a timeout
+ if errors.Cause(err).Error() == "timeout" {
+ if verbosity > 1 {
+ log.Printf("{%d} Timeout propagation", level)
+ }
+ reportStatus(err)
+ if i+1 < concurrentRoutines {
+ // Schröndinger mode and we still have one status to fetch
+ <-status[1-val]
+ }
+ // XXX actually can't close the channel and leave, can I?
+ return err
+ }
+
+ errCount++
+ if verbosity > 2 {
+ log.Printf("{%d} Bad outcome (%v)", level, err)
+ log.Printf("{%d} GUESS was wrong - Setting [%d,%d] to %d",
+ level, line, col, 1-val)
+ }
+
+ t.Set(line, col, 1-val)
+ changed = true
+
+ } // concurrentRoutines
+
+ if (changed && !globalSearch) || schrodinger {
+ // Let's loop again with the new board
+ break
+ }
+ }
+
+ if verbosity > 2 {
+ log.Printf("{%d} End of cycle.\n\n", level)
+ }
+
+ if errCount == 2 {
+ // Both values failed
+ err := errors.New("dead end")
+ reportStatus(err)
+ return err
+ }
+
+ // If we cannot fill more cells (!changed) or if we've made a global search with
+ // both values, the search is complete.
+ if schrodinger || globalSearch || !changed {
+ break
+ }
+
+ if verbosity > 2 {
+ t.DumpBoard()
+ fmt.Println()
+ }
+ }
+
+ // Try to force garbage collection
+ runtime.GC()
+
+ full, err := t.Validate()
+ if err != nil {
+ if verbosity > 1 {
+ log.Println("The takuzu looks wrong - ", err)
+ }
+ err := errors.Wrap(err, "the takuzu looks wrong")
+ reportStatus(err)
+ return err
+ }
+ if full {
+ if verbosity > 1 {
+ log.Println("The takuzu is correct and complete")
+ }
+ solutionsMux.Lock()
+ singleSolution = &t
+ if globalSearch {
+ solutionMap[t.ToString()] = &t
+ }
+ solutionsMux.Unlock()
+ }
+
+ reportStatus(nil)
+ return nil
+ }
+
+ status := make(chan error)
+ go recurseSolve(0, b, status)
+
+ err := <-status // Wait for it...
+
+ firstSol := singleSolution
+ if globalSearch {
+ for _, tp := range solutionMap {
+ *allSolutions = append(*allSolutions, *tp)
+ }
+ }
+
+ if err != nil {
+ return firstSol, err
+ }
+
+ if globalSearch && len(*allSolutions) > 0 {
+ firstSol = &(*allSolutions)[0]
+ }
+ return firstSol, nil
+}
--- a/takuzu.go Fri Sep 09 23:28:58 2016 +0200
+++ b/takuzu.go Sun Oct 16 09:41:57 2016 +0200
@@ -3,18 +3,11 @@
import (
"bytes"
"fmt"
- "log"
"math"
- "runtime"
- "sync"
- "time"
"github.com/pkg/errors"
)
-var verbosity int
-var schrodLvl uint
-
// Cell is a single cell of a Takuzu game board
type Cell struct {
Defined bool
@@ -49,8 +42,6 @@
return nil, errors.New("bad string length")
}
- // TODO: validate chars ([.01OI])
-
i := 0
t := New(size)
@@ -88,7 +79,7 @@
return sbuf.String()
}
-// DumpString writes the content of the board as a stream
+// DumpString writes the content of the board as a string
func (b Takuzu) DumpString() {
fmt.Println(b.ToString())
}
@@ -399,363 +390,3 @@
}
return full, counters[0], counters[1]
}
-
-func (b Takuzu) guessPos(l, c int) int {
- if b.Board[l][c].Defined {
- return b.Board[l][c].Value
- }
-
- bx := b.Clone()
- bx.Set(l, c, 0)
- bx.FillLineColumn(l, c)
- if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {
- return 1
- }
- Copy(&b, &bx)
- bx.Set(l, c, 1)
- bx.FillLineColumn(l, c)
- if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {
- return 0
- }
-
- return -1 // dunno
-}
-
-// TrivialHint returns the coordinates and the value of the first cell that
-// can be guessed using trivial methods.
-// It returns {-1, -1, -1} if none can be found.
-func (b Takuzu) TrivialHint() (line, col, value int) {
- for line = 0; line < b.Size; line++ {
- for col = 0; col < b.Size; col++ {
- if b.Board[line][col].Defined {
- continue
- }
- if value = b.guessPos(line, col); value != -1 {
- return
- }
- }
- }
- value, line, col = -1, -1, -1
- return
-}
-
-// trySolveTrivialPass does 1 pass over the takuzu board and tries to find
-// values using simple guesses.
-func (b Takuzu) trySolveTrivialPass() (changed bool) {
- for line := 0; line < b.Size; line++ {
- for col := 0; col < b.Size; col++ {
- if b.Board[line][col].Defined {
- continue
- }
- if guess := b.guessPos(line, col); guess != -1 {
- b.Set(line, col, guess)
- if verbosity > 3 {
- log.Printf("Trivial: Setting [%d,%d] to %d", line, col, guess)
- }
- changed = true // Ideally remember l,c
- }
- }
- }
- return changed
-}
-
-// TrySolveTrivial tries to solve the takuzu using a loop over simple methods
-// It returns true if all cells are defined, and an error if the grid breaks the rules.
-func (b Takuzu) TrySolveTrivial() (bool, error) {
- for {
- changed := b.trySolveTrivialPass()
- if verbosity > 3 {
- var status string
- if changed {
- status = "ongoing"
- } else {
- status = "stuck"
- }
- log.Println("Trivial resolution -", status)
- }
- if !changed {
- break
- }
-
- if verbosity > 3 {
- b.DumpBoard()
- fmt.Println()
- }
- }
- full, err := b.Validate()
- if err != nil {
- return full, errors.Wrap(err, "the takuzu looks wrong")
- }
- return full, nil
-}
-
-// TrySolveRecurse tries to solve the takuzu recursively, using trivial
-// method first and using guesses if it fails.
-func (b Takuzu) TrySolveRecurse(allSolutions *[]Takuzu, timeout time.Duration) (*Takuzu, error) {
-
- var solutionsMux sync.Mutex
- var singleSolution *Takuzu
- var solutionMap map[string]*Takuzu
-
- var globalSearch bool
- // globalSearch doesn't need to use a mutex and is more convenient
- // to use than allSolutions.
- if allSolutions != nil {
- globalSearch = true
- solutionMap = make(map[string]*Takuzu)
- }
-
- startTime := time.Now()
-
- var recurseSolve func(level int, t Takuzu, errStatus chan<- error) error
-
- recurseSolve = func(level int, t Takuzu, errStatus chan<- error) error {
-
- reportStatus := func(failure error) {
- // Report status to the caller's channel
- if errStatus != nil {
- errStatus <- failure
- }
- }
-
- // In Schröndinger mode we check concurrently both values for a cell
- var schrodinger bool
- concurrentRoutines := 1
- if level < int(schrodLvl) {
- schrodinger = true
- concurrentRoutines = 2
- }
-
- var status [2]chan error
- status[0] = make(chan error)
- status[1] = make(chan error)
-
- for {
- // Try simple resolution first
- full, err := t.TrySolveTrivial()
- if err != nil {
- reportStatus(err)
- return err
- }
-
- if full { // We're done
- if verbosity > 1 {
- log.Printf("{%d} The takuzu is correct and complete.", level)
- }
- solutionsMux.Lock()
- singleSolution = &t
- if globalSearch {
- solutionMap[t.ToString()] = &t
- }
- solutionsMux.Unlock()
-
- reportStatus(nil)
- return nil
- }
-
- if verbosity > 2 {
- log.Printf("{%d} Trivial resolution did not complete.", level)
- }
-
- // Trivial method is stuck, let's use recursion
-
- changed := false
-
- // Looking for first empty cell
- var line, col int
- firstClear:
- for line = 0; line < t.Size; line++ {
- for col = 0; col < t.Size; col++ {
- if !t.Board[line][col].Defined {
- break firstClear
- }
- }
- }
-
- if line == t.Size || col == t.Size {
- break
- }
-
- if verbosity > 2 {
- log.Printf("{%d} GUESS - Trying values for [%d,%d]", level, line, col)
- }
-
- var val int
- err = nil
- errCount := 0
-
- for testval := 0; testval < 2; testval++ {
- if !globalSearch && t.Board[line][col].Defined {
- // No need to "guess" here anymore
- break
- }
-
- // Launch goroutines for cell values of 0 and/or 1
- for testCase := 0; testCase < 2; testCase++ {
- if schrodinger || testval == testCase {
- tx := t.Clone()
- tx.Set(line, col, testCase)
- go recurseSolve(level+1, tx, status[testCase])
- }
- }
-
- // Let's collect the goroutines' results
- for i := 0; i < concurrentRoutines; i++ {
- if schrodinger && verbosity > 1 { // XXX
- log.Printf("{%d} Schrodinger waiting for result #%d for cell [%d,%d]", level, i, line, col)
- }
- select {
- case e := <-status[0]:
- err = e
- val = 0
- case e := <-status[1]:
- err = e
- val = 1
- }
-
- if schrodinger && verbosity > 1 { // XXX
- log.Printf("{%d} Schrodinger result #%d/2 for cell [%d,%d]=%d - err=%v", level, i+1, line, col, val, err)
- }
-
- if err == nil {
- if !globalSearch {
- reportStatus(nil)
- if i+1 < concurrentRoutines {
- // Schröndinger mode and we still have one status to fetch
- <-status[1-val]
- }
- return nil
- }
- continue
- }
- if timeout > 0 && level > 2 && time.Since(startTime) > timeout {
- if errors.Cause(err).Error() != "timeout" {
- if verbosity > 0 {
- log.Printf("{%d} Timeout, giving up", level)
- }
- err := errors.New("timeout")
- reportStatus(err)
- if i+1 < concurrentRoutines {
- // Schröndinger mode and we still have one status to fetch
- <-status[1-val]
- }
- // XXX actually can't close the channel and leave, can I?
- return err
- }
- }
-
- // err != nil: we can set a value -- unless this was a timeout
- if errors.Cause(err).Error() == "timeout" {
- if verbosity > 1 {
- log.Printf("{%d} Timeout propagation", level)
- }
- reportStatus(err)
- if i+1 < concurrentRoutines {
- // Schröndinger mode and we still have one status to fetch
- <-status[1-val]
- }
- // XXX actually can't close the channel and leave, can I?
- return err
- }
-
- errCount++
- if verbosity > 2 {
- log.Printf("{%d} Bad outcome (%v)", level, err)
- log.Printf("{%d} GUESS was wrong - Setting [%d,%d] to %d",
- level, line, col, 1-val)
- }
-
- t.Set(line, col, 1-val)
- changed = true
-
- } // concurrentRoutines
-
- if (changed && !globalSearch) || schrodinger {
- // Let's loop again with the new board
- break
- }
- }
-
- if verbosity > 2 {
- log.Printf("{%d} End of cycle.\n\n", level)
- }
-
- if errCount == 2 {
- // Both values failed
- err := errors.New("dead end")
- reportStatus(err)
- return err
- }
-
- // If we cannot fill more cells (!changed) or if we've made a global search with
- // both values, the search is complete.
- if schrodinger || globalSearch || !changed {
- break
- }
-
- if verbosity > 2 {
- t.DumpBoard()
- fmt.Println()
- }
- }
-
- // Try to force garbage collection
- runtime.GC()
-
- full, err := t.Validate()
- if err != nil {
- if verbosity > 1 {
- log.Println("The takuzu looks wrong - ", err)
- }
- err := errors.Wrap(err, "the takuzu looks wrong")
- reportStatus(err)
- return err
- }
- if full {
- if verbosity > 1 {
- log.Println("The takuzu is correct and complete")
- }
- solutionsMux.Lock()
- singleSolution = &t
- if globalSearch {
- solutionMap[t.ToString()] = &t
- }
- solutionsMux.Unlock()
- }
-
- reportStatus(nil)
- return nil
- }
-
- status := make(chan error)
- go recurseSolve(0, b, status)
-
- err := <-status // Wait for it...
-
- firstSol := singleSolution
- if globalSearch {
- for _, tp := range solutionMap {
- *allSolutions = append(*allSolutions, *tp)
- }
- }
-
- if err != nil {
- return firstSol, err
- }
-
- if globalSearch && len(*allSolutions) > 0 {
- firstSol = &(*allSolutions)[0]
- }
- return firstSol, nil
-}
-
-// SetSchrodingerLevel initializes the "Schrödinger" level (0 means disabled)
-// It must be called before any board generation or reduction.
-func SetSchrodingerLevel(level uint) {
- schrodLvl = level
-}
-
-// SetVerbosityLevel initializes the verbosity level
-func SetVerbosityLevel(level int) {
- verbosity = level
-}