1// Package rules is the only place Takuzu rules exist. A Board is a global2// grid plus a set of shapes; every shape is a Takuzu on its own, played on3// its lines: each maximal horizontal or vertical run of the shape's cells.4// A cell in two shapes is constrained by both; that is the only rule that5// crosses a shape. Nothing here knows about games, tiles as a concept6// beyond "shape", or the solution.7package rules89import (10 "fmt"11 "sort"12 "sync"13)1415// Cell is 0, 1, or Empty.16type Cell int81718const Empty Cell = -11920// Mask selects which rules are active.21type Mask uint82223const (24 Run Mask = 1 << iota // no three equal in a row along a line25 Balance // each line has len/2 of each value26 Unique // no two equal lines of one orientation and length in a shape27 All = Run | Balance | Unique28)2930var maskNames = []struct {31 m Mask32 name string33}{{Run, "run"}, {Balance, "balance"}, {Unique, "unique"}}3435// Names lists the active rule names in a mask, in a fixed order.36func (m Mask) Names() []string {37 out := []string{}38 for _, mn := range maskNames {39 if m&mn.m != 0 {40 out = append(out, mn.name)41 }42 }43 return out44}4546// Shape is a tile: a union of axis-aligned rectangles (local coordinates47// inside a W x H bounding box) placed at (X0, Y0) on the board. Every48// maximal horizontal and vertical run of its cells is a line; the rules49// apply per line. A square n x n is Square(x0, y0, n).50type Shape struct {51 X0, Y0, W, H int52 Rects [][4]int // local [lx, ly, rw, rh]53}5455func Square(x0, y0, n int) Shape {56 return Shape{X0: x0, Y0: y0, W: n, H: n, Rects: [][4]int{{0, 0, n, n}}}57}5859// Mask returns the local W*H membership of the shape's cells.60func (s Shape) Mask() []bool {61 m := make([]bool, s.W*s.H)62 for _, r := range s.Rects {63 for y := r[1]; y < r[1]+r[3]; y++ {64 for x := r[0]; x < r[0]+r[2]; x++ {65 if x >= 0 && y >= 0 && x < s.W && y < s.H {66 m[y*s.W+x] = true67 }68 }69 }70 }71 return m72}7374// Cells counts the shape's cells.75func (s Shape) Cells() int {76 n := 077 for _, b := range s.Mask() {78 if b {79 n++80 }81 }82 return n83}8485// Contains reports whether the global cell (gx, gy) is in the shape.86func (s Shape) Contains(gx, gy int) bool {87 lx, ly := gx-s.X0, gy-s.Y088 if lx < 0 || ly < 0 || lx >= s.W || ly >= s.H {89 return false90 }91 for _, r := range s.Rects {92 if lx >= r[0] && lx < r[0]+r[2] && ly >= r[1] && ly < r[1]+r[3] {93 return true94 }95 }96 return false97}9899// Lines lists the shape's lines as local indexes (ly*W+lx), horizontal runs100// first (top to bottom, left to right), then vertical runs.101func (s Shape) Lines() [][]int {102 m := s.Mask()103 var out [][]int104 for y := 0; y < s.H; y++ {105 var run []int106 for x := 0; x <= s.W; x++ {107 if x < s.W && m[y*s.W+x] {108 run = append(run, y*s.W+x)109 continue110 }111 if len(run) > 0 {112 out = append(out, run)113 run = nil114 }115 }116 }117 for x := 0; x < s.W; x++ {118 var run []int119 for y := 0; y <= s.H; y++ {120 if y < s.H && m[y*s.W+x] {121 run = append(run, y*s.W+x)122 continue123 }124 if len(run) > 0 {125 out = append(out, run)126 run = nil127 }128 }129 }130 return out131}132133// Valid reports whether the shape can carry the rules: every line has an134// even length of at least 4 (balance needs even; a line of two is a coin),135// the cells are 4-connected, and the bounding box is tight.136func (s Shape) Valid() error {137 if s.W <= 0 || s.H <= 0 || len(s.Rects) == 0 {138 return fmt.Errorf("empty shape")139 }140 m := s.Mask()141 rowUsed := make([]bool, s.H)142 colUsed := make([]bool, s.W)143 first := -1144 for i, b := range m {145 if b {146 rowUsed[i/s.W] = true147 colUsed[i%s.W] = true148 if first < 0 {149 first = i150 }151 }152 }153 if first < 0 {154 return fmt.Errorf("empty shape")155 }156 for y, u := range rowUsed {157 if !u {158 return fmt.Errorf("row %d of the bounding box is unused", y)159 }160 }161 for x, u := range colUsed {162 if !u {163 return fmt.Errorf("column %d of the bounding box is unused", x)164 }165 }166 parallel := map[[2]int]int{} // (row?, length) -> count167 for _, ln := range s.Lines() {168 if len(ln) < 4 || len(ln)%2 != 0 {169 return fmt.Errorf("line of length %d at local %d (need even, >= 4)", len(ln), ln[0])170 }171 row := 0172 if len(ln) == 1 || ln[1] == ln[0]+1 {173 row = 1174 }175 parallel[[2]int{row, len(ln)}]++176 }177 // uniqueness is a pigeonhole: a shape may hold at most half as many178 // parallel lines of one length as there are distinct valid lines of179 // that length (decided 2026-08-26; the generator needs room to leave180 // tiles under-determined, not just satisfiable)181 for k, c := range parallel {182 if max := DistinctLines(k[1]) / 2; c > max {183 return fmt.Errorf("%d parallel lines of length %d, at most %d allowed (%d distinct valid lines exist)", c, k[1], max, DistinctLines(k[1]))184 }185 }186 // connectivity187 seen := make([]bool, len(m))188 stack := []int{first}189 seen[first] = true190 count := 0191 for len(stack) > 0 {192 c := stack[len(stack)-1]193 stack = stack[:len(stack)-1]194 count++195 x, y := c%s.W, c/s.W196 for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {197 nx, ny := x+d[0], y+d[1]198 if nx < 0 || ny < 0 || nx >= s.W || ny >= s.H {199 continue200 }201 id := ny*s.W + nx202 if m[id] && !seen[id] {203 seen[id] = true204 stack = append(stack, id)205 }206 }207 }208 if count != s.Cells() {209 return fmt.Errorf("shape is not connected")210 }211 return nil212}213214// DistinctLines is the number of distinct balanced, no-three binary lines215// of length L (even): the ceiling on how many parallel lines of that216// length one shape can hold under the uniqueness rule.217func DistinctLines(L int) int {218 distinctMu.Lock()219 defer distinctMu.Unlock()220 if n, ok := distinct[L]; ok {221 return n222 }223 n := 0224 var rec func(prev []Cell, ones int)225 rec = func(prev []Cell, ones int) {226 if len(prev) == L {227 if ones == L/2 {228 n++229 }230 return231 }232 for v := Cell(0); v <= 1; v++ {233 k := len(prev)234 if k >= 2 && prev[k-1] == v && prev[k-2] == v {235 continue236 }237 o := ones238 if v == 1 {239 o++240 }241 if o > L/2 || (len(prev)+1-o) > L/2 {242 continue243 }244 rec(append(prev, v), o)245 }246 }247 rec(nil, 0)248 distinct[L] = n249 return n250}251252var (253 distinctMu sync.Mutex254 distinct = map[int]int{} // L -> DistinctLines(L); 4:6, 6:14, 8:34, 10:84, 12:208, 14:518, 16:1296255)256257// Local extracts the shape's window from a board-sized slice (row-major,258// width W) as a local W*H slice; cells outside the shape are Empty.259func (s Shape) Local(board []Cell, boardW int) []Cell {260 m := s.Mask()261 out := make([]Cell, s.W*s.H)262 for i := range out {263 out[i] = Empty264 if m[i] {265 out[i] = board[(s.Y0+i/s.W)*boardW+s.X0+i%s.W]266 }267 }268 return out269}270271// Line is one run of a shape's cells on a board, as global cell ids.272type Line struct {273 Shape int274 Row bool275 Cells []int276}277278// geometry is what a board derives from its shapes once; clones share it.279type geometry struct {280 lines []Line281 linesAt [][]int // per global cell: indexes into lines282 shapeCells [][]int // per shape: global cell ids (row-major)283 cells []int // every cell of any shape, in first-seen order284 shapesAt [][]int // per global cell: shapes containing it285}286287// Board is a W-by-H grid of cells and the shapes that constrain it.288type Board struct {289 W, H int290 Cells []Cell291 Shapes []Shape292 geo *geometry293}294295func NewBoard(w, h int) *Board {296 b := &Board{W: w, H: h, Cells: make([]Cell, w*h)}297 for i := range b.Cells {298 b.Cells[i] = Empty299 }300 return b301}302303// Single makes a board that is exactly one shape at the origin of its own304// bounding box, with the given local cells (Empty outside the shape).305func Single(s Shape, cells []Cell) *Board {306 sh := Shape{X0: 0, Y0: 0, W: s.W, H: s.H, Rects: s.Rects}307 return &Board{W: s.W, H: s.H, Cells: cells, Shapes: []Shape{sh}}308}309310func (b *Board) Clone() *Board {311 c := &Board{W: b.W, H: b.H, Cells: make([]Cell, len(b.Cells)), Shapes: b.Shapes, geo: b.geo}312 copy(c.Cells, b.Cells)313 return c314}315316func (b *Board) Idx(x, y int) int { return y*b.W + x }317func (b *Board) At(x, y int) Cell { return b.Cells[y*b.W+x] }318func (b *Board) Set(x, y int, v Cell) { b.Cells[y*b.W+x] = v }319320// Geometry derives lines and ownership; built once per board and shared321// by clones. Call it after changing Shapes.322func (b *Board) Geometry() *geometry {323 if b.geo != nil {324 return b.geo325 }326 g := &geometry{327 linesAt: make([][]int, b.W*b.H),328 shapesAt: make([][]int, b.W*b.H),329 }330 seen := make([]bool, b.W*b.H)331 for si, s := range b.Shapes {332 m := s.Mask()333 var cells []int334 for i, ok := range m {335 if !ok {336 continue337 }338 id := (s.Y0+i/s.W)*b.W + s.X0 + i%s.W339 cells = append(cells, id)340 g.shapesAt[id] = append(g.shapesAt[id], si)341 if !seen[id] {342 seen[id] = true343 g.cells = append(g.cells, id)344 }345 }346 g.shapeCells = append(g.shapeCells, cells)347 for _, ln := range s.Lines() {348 // a horizontal run's local indexes step by 1, a vertical run's by W349 l := Line{Shape: si, Row: len(ln) == 1 || ln[1] == ln[0]+1}350 for _, local := range ln {351 id := (s.Y0+local/s.W)*b.W + s.X0 + local%s.W352 l.Cells = append(l.Cells, id)353 g.linesAt[id] = append(g.linesAt[id], len(g.lines))354 }355 g.lines = append(g.lines, l)356 }357 }358 b.geo = g359 return g360}361362// Lines exposes the derived lines.363func (b *Board) Lines() []Line { return b.Geometry().lines }364365// excludes returns the rules under which placing v at global cell id is366// illegal, each rule evaluated independently of the others, over every367// line through the cell.368func (b *Board) excludes(id int, v Cell, mask Mask) Mask {369 var out Mask370 g := b.Geometry()371 for _, li := range g.linesAt[id] {372 ln := g.lines[li]373 n := len(ln.Cells)374 pos := 0375 for k, c := range ln.Cells {376 if c == id {377 pos = k378 break379 }380 }381 at := func(k int) Cell { return b.Cells[ln.Cells[k]] }382 if mask&Run != 0 {383 if (pos >= 2 && at(pos-1) == v && at(pos-2) == v) ||384 (pos >= 1 && pos < n-1 && at(pos-1) == v && at(pos+1) == v) ||385 (pos <= n-3 && at(pos+1) == v && at(pos+2) == v) {386 out |= Run387 }388 }389 if mask&(Balance|Unique) != 0 {390 countV, filled := 0, 0391 for k := 0; k < n; k++ {392 c := at(k)393 if c != Empty {394 filled++395 if c == v {396 countV++397 }398 }399 }400 if mask&Balance != 0 && countV >= n/2 {401 out |= Balance402 }403 if mask&Unique != 0 && out&Unique == 0 &&404 (filled == n-1 || (filled == n-2 && mask&Balance != 0)) {405 for oi, other := range g.lines {406 if oi == li || other.Shape != ln.Shape || other.Row != ln.Row || len(other.Cells) != n {407 continue408 }409 if b.lineWouldDuplicate(ln, pos, v, other) {410 out |= Unique411 break412 }413 }414 }415 }416 }417 return out418}419420// lineWouldDuplicate reports whether placing v at position pos of line ln421// makes it equal to the complete line other: every filled cell already422// agrees, the placed cell agrees, and with at most one further blank423// balance would fill it identically.424func (b *Board) lineWouldDuplicate(ln Line, pos int, v Cell, other Line) bool {425 blanks := 0426 for k := range ln.Cells {427 a, o := b.Cells[ln.Cells[k]], b.Cells[other.Cells[k]]428 if k == pos {429 a = v430 }431 if o == Empty {432 return false433 }434 if a == Empty {435 blanks++436 continue437 }438 if a != o {439 return false440 }441 }442 return blanks <= 1443}444445// Step is one cell fixed by propagation.446type Step struct {447 X, Y int448 V Cell449 Rules []string // rules that excluded the other value; "bifurcation" when found by search450}451452// Validate reports the first violated rule among filled cells of any shape.453func (b *Board) Validate(mask Mask) error {454 g := b.Geometry()455 for li, ln := range g.lines {456 n := len(ln.Cells)457 c0, c1 := 0, 0458 for k, id := range ln.Cells {459 c := b.Cells[id]460 switch c {461 case 0:462 c0++463 case 1:464 c1++465 }466 if mask&Run != 0 && k >= 2 && c != Empty && c == b.Cells[ln.Cells[k-1]] && c == b.Cells[ln.Cells[k-2]] {467 return fmt.Errorf("run: three %d in line %d of shape %d", c, li, ln.Shape)468 }469 }470 if mask&Balance != 0 && (c0 > n/2 || c1 > n/2) {471 return fmt.Errorf("balance: line %d of shape %d exceeds %d", li, ln.Shape, n/2)472 }473 }474 if mask&Unique != 0 {475 for i, a := range g.lines {476 for j := i + 1; j < len(g.lines); j++ {477 o := g.lines[j]478 if o.Shape != a.Shape || o.Row != a.Row || len(o.Cells) != len(a.Cells) {479 continue480 }481 eq := true482 for k := range a.Cells {483 if b.Cells[a.Cells[k]] == Empty || b.Cells[a.Cells[k]] != b.Cells[o.Cells[k]] {484 eq = false485 break486 }487 }488 if eq {489 return fmt.Errorf("unique: lines %d and %d equal in shape %d", i, j, a.Shape)490 }491 }492 }493 }494 return nil495}496497// Complete reports whether every cell of every shape is filled.498func (b *Board) Complete() bool {499 for _, id := range b.Geometry().cells {500 if b.Cells[id] == Empty {501 return false502 }503 }504 return true505}506507// Propagate fixes every cell that the active rules force, to a fixpoint,508// then (depth > 0) bifurcates: a value whose assumption propagates (at509// depth-1) to a contradiction is excluded. Returns the steps in order and510// false on contradiction. The board is mutated.511func (b *Board) Propagate(mask Mask, depth int) ([]Step, bool) {512 var steps []Step513 for {514 for {515 st, ok := b.propagateOnce(mask)516 if !ok {517 return steps, false518 }519 if len(st) == 0 {520 break521 }522 steps = append(steps, st...)523 }524 if depth <= 0 {525 return steps, true526 }527 found := false528 for _, id := range b.Geometry().cells {529 if b.Cells[id] != Empty {530 continue531 }532 var bad [2]bool533 for v := Cell(0); v <= 1; v++ {534 t := b.Clone()535 t.Cells[id] = v536 if _, ok := t.Propagate(mask, depth-1); !ok {537 bad[v] = true538 }539 }540 if bad[0] && bad[1] {541 return steps, false542 }543 if bad[0] || bad[1] {544 v := Cell(0)545 if bad[0] {546 v = 1547 }548 b.Cells[id] = v549 steps = append(steps, Step{X: id % b.W, Y: id / b.W, V: v, Rules: []string{"bifurcation"}})550 found = true551 break552 }553 }554 if !found {555 return steps, true556 }557 }558}559560// propagateOnce evaluates every empty cell once against every line561// through it and fixes those with a single admissible value. Rule562// attribution is the union over lines of the rules excluding the rejected563// value.564func (b *Board) propagateOnce(mask Mask) ([]Step, bool) {565 var steps []Step566 type ex struct {567 id int568 e [2]Mask569 }570 var exs []ex571 for _, id := range b.Geometry().cells {572 if b.Cells[id] != Empty {573 continue574 }575 exs = append(exs, ex{id, [2]Mask{b.excludes(id, 0, mask), b.excludes(id, 1, mask)}})576 }577 for _, a := range exs {578 if a.e[0] != 0 && a.e[1] != 0 {579 return steps, false580 }581 if a.e[0] == 0 && a.e[1] == 0 {582 continue583 }584 v, why := Cell(0), a.e[1]585 if a.e[0] != 0 {586 v, why = 1, a.e[0]587 }588 if b.Cells[a.id] != Empty {589 continue590 }591 b.Cells[a.id] = v592 steps = append(steps, Step{X: a.id % b.W, Y: a.id / b.W, V: v, Rules: why.Names()})593 }594 return steps, true595}596597// Solutions enumerates up to limit complete assignments consistent with the598// active rules, by propagation plus branching on the most constrained cell.599// The search is bounded by DefaultBudget nodes; see SolutionsBudget.600func (b *Board) Solutions(mask Mask, limit int) [][]Cell {601 out, _ := b.SolutionsBudget(mask, limit, DefaultBudget)602 return out603}604605// DefaultBudget is the node budget for Solutions: past it the enumeration606// stops and reports exhausted=false. This solver models technique, not607// search; the sat package answers counting questions definitively.608const DefaultBudget = 200000609610// SolutionsBudget is Solutions with an explicit node budget. exhausted is611// true when the search space was fully explored (or limit was reached).612func (b *Board) SolutionsBudget(mask Mask, limit int, budget int) (sols [][]Cell, exhausted bool) {613 var out [][]Cell614 nodes := 0615 over := false616 var rec func(t *Board)617 rec = func(t *Board) {618 if len(out) >= limit || over {619 return620 }621 nodes++622 if nodes > budget {623 over = true624 return625 }626 if _, ok := t.Propagate(mask, 0); !ok {627 return628 }629 if t.Complete() {630 if t.Validate(mask) == nil {631 c := make([]Cell, len(t.Cells))632 copy(c, t.Cells)633 out = append(out, c)634 }635 return636 }637 id := t.pickBranch()638 for v := Cell(0); v <= 1; v++ {639 u := t.Clone()640 u.Cells[id] = v641 rec(u)642 if len(out) >= limit || over {643 return644 }645 }646 }647 rec(b.Clone())648 return out, !over649}650651// pickBranch chooses an empty cell whose lines are the most filled.652func (b *Board) pickBranch() int {653 g := b.Geometry()654 filled := make([]int, len(g.lines))655 for li, ln := range g.lines {656 for _, id := range ln.Cells {657 if b.Cells[id] != Empty {658 filled[li]++659 }660 }661 }662 best, bestScore := -1, -1663 for _, id := range g.cells {664 if b.Cells[id] != Empty {665 continue666 }667 s := 0668 for _, li := range g.linesAt[id] {669 s += filled[li]670 }671 if s > bestScore {672 best, bestScore = id, s673 }674 }675 return best676}677678// Rect is a 2x2 flip rectangle in shape-local coordinates: cells679// (C1,R1),(C2,R1),(C1,R2),(C2,R2) with S[R1][C1]=S[R2][C2] != S[R1][C2]=S[R2][C1].680type Rect struct{ R1, C1, R2, C2 int }681682func (r Rect) Cells() [4][2]int {683 return [4][2]int{{r.C1, r.R1}, {r.C2, r.R1}, {r.C1, r.R2}, {r.C2, r.R2}}684}685686// FindFlips lists every rectangle of a complete shape (s is H rows of W687// local cells, Empty outside the shape) whose four corners lie on two688// shared row lines and two shared column lines and can be flipped (0<->1)689// leaving the shape valid under mask.690func FindFlips(sh Shape, s [][]Cell, mask Mask) []Rect {691 W, H := sh.W, sh.H692 m := sh.Mask()693 // line id per cell per orientation, for the "same line" test694 rowOf := make([]int, W*H)695 colOf := make([]int, W*H)696 for i := range rowOf {697 rowOf[i], colOf[i] = -1, -1698 }699 for li, ln := range sh.Lines() {700 row := len(ln) == 1 || ln[1] == ln[0]+1701 for _, c := range ln {702 if row {703 rowOf[c] = li704 } else {705 colOf[c] = li706 }707 }708 }709 var out []Rect710 for r1 := 0; r1 < H; r1++ {711 for r2 := r1 + 1; r2 < H; r2++ {712 for c1 := 0; c1 < W; c1++ {713 for c2 := c1 + 1; c2 < W; c2++ {714 a, bb, c, d := r1*W+c1, r1*W+c2, r2*W+c1, r2*W+c2715 if !m[a] || !m[bb] || !m[c] || !m[d] {716 continue717 }718 if rowOf[a] != rowOf[bb] || rowOf[c] != rowOf[d] || colOf[a] != colOf[c] || colOf[bb] != colOf[d] {719 continue720 }721 if s[r1][c1] != s[r2][c2] || s[r1][c2] != s[r2][c1] || s[r1][c1] == s[r1][c2] {722 continue723 }724 r := Rect{r1, c1, r2, c2}725 t := FlipGrid(s, r)726 cells := make([]Cell, W*H)727 for y := 0; y < H; y++ {728 copy(cells[y*W:(y+1)*W], t[y])729 }730 if Single(sh, cells).Validate(mask) == nil {731 out = append(out, r)732 }733 }734 }735 }736 }737 return out738}739740// FlipGrid returns a copy of s with the rectangle's corners inverted.741func FlipGrid(s [][]Cell, r Rect) [][]Cell {742 t := make([][]Cell, len(s))743 for i := range s {744 t[i] = append([]Cell(nil), s[i]...)745 }746 for _, c := range r.Cells() {747 t[c[1]][c[0]] = 1 - t[c[1]][c[0]]748 }749 return t750}751752// TileSolutions is the solution set of one shape alone, as flat local W*H753// slices (Empty outside the shape).754type TileSolutions [][]Cell755756// CoupledSolutionsGrid counts coupled solutions for an X-by-X grid of757// n-squares on a pitch of n-1 (the phase-1 layout).758func CoupledSolutionsGrid(X, n int, sols []TileSolutions, limit int) (int, [][]int) {759 ws := make([]Shape, 0, X*X)760 for ty := 0; ty < X; ty++ {761 for tx := 0; tx < X; tx++ {762 ws = append(ws, Square(tx*(n-1), ty*(n-1), n))763 }764 }765 return CoupledSolutions(ws, sols, limit)766}767768// CoupledSolutions counts (up to limit) the choices of one solution per769// shape such that every pair of shapes agrees on every shared cell.770func CoupledSolutions(ws []Shape, sols []TileSolutions, limit int) (int, [][]int) {771 type pair struct{ a, b int }772 masks := make([][]bool, len(ws))773 for i, s := range ws {774 masks[i] = s.Mask()775 }776 overlap := func(a, b int) [][2]int {777 wa, wb := ws[a], ws[b]778 var cells [][2]int // local index in a, local index in b779 x0, x1 := max(wa.X0, wb.X0), min(wa.X0+wa.W, wb.X0+wb.W)780 y0, y1 := max(wa.Y0, wb.Y0), min(wa.Y0+wa.H, wb.Y0+wb.H)781 for gy := y0; gy < y1; gy++ {782 for gx := x0; gx < x1; gx++ {783 la := (gy-wa.Y0)*wa.W + gx - wa.X0784 lb := (gy-wb.Y0)*wb.W + gx - wb.X0785 if masks[a][la] && masks[b][lb] {786 cells = append(cells, [2]int{la, lb})787 }788 }789 }790 return cells791 }792 compat := map[pair][][]bool{}793 neighbours := make([][]int, len(ws))794 for a := range ws {795 for b := a + 1; b < len(ws); b++ {796 cells := overlap(a, b)797 if len(cells) == 0 {798 continue799 }800 neighbours[a] = append(neighbours[a], b)801 neighbours[b] = append(neighbours[b], a)802 tbl := make([][]bool, len(sols[a]))803 for i, sa := range sols[a] {804 tbl[i] = make([]bool, len(sols[b]))805 for j, sb := range sols[b] {806 ok := true807 for _, c := range cells {808 if sa[c[0]] != sb[c[1]] {809 ok = false810 break811 }812 }813 tbl[i][j] = ok814 }815 }816 compat[pair{a, b}] = tbl817 }818 }819 ok := func(a, i, b, j int) bool {820 if a < b {821 return compat[pair{a, b}][i][j]822 }823 return compat[pair{b, a}][j][i]824 }825 choice := make([]int, len(ws))826 for i := range choice {827 choice[i] = -1828 }829 var found [][]int830 var rec func(t int)831 rec = func(t int) {832 if len(found) >= limit {833 return834 }835 if t == len(ws) {836 found = append(found, append([]int(nil), choice...))837 return838 }839 for i := range sols[t] {840 good := true841 for _, nb := range neighbours[t] {842 if choice[nb] >= 0 && !ok(t, i, nb, choice[nb]) {843 good = false844 break845 }846 }847 if !good {848 continue849 }850 choice[t] = i851 rec(t + 1)852 choice[t] = -1853 }854 }855 rec(0)856 return len(found), found857}858859// Diff lists the flat indices where two equal-length cell slices differ.860func Diff(a, b []Cell) []int {861 var out []int862 for i := range a {863 if a[i] != b[i] {864 out = append(out, i)865 }866 }867 sort.Ints(out)868 return out869}870871// Rating is the technique ladder's verdict on a puzzle: which techniques872// the ladder solver had to use. The ladder is the one the difficulty873// literature uses: run+balance propagation first, the uniqueness rule only874// when that stalls, and a depth-1 bifurcation only when all three stall.875type Rating struct {876 UsedUnique bool877 UsedBifurcation bool878 Complete bool879 Bifurcations int880}881882// Ladder solves b (mutating it) with the technique ladder and reports what883// it needed. maxBifurcations bounds the search; when exceeded Complete is884// false and UsedBifurcation is true.885func (b *Board) Ladder(maxBifurcations int) Rating {886 var r Rating887 for {888 if _, ok := b.Propagate(Run|Balance, 0); !ok {889 return r890 }891 if b.Complete() {892 r.Complete = true893 return r894 }895 st, ok := b.propagateOnce(All)896 if !ok {897 return r898 }899 for _, s := range st {900 for _, name := range s.Rules {901 if name == "unique" {902 r.UsedUnique = true903 }904 }905 }906 if len(st) > 0 {907 continue908 }909 if b.Complete() {910 r.Complete = true911 return r912 }913 r.UsedBifurcation = true914 if r.Bifurcations >= maxBifurcations {915 return r916 }917 r.Bifurcations++918 found, ok := b.bifurcateOnce(All)919 if !ok {920 return r921 }922 if !found {923 return r924 }925 }926}927928// bifurcateOnce fixes the first cell whose one value propagates (depth 0,929// mask) to a contradiction. Returns found=false when no cell is decidable930// this way, ok=false when both values contradict.931func (b *Board) bifurcateOnce(mask Mask) (found bool, ok bool) {932 for _, id := range b.Geometry().cells {933 if b.Cells[id] != Empty {934 continue935 }936 var bad [2]bool937 for v := Cell(0); v <= 1; v++ {938 t := b.Clone()939 t.Cells[id] = v940 if _, ok := t.Propagate(mask, 0); !ok {941 bad[v] = true942 }943 }944 if bad[0] && bad[1] {945 return false, false946 }947 if bad[0] || bad[1] {948 v := Cell(0)949 if bad[0] {950 v = 1951 }952 b.Cells[id] = v953 return true, true954 }955 }956 return false, true957}