1package rippleeffect23import "math"45type validationResult struct {6 solved bool7 conflicts [][]bool8}910func validateGridState(state grid, geo *geometry) validationResult {11 conflicts := newConflictGrid(geo.width, geo.height)12 complete := true1314 for cageIdx, cells := range geo.cageCells {15 size := geo.cageSizes[cageIdx]16 seen := make(map[int]point, size)17 for _, cell := range cells {18 value := state[cell.y][cell.x]19 if value == 0 {20 complete = false21 continue22 }23 if value < 1 || value > size {24 conflicts[cell.y][cell.x] = true25 continue26 }27 if prior, exists := seen[value]; exists {28 conflicts[cell.y][cell.x] = true29 conflicts[prior.y][prior.x] = true30 continue31 }32 seen[value] = cell33 }34 }3536 for y := range geo.height {37 for x := range geo.width {38 value := state[y][x]39 if value == 0 {40 continue41 }42 for step := 1; step < value; step++ {43 if x+step < geo.width && state[y][x+step] == value {44 conflicts[y][x] = true45 conflicts[y][x+step] = true46 }47 if y+step < geo.height && state[y+step][x] == value {48 conflicts[y][x] = true49 conflicts[y+step][x] = true50 }51 }52 }53 }5455 return validationResult{56 solved: complete && !hasConflicts(conflicts),57 conflicts: conflicts,58 }59}6061func newConflictGrid(width, height int) [][]bool {62 conflicts := make([][]bool, height)63 for y := range height {64 conflicts[y] = make([]bool, width)65 }66 return conflicts67}6869func hasConflicts(conflicts [][]bool) bool {70 for y := range len(conflicts) {71 for x := range len(conflicts[y]) {72 if conflicts[y][x] {73 return true74 }75 }76 }77 return false78}7980func countSolutions(geo *geometry, givens grid, limit int) int {81 working := cloneGrid(givens)82 return searchSolutions(geo, working, limit)83}8485func searchSolutions(geo *geometry, state grid, limit int) int {86 if limit <= 0 {87 return 088 }8990 cell, candidates, ok := chooseNextCell(geo, state)91 if !ok {92 if validateGridState(state, geo).solved {93 return 194 }95 return 096 }97 if len(candidates) == 0 {98 return 099 }100101 total := 0102 for _, value := range candidates {103 state[cell.y][cell.x] = value104 total += searchSolutions(geo, state, limit-total)105 if total >= limit {106 state[cell.y][cell.x] = 0107 return total108 }109 state[cell.y][cell.x] = 0110 }111112 return total113}114115func chooseNextCell(geo *geometry, state grid) (point, []int, bool) {116 best := point{}117 bestCandidates := []int(nil)118 bestCount := math.MaxInt119120 for y := range geo.height {121 for x := range geo.width {122 if state[y][x] != 0 {123 continue124 }125 cell := point{x: x, y: y}126 candidates := candidatesForCell(geo, state, cell)127 if len(candidates) < bestCount {128 best = cell129 bestCandidates = candidates130 bestCount = len(candidates)131 if bestCount <= 1 {132 return best, bestCandidates, true133 }134 }135 }136 }137138 if bestCount == math.MaxInt {139 return point{}, nil, false140 }141 return best, bestCandidates, true142}143144func candidatesForCell(geo *geometry, state grid, cell point) []int {145 cageIdx := geo.cageGrid[cell.y][cell.x]146 size := geo.cageSizes[cageIdx]147 candidates := make([]int, 0, size)148 for value := 1; value <= size; value++ {149 if valueAllowed(geo, state, cell, value) {150 candidates = append(candidates, value)151 }152 }153 return candidates154}155156func valueAllowed(geo *geometry, state grid, cell point, value int) bool {157 if value <= 0 {158 return false159 }160161 cageIdx := geo.cageGrid[cell.y][cell.x]162 if value > geo.cageSizes[cageIdx] {163 return false164 }165166 for _, other := range geo.cageCells[cageIdx] {167 if other == cell {168 continue169 }170 if state[other.y][other.x] == value {171 return false172 }173 }174175 for step := 1; step < value; step++ {176 if cell.x-step >= 0 && state[cell.y][cell.x-step] == value {177 return false178 }179 if cell.x+step < geo.width && state[cell.y][cell.x+step] == value {180 return false181 }182 if cell.y-step >= 0 && state[cell.y-step][cell.x] == value {183 return false184 }185 if cell.y+step < geo.height && state[cell.y+step][cell.x] == value {186 return false187 }188 }189190 return true191}