1package rippleeffect23import (4 "context"5 "math"6)78type validationResult struct {9 solved bool10 conflicts [][]bool11}1213func validateGridState(state grid, geo *geometry) validationResult {14 conflicts := newConflictGrid(geo.width, geo.height)15 complete := true1617 for cageIdx, cells := range geo.cageCells {18 size := geo.cageSizes[cageIdx]19 seen := make(map[int]point, size)20 for _, cell := range cells {21 value := state[cell.y][cell.x]22 if value == 0 {23 complete = false24 continue25 }26 if value < 1 || value > size {27 conflicts[cell.y][cell.x] = true28 continue29 }30 if prior, exists := seen[value]; exists {31 conflicts[cell.y][cell.x] = true32 conflicts[prior.y][prior.x] = true33 continue34 }35 seen[value] = cell36 }37 }3839 for y := range geo.height {40 for x := range geo.width {41 value := state[y][x]42 if value == 0 {43 continue44 }45 for step := 1; step < value; step++ {46 if x+step < geo.width && state[y][x+step] == value {47 conflicts[y][x] = true48 conflicts[y][x+step] = true49 }50 if y+step < geo.height && state[y+step][x] == value {51 conflicts[y][x] = true52 conflicts[y+step][x] = true53 }54 }55 }56 }5758 return validationResult{59 solved: complete && !hasConflicts(conflicts),60 conflicts: conflicts,61 }62}6364func newConflictGrid(width, height int) [][]bool {65 conflicts := make([][]bool, height)66 for y := range height {67 conflicts[y] = make([]bool, width)68 }69 return conflicts70}7172func hasConflicts(conflicts [][]bool) bool {73 for y := range len(conflicts) {74 for x := range len(conflicts[y]) {75 if conflicts[y][x] {76 return true77 }78 }79 }80 return false81}8283func countSolutions(geo *geometry, givens grid, limit int) int {84 return countSolutionsContext(context.Background(), geo, givens, limit)85}8687func countSolutionsContext(ctx context.Context, geo *geometry, givens grid, limit int) int {88 working := cloneGrid(givens)89 return searchSolutionsContext(ctx, geo, working, limit)90}9192func searchSolutionsContext(ctx context.Context, geo *geometry, state grid, limit int) int {93 if limit <= 0 {94 return 095 }96 if ctx.Err() != nil {97 return -198 }99100 cell, candidates, ok := chooseNextCell(geo, state)101 if !ok {102 if validateGridState(state, geo).solved {103 return 1104 }105 return 0106 }107 if len(candidates) == 0 {108 return 0109 }110111 total := 0112 for _, value := range candidates {113 state[cell.y][cell.x] = value114 n := searchSolutionsContext(ctx, geo, state, limit-total)115 if n < 0 {116 state[cell.y][cell.x] = 0117 return n118 }119 total += n120 if total >= limit {121 state[cell.y][cell.x] = 0122 return total123 }124 state[cell.y][cell.x] = 0125 }126127 return total128}129130func chooseNextCell(geo *geometry, state grid) (point, []int, bool) {131 best := point{}132 bestCandidates := []int(nil)133 bestCount := math.MaxInt134135 for y := range geo.height {136 for x := range geo.width {137 if state[y][x] != 0 {138 continue139 }140 cell := point{x: x, y: y}141 candidates := candidatesForCell(geo, state, cell)142 if len(candidates) < bestCount {143 best = cell144 bestCandidates = candidates145 bestCount = len(candidates)146 if bestCount <= 1 {147 return best, bestCandidates, true148 }149 }150 }151 }152153 if bestCount == math.MaxInt {154 return point{}, nil, false155 }156 return best, bestCandidates, true157}158159func candidatesForCell(geo *geometry, state grid, cell point) []int {160 cageIdx := geo.cageGrid[cell.y][cell.x]161 size := geo.cageSizes[cageIdx]162 candidates := make([]int, 0, size)163 for value := 1; value <= size; value++ {164 if valueAllowed(geo, state, cell, value) {165 candidates = append(candidates, value)166 }167 }168 return candidates169}170171func valueAllowed(geo *geometry, state grid, cell point, value int) bool {172 if value <= 0 {173 return false174 }175176 cageIdx := geo.cageGrid[cell.y][cell.x]177 if value > geo.cageSizes[cageIdx] {178 return false179 }180181 for _, other := range geo.cageCells[cageIdx] {182 if other == cell {183 continue184 }185 if state[other.y][other.x] == value {186 return false187 }188 }189190 for step := 1; step < value; step++ {191 if cell.x-step >= 0 && state[cell.y][cell.x-step] == value {192 return false193 }194 if cell.x+step < geo.width && state[cell.y][cell.x+step] == value {195 return false196 }197 if cell.y-step >= 0 && state[cell.y-step][cell.x] == value {198 return false199 }200 if cell.y+step < geo.height && state[cell.y+step][cell.x] == value {201 return false202 }203 }204205 return true206}