1package sudoku23import "math/rand/v2"45const allDigitsMask uint16 = 0x3FE67type solverMasks struct {8 row [gridSize]uint169 col [gridSize]uint1610 box [gridSize]uint1611}1213// newRNG creates a fresh non-deterministic RNG.14func newRNG() *rand.Rand {15 return rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))16}1718func valueBit(val int) uint16 {19 return uint16(1 << val)20}2122func boxIndex(x, y int) int {23 return (y/3)*3 + (x / 3)24}2526func buildMasks(g *grid) (solverMasks, bool) {27 var masks solverMasks28 for y := range gridSize {29 for x := range gridSize {30 val := g[y][x].v31 if val == 0 {32 continue33 }34 if val < 0 || val > gridSize {35 return solverMasks{}, false36 }3738 bit := valueBit(val)39 box := boxIndex(x, y)40 if masks.row[y]&bit != 0 || masks.col[x]&bit != 0 || masks.box[box]&bit != 0 {41 return solverMasks{}, false42 }4344 masks.row[y] |= bit45 masks.col[x] |= bit46 masks.box[box] |= bit47 }48 }49 return masks, true50}5152func canPlace(masks *solverMasks, val, x, y int) bool {53 bit := valueBit(val)54 box := boxIndex(x, y)55 return masks.row[y]&bit == 0 && masks.col[x]&bit == 0 && masks.box[box]&bit == 056}5758func placeValue(g *grid, masks *solverMasks, val, x, y int) {59 bit := valueBit(val)60 box := boxIndex(x, y)61 g[y][x].v = val62 masks.row[y] |= bit63 masks.col[x] |= bit64 masks.box[box] |= bit65}6667func clearValue(g *grid, masks *solverMasks, val, x, y int) {68 bit := valueBit(val)69 box := boxIndex(x, y)70 g[y][x].v = 071 masks.row[y] &^= bit72 masks.col[x] &^= bit73 masks.box[box] &^= bit74}7576func candidatesForCell(masks *solverMasks, x, y int) uint16 {77 used := masks.row[y] | masks.col[x] | masks.box[boxIndex(x, y)]78 return allDigitsMask &^ used79}8081func findFirstEmptyCell(g *grid) (x, y int, found bool) {82 for y := range gridSize {83 for x := range gridSize {84 if g[y][x].v == 0 {85 return x, y, true86 }87 }88 }89 return 0, 0, false90}9192func fillGridRec(g *grid, rng *rand.Rand, masks *solverMasks) bool {93 x, y, found := findFirstEmptyCell(g)94 if !found {95 return true96 }9798 order := rng.Perm(gridSize)99 for _, i := range order {100 val := i + 1101 if !canPlace(masks, val, x, y) {102 continue103 }104105 placeValue(g, masks, val, x, y)106 if fillGridRec(g, rng, masks) {107 return true108 }109 clearValue(g, masks, val, x, y)110 }111112 return false113}114115func countCandidateBits(mask uint16) int {116 count := 0117 for val := 1; val <= gridSize; val++ {118 if mask&valueBit(val) != 0 {119 count++120 }121 }122 return count123}124125func findMostConstrainedEmptyCell(g *grid, masks *solverMasks) (x, y int, candidates uint16, found bool) {126 bestCount := gridSize + 1127 bestX, bestY := 0, 0128 for y := range gridSize {129 for x := range gridSize {130 if g[y][x].v != 0 {131 continue132 }133134 mask := candidatesForCell(masks, x, y)135 candidateCount := countCandidateBits(mask)136 if candidateCount == 0 {137 return x, y, 0, true138 }139140 if !found || candidateCount < bestCount {141 bestCount = candidateCount142 candidates = mask143 bestX, bestY = x, y144 found = true145 }146 if bestCount == 1 {147 return bestX, bestY, candidates, true148 }149 }150 }151152 return bestX, bestY, candidates, found153}154155// isValid checks whether placing val at (x, y) in the grid is valid.156func isValid(g *grid, val, x, y int) bool {157 for i := range gridSize {158 if i != x && g[y][i].v == val {159 return false160 }161 if i != y && g[i][x].v == val {162 return false163 }164 }165 boxX, boxY := (x/3)*3, (y/3)*3166 for by := boxY; by < boxY+3; by++ {167 for bx := boxX; bx < boxX+3; bx++ {168 if (bx != x || by != y) && g[by][bx].v == val {169 return false170 }171 }172 }173 return true174}175176// fillGrid fills an empty grid with a random valid sudoku solution using backtracking.177func fillGrid(g *grid) bool {178 rng := newRNG()179 return fillGridSeeded(g, rng)180}181182func fillGridSeeded(g *grid, rng *rand.Rand) bool {183 masks, ok := buildMasks(g)184 if !ok {185 return false186 }187 return fillGridRec(g, rng, &masks)188}189190// countSolutions counts solutions of the grid up to limit using backtracking.191// Returns 0 immediately if the grid already contains conflicting values.192func countSolutions(g *grid, limit int) int {193 if limit <= 0 {194 return 0195 }196197 masks, ok := buildMasks(g)198 if !ok {199 return 0200 }201 return countSolutionsRec(g, limit, &masks)202}203204// countSolutionsRec is the recursive backtracking helper for countSolutions.205func countSolutionsRec(g *grid, limit int, masks *solverMasks) int {206 if limit <= 0 {207 return 0208 }209210 x, y, candidateMask, found := findMostConstrainedEmptyCell(g, masks)211 if !found {212 return 1213 }214 if candidateMask == 0 {215 return 0216 }217218 count := 0219 for val := 1; val <= gridSize; val++ {220 bit := valueBit(val)221 if candidateMask&bit == 0 {222 continue223 }224225 placeValue(g, masks, val, x, y)226 count += countSolutionsRec(g, limit-count, masks)227 clearValue(g, masks, val, x, y)228 if count >= limit {229 return count230 }231 }232 return count233}234235// GenerateProvidedCells generates a random sudoku puzzle with the number of236// provided cells determined by the mode's ProvidedCount.237func GenerateProvidedCells(m SudokuMode) []cell {238 return GenerateProvidedCellsSeeded(m, newRNG())239}240241type pos struct{ x, y int }242243func clueRemovalScore(g *grid, x, y int) int {244 score := 0245 for i := range gridSize {246 if i != x && g[y][i].v == 0 {247 score++248 }249 if i != y && g[i][x].v == 0 {250 score++251 }252 }253254 boxX, boxY := (x/3)*3, (y/3)*3255 for by := boxY; by < boxY+3; by++ {256 for bx := boxX; bx < boxX+3; bx++ {257 if (bx != x || by != y) && g[by][bx].v == 0 {258 score++259 }260 }261 }262263 return score264}265266func pickRemovalCandidateIndex(g *grid, positions []pos, rng *rand.Rand) int {267 bestIndex := 0268 bestScore := clueRemovalScore(g, positions[0].x, positions[0].y)269 for i := 1; i < len(positions); i++ {270 score := clueRemovalScore(g, positions[i].x, positions[i].y)271 if score < bestScore || (score == bestScore && rng.IntN(2) == 0) {272 bestScore = score273 bestIndex = i274 }275 }276 return bestIndex277}278279func GenerateProvidedCellsSeeded(m SudokuMode, rng *rand.Rand) []cell {280 g := newGrid(nil)281 fillGridSeeded(&g, rng)282283 // Build shuffled list of all positions284 positions := make([]pos, 0, gridSize*gridSize)285 for y := range gridSize {286 for x := range gridSize {287 positions = append(positions, pos{x, y})288 }289 }290 rng.Shuffle(len(positions), func(i, j int) {291 positions[i], positions[j] = positions[j], positions[i]292 })293294 // Iteratively remove cells in low-impact-first order while preserving uniqueness.295 filled := gridSize * gridSize296 for len(positions) > 0 && filled > m.ProvidedCount {297 idx := pickRemovalCandidateIndex(&g, positions, rng)298 p := positions[idx]299 positions[idx] = positions[len(positions)-1]300 positions = positions[:len(positions)-1]301302 saved := g[p.y][p.x].v303 g[p.y][p.x].v = 0304 if countSolutions(&g, 2) != 1 {305 g[p.y][p.x].v = saved306 } else {307 filled--308 }309 }310311 // Collect remaining filled cells as provided hints312 var cells []cell313 for y := range gridSize {314 for x := range gridSize {315 if g[y][x].v != 0 {316 cells = append(cells, g[y][x])317 }318 }319 }320 return cells321}