--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/takuzu.go Fri Sep 02 21:50:48 2016 +0200
@@ -0,0 +1,731 @@
+package takuzu
+
+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
+ Value int
+}
+
+// Takuzu is a Takuzu game board (Size x Size)
+type Takuzu struct {
+ Size int
+ Board [][]Cell
+}
+
+// New creates a new Takuzu board
+func New(size int) Takuzu {
+ t := Takuzu{Size: size}
+ t.Board = make([][]Cell, size)
+ for l := range t.Board {
+ t.Board[l] = make([]Cell, size)
+ }
+ return t
+}
+
+// NewFromString creates a new Takuzu board from a string definition
+func NewFromString(s string) (*Takuzu, error) {
+ l := len(s)
+ // TODO: validate chars ([.01OI])
+ size := int(math.Sqrt(float64(l)))
+ if size*size != l {
+ return nil, errors.New("bad string length")
+ }
+
+ i := 0
+ t := New(size)
+
+ for line := 0; line < size; line++ {
+ for col := 0; col < size; col++ {
+ switch s[i] {
+ case '0', 'O':
+ t.Board[line][col].Defined = true
+ t.Board[line][col].Value = 0
+ case '1', 'I':
+ t.Board[line][col].Defined = true
+ t.Board[line][col].Value = 1
+ case '.':
+ default:
+ return nil, errors.New("invalid char in string")
+ }
+ i++
+ }
+ }
+ return &t, nil
+}
+
+// ToString converts a takuzu board to its string representation
+func (b Takuzu) ToString() string {
+ var sbuf bytes.Buffer
+ for line := 0; line < b.Size; line++ {
+ for col := 0; col < b.Size; col++ {
+ if b.Board[line][col].Defined {
+ sbuf.WriteString(fmt.Sprintf("%d", b.Board[line][col].Value))
+ continue
+ }
+ sbuf.WriteByte('.')
+ }
+ }
+ return sbuf.String()
+}
+
+// DumpString writes the content of the board as a stream
+func (b Takuzu) DumpString() {
+ fmt.Println(b.ToString())
+}
+
+// Clone returns a copy of the Takuzu board
+func (b Takuzu) Clone() Takuzu {
+ c := New(b.Size)
+ for line := range b.Board {
+ for col := range b.Board[line] {
+ c.Board[line][col] = b.Board[line][col]
+ }
+ }
+ return c
+}
+
+// Copy copies a Takuzu board to another existing board
+func Copy(src, dst *Takuzu) error {
+ if src.Size != dst.Size {
+ return errors.New("sizes do not match")
+ }
+ for line := range src.Board {
+ for col := range src.Board[line] {
+ dst.Board[line][col] = src.Board[line][col]
+ }
+ }
+ return nil
+}
+
+// BoardsMatch compares a Takuzu board to another, optionally ignoring
+// empty cells. Returns true if the two boards match.
+func BoardsMatch(t1, t2 *Takuzu, ignoreUndefined bool) (match bool, line, col int) {
+ match = true
+
+ if t1.Size != t2.Size {
+ line, col = -1, -1
+ match = false
+ return
+ }
+ for line = range t1.Board {
+ for col = range t1.Board[line] {
+ if !t1.Board[line][col].Defined || !t2.Board[line][col].Defined {
+ // At least one of the cells is empty
+ if ignoreUndefined ||
+ !(t1.Board[line][col].Defined || t2.Board[line][col].Defined) {
+ // Both cells are empty or we ignore empty cells
+ continue
+ }
+ match = false
+ return
+ }
+ // Both cells are defined
+ if t1.Board[line][col].Value != t2.Board[line][col].Value {
+ match = false
+ return
+ }
+ }
+ }
+
+ line, col = -1, -1
+ return
+}
+
+// Set sets the value of the cell; a value -1 will set the cell as undefined
+func (c *Cell) Set(value int) {
+ if value != 0 && value != 1 {
+ c.Defined = false
+ return
+ }
+ c.Defined = true
+ c.Value = value
+}
+
+// Set sets the value of a specific cell
+// A value -1 will undefine the cell
+func (b Takuzu) Set(l, c, value int) {
+ if value != 0 && value != 1 {
+ b.Board[l][c].Defined = false
+ return
+ }
+ b.Board[l][c].Defined = true
+ b.Board[l][c].Value = value
+}
+
+// GetLine returns a slice of cells containing the ith line of the board
+func (b Takuzu) GetLine(i int) []Cell {
+ return b.Board[i]
+}
+
+// GetColumn returns a slice of cells containing the ith column of the board
+func (b Takuzu) GetColumn(i int) []Cell {
+ c := make([]Cell, b.Size)
+ for l := range b.Board {
+ c[l] = b.Board[l][i]
+ }
+ return c
+}
+
+// GetLinePointers returns a slice of pointers to the cells of the ith line of the board
+func (b Takuzu) GetLinePointers(i int) []*Cell {
+ r := make([]*Cell, b.Size)
+ for l := range b.Board[i] {
+ r[l] = &b.Board[i][l]
+ }
+ return r
+}
+
+// GetColumnPointers returns a slice of pointers to the cells of the ith column of the board
+func (b Takuzu) GetColumnPointers(i int) []*Cell {
+ r := make([]*Cell, b.Size)
+ for l := range b.Board {
+ r[l] = &b.Board[l][i]
+ }
+ return r
+}
+
+// FillLineColumn add missing 0s or 1s if all 1s or 0s are there.
+// Note: This method can update b.
+func (b Takuzu) FillLineColumn(l, c int) {
+ fillRange := func(r []*Cell) {
+ size := len(r)
+ var notFull bool
+ var n [2]int
+ for x := 0; x < size; x++ {
+ if r[x].Defined {
+ n[r[x].Value]++
+ } else {
+ notFull = true
+ }
+ }
+ if !notFull {
+ return
+ }
+ if n[0] == size/2 {
+ // Let's fill the 1s
+ for _, x := range r {
+ if !x.Defined {
+ x.Defined = true
+ x.Value = 1
+ }
+ }
+ } else if n[1] == size/2 {
+ // Let's fill the 0s
+ for _, x := range r {
+ if !x.Defined {
+ x.Defined = true
+ x.Value = 0
+ }
+ }
+ }
+ }
+
+ var cells []*Cell
+
+ // Fill line
+ cells = b.GetLinePointers(l)
+ fillRange(cells)
+ // Fill column
+ cells = b.GetColumnPointers(c)
+ fillRange(cells)
+}
+
+// DumpBoard displays the Takuzu board
+func (b Takuzu) DumpBoard() {
+ fmt.Println()
+ for i := range b.Board {
+ dumpRange(b.Board[i])
+ }
+}
+
+// CheckLine returns an error if the line i fails validation
+func (b Takuzu) CheckLine(i int) error {
+ _, err := checkRange(b.GetLine(i))
+ return err
+}
+
+// CheckColumn returns an error if the column i fails validation
+func (b Takuzu) CheckColumn(i int) error {
+ _, err := checkRange(b.GetColumn(i))
+ return err
+}
+
+// Validate checks a whole board for errors (not completeness)
+// Returns true if all cells are defined.
+func (b Takuzu) Validate() (bool, error) {
+ finished := true
+
+ computeVal := func(cells []Cell) (val int) {
+ for i := 0; i < len(cells); i++ {
+ val += cells[i].Value * 1 << uint(i)
+ }
+ return
+ }
+
+ lineVals := make(map[int]bool)
+ colVals := make(map[int]bool)
+
+ for i := 0; i < b.Size; i++ {
+ var d []Cell
+ var full bool
+ var err error
+
+ // Let's check line i
+ d = b.GetLine(i)
+ full, err = checkRange(d)
+ if err != nil {
+ return false, errors.Wrapf(err, "line %d", i)
+ }
+ if full {
+ hv := computeVal(d)
+ if lineVals[hv] {
+ return false, fmt.Errorf("duplicate lines (%d)", i)
+ }
+ lineVals[hv] = true
+ } else {
+ finished = false
+ }
+
+ // Let's check column i
+ d = b.GetColumn(i)
+ full, err = checkRange(d)
+ if err != nil {
+ return false, errors.Wrapf(err, "column %d", i)
+ }
+ if full {
+ hv := computeVal(d)
+ if colVals[hv] {
+ return false, fmt.Errorf("duplicate colums (%d)", i)
+ }
+ colVals[hv] = true
+ } else {
+ finished = false
+ }
+ }
+ return finished, nil
+}
+
+func dumpRange(cells []Cell) {
+ for _, c := range cells {
+ if !c.Defined {
+ fmt.Printf(". ")
+ continue
+ }
+ fmt.Printf("%d ", c.Value)
+ }
+ fmt.Println()
+}
+
+// checkRange returns true if the range is completely defined, and an error
+// if it doesn't follow the rules for a takuzu line or column
+// Note that the boolean might be invalid if the error is not nil.
+func checkRange(cells []Cell) (bool, error) {
+ full := true
+ size := len(cells)
+ counters := []int{0, 0}
+
+ var prevCell Cell
+ var prevCellCount int
+
+ for _, c := range cells {
+ if !c.Defined {
+ full = false
+ prevCell.Defined = false
+ prevCellCount = 0
+ continue
+ }
+ counters[c.Value]++
+ if prevCellCount == 0 {
+ prevCellCount = 1
+ } else {
+ if c.Value == prevCell.Value {
+ prevCellCount++
+ if prevCellCount > 2 {
+ return full, errors.Errorf("3+ same values %d", c.Value)
+ }
+ } else {
+ prevCellCount = 1
+ }
+
+ }
+ prevCell = c
+ }
+ if counters[0] > size/2 {
+ return full, errors.Errorf("too many zeroes")
+ }
+ if counters[1] > size/2 {
+ return full, errors.Errorf("too many ones")
+ }
+ return full, nil
+}
+
+func checkRangeCounts(cells []Cell) (full bool, n0, n1 int) {
+ counters := []int{0, 0}
+ full = true
+
+ for _, c := range cells {
+ if c.Defined {
+ counters[c.Value]++
+ } else {
+ full = false
+ }
+ }
+ 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
+}
+
+// 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
+}