1package fillomino23import (4 "fmt"5 "math/rand/v2"6)78type Puzzle struct {9 Width int10 Height int11 Givens grid12 Solution grid13}1415type region struct {16 cells []point17 size int18}1920func GeneratePuzzle(width, height, maxRegion int, givenRatio float64) (Puzzle, error) {21 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))22 return GeneratePuzzleSeeded(width, height, maxRegion, givenRatio, rng)23}2425func GeneratePuzzleSeeded(width, height, maxRegion int, givenRatio float64, rng *rand.Rand) (Puzzle, error) {26 const maxAttempts = 1227 for range maxAttempts {28 solution, _, err := generateSolution(width, height, maxRegion, rng)29 if err != nil {30 continue31 }3233 givens := buildStartingGivens(solution)34 givens = removeClues(givens, maxRegion, givenRatio, rng)35 if countSolutions(givens, maxRegion, 2) != 1 {36 continue37 }3839 return Puzzle{40 Width: width,41 Height: height,42 Givens: givens,43 Solution: solution,44 }, nil45 }4647 return Puzzle{}, fmt.Errorf("generate fillomino puzzle %dx%d: exceeded retry budget", width, height)48}4950func generateSolution(width, height, maxRegion int, rng *rand.Rand) (grid, []region, error) {51 assigned := newGrid(width, height)52 used := make([][]bool, height)53 for y := range height {54 used[y] = make([]bool, width)55 }5657 regions := make([]region, 0, width*height/2)58 if !fillRegions(assigned, used, ®ions, maxRegion, rng) {59 return nil, nil, fmt.Errorf("unable to fill solved grid")60 }61 return assigned, regions, nil62}6364func fillRegions(solution grid, used [][]bool, regions *[]region, maxRegion int, rng *rand.Rand) bool {65 start, ok := firstUnused(used)66 if !ok {67 return true68 }6970 candidates := rectangleCandidates(used, start, maxRegion, rng)71 for _, candidate := range candidates {72 if touchesEqualRegion(solution, candidate.cells, candidate.size) {73 continue74 }7576 applyShape(solution, used, candidate.cells, candidate.size, true)77 *regions = append(*regions, candidate)78 if fillRegions(solution, used, regions, maxRegion, rng) {79 return true80 }81 *regions = (*regions)[:len(*regions)-1]82 applyShape(solution, used, candidate.cells, candidate.size, false)83 }8485 return false86}8788func firstUnused(used [][]bool) (point, bool) {89 for y := range len(used) {90 for x := range len(used[y]) {91 if !used[y][x] {92 return point{x: x, y: y}, true93 }94 }95 }96 return point{}, false97}9899func rectangleCandidates(used [][]bool, start point, maxRegion int, rng *rand.Rand) []region {100 height := len(used)101 width := len(used[0])102103 var candidates []region104 for h := 1; start.y+h <= height; h++ {105 for w := 1; start.x+w <= width; w++ {106 size := w * h107 if size > maxRegion {108 break109 }110 cells := make([]point, 0, size)111 valid := true112 for y := start.y; y < start.y+h && valid; y++ {113 for x := start.x; x < start.x+w; x++ {114 if used[y][x] {115 valid = false116 break117 }118 cells = append(cells, point{x: x, y: y})119 }120 }121 if !valid {122 continue123 }124 candidates = append(candidates, region{cells: cells, size: size})125 }126 }127 rng.Shuffle(len(candidates), func(i, j int) {128 candidates[i], candidates[j] = candidates[j], candidates[i]129 })130 return candidates131}132133func touchesEqualRegion(solution grid, shape []point, size int) bool {134 shapeCells := make(map[point]struct{}, len(shape))135 for _, cell := range shape {136 shapeCells[cell] = struct{}{}137 }138139 for _, cell := range shape {140 for _, next := range orthogonalNeighbors(cell, len(solution[0]), len(solution)) {141 if _, ok := shapeCells[next]; ok {142 continue143 }144 if solution[next.y][next.x] == size {145 return true146 }147 }148 }149150 return false151}152153func applyShape(solution grid, used [][]bool, shape []point, size int, place bool) {154 value := 0155 if place {156 value = size157 }158 for _, cell := range shape {159 used[cell.y][cell.x] = place160 solution[cell.y][cell.x] = value161 }162}163164func buildStartingGivens(solution grid) grid {165 return cloneGrid(solution)166}167168func removeClues(givens grid, maxRegion int, givenRatio float64, rng *rand.Rand) grid {169 width := len(givens[0])170 height := len(givens)171 target := int(float64(width*height) * givenRatio)172 target = max(target, 1)173174 cells := make([]point, 0, width*height)175 for y := range height {176 for x := range width {177 if givens[y][x] != 0 {178 cells = append(cells, point{x: x, y: y})179 }180 }181 }182 rng.Shuffle(len(cells), func(i, j int) {183 cells[i], cells[j] = cells[j], cells[i]184 })185186 remaining := len(cells)187 for _, cell := range cells {188 if remaining <= target {189 break190 }191 value := givens[cell.y][cell.x]192 givens[cell.y][cell.x] = 0193 if countSolutions(givens, maxRegion, 2) != 1 {194 givens[cell.y][cell.x] = value195 continue196 }197 remaining--198 }199 return givens200}