1package fillomino23import (4 "errors"5 "math"6)78var errInvalidGridEncoding = errors.New("invalid fillomino grid encoding")910type component struct {11 value int12 cells []point13 frontier map[point]struct{}14}1516type validationResult struct {17 solved bool18 conflicts [][]bool19}2021func validateGridState(g grid) validationResult {22 height := len(g)23 width := 024 if height > 0 {25 width = len(g[0])26 }2728 conflicts := make([][]bool, height)29 for y := range height {30 conflicts[y] = make([]bool, width)31 }3233 visited := make([][]bool, height)34 for y := range height {35 visited[y] = make([]bool, width)36 }3738 complete := true39 for y := range height {40 for x := range width {41 if g[y][x] == 0 {42 complete = false43 continue44 }45 if visited[y][x] {46 continue47 }4849 comp := buildComponent(g, point{x: x, y: y}, visited)50 markComponentConflicts(comp, complete, conflicts)51 }52 }5354 solved := complete && !hasConflicts(conflicts)55 return validationResult{56 solved: solved,57 conflicts: conflicts,58 }59}6061func hasConflicts(conflicts [][]bool) bool {62 for y := range len(conflicts) {63 for x := range len(conflicts[y]) {64 if conflicts[y][x] {65 return true66 }67 }68 }69 return false70}7172func buildComponent(g grid, start point, visited [][]bool) component {73 value := g[start.y][start.x]74 queue := []point{start}75 visited[start.y][start.x] = true76 comp := component{77 value: value,78 frontier: make(map[point]struct{}),79 }8081 for len(queue) > 0 {82 curr := queue[0]83 queue = queue[1:]84 comp.cells = append(comp.cells, curr)8586 for _, next := range orthogonalNeighbors(curr, len(g[0]), len(g)) {87 switch {88 case g[next.y][next.x] == value && !visited[next.y][next.x]:89 visited[next.y][next.x] = true90 queue = append(queue, next)91 case g[next.y][next.x] == 0:92 comp.frontier[next] = struct{}{}93 }94 }95 }9697 return comp98}99100func markComponentConflicts(comp component, assumeComplete bool, conflicts [][]bool) {101 size := len(comp.cells)102 value := comp.value103 if value <= 0 {104 for _, cell := range comp.cells {105 conflicts[cell.y][cell.x] = true106 }107 return108 }109110 if size > value || size+len(comp.frontier) < value {111 for _, cell := range comp.cells {112 conflicts[cell.y][cell.x] = true113 }114 for cell := range comp.frontier {115 conflicts[cell.y][cell.x] = true116 }117 return118 }119120 if assumeComplete && size != value {121 for _, cell := range comp.cells {122 conflicts[cell.y][cell.x] = true123 }124 }125}126127func orthogonalNeighbors(p point, width, height int) []point {128 neighbors := make([]point, 0, 4)129 if p.x > 0 {130 neighbors = append(neighbors, point{x: p.x - 1, y: p.y})131 }132 if p.x+1 < width {133 neighbors = append(neighbors, point{x: p.x + 1, y: p.y})134 }135 if p.y > 0 {136 neighbors = append(neighbors, point{x: p.x, y: p.y - 1})137 }138 if p.y+1 < height {139 neighbors = append(neighbors, point{x: p.x, y: p.y + 1})140 }141 return neighbors142}143144func countSolutions(givens grid, maxValue, limit int) int {145 working := cloneGrid(givens)146 return searchSolutions(working, maxValue, limit)147}148149func searchSolutions(g grid, maxValue, limit int) int {150 if limit <= 0 {151 return 0152 }153 if !isPartialGridValid(g) {154 return 0155 }156157 cell, candidates, ok := chooseNextCell(g, maxValue)158 if !ok {159 if validateGridState(g).solved {160 return 1161 }162 return 0163 }164165 total := 0166 for _, value := range candidates {167 g[cell.y][cell.x] = value168 total += searchSolutions(g, maxValue, limit-total)169 if total >= limit {170 g[cell.y][cell.x] = 0171 return total172 }173 g[cell.y][cell.x] = 0174 }175 return total176}177178func chooseNextCell(g grid, maxValue int) (point, []int, bool) {179 best := point{}180 bestCandidates := []int(nil)181 bestCount := math.MaxInt182183 for y := range len(g) {184 for x := range len(g[y]) {185 if g[y][x] != 0 {186 continue187 }188189 candidates := candidatesForCell(g, point{x: x, y: y}, maxValue)190 if len(candidates) == 0 {191 return point{x: x, y: y}, nil, true192 }193 if len(candidates) < bestCount {194 best = point{x: x, y: y}195 bestCandidates = candidates196 bestCount = len(candidates)197 if bestCount == 1 {198 return best, bestCandidates, true199 }200 }201 }202 }203204 if bestCount == math.MaxInt {205 return point{}, nil, false206 }207 return best, bestCandidates, true208}209210func candidatesForCell(g grid, cell point, maxValue int) []int {211 candidates := make([]int, 0, maxValue)212 for value := 1; value <= maxValue; value++ {213 g[cell.y][cell.x] = value214 if isPartialGridValid(g) {215 candidates = append(candidates, value)216 }217 g[cell.y][cell.x] = 0218 }219 return candidates220}221222func isPartialGridValid(g grid) bool {223 height := len(g)224 if height == 0 {225 return true226 }227 width := len(g[0])228229 visited := make([][]bool, height)230 for y := range height {231 visited[y] = make([]bool, width)232 }233234 for y := range height {235 for x := range width {236 if g[y][x] == 0 || visited[y][x] {237 continue238 }239240 comp := buildComponent(g, point{x: x, y: y}, visited)241 size := len(comp.cells)242 if size > comp.value {243 return false244 }245 if size+len(comp.frontier) < comp.value {246 return false247 }248 if len(comp.frontier) == 0 && size != comp.value {249 return false250 }251 }252 }253254 return true255}