diff -r 733df0275d78 -r 110d38ae22cd solve.go
--- /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
+}