1package takuzuplus23import "github.com/FelineStateMachine/puzzletea/games/takuzu"45type mrvChoice struct {6 x, y int7 vals [2]rune8 count int9}1011func relationForValues(a, b rune) rune {12 if a == b {13 return relationSame14 }15 return relationDiff16}1718func relationSatisfied(kind, a, b rune) bool {19 switch kind {20 case relationSame:21 return a == b22 case relationDiff:23 return a != b24 default:25 return true26 }27}2829func relationAllowed(g grid, rels relations, x, y int, val rune) bool {30 if x > 0 {31 if rel := rels.horizontal[y][x-1]; rel != relationNone && g[y][x-1] != emptyCell && !relationSatisfied(rel, g[y][x-1], val) {32 return false33 }34 }35 if x < len(g[y])-1 {36 if rel := rels.horizontal[y][x]; rel != relationNone && g[y][x+1] != emptyCell && !relationSatisfied(rel, val, g[y][x+1]) {37 return false38 }39 }40 if y > 0 {41 if rel := rels.vertical[y-1][x]; rel != relationNone && g[y-1][x] != emptyCell && !relationSatisfied(rel, g[y-1][x], val) {42 return false43 }44 }45 if y < len(g)-1 {46 if rel := rels.vertical[y][x]; rel != relationNone && g[y+1][x] != emptyCell && !relationSatisfied(rel, val, g[y+1][x]) {47 return false48 }49 }50 return true51}5253func checkRelations(g grid, rels relations) bool {54 for y, row := range rels.horizontal {55 for x, rel := range row {56 if rel == relationNone || g[y][x] == emptyCell || g[y][x+1] == emptyCell {57 continue58 }59 if !relationSatisfied(rel, g[y][x], g[y][x+1]) {60 return false61 }62 }63 }64 for y, row := range rels.vertical {65 for x, rel := range row {66 if rel == relationNone || g[y][x] == emptyCell || g[y+1][x] == emptyCell {67 continue68 }69 if !relationSatisfied(rel, g[y][x], g[y+1][x]) {70 return false71 }72 }73 }74 return true75}7677func canPlaceWithRelations(g grid, size, x, y int, val rune, rels relations) bool {78 return takuzu.CanPlaceInGrid(g, size, x, y, val) && relationAllowed(g, rels, x, y, val)79}8081func selectMRVCell(g grid, size int, rels relations) mrvChoice {82 choice := mrvChoice{x: -1, y: -1, count: 3}83 for y := range size {84 for x := range size {85 if g[y][x] != emptyCell {86 continue87 }8889 var vals [2]rune90 count := 091 if canPlaceWithRelations(g, size, x, y, zeroCell, rels) {92 vals[count] = zeroCell93 count++94 }95 if canPlaceWithRelations(g, size, x, y, oneCell, rels) {96 vals[count] = oneCell97 count++98 }99100 if count == 0 {101 return mrvChoice{x: x, y: y, count: 0}102 }103 if count < choice.count {104 choice = mrvChoice{x: x, y: y, vals: vals, count: count}105 }106 }107 }108 if choice.x < 0 {109 return mrvChoice{x: -1, y: -1, count: 0}110 }111 return choice112}113114func countSolutions(g grid, size, limit int, rels relations) int {115 choice := selectMRVCell(g, size, rels)116 if choice.x < 0 {117 if takuzu.CheckConstraintsGrid(g, size) && takuzu.HasUniqueLinesGrid(g, size) && checkRelations(g, rels) {118 return 1119 }120 return 0121 }122 if choice.count == 0 {123 return 0124 }125126 total := 0127 for i := range choice.count {128 val := choice.vals[i]129 g[choice.y][choice.x] = val130 total += countSolutions(g, size, limit-total, rels)131 g[choice.y][choice.x] = emptyCell132 if total >= limit {133 return total134 }135 }136 return total137}