# HG changeset patch
# User Mikael Berthe <mikael@lilotux.net>
# Date 1472845848 -7200
# Node ID 00371339bbccd35a85d77796557bfc401091712b

Import refactored version

diff -r 000000000000 -r 00371339bbcc .hgignore
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Fri Sep 02 21:50:48 2016 +0200
@@ -0,0 +1,3 @@
+syntax: glob
+
+*.sw[op]
diff -r 000000000000 -r 00371339bbcc build.go
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/build.go	Fri Sep 02 21:50:48 2016 +0200
@@ -0,0 +1,329 @@
+package takuzu
+
+import (
+	"fmt"
+	"log"
+	"math/rand"
+	"time"
+
+	"github.com/pkg/errors"
+)
+
+func init() {
+	rand.Seed(time.Now().UTC().UnixNano())
+}
+
+type buildTakuzuOptions struct {
+	size                                  int
+	minRatio, maxRatio                    int
+	simple                                bool
+	buildBoardTimeout, reduceBoardTimeout time.Duration
+}
+
+// ReduceBoard randomly removes as many numbers as possible from the
+// takuzu board and returns a pointer to the new board.
+// The initial takuzu might be modified.
+func (tak Takuzu) ReduceBoard(trivial bool, wid string, buildBoardTimeout, reduceBoardTimeout time.Duration) (*Takuzu, error) {
+
+	size := tak.Size
+
+	// First check if the board is correct
+	if verbosity > 0 {
+		log.Printf("[%v]ReduceBoard: Checking for all grid solutions...", wid)
+	}
+
+	allSol := &[]Takuzu{}
+	_, err := tak.Clone().TrySolveRecurse(allSol, buildBoardTimeout)
+	ns := len(*allSol)
+	if err != nil && errors.Cause(err).Error() == "timeout" {
+		if verbosity > 0 {
+			log.Printf("[%v]ReduceBoard: There was a timeout (%d resolution(s) found).", wid, ns)
+		}
+		if ns == 0 {
+			return nil, err
+		}
+		//if ns < 10 { return nil, err }
+		if verbosity > 0 {
+			log.Printf("[%v]ReduceBoard: Going on anyway...", wid)
+		}
+	}
+
+	if verbosity > 0 {
+		log.Printf("[%v]ReduceBoard: %d solution(s) found.", wid, ns)
+	}
+
+	if ns == 0 {
+		return nil, err
+	} else if ns > 1 {
+		tak = (*allSol)[rand.Intn(ns)]
+		if verbosity > 0 {
+			log.Printf("[%v]ReduceBoard: Warning: there are %d solutions.", wid, ns)
+			log.Printf("[%v]ReduceBoard: Picking one randomly.", wid)
+
+			if verbosity > 1 {
+				tak.DumpBoard()
+				fmt.Println()
+			}
+		}
+		allSol = nil
+	} else {
+		// 1 and only 1 solution
+		if verbosity > 1 {
+			tak.DumpBoard()
+			fmt.Println()
+		}
+	}
+
+	if verbosity > 0 {
+		log.Printf("[%v]ReduceBoard: Grid reduction...", wid)
+	}
+	fields := make([]*Cell, size*size)
+	n := 0
+	for l := range tak.Board {
+		for c := range tak.Board[l] {
+			if tak.Board[l][c].Defined {
+				fields[n] = &tak.Board[l][c]
+				n++
+			}
+		}
+	}
+
+	nDigits := 0
+	initialDigits := n
+	ratio := 0
+	if verbosity > 0 {
+		log.Printf("[%v]ReduceBoard: %d%%", wid, ratio)
+	}
+
+	for ; n > 0; n-- {
+		var rollback bool
+		i := rand.Intn(n)
+		fields[i].Defined = false
+		if trivial {
+			full, err := tak.Clone().TrySolveTrivial()
+			if err != nil || !full {
+				rollback = true
+			}
+		} else {
+			allSol = &[]Takuzu{}
+			_, err := tak.Clone().TrySolveRecurse(allSol, reduceBoardTimeout)
+			if err != nil || len(*allSol) != 1 {
+				rollback = true
+			}
+		}
+
+		if rollback {
+			if verbosity > 1 {
+				log.Printf("[%v]ReduceBoard: Backing out", wid)
+			}
+			fields[i].Defined = true // Back out!
+			nDigits++
+		}
+		fields = append(fields[:i], fields[i+1:]...)
+
+		if verbosity > 0 {
+			nr := (initialDigits - n) * 100 / initialDigits
+			if nr > ratio {
+				ratio = nr
+				log.Printf("[%v]ReduceBoard: %d%%", wid, ratio)
+			}
+		}
+	}
+
+	if verbosity > 0 {
+		log.Printf("[%v]ReduceBoard: I have left %d digits.", wid, nDigits)
+	}
+
+	return &tak, nil
+}
+
+// newRandomTakuzu creates a new Takuzu board with a given size
+// It is intended to be called by NewRandomTakuzu only.
+func newRandomTakuzu(wid string, buildOpts buildTakuzuOptions) (*Takuzu, error) {
+	size := buildOpts.size
+	easy := buildOpts.simple
+	buildBoardTimeout := buildOpts.buildBoardTimeout
+	reduceBoardTimeout := buildOpts.reduceBoardTimeout
+	minRatio := buildOpts.minRatio
+	maxRatio := buildOpts.maxRatio
+
+	tak := New(size)
+	n := size * size
+	fields := make([]*Cell, n)
+
+	i := 0
+	for l := range tak.Board {
+		for c := range tak.Board[l] {
+			fields[i] = &tak.Board[l][c]
+			i++
+		}
+	}
+
+	if verbosity > 0 {
+		log.Printf("[%v]NewRandomTakuzu: Filling new board (%dx%[2]d)...", wid, size)
+	}
+
+	nop := 0
+
+	// #1. Loop until the ratio of empty cells is less than minRatio% (e.g. 55%)
+
+	for n > size*size*minRatio/100 {
+		i := rand.Intn(n)
+		fields[i].Defined = true
+		fields[i].Value = rand.Intn(2)
+
+		var err error
+
+		if _, err = tak.Validate(); err != nil {
+			if verbosity > 1 {
+				log.Printf("[%v]NewRandomTakuzu: Could not set cell value to %v", wid, fields[i].Value)
+			}
+		} else if _, err = tak.Clone().TrySolveTrivial(); err != nil {
+			if verbosity > 1 {
+				log.Printf("[%v]NewRandomTakuzu: Trivial checks: Could not set cell value to %v", wid, fields[i].Value)
+			}
+		}
+
+		if err == nil {
+			fields = append(fields[:i], fields[i+1:]...)
+			n--
+			continue
+		}
+
+		// If any of the above checks fails, we roll back
+		fields[i].Defined = false
+		fields[i].Value = 0 // Let's reset but it is useless
+
+		// Safety check to avoid deadlock on bad boards
+		nop++
+		if nop > 2*size*size {
+			log.Printf("[%v]NewRandomTakuzu: Could not fill up board!", wid)
+			// Givin up on this board
+			return nil, errors.New("could not fill up board") // Try again
+		}
+
+	}
+
+	var ptak *Takuzu
+	var removed int
+
+	// #2. Try to solve the current board; try to remove some cells if it fails
+
+	// Initial empty cells count
+	iecc := n
+
+	for {
+		// Current count of empty (i.e. undefined) cells
+		ec := iecc + removed
+		ecpc := ec * 100 / (size * size)
+		if verbosity > 0 {
+			log.Printf("[%v]NewRandomTakuzu: Empty cells: %d (%d%%)", wid, ec, ecpc)
+		}
+		if ecpc > maxRatio {
+			if verbosity > 0 {
+				log.Printf("[%v]NewRandomTakuzu: Too many empty cells (%d); giving up on this board", wid, ec)
+			}
+			break
+		}
+		var err error
+		ptak, err = tak.ReduceBoard(easy, wid, buildBoardTimeout, reduceBoardTimeout)
+		if err != nil && errors.Cause(err).Error() == "timeout" {
+			break
+		}
+		if err == nil && ptak != nil {
+			break
+		}
+		if verbosity > 0 {
+			log.Printf("[%v]NewRandomTakuzu: Could not use this grid", wid)
+		}
+		inc := size * size / 150
+		if inc == 0 {
+			inc = 1
+		}
+		tak.removeRandomCell(inc)
+		removed += inc
+		if verbosity > 1 {
+			log.Printf("[%v]NewRandomTakuzu: Removed %d numbers", wid, removed)
+			if verbosity > 1 {
+				tak.DumpBoard()
+			}
+		}
+	}
+
+	if ptak == nil {
+		if verbosity > 0 {
+			log.Printf("[%v]NewRandomTakuzu: Couldn't use this board, restarting from scratch...", wid)
+		}
+		return nil, errors.New("could not use current board") // Try again
+	}
+
+	return ptak, nil
+}
+
+// NewRandomTakuzu creates a new Takuzu board with a given size
+func NewRandomTakuzu(size int, simple bool, wid string, buildBoardTimeout, reduceBoardTimeout time.Duration, minRatio, maxRatio int) (*Takuzu, error) {
+	if size%2 != 0 {
+		return nil, errors.New("board size should be an even value")
+	}
+
+	if size < 4 {
+		return nil, errors.New("board size is too small")
+	}
+
+	// minRatio : percentage (1-100) of empty cells when creating a new board
+	// If the board is wrong the cells will be removed until we reach maxRatio
+
+	if minRatio < 40 {
+		minRatio = 40
+	}
+	if minRatio > maxRatio {
+		return nil, errors.New("minRatio/maxRatio incorrect")
+	}
+
+	if maxRatio > 99 {
+		maxRatio = 99
+	}
+
+	buildOptions := buildTakuzuOptions{
+		size:               size,
+		minRatio:           minRatio,
+		maxRatio:           maxRatio,
+		simple:             simple,
+		buildBoardTimeout:  buildBoardTimeout,
+		reduceBoardTimeout: reduceBoardTimeout,
+	}
+
+	var takP *Takuzu
+
+	for {
+		var err error
+		takP, err = newRandomTakuzu(wid, buildOptions)
+		if err == nil {
+			break
+		}
+	}
+
+	return takP, nil
+}
+
+func (tak Takuzu) removeRandomCell(number int) {
+	size := tak.Size
+	fields := make([]*Cell, size*size)
+	n := 0
+	for l := range tak.Board {
+		for c := range tak.Board[l] {
+			if tak.Board[l][c].Defined {
+				fields[n] = &tak.Board[l][c]
+				n++
+			}
+		}
+	}
+	for i := 0; i < number; i++ {
+		if n == 0 {
+			return
+		}
+		fields[rand.Intn(n)].Defined = false
+		fields = append(fields[:i], fields[i+1:]...)
+		n--
+	}
+}
diff -r 000000000000 -r 00371339bbcc gotak/gotak.go
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gotak/gotak.go	Fri Sep 02 21:50:48 2016 +0200
@@ -0,0 +1,208 @@
+package main
+
+import (
+	"fmt"
+	"log"
+	"os"
+	"time"
+
+	flag "github.com/docker/docker/pkg/mflag"
+
+	"mikael/takuzu"
+)
+
+var verbosity int
+
+func newTakuzuGameBoard(size int, simple bool, jobs int, buildBoardTimeout, reduceBoardTimeout time.Duration, minRatio, maxRatio int) *takuzu.Takuzu {
+	results := make(chan *takuzu.Takuzu)
+
+	newTak := func(i int) {
+		takuzu, err := takuzu.NewRandomTakuzu(size, simple, fmt.Sprintf("%v", i),
+			buildBoardTimeout, reduceBoardTimeout, minRatio, maxRatio)
+
+		if err == nil && takuzu != nil {
+			results <- takuzu
+			if verbosity > 0 && jobs > 1 {
+				log.Printf("Worker #%d done.", i)
+			}
+		} else {
+			results <- nil
+		}
+	}
+
+	if jobs == 0 {
+		return nil
+	}
+	for i := 0; i < jobs; i++ {
+		go newTak(i)
+	}
+	tak := <-results
+	return tak
+}
+
+func main() {
+	var game string
+
+	vbl := flag.Uint([]string{"-vl"}, 0, "Verbosity Level")
+	simple := flag.Bool([]string{"-simple"}, false, "Only look for trivial solutions")
+	out := flag.Bool([]string{"-out"}, false, "Send solution string to output")
+	flag.StringVar(&game, []string{"-game"}, "", "Load game string")
+	schrodLvl := flag.Uint([]string{"-x-sl"}, 0, "[Advanced] Schrödinger level")
+	resolveTimeout := flag.Duration([]string{"-x-timeout"}, 0, "[Advanced] Resolution timeout")
+	buildBoardTimeout := flag.Duration([]string{"-x-build-timeout"}, 5*time.Minute, "[Advanced] Build timeout per resolution")
+	reduceBoardTimeout := flag.Duration([]string{"-x-reduce-timeout"}, 20*time.Minute, "[Advanced] Reduction timeout")
+	buildMinRatio := flag.Uint([]string{"-x-new-min-ratio"}, 55, "[Advanced] Build empty cell ratio (40-60)")
+	buildMaxRatio := flag.Uint([]string{"-x-new-max-ratio"}, 62, "[Advanced] Build empty cell ratio (50-99)")
+	all := flag.Bool([]string{"-all"}, false, "Look for all possible solutions")
+	reduce := flag.Bool([]string{"-reduce"}, false, "Try to reduce the number of digits")
+	buildNewSize := flag.Uint([]string{"-new"}, 0, "Build a new takuzu board (with given size)")
+	pdfFileName := flag.String([]string{"-to-pdf"}, "", "PDF output file name")
+	workers := flag.Uint([]string{"-workers"}, 1, "Number of parallel workers (use with --new)")
+
+	flag.Parse()
+
+	verbosity = int(*vbl)
+	takuzu.SetVerbosityLevel(verbosity)
+	takuzu.SetSchrodingerLevel(*schrodLvl)
+
+	var tak *takuzu.Takuzu
+
+	if game != "" {
+		var err error
+		tak, err = takuzu.NewFromString(game)
+		if tak == nil || err != nil {
+			fmt.Fprintln(os.Stderr, "Error:", err)
+			tak = nil
+		}
+	}
+
+	if *buildNewSize > 0 {
+		if verbosity > 1 {
+			log.Printf("buildBoardTimeout:   %v", *buildBoardTimeout)
+			log.Printf("reduceBoardTimeout:  %v", *reduceBoardTimeout)
+			log.Printf("Free cell min ratio: %v", *buildMinRatio)
+			log.Printf("Free cell max ratio: %v", *buildMaxRatio)
+		}
+		tak = newTakuzuGameBoard(int(*buildNewSize), *simple,
+			int(*workers),
+			*buildBoardTimeout, *reduceBoardTimeout,
+			int(*buildMinRatio), int(*buildMaxRatio))
+	}
+
+	if tak == nil {
+		fmt.Fprintln(os.Stderr, "Could not create takuzu board.")
+		os.Exit(255)
+	}
+
+	tak.DumpBoard()
+	fmt.Println()
+
+	if *pdfFileName != "" {
+		if err := tak2pdf(tak, *pdfFileName); err != nil {
+			log.Println(err)
+			os.Exit(1)
+		}
+		if *out {
+			tak.DumpString()
+		}
+		os.Exit(0)
+	}
+
+	if *buildNewSize > 0 {
+		if *out {
+			tak.DumpString()
+		}
+		os.Exit(0)
+	}
+
+	if *reduce {
+		if verbosity > 1 {
+			log.Printf("buildBoardTimeout:   %v", *buildBoardTimeout)
+			log.Printf("reduceBoardTimeout:  %v", *reduceBoardTimeout)
+		}
+		var err error
+		if tak, err = tak.ReduceBoard(*simple, "0", *buildBoardTimeout, *reduceBoardTimeout); err != nil {
+			log.Println(err)
+			os.Exit(1)
+		}
+
+		tak.DumpBoard()
+		fmt.Println()
+
+		if *out {
+			tak.DumpString()
+		}
+
+		os.Exit(0)
+	}
+
+	if *simple {
+		full, err := tak.TrySolveTrivial()
+		if err != nil {
+			log.Println(err)
+			os.Exit(1)
+		}
+		if !full {
+			tak.DumpBoard()
+			log.Println("The takuzu could not be completed using trivial methods.")
+			os.Exit(2)
+		}
+
+		log.Println("The takuzu is correct and complete.")
+		tak.DumpBoard()
+		fmt.Println()
+
+		if *out {
+			tak.DumpString()
+		}
+		os.Exit(0)
+	}
+
+	var allSol *[]takuzu.Takuzu
+	if *all {
+		allSol = &[]takuzu.Takuzu{}
+	}
+	res, err := tak.TrySolveRecurse(allSol, *resolveTimeout)
+	if err != nil && verbosity > 1 {
+		// The last trivial resolution failed
+		log.Println("Trivial resolution failed:", err)
+	}
+
+	// Ignoring res & err if a full search was requested
+	if *all {
+		log.Println(len(*allSol), "solution(s) found.")
+		if len(*allSol) > 0 {
+			for _, s := range *allSol {
+				if *out {
+					s.DumpString()
+				} else {
+					s.DumpBoard()
+					fmt.Println()
+				}
+			}
+			if len(*allSol) > 1 {
+				os.Exit(3)
+			}
+			os.Exit(0)
+		}
+		fmt.Println("No solution found.")
+		os.Exit(2)
+	}
+
+	if err != nil {
+		log.Println(err)
+		os.Exit(1)
+	}
+	if res != nil {
+		res.DumpBoard()
+		fmt.Println()
+
+		if *out {
+			res.DumpString()
+		}
+		os.Exit(0)
+	}
+
+	fmt.Println("No solution found.")
+	os.Exit(2)
+}
diff -r 000000000000 -r 00371339bbcc gotak/pdf.go
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gotak/pdf.go	Fri Sep 02 21:50:48 2016 +0200
@@ -0,0 +1,58 @@
+package main
+
+import (
+	"fmt"
+
+	"github.com/jung-kurt/gofpdf"
+	"github.com/pkg/errors"
+
+	"mikael/takuzu"
+)
+
+func tak2pdf(takuzu *takuzu.Takuzu, pdfFileName string) error {
+
+	if pdfFileName == "" {
+		return errors.New("no PDF file name")
+	}
+
+	size := takuzu.Size
+
+	pdf := gofpdf.New("P", "mm", "A4", "")
+	pdf.SetFont("Arial", "", 14)
+
+	basicTable := func() {
+
+		for ln, l := range takuzu.Board {
+			for cn, cell := range l {
+				border := "" // empty, "1", "L", "T", "R" and "B"
+				if ln == 0 {
+					border += "T"
+				}
+				if cn == 0 {
+					border += "L"
+				}
+				if ln+1 == size {
+					border += "B"
+				}
+				if cn+1 == size {
+					border += "R"
+				}
+				align := "CM" // horiz=Center vert=Middle
+				if cell.Defined {
+					pdf.CellFormat(8, 8, fmt.Sprint(cell.Value), border, 0, align, false, 0, "")
+				} else {
+					pdf.CellFormat(8, 8, ".", border, 0, align, false, 0, "")
+				}
+			}
+			pdf.Ln(-1)
+		}
+	}
+
+	pdf.AddPage()
+	basicTable()
+	if err := pdf.OutputFileAndClose(pdfFileName); err != nil {
+		return err
+	}
+
+	return nil
+}
diff -r 000000000000 -r 00371339bbcc takuzu.go
--- /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
+}