1package hitori23import (4 "context"5 "errors"6 "math/rand/v2"7 "sort"8)910type cellPos struct{ x, y int }1112// generateLatinSquare creates an NxN grid where each number 1..N appears13// exactly once in each row and column. Uses cyclic shifts with row and14// column shuffling.15func generateLatinSquare(size int) grid {16 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))17 return generateLatinSquareSeeded(size, rng)18}1920func generateLatinSquareSeeded(size int, rng *rand.Rand) grid {21 firstRow := make([]rune, size)22 for i := range size {23 firstRow[i] = rune('1' + i)24 }25 rng.Shuffle(len(firstRow), func(i, j int) {26 firstRow[i], firstRow[j] = firstRow[j], firstRow[i]27 })2829 g := make(grid, size)30 for y := range size {31 g[y] = make([]rune, size)32 for x := range size {33 g[y][x] = firstRow[(x+y)%size]34 }35 }3637 cols := make([]int, size)38 for i := range size {39 cols[i] = i40 }41 rng.Shuffle(len(cols), func(i, j int) {42 cols[i], cols[j] = cols[j], cols[i]43 })4445 rowOrder := make([]int, size)46 for i := range size {47 rowOrder[i] = i48 }49 rng.Shuffle(len(rowOrder), func(i, j int) {50 rowOrder[i], rowOrder[j] = rowOrder[j], rowOrder[i]51 })5253 result := make(grid, size)54 for y := range size {55 result[y] = make([]rune, size)56 for x := range size {57 result[y][x] = g[rowOrder[y]][cols[x]]58 }59 }6061 return result62}6364// generateValidMask determines which cells should be black. The mask65// satisfies: no adjacent black cells, and all white cells connected.66func generateValidMask(size int, blackRatio float64) [][]bool {67 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))68 return generateValidMaskSeeded(size, blackRatio, rng)69}7071func generateValidMaskSeeded(size int, blackRatio float64, rng *rand.Rand) [][]bool {72 mask := make([][]bool, size)73 for y := range size {74 mask[y] = make([]bool, size)75 }7677 targetBlack := int(blackRatio * float64(size*size))7879 positions := make([]cellPos, 0, size*size)80 for y := range size {81 for x := range size {82 positions = append(positions, cellPos{x, y})83 }84 }85 rng.Shuffle(len(positions), func(i, j int) {86 positions[i], positions[j] = positions[j], positions[i]87 })8889 blackCount := 090 for _, p := range positions {91 if blackCount >= targetBlack {92 break93 }9495 if hasOrthogonalNeighbor(mask, size, p.x, p.y) {96 continue97 }9899 mask[p.y][p.x] = true100101 if requiresConnectivityCheck(mask, size, p.x, p.y) &&102 !whiteCellsConnected(mask, size) {103 mask[p.y][p.x] = false104 continue105 }106107 blackCount++108 }109110 return mask111}112113func hasOrthogonalNeighbor(mask [][]bool, size, x, y int) bool {114 if x > 0 && mask[y][x-1] {115 return true116 }117 if x < size-1 && mask[y][x+1] {118 return true119 }120 if y > 0 && mask[y-1][x] {121 return true122 }123 if y < size-1 && mask[y+1][x] {124 return true125 }126 return false127}128129func requiresConnectivityCheck(mask [][]bool, size, x, y int) bool {130 neighbors := 0131 if x > 0 && !mask[y][x-1] {132 neighbors++133 }134 if x < size-1 && !mask[y][x+1] {135 neighbors++136 }137 if y > 0 && !mask[y-1][x] {138 neighbors++139 }140 if y < size-1 && !mask[y+1][x] {141 neighbors++142 }143 return neighbors > 1144}145146func whiteCellsConnected(mask [][]bool, size int) bool {147 startX, startY := -1, -1148 whiteCount := 0149 for y := range size {150 for x := range size {151 if !mask[y][x] {152 whiteCount++153 if startX == -1 {154 startX, startY = x, y155 }156 }157 }158 }159 if whiteCount <= 1 {160 return true161 }162163 visited := make([][]bool, size)164 for y := range size {165 visited[y] = make([]bool, size)166 }167168 queue := []cellPos{{startX, startY}}169 visited[startY][startX] = true170 visitedCount := 1171172 dirs := [4]cellPos{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}173 for len(queue) > 0 {174 curr := queue[0]175 queue = queue[1:]176177 for _, d := range dirs {178 nx, ny := curr.x+d.x, curr.y+d.y179 if nx >= 0 && nx < size && ny >= 0 && ny < size &&180 !visited[ny][nx] && !mask[ny][nx] {181 visited[ny][nx] = true182 visitedCount++183 queue = append(queue, cellPos{nx, ny})184 }185 }186 }187188 return visitedCount == whiteCount189}190191// constructPuzzleSeeded builds the initial puzzle grid from a Latin square and mask.192// White cells keep their original number. Black cells get a duplicate from193// a white cell in the same row.194func constructPuzzleSeeded(baseGrid grid, mask [][]bool, rng *rand.Rand) grid {195 size := len(baseGrid)196 puzzle := baseGrid.clone()197198 for y := range size {199 for x := range size {200 if !mask[y][x] {201 continue202 }203 // Collect white cell numbers in same row.204 var rowNums []rune205 for cx := range size {206 if cx != x && !mask[y][cx] {207 rowNums = append(rowNums, baseGrid[y][cx])208 }209 }210 if len(rowNums) > 0 {211 puzzle[y][x] = rowNums[rng.IntN(len(rowNums))]212 continue213 }214 // Fallback: column numbers.215 var colNums []rune216 for cy := range size {217 if cy != y && !mask[cy][x] {218 colNums = append(colNums, baseGrid[cy][x])219 }220 }221 if len(colNums) > 0 {222 puzzle[y][x] = colNums[rng.IntN(len(colNums))]223 }224 }225 }226 return puzzle227}228229func refinePuzzleSeededContext(ctx context.Context, puzzle grid, mask [][]bool, size int, rng *rand.Rand) (grid, bool) {230 // Collect black cell positions.231 var blackCells []cellPos232 for y := range size {233 for x := range size {234 if mask[y][x] {235 blackCells = append(blackCells, cellPos{x, y})236 }237 }238 }239240 if len(blackCells) == 0 {241 return puzzle, countPuzzleSolutionsContext(ctx, puzzle, size, 2) == 1242 }243244 // Try to refine each black cell's value to reduce solution count.245 refined := puzzle.clone()246 currentCount := countPuzzleSolutionsContext(ctx, refined, size, 3)247 for _, bc := range blackCells {248 if ctx.Err() != nil {249 return refined, false250 }251 // Collect candidate numbers for this black cell.252 candidates := cellCandidates(refined, mask, size, bc.x, bc.y)253 rankRefinementCandidates(refined, mask, size, bc.x, bc.y, candidates, rng)254255 best := refined[bc.y][bc.x]256 bestCount := currentCount257258 for _, num := range candidates {259 if num == best {260 continue261 }262 refined[bc.y][bc.x] = num263 c := countPuzzleSolutionsContext(ctx, refined, size, 3)264 if c == 1 {265 return refined, true266 }267 if c > 0 && c < bestCount {268 best = num269 bestCount = c270 }271 }272 refined[bc.y][bc.x] = best273 currentCount = bestCount274275 if currentCount == 1 {276 return refined, true277 }278 }279280 return refined, countPuzzleSolutionsContext(ctx, refined, size, 2) == 1281}282283func rankRefinementCandidates(284 puzzle grid,285 mask [][]bool,286 size, x, y int,287 candidates []rune,288 rng *rand.Rand,289) {290 if len(candidates) <= 1 {291 return292 }293294 rng.Shuffle(len(candidates), func(i, j int) {295 candidates[i], candidates[j] = candidates[j], candidates[i]296 })297298 for i := 1; i < len(candidates); i++ {299 key := candidates[i]300 keyScore := candidateConstraintScore(puzzle, mask, size, x, y, key)301 j := i - 1302 for ; j >= 0; j-- {303 score := candidateConstraintScore(puzzle, mask, size, x, y, candidates[j])304 if score >= keyScore {305 break306 }307 candidates[j+1] = candidates[j]308 }309 candidates[j+1] = key310 }311}312313func candidateConstraintScore(puzzle grid, mask [][]bool, size, x, y int, num rune) int {314 score := 0315 for cx := range size {316 if cx != x && !mask[y][cx] && puzzle[y][cx] == num {317 score++318 }319 }320 for cy := range size {321 if cy != y && !mask[cy][x] && puzzle[cy][x] == num {322 score++323 }324 }325 return score326}327328// cellCandidates returns all valid number choices for a black cell at (x,y):329// any number that appears among white cells in the same row or column.330func cellCandidates(puzzle grid, mask [][]bool, size, x, y int) []rune {331 seen := map[rune]bool{}332 for cx := range size {333 if cx != x && !mask[y][cx] {334 seen[puzzle[y][cx]] = true335 }336 }337 for cy := range size {338 if cy != y && !mask[cy][x] {339 seen[puzzle[cy][x]] = true340 }341 }342 result := make([]rune, 0, len(seen))343 for num := range seen {344 result = append(result, num)345 }346 sort.Slice(result, func(i, j int) bool {347 return result[i] < result[j]348 })349 return result350}351352// solverState is used during backtracking to track cell assignments.353type solverState int354355const (356 unknown solverState = iota357 white358 black359)360361func countPuzzleSolutions(puzzle grid, size, limit int) int {362 return countPuzzleSolutionsContext(context.Background(), puzzle, size, limit)363}364365func countPuzzleSolutionsContext(ctx context.Context, puzzle grid, size, limit int) int {366 st := make([][]solverState, size)367 for y := range size {368 st[y] = make([]solverState, size)369 }370 order := rowMajorOrder(size)371 return solveBTContext(ctx, puzzle, st, order, 0, limit)372}373374func solveBTContext(375 ctx context.Context,376 puzzle grid,377 st [][]solverState,378 order []cellPos,379 pos, limit int,380) int {381 if ctx.Err() != nil {382 return -1383 }384 size := len(st)385 if pos == len(order) {386 marks := stateToMarks(st, size)387 if allWhiteConnected(marks, size) {388 return 1389 }390 return 0391 }392393 nextIdx := pickNextOrderIndex(puzzle, st, order, pos, size)394 order[pos], order[nextIdx] = order[nextIdx], order[pos]395396 x, y := order[pos].x, order[pos].y397 whiteOK := canBeWhite(puzzle, st, size, x, y)398 blackOK := canBeBlack(st, size, x, y)399 count := 0400401 if !whiteOK && !blackOK {402 order[pos], order[nextIdx] = order[nextIdx], order[pos]403 return 0404 }405406 if whiteOK {407 st[y][x] = white408 n := solveBTContext(ctx, puzzle, st, order, pos+1, limit-count)409 st[y][x] = unknown410 if n < 0 {411 order[pos], order[nextIdx] = order[nextIdx], order[pos]412 return n413 }414 count += n415 if count >= limit {416 order[pos], order[nextIdx] = order[nextIdx], order[pos]417 return count418 }419 }420421 if blackOK {422 st[y][x] = black423 n := solveBTContext(ctx, puzzle, st, order, pos+1, limit-count)424 st[y][x] = unknown425 if n < 0 {426 order[pos], order[nextIdx] = order[nextIdx], order[pos]427 return n428 }429 count += n430 if count >= limit {431 order[pos], order[nextIdx] = order[nextIdx], order[pos]432 return count433 }434 }435436 order[pos], order[nextIdx] = order[nextIdx], order[pos]437 return count438}439440func rowMajorOrder(size int) []cellPos {441 order := make([]cellPos, 0, size*size)442 for y := range size {443 for x := range size {444 order = append(order, cellPos{x, y})445 }446 }447 return order448}449450func pickNextOrderIndex(451 puzzle grid,452 st [][]solverState,453 order []cellPos,454 pos, size int,455) int {456 const lookaheadWindow = 2457458 end := pos + lookaheadWindow459 end = min(end, len(order))460461 for i := pos; i < end; i++ {462 x, y := order[i].x, order[i].y463 whiteOK := canBeWhite(puzzle, st, size, x, y)464 blackOK := canBeBlack(st, size, x, y)465466 options := 0467 if whiteOK {468 options++469 }470 if blackOK {471 options++472 }473 if options <= 1 {474 return i475 }476 }477478 return pos479}480481func canBeWhite(puzzle grid, st [][]solverState, size, x, y int) bool {482 num := puzzle[y][x]483 for i := range size {484 if i != x && st[y][i] == white && puzzle[y][i] == num {485 return false486 }487 }488 for i := range size {489 if i != y && st[i][x] == white && puzzle[i][x] == num {490 return false491 }492 }493 return true494}495496func canBeBlack(st [][]solverState, size, x, y int) bool {497 if x > 0 && st[y][x-1] == black {498 return false499 }500 if x < size-1 && st[y][x+1] == black {501 return false502 }503 if y > 0 && st[y-1][x] == black {504 return false505 }506 if y < size-1 && st[y+1][x] == black {507 return false508 }509 return true510}511512func stateToMarks(st [][]solverState, size int) [][]cellMark {513 marks := make([][]cellMark, size)514 for y := range size {515 marks[y] = make([]cellMark, size)516 for x := range size {517 if st[y][x] == black {518 marks[y][x] = shaded519 }520 }521 }522 return marks523}524525// Generate creates a Hitori puzzle of the given size. Returns the puzzle526// numbers grid or an error if generation fails after all attempts.527func Generate(size int, blackRatio float64) (grid, error) {528 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))529 return GenerateSeeded(size, blackRatio, rng)530}531532func GenerateSeeded(size int, blackRatio float64, rng *rand.Rand) (grid, error) {533 return GenerateSeededContext(context.Background(), size, blackRatio, rng)534}535536func GenerateSeededContext(ctx context.Context, size int, blackRatio float64, rng *rand.Rand) (grid, error) {537 const maxAttempts = 200538539 for range maxAttempts {540 if err := ctx.Err(); err != nil {541 return nil, err542 }543 baseGrid := generateLatinSquareSeeded(size, rng)544 mask := generateValidMaskSeeded(size, blackRatio, rng)545 puzzle := constructPuzzleSeeded(baseGrid, mask, rng)546547 // First try the random construction.548 if countPuzzleSolutionsContext(ctx, puzzle, size, 2) == 1 {549 return puzzle, nil550 }551552 // Refine by trying different values for black cells.553 refined, ok := refinePuzzleSeededContext(ctx, puzzle, mask, size, rng)554 if ok {555 return refined, nil556 }557 }558559 return nil, errors.New("failed to generate hitori puzzle after max attempts")560}