1package takuzu23import "math/rand/v2"45type cellPos struct{ x, y int }67type lineStats struct {8 rowZero []int9 rowOne []int10 colZero []int11 colOne []int12 rowFilled []int13 colFilled []int14}1516type mrvChoice struct {17 x, y int18 vals [2]rune19 count int20}2122func newLineStats(g grid, size int) *lineStats {23 stats := &lineStats{24 rowZero: make([]int, size),25 rowOne: make([]int, size),26 colZero: make([]int, size),27 colOne: make([]int, size),28 rowFilled: make([]int, size),29 colFilled: make([]int, size),30 }3132 for y := range size {33 for x := range size {34 val := g[y][x]35 if val == emptyCell {36 continue37 }3839 stats.rowFilled[y]++40 stats.colFilled[x]++41 switch val {42 case zeroCell:43 stats.rowZero[y]++44 stats.colZero[x]++45 case oneCell:46 stats.rowOne[y]++47 stats.colOne[x]++48 }49 }50 }5152 return stats53}5455func (s *lineStats) apply(x, y int, val rune, delta int) {56 s.rowFilled[y] += delta57 s.colFilled[x] += delta5859 switch val {60 case zeroCell:61 s.rowZero[y] += delta62 s.colZero[x] += delta63 case oneCell:64 s.rowOne[y] += delta65 s.colOne[x] += delta66 }67}6869// generateComplete fills an empty grid with a valid Takuzu solution using70// backtracking with retry on failure.71func generateComplete(size int) grid {72 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))73 return generateCompleteSeeded(size, rng)74}7576func generateCompleteSeeded(size int, rng *rand.Rand) grid {77 g := newGrid(createEmptyState(size))7879 const maxRetries = 1080 for range maxRetries {81 for y := range size {82 for x := range size {83 g[y][x] = emptyCell84 }85 }8687 if fillGridSeeded(g, size, rng) {88 return g89 }90 }9192 // Last attempt - use more exhaustive search93 for y := range size {94 for x := range size {95 g[y][x] = emptyCell96 }97 }98 if fillGridSeeded(g, size, rng) {99 return g100 }101102 panic("failed to generate complete grid")103}104105func fillGrid(g grid, size int) bool {106 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))107 return fillGridSeeded(g, size, rng)108}109110func fillGridSeeded(g grid, size int, rng *rand.Rand) bool {111 stats := newLineStats(g, size)112 return fillGridSeededWithStats(g, size, rng, stats)113}114115func fillGridSeededWithStats(g grid, size int, rng *rand.Rand, stats *lineStats) bool {116 choice := selectMRVCell(g, size, stats, rng)117 if choice.x < 0 {118 return true119 }120 if choice.count == 0 {121 return false122 }123124 if choice.count == 2 && rng.IntN(2) == 0 {125 choice.vals[0], choice.vals[1] = choice.vals[1], choice.vals[0]126 }127128 for i := range choice.count {129 v := choice.vals[i]130 g[choice.y][choice.x] = v131 stats.apply(choice.x, choice.y, v, 1)132 if fillGridSeededWithStats(g, size, rng, stats) {133 return true134 }135 stats.apply(choice.x, choice.y, v, -1)136 g[choice.y][choice.x] = emptyCell137 }138139 return false140}141142func selectMRVCell(g grid, size int, stats *lineStats, rng *rand.Rand) mrvChoice {143 choice := mrvChoice{x: -1, y: -1, count: 3}144 tieCount := 0145146 for y := range size {147 for x := range size {148 if g[y][x] != emptyCell {149 continue150 }151152 vals, count := cellCandidates(g, size, x, y, stats)153 if count == 0 {154 return mrvChoice{x: x, y: y}155 }156157 if count < choice.count {158 choice = mrvChoice{x: x, y: y, vals: vals, count: count}159 tieCount = 1160 continue161 }162163 if count == choice.count {164 tieCount++165 if rng != nil && rng.IntN(tieCount) == 0 {166 choice = mrvChoice{x: x, y: y, vals: vals, count: count}167 }168 }169 }170 }171172 if choice.x < 0 {173 return mrvChoice{x: -1, y: -1, count: 0}174 }175176 return choice177}178179func cellCandidates(g grid, size, x, y int, stats *lineStats) ([2]rune, int) {180 var vals [2]rune181 count := 0182183 if canPlaceWithStats(g, size, x, y, zeroCell, stats) {184 vals[count] = zeroCell185 count++186 }187 if canPlaceWithStats(g, size, x, y, oneCell, stats) {188 vals[count] = oneCell189 count++190 }191192 return vals, count193}194195// generatePuzzle removes cells from a complete grid to create a puzzle with a unique solution.196func generatePuzzle(complete grid, size int, prefilled float64) (puzzle grid, provided [][]bool) {197 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))198 return generatePuzzleSeeded(complete, size, prefilled, rng)199}200201func generatePuzzleSeeded(complete grid, size int, prefilled float64, rng *rand.Rand) (puzzle grid, provided [][]bool) {202 puzzle = complete.clone()203 provided = make([][]bool, size)204 for y := range size {205 provided[y] = make([]bool, size)206 for x := range size {207 provided[y][x] = true208 }209 }210211 target := int(prefilled * float64(size*size))212213 rowProvided := make([]int, size)214 colProvided := make([]int, size)215 for i := range size {216 rowProvided[i] = size217 colProvided[i] = size218 }219220 candidates := make([]cellPos, 0, size*size)221 for y := range size {222 for x := range size {223 candidates = append(candidates, cellPos{x, y})224 }225 }226 rng.Shuffle(len(candidates), func(i, j int) {227 candidates[i], candidates[j] = candidates[j], candidates[i]228 })229230 stats := newLineStats(puzzle, size)231 filled := size * size232 for len(candidates) > 0 && filled > target {233 bestIdx := pickRemovalCandidate(candidates, puzzle, rowProvided, colProvided, rng)234 p := candidates[bestIdx]235 last := len(candidates) - 1236 candidates[bestIdx] = candidates[last]237 candidates = candidates[:last]238239 if puzzle[p.y][p.x] == emptyCell {240 continue241 }242243 saved := puzzle[p.y][p.x]244 puzzle[p.y][p.x] = emptyCell245 stats.apply(p.x, p.y, saved, -1)246 if countSolutionsWithStats(puzzle, size, 2, stats) != 1 {247 puzzle[p.y][p.x] = saved248 stats.apply(p.x, p.y, saved, 1)249 } else {250 provided[p.y][p.x] = false251 filled--252 rowProvided[p.y]--253 colProvided[p.x]--254 }255 }256257 return puzzle, provided258}259260func pickRemovalCandidate(candidates []cellPos, puzzle grid, rowProvided, colProvided []int, rng *rand.Rand) int {261 bestIdx := 0262 bestScore := clueRemovalScore(candidates[0], puzzle, rowProvided, colProvided)263264 for i := 1; i < len(candidates); i++ {265 score := clueRemovalScore(candidates[i], puzzle, rowProvided, colProvided)266 if score > bestScore || (score == bestScore && rng.IntN(2) == 0) {267 bestIdx = i268 bestScore = score269 }270 }271272 return bestIdx273}274275func clueRemovalScore(p cellPos, puzzle grid, rowProvided, colProvided []int) int {276 size := len(puzzle)277 score := rowProvided[p.y] + colProvided[p.x]278279 if p.x > 0 && puzzle[p.y][p.x-1] != emptyCell {280 score++281 }282 if p.x < size-1 && puzzle[p.y][p.x+1] != emptyCell {283 score++284 }285 if p.y > 0 && puzzle[p.y-1][p.x] != emptyCell {286 score++287 }288 if p.y < size-1 && puzzle[p.y+1][p.x] != emptyCell {289 score++290 }291292 return score293}294295// countSolutions counts solutions of the grid up to limit using backtracking.296func countSolutions(g grid, size, limit int) int {297 stats := newLineStats(g, size)298 return countSolutionsWithStats(g, size, limit, stats)299}300301func countSolutionsWithStats(g grid, size, limit int, stats *lineStats) int {302 choice := selectMRVCell(g, size, stats, nil)303 if choice.x < 0 {304 if hasUniqueLines(g, size) {305 return 1306 }307 return 0308 }309 if choice.count == 0 {310 return 0311 }312313 total := 0314 for i := range choice.count {315 v := choice.vals[i]316 g[choice.y][choice.x] = v317 stats.apply(choice.x, choice.y, v, 1)318 total += countSolutionsWithStats(g, size, limit-total, stats)319 stats.apply(choice.x, choice.y, v, -1)320 g[choice.y][choice.x] = emptyCell321 if total >= limit {322 return total323 }324 }325326 return total327}328329// checkConstraints verifies no-triples and equal-count rules for every row and column.330func checkConstraints(g grid, size int) bool {331 half := size / 2332 for i := range size {333 zeroRow, oneRow := 0, 0334 zeroCol, oneCol := 0, 0335 for j := range size {336 switch g[i][j] {337 case zeroCell:338 zeroRow++339 case oneCell:340 oneRow++341 }342 switch g[j][i] {343 case zeroCell:344 zeroCol++345 case oneCell:346 oneCol++347 }348 if j >= 2 && g[i][j] == g[i][j-1] && g[i][j] == g[i][j-2] {349 return false350 }351 if j >= 2 && g[j][i] == g[j-1][i] && g[j][i] == g[j-2][i] {352 return false353 }354 }355 if zeroRow != half || oneRow != half {356 return false357 }358 if zeroCol != half || oneCol != half {359 return false360 }361 }362 return true363}364365// hasUniqueLines checks that all rows are unique and all columns are unique.366func hasUniqueLines(g grid, size int) bool {367 for i := range size {368 for j := i + 1; j < size; j++ {369 if rowEqual(g[i], g[j]) {370 return false371 }372 }373 }374 for i := range size {375 for j := i + 1; j < size; j++ {376 if colEqual(g, size, i, j) {377 return false378 }379 }380 }381 return true382}383384func rowEqual(a, b []rune) bool {385 if len(a) != len(b) {386 return false387 }388 for i := range a {389 if a[i] != b[i] {390 return false391 }392 }393 return true394}395396func colEqual(g grid, size, c1, c2 int) bool {397 for r := range size {398 if g[r][c1] != g[r][c2] {399 return false400 }401 }402 return true403}404405// canPlace checks whether placing val at (x,y) would violate Takuzu constraints.406func canPlace(g grid, size, x, y int, val rune) bool {407 stats := newLineStats(g, size)408 return canPlaceWithStats(g, size, x, y, val, stats)409}410411func canPlaceWithStats(g grid, size, x, y int, val rune, stats *lineStats) bool {412 if g[y][x] != emptyCell {413 return false414 }415416 if x >= 2 && g[y][x-1] == val && g[y][x-2] == val {417 return false418 }419 if x >= 1 && x < size-1 && g[y][x-1] == val && g[y][x+1] == val {420 return false421 }422 if x <= size-3 && g[y][x+1] == val && g[y][x+2] == val {423 return false424 }425426 if y >= 2 && g[y-1][x] == val && g[y-2][x] == val {427 return false428 }429 if y >= 1 && y < size-1 && g[y-1][x] == val && g[y+1][x] == val {430 return false431 }432 if y <= size-3 && g[y+1][x] == val && g[y+2][x] == val {433 return false434 }435436 half := size / 2437 switch val {438 case zeroCell:439 if stats.rowZero[y] >= half || stats.colZero[x] >= half {440 return false441 }442 case oneCell:443 if stats.rowOne[y] >= half || stats.colOne[x] >= half {444 return false445 }446 }447448 if stats.rowFilled[y] == size-1 {449 for other := range size {450 if other != y && stats.rowFilled[other] == size && rowEqualWith(g[y], g[other], x, val) {451 return false452 }453 }454 }455456 if stats.colFilled[x] == size-1 {457 for other := range size {458 if other != x && stats.colFilled[other] == size && colEqualWith(g, size, x, other, y, val) {459 return false460 }461 }462 }463464 return true465}466467func rowEqualWith(a, b []rune, overrideIdx int, overrideVal rune) bool {468 if len(a) != len(b) {469 return false470 }471 for i := range a {472 av := a[i]473 if i == overrideIdx {474 av = overrideVal475 }476 if av != b[i] {477 return false478 }479 }480 return true481}482483func colEqualWith(g grid, size, c1, c2, overrideRow int, overrideVal rune) bool {484 for r := range size {485 v1 := g[r][c1]486 if r == overrideRow {487 v1 = overrideVal488 }489 if v1 != g[r][c2] {490 return false491 }492 }493 return true494}495496func rowFilled(g grid, y, size int) bool {497 for x := range size {498 if g[y][x] == emptyCell {499 return false500 }501 }502 return true503}504505func GenerateCompleteGrid(size int) [][]rune {506 return generateComplete(size).clone()507}508509func GenerateCompleteGridSeeded(size int, rng *rand.Rand) [][]rune {510 return generateCompleteSeeded(size, rng).clone()511}512513func GeneratePuzzleFromComplete(complete [][]rune, size int, prefilled float64) ([][]rune, [][]bool) {514 puzzle, provided := generatePuzzle(grid(complete).clone(), size, prefilled)515 return puzzle.clone(), provided516}517518func GeneratePuzzleFromCompleteSeeded(complete [][]rune, size int, prefilled float64, rng *rand.Rand) ([][]rune, [][]bool) {519 puzzle, provided := generatePuzzleSeeded(grid(complete).clone(), size, prefilled, rng)520 return puzzle.clone(), provided521}522523func CountSolutionsGrid(g [][]rune, size, limit int) int {524 return countSolutions(grid(g).clone(), size, limit)525}526527func CheckConstraintsGrid(g [][]rune, size int) bool {528 return checkConstraints(grid(g), size)529}530531func HasUniqueLinesGrid(g [][]rune, size int) bool {532 return hasUniqueLines(grid(g), size)533}534535func CanPlaceInGrid(g [][]rune, size, x, y int, val rune) bool {536 return canPlace(grid(g), size, x, y, val)537}538539func colFilled(g grid, x, size int) bool {540 for y := range size {541 if g[y][x] == emptyCell {542 return false543 }544 }545 return true546}