1package rules23import (4 "strings"5 "testing"6)78func parse(t *testing.T, rows ...string) *Board {9 t.Helper()10 n := len(rows)11 b := NewBoard(n, n)12 b.Shapes = []Shape{Square(0, 0, n)}13 for y, r := range rows {14 if len(r) != n {15 t.Fatalf("row %d has %d cells, want %d", y, len(r), n)16 }17 for x, ch := range r {18 switch ch {19 case '0':20 b.Set(x, y, 0)21 case '1':22 b.Set(x, y, 1)23 }24 }25 }26 return b27}2829func TestExcludesEachRuleIndependently(t *testing.T) {30 // row 0: "00...." -> placing 0 at (2,0) makes a run; balance needs 3 of each31 b := parse(t,32 "00....",33 "......",34 "......",35 "......",36 "......",37 "......")38 if ex := b.excludes(b.Idx(2, 0), 0, All); ex&Run == 0 || ex&Balance != 0 {39 t.Fatalf("want run only, got %v", ex.Names())40 }41 // balance: row 1 already has three 1s42 b = parse(t,43 "......",44 "1.1.1.",45 "......",46 "......",47 "......",48 "......")49 if ex := b.excludes(b.Idx(1, 1), 1, All); ex&Balance == 0 {50 t.Fatalf("want balance, got %v", ex.Names())51 }52 // unique: completing row 1 as 010101 would equal row 053 b = parse(t,54 "010101",55 "0.0101",56 "......",57 "......",58 "......",59 "......")60 if ex := b.excludes(b.Idx(1, 1), 1, All); ex&Unique == 0 {61 t.Fatalf("want unique, got %v", ex.Names())62 }63 if ex := b.excludes(b.Idx(1, 1), 1, Run|Balance); ex != 0 {64 t.Fatalf("unique must not fire when masked out, got %v", ex.Names())65 }66}6768func TestPropagateRecoversRemovedCluesWithAttribution(t *testing.T) {69 e := NewBoard(6, 6)70 e.Shapes = []Shape{Square(0, 0, 6)}71 sol := e.Solutions(All, 1)[0]72 // blank a cell only when propagation gets it back: the puzzle stays73 // propagation-solvable and every step must carry a rule name.74 b := &Board{W: 6, H: 6, Cells: append([]Cell(nil), sol...), Shapes: e.Shapes}75 blanked := 076 for i := range sol {77 b.Cells[i] = Empty78 t2 := b.Clone()79 t2.Propagate(All, 0)80 if t2.Cells[i] != sol[i] {81 b.Cells[i] = sol[i]82 continue83 }84 blanked++85 }86 if blanked < 10 {87 t.Fatalf("only %d cells blanked", blanked)88 }89 steps, ok := b.Propagate(All, 0)90 if !ok || !b.Complete() {91 t.Fatalf("ok=%v complete=%v\n%s", ok, b.Complete(), dump(b))92 }93 for i := range sol {94 if b.Cells[i] != sol[i] {95 t.Fatalf("cell %d differs from the solution", i)96 }97 }98 if len(steps) != blanked {99 t.Fatalf("%d steps for %d blanks", len(steps), blanked)100 }101 for _, s := range steps {102 if len(s.Rules) == 0 {103 t.Fatalf("step %v has no rule attribution", s)104 }105 }106}107108func TestSolutionsCountsAndMask(t *testing.T) {109 // an empty 4x4 has 72 valid grids under run+balance, fewer with uniqueness110 e := NewBoard(4, 4)111 e.Shapes = []Shape{Square(0, 0, 4)}112 all := len(e.Solutions(All, 1000))113 noUnique := len(e.Solutions(Run|Balance, 1000))114 if noUnique <= all || all == 0 {115 t.Fatalf("all=%d noUnique=%d", all, noUnique)116 }117 for _, s := range e.Solutions(All, 1000) {118 c := &Board{W: 4, H: 4, Cells: s, Shapes: e.Shapes}119 if err := c.Validate(All); err != nil {120 t.Fatal(err)121 }122 }123}124125func TestSeamCouplesTwoShapes(t *testing.T) {126 // two 4x4 squares overlapping by one column (pitch 3) on a 7x4 board127 b := NewBoard(7, 4)128 b.Shapes = []Shape{Square(0, 0, 4), Square(3, 0, 4)}129 sols := b.Solutions(All, 100000)130 single := NewBoard(4, 4)131 single.Shapes = []Shape{Square(0, 0, 4)}132 one := len(single.Solutions(All, 1000))133 if len(sols) >= one*one {134 t.Fatalf("seam did not constrain: %d coupled vs %d*%d", len(sols), one, one)135 }136}137138func TestFindFlipsProducesValidAlternatives(t *testing.T) {139 s := [][]Cell{140 {0, 1, 0, 1, 1, 0},141 {1, 0, 1, 0, 0, 1},142 {0, 1, 1, 0, 1, 0},143 {1, 0, 0, 1, 0, 1},144 {0, 1, 0, 1, 1, 0},145 {1, 0, 1, 0, 0, 1},146 }147 // rows 0 and 4 are equal: not a valid Takuzu, so fix row 4/5 to be distinct148 s[4] = []Cell{1, 1, 0, 0, 1, 0}149 s[5] = []Cell{0, 0, 1, 1, 0, 1}150 sq := Square(0, 0, 6)151 b := &Board{W: 6, H: 6, Shapes: []Shape{sq}}152 for _, r := range s {153 b.Cells = append(b.Cells, r...)154 }155 if err := b.Validate(All); err != nil {156 t.Skip("fixture invalid: " + err.Error())157 }158 flips := FindFlips(sq, s, All)159 for _, r := range flips {160 f := FlipGrid(s, r)161 c := &Board{W: 6, H: 6, Shapes: b.Shapes}162 for _, row := range f {163 c.Cells = append(c.Cells, row...)164 }165 if err := c.Validate(All); err != nil {166 t.Fatalf("flip %v invalid: %v", r, err)167 }168 if len(Diff(b.Cells, c.Cells)) != 4 {169 t.Fatalf("flip %v changed %d cells", r, len(Diff(b.Cells, c.Cells)))170 }171 }172}173174func TestCoupledSolutionsAgreesOnSharedCells(t *testing.T) {175 // a real 2x2 mosaic of 4x4 tiles (7x7 board); each tile's solution set is176 // its true window plus the windows of other coupled mosaics, so the CSP177 // must find the true assignment and reject any seam mismatch.178 n, X := 4, 2179 b := NewBoard(7, 7)180 b.Shapes = []Shape{Square(0, 0, n), Square(3, 0, n), Square(0, 3, n), Square(3, 3, n)}181 all := b.Solutions(All, 6)182 if len(all) < 2 {183 t.Fatalf("want several mosaics, got %d", len(all))184 }185 sols := make([]TileSolutions, X*X)186 for ti, sh := range b.Shapes {187 for _, mosaic := range all {188 sols[ti] = append(sols[ti], sh.Local(mosaic, 7))189 }190 }191 count, found := CoupledSolutionsGrid(X, n, sols, 100)192 if count < len(all) {193 t.Fatalf("count %d < %d true mosaics", count, len(all))194 }195 for _, ch := range found {196 s0, s1 := sols[0][ch[0]], sols[1][ch[1]]197 for y := 0; y < n; y++ {198 if s0[y*n+3] != s1[y*n] {199 t.Fatalf("seam mismatch in %v", ch)200 }201 }202 }203}204205// tee is a T: an 8-wide, 6-tall crossbar over a 4-wide, 2-tall stem206// (bounding box 8x8, 56 cells). Lines: rows of 8 (6 of them), rows of 4207// (2, the stem), columns of 8 (4, through the stem), columns of 6 (4,208// crossbar only). Two parallel 4-lines is within the pigeonhole bound209// (at most DistinctLines(4)/2 = 3).210func tee() Shape {211 return Shape{W: 8, H: 8, Rects: [][4]int{{0, 0, 8, 6}, {2, 6, 4, 2}}}212}213214func TestShapeLinesAndValid(t *testing.T) {215 sh := tee()216 if sh.Cells() != 56 {217 t.Fatalf("cells %d", sh.Cells())218 }219 lines := sh.Lines()220 if len(lines) != 16 {221 t.Fatalf("%d lines, want 16", len(lines))222 }223 lens := map[int]int{}224 for _, ln := range lines {225 lens[len(ln)]++226 }227 if lens[8] != 10 || lens[4] != 2 || lens[6] != 4 {228 t.Fatalf("line lengths %v", lens)229 }230 if err := sh.Valid(); err != nil {231 t.Fatal(err)232 }233 // odd stem width -> odd lines234 bad := Shape{W: 8, H: 8, Rects: [][4]int{{0, 0, 8, 6}, {2, 6, 3, 2}}}235 if bad.Valid() == nil {236 t.Fatal("odd line accepted")237 }238 // a 2-wide stem makes 2-long rows239 short := Shape{W: 8, H: 8, Rects: [][4]int{{0, 0, 8, 6}, {3, 6, 2, 2}}}240 if short.Valid() == nil {241 t.Fatal("2-long line accepted")242 }243 // disconnected244 two := Shape{W: 10, H: 4, Rects: [][4]int{{0, 0, 4, 4}, {6, 0, 4, 4}}}245 if two.Valid() == nil {246 t.Fatal("disconnected shape accepted")247 }248 // loose bounding box249 loose := Shape{W: 6, H: 4, Rects: [][4]int{{0, 0, 4, 4}}}250 if loose.Valid() == nil {251 t.Fatal("loose bounding box accepted")252 }253 if !sh.Contains(3, 6) || sh.Contains(0, 6) || sh.Contains(8, 0) {254 t.Fatal("Contains wrong")255 }256 // pigeonhole: at most DistinctLines(L)/2 parallel lines of length L.257 // A 4x12 has 12 parallel 4-lines (6 distinct exist, 3 allowed); even a258 // 4x4 square has 4 > 3; a 6x6 has 6 parallel 6-lines (14 exist, 7259 // allowed) and is the smallest square260 thin := Shape{W: 4, H: 12, Rects: [][4]int{{0, 0, 4, 12}}}261 if thin.Valid() == nil {262 t.Fatal("4x12 accepted despite the uniqueness pigeonhole")263 }264 if Square(0, 0, 4).Valid() == nil {265 t.Fatal("4x4 accepted: 4 parallel 4-lines, 3 allowed")266 }267 if Square(0, 0, 6).Valid() != nil || Square(0, 0, 16).Valid() != nil {268 t.Fatal("6x6 or 16x16 rejected")269 }270 if (Shape{W: 12, H: 6, Rects: [][4]int{{0, 0, 12, 6}}}).Valid() == nil {271 t.Fatal("12x6 accepted: 12 parallel 6-lines, 7 allowed")272 }273 if (Shape{W: 12, H: 8, Rects: [][4]int{{0, 0, 12, 8}}}).Valid() != nil {274 t.Fatal("12x8 rejected: 12 parallel 8-lines, 17 allowed")275 }276 want := map[int]int{4: 6, 6: 14, 8: 34, 10: 84, 12: 208, 14: 518, 16: 1296}277 for L, n := range want {278 if DistinctLines(L) != n {279 t.Fatalf("DistinctLines(%d) = %d, want %d", L, DistinctLines(L), n)280 }281 }282}283284func TestShapeRulesOnATee(t *testing.T) {285 sh := tee()286 b := NewBoard(8, 8)287 b.Shapes = []Shape{sh}288 // the stem's row at y=6 spans x=2..5: two 0s at x=2,3 exclude 0 at x=4 (run)289 b.Set(2, 6, 0)290 b.Set(3, 6, 0)291 if ex := b.excludes(b.Idx(4, 6), 0, All); ex&Run == 0 {292 t.Fatalf("run along a 4-line: %v", ex.Names())293 }294 // balance on the 4-line: two 0s already -> a third 0 at x=5 is excluded295 if ex := b.excludes(b.Idx(5, 6), 0, All); ex&Balance == 0 {296 t.Fatalf("balance along a 4-line: %v", ex.Names())297 }298 // cells outside the shape are never touched by propagation299 steps, ok := b.Propagate(All, 0)300 if !ok {301 t.Fatal("contradiction on a legal partial")302 }303 for _, s := range steps {304 if !sh.Contains(s.X, s.Y) {305 t.Fatalf("step outside the shape at (%d,%d)", s.X, s.Y)306 }307 }308 if b.At(0, 6) != Empty {309 t.Fatal("hole cell was written")310 }311 // a full solution exists, validates, and the ladder can solve a312 // propagation-friendly puzzle over it313 e := NewBoard(8, 8)314 e.Shapes = []Shape{sh}315 sols := e.Solutions(All, 3)316 if len(sols) == 0 {317 t.Fatal("no solution for a T")318 }319 full := &Board{W: 8, H: 8, Cells: sols[0], Shapes: e.Shapes}320 if err := full.Validate(All); err != nil {321 t.Fatal(err)322 }323 for _, id := range full.Geometry().cells {324 if full.Cells[id] == Empty {325 t.Fatal("incomplete solution")326 }327 }328 if !full.Complete() {329 t.Fatal("Complete false on a full T")330 }331 puzzle := full.Clone()332 for i := range puzzle.Cells {333 if sh.Contains(i%8, i/8) && i%3 == 0 {334 puzzle.Cells[i] = Empty335 }336 }337 r := puzzle.Ladder(4)338 if !r.Complete && !r.UsedBifurcation {339 t.Fatalf("ladder neither completed nor bifurcated: %+v", r)340 }341 // uniqueness only compares lines of equal length and orientation: the342 // crossbar's 8-rows never collide with the stem's 4-rows343 loc := sh.Local(full.Cells, 8)344 rows := [][]Cell{}345 for y := 0; y < 8; y++ {346 rows = append(rows, loc[y*8:(y+1)*8])347 }348 for _, r := range FindFlips(sh, rows, All) {349 for _, c := range r.Cells() {350 if !sh.Contains(c[0], c[1]) {351 t.Fatalf("flip %v uses a cell outside the shape", r)352 }353 }354 // both rows of the rectangle must be one line each: a crossbar row355 // and a stem row share x=2..5, and a rectangle across them is fine356 // only if all four cells are on shared lines, which FindFlips checks357 f := FlipGrid(rows, r)358 cells := make([]Cell, 64)359 for y := 0; y < 8; y++ {360 copy(cells[y*8:(y+1)*8], f[y])361 }362 if err := Single(sh, cells).Validate(All); err != nil {363 t.Fatalf("flip %v invalid: %v", r, err)364 }365 }366}367368func dump(b *Board) string {369 var sb strings.Builder370 for y := 0; y < b.H; y++ {371 for x := 0; x < b.W; x++ {372 switch b.At(x, y) {373 case Empty:374 sb.WriteByte('.')375 default:376 sb.WriteByte(byte('0' + b.At(x, y)))377 }378 }379 sb.WriteByte('\n')380 }381 return sb.String()382}