1package hitori23import (4 "errors"5 "math/rand/v2"6)78type cellPos struct{ x, y int }910// generateLatinSquare creates an NxN grid where each number 1..N appears11// exactly once in each row and column. Uses cyclic shifts with row and12// column shuffling.13func generateLatinSquare(size int) grid {14 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))15 return generateLatinSquareSeeded(size, rng)16}1718func generateLatinSquareSeeded(size int, rng *rand.Rand) grid {19 firstRow := make([]rune, size)20 for i := range size {21 firstRow[i] = rune('1' + i)22 }23 rng.Shuffle(len(firstRow), func(i, j int) {24 firstRow[i], firstRow[j] = firstRow[j], firstRow[i]25 })2627 g := make(grid, size)28 for y := range size {29 g[y] = make([]rune, size)30 for x := range size {31 g[y][x] = firstRow[(x+y)%size]32 }33 }3435 cols := make([]int, size)36 for i := range size {37 cols[i] = i38 }39 rng.Shuffle(len(cols), func(i, j int) {40 cols[i], cols[j] = cols[j], cols[i]41 })4243 rowOrder := make([]int, size)44 for i := range size {45 rowOrder[i] = i46 }47 rng.Shuffle(len(rowOrder), func(i, j int) {48 rowOrder[i], rowOrder[j] = rowOrder[j], rowOrder[i]49 })5051 result := make(grid, size)52 for y := range size {53 result[y] = make([]rune, size)54 for x := range size {55 result[y][x] = g[rowOrder[y]][cols[x]]56 }57 }5859 return result60}6162// generateValidMask determines which cells should be black. The mask63// satisfies: no adjacent black cells, and all white cells connected.64func generateValidMask(size int, blackRatio float64) [][]bool {65 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))66 return generateValidMaskSeeded(size, blackRatio, rng)67}6869func generateValidMaskSeeded(size int, blackRatio float64, rng *rand.Rand) [][]bool {70 mask := make([][]bool, size)71 for y := range size {72 mask[y] = make([]bool, size)73 }7475 targetBlack := int(blackRatio * float64(size*size))7677 positions := make([]cellPos, 0, size*size)78 for y := range size {79 for x := range size {80 positions = append(positions, cellPos{x, y})81 }82 }83 rng.Shuffle(len(positions), func(i, j int) {84 positions[i], positions[j] = positions[j], positions[i]85 })8687 blackCount := 088 for _, p := range positions {89 if blackCount >= targetBlack {90 break91 }9293 if hasOrthogonalNeighbor(mask, size, p.x, p.y) {94 continue95 }9697 mask[p.y][p.x] = true9899 if requiresConnectivityCheck(mask, size, p.x, p.y) &&100 !whiteCellsConnected(mask, size) {101 mask[p.y][p.x] = false102 continue103 }104105 blackCount++106 }107108 return mask109}110111func hasOrthogonalNeighbor(mask [][]bool, size, x, y int) bool {112 if x > 0 && mask[y][x-1] {113 return true114 }115 if x < size-1 && mask[y][x+1] {116 return true117 }118 if y > 0 && mask[y-1][x] {119 return true120 }121 if y < size-1 && mask[y+1][x] {122 return true123 }124 return false125}126127func requiresConnectivityCheck(mask [][]bool, size, x, y int) bool {128 neighbors := 0129 if x > 0 && !mask[y][x-1] {130 neighbors++131 }132 if x < size-1 && !mask[y][x+1] {133 neighbors++134 }135 if y > 0 && !mask[y-1][x] {136 neighbors++137 }138 if y < size-1 && !mask[y+1][x] {139 neighbors++140 }141 return neighbors > 1142}143144func whiteCellsConnected(mask [][]bool, size int) bool {145 startX, startY := -1, -1146 whiteCount := 0147 for y := range size {148 for x := range size {149 if !mask[y][x] {150 whiteCount++151 if startX == -1 {152 startX, startY = x, y153 }154 }155 }156 }157 if whiteCount <= 1 {158 return true159 }160161 visited := make([][]bool, size)162 for y := range size {163 visited[y] = make([]bool, size)164 }165166 queue := []cellPos{{startX, startY}}167 visited[startY][startX] = true168 visitedCount := 1169170 dirs := [4]cellPos{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}171 for len(queue) > 0 {172 curr := queue[0]173 queue = queue[1:]174175 for _, d := range dirs {176 nx, ny := curr.x+d.x, curr.y+d.y177 if nx >= 0 && nx < size && ny >= 0 && ny < size &&178 !visited[ny][nx] && !mask[ny][nx] {179 visited[ny][nx] = true180 visitedCount++181 queue = append(queue, cellPos{nx, ny})182 }183 }184 }185186 return visitedCount == whiteCount187}188189// constructPuzzleSeeded builds the initial puzzle grid from a Latin square and mask.190// White cells keep their original number. Black cells get a duplicate from191// a white cell in the same row.192func constructPuzzleSeeded(baseGrid grid, mask [][]bool, rng *rand.Rand) grid {193 size := len(baseGrid)194 puzzle := baseGrid.clone()195196 for y := range size {197 for x := range size {198 if !mask[y][x] {199 continue200 }201 // Collect white cell numbers in same row.202 var rowNums []rune203 for cx := range size {204 if cx != x && !mask[y][cx] {205 rowNums = append(rowNums, baseGrid[y][cx])206 }207 }208 if len(rowNums) > 0 {209 puzzle[y][x] = rowNums[rng.IntN(len(rowNums))]210 continue211 }212 // Fallback: column numbers.213 var colNums []rune214 for cy := range size {215 if cy != y && !mask[cy][x] {216 colNums = append(colNums, baseGrid[cy][x])217 }218 }219 if len(colNums) > 0 {220 puzzle[y][x] = colNums[rng.IntN(len(colNums))]221 }222 }223 }224 return puzzle225}226227// refinePuzzleSeeded tries different number assignments for black cells to achieve228// a unique solution. It iterates through each black cell trying all possible229// duplicate values, checking if the resulting puzzle has exactly one solution.230func refinePuzzleSeeded(puzzle grid, mask [][]bool, size int, rng *rand.Rand) (grid, bool) {231 // Collect black cell positions.232 var blackCells []cellPos233 for y := range size {234 for x := range size {235 if mask[y][x] {236 blackCells = append(blackCells, cellPos{x, y})237 }238 }239 }240241 if len(blackCells) == 0 {242 return puzzle, countPuzzleSolutions(puzzle, size, 2) == 1243 }244245 // Try to refine each black cell's value to reduce solution count.246 refined := puzzle.clone()247 currentCount := countPuzzleSolutions(refined, size, 3)248 for _, bc := range blackCells {249 // Collect candidate numbers for this black cell.250 candidates := cellCandidates(refined, mask, size, bc.x, bc.y)251 rankRefinementCandidates(refined, mask, size, bc.x, bc.y, candidates, rng)252253 best := refined[bc.y][bc.x]254 bestCount := currentCount255256 for _, num := range candidates {257 if num == best {258 continue259 }260 refined[bc.y][bc.x] = num261 c := countPuzzleSolutions(refined, size, 3)262 if c == 1 {263 return refined, true264 }265 if c > 0 && c < bestCount {266 best = num267 bestCount = c268 }269 }270 refined[bc.y][bc.x] = best271 currentCount = bestCount272273 if currentCount == 1 {274 return refined, true275 }276 }277278 return refined, countPuzzleSolutions(refined, size, 2) == 1279}280281func rankRefinementCandidates(282 puzzle grid,283 mask [][]bool,284 size, x, y int,285 candidates []rune,286 rng *rand.Rand,287) {288 if len(candidates) <= 1 {289 return290 }291292 rng.Shuffle(len(candidates), func(i, j int) {293 candidates[i], candidates[j] = candidates[j], candidates[i]294 })295296 for i := 1; i < len(candidates); i++ {297 key := candidates[i]298 keyScore := candidateConstraintScore(puzzle, mask, size, x, y, key)299 j := i - 1300 for ; j >= 0; j-- {301 score := candidateConstraintScore(puzzle, mask, size, x, y, candidates[j])302 if score >= keyScore {303 break304 }305 candidates[j+1] = candidates[j]306 }307 candidates[j+1] = key308 }309}310311func candidateConstraintScore(puzzle grid, mask [][]bool, size, x, y int, num rune) int {312 score := 0313 for cx := range size {314 if cx != x && !mask[y][cx] && puzzle[y][cx] == num {315 score++316 }317 }318 for cy := range size {319 if cy != y && !mask[cy][x] && puzzle[cy][x] == num {320 score++321 }322 }323 return score324}325326// cellCandidates returns all valid number choices for a black cell at (x,y):327// any number that appears among white cells in the same row or column.328func cellCandidates(puzzle grid, mask [][]bool, size, x, y int) []rune {329 seen := map[rune]bool{}330 for cx := range size {331 if cx != x && !mask[y][cx] {332 seen[puzzle[y][cx]] = true333 }334 }335 for cy := range size {336 if cy != y && !mask[cy][x] {337 seen[puzzle[cy][x]] = true338 }339 }340 result := make([]rune, 0, len(seen))341 for num := range seen {342 result = append(result, num)343 }344 return result345}346347// solverState is used during backtracking to track cell assignments.348type solverState int349350const (351 unknown solverState = iota352 white353 black354)355356func countPuzzleSolutions(puzzle grid, size, limit int) int {357 st := make([][]solverState, size)358 for y := range size {359 st[y] = make([]solverState, size)360 }361 order := rowMajorOrder(size)362 return solveBT(puzzle, st, order, 0, limit)363}364365func solveBT(366 puzzle grid,367 st [][]solverState,368 order []cellPos,369 pos, limit int,370) int {371 size := len(st)372 if pos == len(order) {373 marks := stateToMarks(st, size)374 if allWhiteConnected(marks, size) {375 return 1376 }377 return 0378 }379380 nextIdx := pickNextOrderIndex(puzzle, st, order, pos, size)381 order[pos], order[nextIdx] = order[nextIdx], order[pos]382383 x, y := order[pos].x, order[pos].y384 whiteOK := canBeWhite(puzzle, st, size, x, y)385 blackOK := canBeBlack(st, size, x, y)386 count := 0387388 if !whiteOK && !blackOK {389 order[pos], order[nextIdx] = order[nextIdx], order[pos]390 return 0391 }392393 if whiteOK {394 st[y][x] = white395 count += solveBT(puzzle, st, order, pos+1, limit-count)396 st[y][x] = unknown397 if count >= limit {398 order[pos], order[nextIdx] = order[nextIdx], order[pos]399 return count400 }401 }402403 if blackOK {404 st[y][x] = black405 count += solveBT(puzzle, st, order, pos+1, limit-count)406 st[y][x] = unknown407 if count >= limit {408 order[pos], order[nextIdx] = order[nextIdx], order[pos]409 return count410 }411 }412413 order[pos], order[nextIdx] = order[nextIdx], order[pos]414 return count415}416417func rowMajorOrder(size int) []cellPos {418 order := make([]cellPos, 0, size*size)419 for y := range size {420 for x := range size {421 order = append(order, cellPos{x, y})422 }423 }424 return order425}426427func pickNextOrderIndex(428 puzzle grid,429 st [][]solverState,430 order []cellPos,431 pos, size int,432) int {433 const lookaheadWindow = 2434435 end := pos + lookaheadWindow436 end = min(end, len(order))437438 for i := pos; i < end; i++ {439 x, y := order[i].x, order[i].y440 whiteOK := canBeWhite(puzzle, st, size, x, y)441 blackOK := canBeBlack(st, size, x, y)442443 options := 0444 if whiteOK {445 options++446 }447 if blackOK {448 options++449 }450 if options <= 1 {451 return i452 }453 }454455 return pos456}457458func canBeWhite(puzzle grid, st [][]solverState, size, x, y int) bool {459 num := puzzle[y][x]460 for i := range size {461 if i != x && st[y][i] == white && puzzle[y][i] == num {462 return false463 }464 }465 for i := range size {466 if i != y && st[i][x] == white && puzzle[i][x] == num {467 return false468 }469 }470 return true471}472473func canBeBlack(st [][]solverState, size, x, y int) bool {474 if x > 0 && st[y][x-1] == black {475 return false476 }477 if x < size-1 && st[y][x+1] == black {478 return false479 }480 if y > 0 && st[y-1][x] == black {481 return false482 }483 if y < size-1 && st[y+1][x] == black {484 return false485 }486 return true487}488489func stateToMarks(st [][]solverState, size int) [][]cellMark {490 marks := make([][]cellMark, size)491 for y := range size {492 marks[y] = make([]cellMark, size)493 for x := range size {494 if st[y][x] == black {495 marks[y][x] = shaded496 }497 }498 }499 return marks500}501502// Generate creates a Hitori puzzle of the given size. Returns the puzzle503// numbers grid or an error if generation fails after all attempts.504func Generate(size int, blackRatio float64) (grid, error) {505 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))506 return GenerateSeeded(size, blackRatio, rng)507}508509func GenerateSeeded(size int, blackRatio float64, rng *rand.Rand) (grid, error) {510 const maxAttempts = 200511512 for range maxAttempts {513 baseGrid := generateLatinSquareSeeded(size, rng)514 mask := generateValidMaskSeeded(size, blackRatio, rng)515 puzzle := constructPuzzleSeeded(baseGrid, mask, rng)516517 // First try the random construction.518 if countPuzzleSolutions(puzzle, size, 2) == 1 {519 return puzzle, nil520 }521522 // Refine by trying different values for black cells.523 refined, ok := refinePuzzleSeeded(puzzle, mask, size, rng)524 if ok {525 return refined, nil526 }527 }528529 return nil, errors.New("failed to generate hitori puzzle after max attempts")530}