6 	"log"

     8 	"runtime"

     9 	"sync"

    10 	"time"

    14 

    15 var verbosity int

    16 var schrodLvl uint

    51 

    52 	// TODO: validate chars ([.01OI])

   402 

   403 func (b Takuzu) guessPos(l, c int) int {

   404 	if b.Board[l][c].Defined {

   405 		return b.Board[l][c].Value

   406 	}

   407 

   408 	bx := b.Clone()

   409 	bx.Set(l, c, 0)

   410 	bx.FillLineColumn(l, c)

   411 	if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {

   412 		return 1

   413 	}

   414 	Copy(&b, &bx)

   415 	bx.Set(l, c, 1)

   416 	bx.FillLineColumn(l, c)

   417 	if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil {

   418 		return 0

   419 	}

   420 

   421 	return -1 // dunno

   422 }

   423 

   424 // TrivialHint returns the coordinates and the value of the first cell that

   425 // can be guessed using trivial methods.

   426 // It returns {-1, -1, -1} if none can be found.

   427 func (b Takuzu) TrivialHint() (line, col, value int) {

   428 	for line = 0; line < b.Size; line++ {

   429 		for col = 0; col < b.Size; col++ {

   430 			if b.Board[line][col].Defined {

   431 				continue

   432 			}

   433 			if value = b.guessPos(line, col); value != -1 {

   434 				return

   435 			}

   436 		}

   437 	}

   438 	value, line, col = -1, -1, -1

   439 	return

   440 }

   441 

   442 // trySolveTrivialPass does 1 pass over the takuzu board and tries to find

   443 // values using simple guesses.

   444 func (b Takuzu) trySolveTrivialPass() (changed bool) {

   445 	for line := 0; line < b.Size; line++ {

   446 		for col := 0; col < b.Size; col++ {

   447 			if b.Board[line][col].Defined {

   448 				continue

   449 			}

   450 			if guess := b.guessPos(line, col); guess != -1 {

   451 				b.Set(line, col, guess)

   452 				if verbosity > 3 {

   453 					log.Printf("Trivial: Setting [%d,%d] to %d", line, col, guess)

   454 				}

   455 				changed = true // Ideally remember l,c

   456 			}

   457 		}

   458 	}

   459 	return changed

   460 }

   461 

   462 // TrySolveTrivial tries to solve the takuzu using a loop over simple methods

   463 // It returns true if all cells are defined, and an error if the grid breaks the rules.

   464 func (b Takuzu) TrySolveTrivial() (bool, error) {

   465 	for {

   466 		changed := b.trySolveTrivialPass()

   467 		if verbosity > 3 {

   468 			var status string

   469 			if changed {

   470 				status = "ongoing"

   471 			} else {

   472 				status = "stuck"

   473 			}

   474 			log.Println("Trivial resolution -", status)

   475 		}

   476 		if !changed {

   477 			break

   478 		}

   479 

   480 		if verbosity > 3 {

   481 			b.DumpBoard()

   482 			fmt.Println()

   483 		}

   484 	}

   485 	full, err := b.Validate()

   486 	if err != nil {

   487 		return full, errors.Wrap(err, "the takuzu looks wrong")

   488 	}

   489 	return full, nil

   490 }

   491 

   492 // TrySolveRecurse tries to solve the takuzu recursively, using trivial

   493 // method first and using guesses if it fails.

   494 func (b Takuzu) TrySolveRecurse(allSolutions *[]Takuzu, timeout time.Duration) (*Takuzu, error) {

   495 

   496 	var solutionsMux sync.Mutex

   497 	var singleSolution *Takuzu

   498 	var solutionMap map[string]*Takuzu

   499 

   500 	var globalSearch bool

   501 	// globalSearch doesn't need to use a mutex and is more convenient

   502 	// to use than allSolutions.

   503 	if allSolutions != nil {

   504 		globalSearch = true

   505 		solutionMap = make(map[string]*Takuzu)

   506 	}

   507 

   508 	startTime := time.Now()

   509 

   510 	var recurseSolve func(level int, t Takuzu, errStatus chan<- error) error

   511 

   512 	recurseSolve = func(level int, t Takuzu, errStatus chan<- error) error {

   513 

   514 		reportStatus := func(failure error) {

   515 			// Report status to the caller's channel

   516 			if errStatus != nil {

   517 				errStatus <- failure

   518 			}

   519 		}

   520 

   521 		// In Schröndinger mode we check concurrently both values for a cell

   522 		var schrodinger bool

   523 		concurrentRoutines := 1

   524 		if level < int(schrodLvl) {

   525 			schrodinger = true

   526 			concurrentRoutines = 2

   527 		}

   528 

   529 		var status [2]chan error

   530 		status[0] = make(chan error)

   531 		status[1] = make(chan error)

   532 

   533 		for {

   534 			// Try simple resolution first

   535 			full, err := t.TrySolveTrivial()

   536 			if err != nil {

   537 				reportStatus(err)

   538 				return err

   539 			}

   540 

   541 			if full { // We're done

   542 				if verbosity > 1 {

   543 					log.Printf("{%d} The takuzu is correct and complete.", level)

   544 				}

   545 				solutionsMux.Lock()

   546 				singleSolution = &t

   547 				if globalSearch {

   548 					solutionMap[t.ToString()] = &t

   549 				}

   550 				solutionsMux.Unlock()

   551 

   552 				reportStatus(nil)

   553 				return nil

   554 			}

   555 

   556 			if verbosity > 2 {

   557 				log.Printf("{%d} Trivial resolution did not complete.", level)

   558 			}

   559 

   560 			// Trivial method is stuck, let's use recursion

   561 

   562 			changed := false

   563 

   564 			// Looking for first empty cell

   565 			var line, col int

   566 		firstClear:

   567 			for line = 0; line < t.Size; line++ {

   568 				for col = 0; col < t.Size; col++ {

   569 					if !t.Board[line][col].Defined {

   570 						break firstClear

   571 					}

   572 				}

   573 			}

   574 

   575 			if line == t.Size || col == t.Size {

   576 				break

   577 			}

   578 

   579 			if verbosity > 2 {

   580 				log.Printf("{%d} GUESS - Trying values for [%d,%d]", level, line, col)

   581 			}

   582 

   583 			var val int

   584 			err = nil

   585 			errCount := 0

   586 

   587 			for testval := 0; testval < 2; testval++ {

   588 				if !globalSearch && t.Board[line][col].Defined {

   589 					// No need to "guess" here anymore

   590 					break

   591 				}

   592 

   593 				// Launch goroutines for cell values of 0 and/or 1

   594 				for testCase := 0; testCase < 2; testCase++ {

   595 					if schrodinger || testval == testCase {

   596 						tx := t.Clone()

   597 						tx.Set(line, col, testCase)

   598 						go recurseSolve(level+1, tx, status[testCase])

   599 					}

   600 				}

   601 

   602 				// Let's collect the goroutines' results

   603 				for i := 0; i < concurrentRoutines; i++ {

   604 					if schrodinger && verbosity > 1 { // XXX

   605 						log.Printf("{%d} Schrodinger waiting for result #%d for cell [%d,%d]", level, i, line, col)

   606 					}

   607 					select {

   608 					case e := <-status[0]:

   609 						err = e

   610 						val = 0

   611 					case e := <-status[1]:

   612 						err = e

   613 						val = 1

   614 					}

   615 

   616 					if schrodinger && verbosity > 1 { // XXX

   617 						log.Printf("{%d} Schrodinger result #%d/2 for cell [%d,%d]=%d - err=%v", level, i+1, line, col, val, err)

   618 					}

   619 

   620 					if err == nil {

   621 						if !globalSearch {

   622 							reportStatus(nil)

   623 							if i+1 < concurrentRoutines {

   624 								// Schröndinger mode and we still have one status to fetch

   625 								<-status[1-val]

   626 							}

   627 							return nil

   628 						}

   629 						continue

   630 					}

   631 					if timeout > 0 && level > 2 && time.Since(startTime) > timeout {

   632 						if errors.Cause(err).Error() != "timeout" {

   633 							if verbosity > 0 {

   634 								log.Printf("{%d} Timeout, giving up", level)

   635 							}

   636 							err := errors.New("timeout")

   637 							reportStatus(err)

   638 							if i+1 < concurrentRoutines {

   639 								// Schröndinger mode and we still have one status to fetch

   640 								<-status[1-val]

   641 							}

   642 							// XXX actually can't close the channel and leave, can I?

   643 							return err

   644 						}

   645 					}

   646 

   647 					// err != nil: we can set a value --  unless this was a timeout

   648 					if errors.Cause(err).Error() == "timeout" {

   649 						if verbosity > 1 {

   650 							log.Printf("{%d} Timeout propagation", level)

   651 						}

   652 						reportStatus(err)

   653 						if i+1 < concurrentRoutines {

   654 							// Schröndinger mode and we still have one status to fetch

   655 							<-status[1-val]

   656 						}

   657 						// XXX actually can't close the channel and leave, can I?

   658 						return err

   659 					}

   660 

   661 					errCount++

   662 					if verbosity > 2 {

   663 						log.Printf("{%d} Bad outcome (%v)", level, err)

   664 						log.Printf("{%d} GUESS was wrong - Setting [%d,%d] to %d",

   665 							level, line, col, 1-val)

   666 					}

   667 

   668 					t.Set(line, col, 1-val)

   669 					changed = true

   670 

   671 				} // concurrentRoutines

   672 

   673 				if (changed && !globalSearch) || schrodinger {

   674 					// Let's loop again with the new board

   675 					break

   676 				}

   677 			}

   678 

   679 			if verbosity > 2 {

   680 				log.Printf("{%d} End of cycle.\n\n", level)

   681 			}

   682 

   683 			if errCount == 2 {

   684 				// Both values failed

   685 				err := errors.New("dead end")

   686 				reportStatus(err)

   687 				return err

   688 			}

   689 

   690 			// If we cannot fill more cells (!changed) or if we've made a global search with

   691 			// both values, the search is complete.

   692 			if schrodinger || globalSearch || !changed {

   693 				break

   694 			}

   695 

   696 			if verbosity > 2 {

   697 				t.DumpBoard()

   698 				fmt.Println()

   699 			}

   700 		}

   701 

   702 		// Try to force garbage collection

   703 		runtime.GC()

   704 

   705 		full, err := t.Validate()

   706 		if err != nil {

   707 			if verbosity > 1 {

   708 				log.Println("The takuzu looks wrong - ", err)

   709 			}

   710 			err := errors.Wrap(err, "the takuzu looks wrong")

   711 			reportStatus(err)

   712 			return err

   713 		}

   714 		if full {

   715 			if verbosity > 1 {

   716 				log.Println("The takuzu is correct and complete")

   717 			}

   718 			solutionsMux.Lock()

   719 			singleSolution = &t

   720 			if globalSearch {

   721 				solutionMap[t.ToString()] = &t

   722 			}

   723 			solutionsMux.Unlock()

   724 		}

   725 

   726 		reportStatus(nil)

   727 		return nil

   728 	}

   729 

   730 	status := make(chan error)

   731 	go recurseSolve(0, b, status)

   732 

   733 	err := <-status // Wait for it...

   734 

   735 	firstSol := singleSolution

   736 	if globalSearch {

   737 		for _, tp := range solutionMap {

   738 			*allSolutions = append(*allSolutions, *tp)

   739 		}

   740 	}

   741 

   742 	if err != nil {

   743 		return firstSol, err

   744 	}

   745 

   746 	if globalSearch && len(*allSolutions) > 0 {

   747 		firstSol = &(*allSolutions)[0]

   748 	}

   749 	return firstSol, nil

   750 }

   751 

   752 // SetSchrodingerLevel initializes the "Schrödinger" level (0 means disabled)

   753 // It must be called before any board generation or reduction.

   754 func SetSchrodingerLevel(level uint) {

   755 	schrodLvl = level

   756 }

   757 

   758 // SetVerbosityLevel initializes the verbosity level

   759 func SetVerbosityLevel(level int) {

   760 	verbosity = level

   761 }