1package sudokurgb23import "math/rand/v2"45type quotaState struct {6 row [gridSize][valueCount + 1]uint87 col [gridSize][valueCount + 1]uint88 box [gridSize][valueCount + 1]uint89}1011type pos struct{ x, y int }1213func newRNG() *rand.Rand {14 return rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))15}1617func boxIndex(x, y int) int {18 return (y/3)*3 + (x / 3)19}2021func buildQuotaState(g *grid) (quotaState, bool) {22 var state quotaState23 for i := range gridSize {24 for value := 1; value <= valueCount; value++ {25 state.row[i][value] = houseQuota26 state.col[i][value] = houseQuota27 state.box[i][value] = houseQuota28 }29 }3031 for y := range gridSize {32 for x := range gridSize {33 value := g[y][x].v34 if value == 0 {35 continue36 }37 if value < 1 || value > valueCount {38 return quotaState{}, false39 }4041 box := boxIndex(x, y)42 if state.row[y][value] == 0 || state.col[x][value] == 0 || state.box[box][value] == 0 {43 return quotaState{}, false44 }4546 state.row[y][value]--47 state.col[x][value]--48 state.box[box][value]--49 }50 }5152 return state, true53}5455func canPlace(state *quotaState, value, x, y int) bool {56 box := boxIndex(x, y)57 return state.row[y][value] > 0 && state.col[x][value] > 0 && state.box[box][value] > 058}5960func placeValue(g *grid, state *quotaState, value, x, y int) {61 box := boxIndex(x, y)62 g[y][x].v = value63 state.row[y][value]--64 state.col[x][value]--65 state.box[box][value]--66}6768func clearValue(g *grid, state *quotaState, value, x, y int) {69 box := boxIndex(x, y)70 g[y][x].v = 071 state.row[y][value]++72 state.col[x][value]++73 state.box[box][value]++74}7576func candidateMaskForCell(state *quotaState, x, y int) uint8 {77 var mask uint878 for value := 1; value <= valueCount; value++ {79 if canPlace(state, value, x, y) {80 mask |= 1 << value81 }82 }83 return mask84}8586func countCandidateBits(mask uint8) int {87 count := 088 for value := 1; value <= valueCount; value++ {89 if mask&(1<<value) != 0 {90 count++91 }92 }93 return count94}9596func findMostConstrainedEmptyCell(g *grid, state *quotaState) (x, y int, candidates uint8, found bool) {97 bestCount := valueCount + 198 bestX, bestY := 0, 099 for y := range gridSize {100 for x := range gridSize {101 if g[y][x].v != 0 {102 continue103 }104105 mask := candidateMaskForCell(state, x, y)106 candidateCount := countCandidateBits(mask)107 if candidateCount == 0 {108 return x, y, 0, true109 }110 if !found || candidateCount < bestCount {111 found = true112 bestCount = candidateCount113 bestX, bestY = x, y114 candidates = mask115 if candidateCount == 1 {116 return bestX, bestY, candidates, true117 }118 }119 }120 }121 return bestX, bestY, candidates, found122}123124func randomCandidateOrder(mask uint8, rng *rand.Rand) []int {125 values := make([]int, 0, valueCount)126 for value := 1; value <= valueCount; value++ {127 if mask&(1<<value) != 0 {128 values = append(values, value)129 }130 }131 rng.Shuffle(len(values), func(i, j int) {132 values[i], values[j] = values[j], values[i]133 })134 return values135}136137func fillGridRec(g *grid, rng *rand.Rand, state *quotaState) bool {138 x, y, candidates, found := findMostConstrainedEmptyCell(g, state)139 if !found {140 return true141 }142 if candidates == 0 {143 return false144 }145146 for _, value := range randomCandidateOrder(candidates, rng) {147 placeValue(g, state, value, x, y)148 if fillGridRec(g, rng, state) {149 return true150 }151 clearValue(g, state, value, x, y)152 }153154 return false155}156157func fillGridSeeded(g *grid, rng *rand.Rand) bool {158 state, ok := buildQuotaState(g)159 if !ok {160 return false161 }162 return fillGridRec(g, rng, &state)163}164165func countSolutions(g *grid, limit int) int {166 if limit <= 0 {167 return 0168 }169170 state, ok := buildQuotaState(g)171 if !ok {172 return 0173 }174 return countSolutionsRec(g, limit, &state)175}176177func countSolutionsRec(g *grid, limit int, state *quotaState) int {178 if limit <= 0 {179 return 0180 }181182 x, y, candidates, found := findMostConstrainedEmptyCell(g, state)183 if !found {184 return 1185 }186 if candidates == 0 {187 return 0188 }189190 count := 0191 for value := 1; value <= valueCount; value++ {192 if candidates&(1<<value) == 0 {193 continue194 }195 placeValue(g, state, value, x, y)196 count += countSolutionsRec(g, limit-count, state)197 clearValue(g, state, value, x, y)198 if count >= limit {199 return count200 }201 }202 return count203}204205func GenerateProvidedCells(mode SudokuRGBMode) []cell {206 return GenerateProvidedCellsSeeded(mode, newRNG())207}208209func clueRemovalScore(g *grid, x, y int) int {210 score := 0211 for i := range gridSize {212 if i != x && g[y][i].v == 0 {213 score++214 }215 if i != y && g[i][x].v == 0 {216 score++217 }218 }219220 boxX, boxY := (x/3)*3, (y/3)*3221 for dy := range 3 {222 for dx := range 3 {223 cx, cy := boxX+dx, boxY+dy224 if (cx != x || cy != y) && g[cy][cx].v == 0 {225 score++226 }227 }228 }229 return score230}231232func pickRemovalCandidateIndex(g *grid, positions []pos, rng *rand.Rand) int {233 bestIndex := 0234 bestScore := clueRemovalScore(g, positions[0].x, positions[0].y)235 for i := 1; i < len(positions); i++ {236 score := clueRemovalScore(g, positions[i].x, positions[i].y)237 if score < bestScore || (score == bestScore && rng.IntN(2) == 0) {238 bestScore = score239 bestIndex = i240 }241 }242 return bestIndex243}244245func collectFilledCells(g *grid) []cell {246 cells := make([]cell, 0, gridSize*gridSize)247 for y := range gridSize {248 for x := range gridSize {249 if g[y][x].v != 0 {250 cells = append(cells, g[y][x])251 }252 }253 }254 return cells255}256257func GenerateProvidedCellsSeeded(mode SudokuRGBMode, rng *rand.Rand) []cell {258 bestCells := []cell{}259 bestCount := gridSize*gridSize + 1260261 for range 96 {262 g := newGrid(nil)263 if !fillGridSeeded(&g, rng) {264 continue265 }266267 positions := make([]pos, 0, gridSize*gridSize)268 for y := range gridSize {269 for x := range gridSize {270 positions = append(positions, pos{x: x, y: y})271 }272 }273 rng.Shuffle(len(positions), func(i, j int) {274 positions[i], positions[j] = positions[j], positions[i]275 })276277 filled := gridSize * gridSize278 for len(positions) > 0 && filled > mode.ProvidedCount {279 idx := pickRemovalCandidateIndex(&g, positions, rng)280 p := positions[idx]281 positions[idx] = positions[len(positions)-1]282 positions = positions[:len(positions)-1]283284 saved := g[p.y][p.x].v285 g[p.y][p.x].v = 0286 if countSolutions(&g, 2) != 1 {287 g[p.y][p.x].v = saved288 continue289 }290 filled--291 }292293 cells := collectFilledCells(&g)294 if len(cells) == mode.ProvidedCount {295 return cells296 }297 if len(cells) < bestCount {298 bestCount = len(cells)299 bestCells = cells300 }301 }302303 return bestCells304}