--- /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--
+ }
+}