1package rippleeffect23import (4 "fmt"5 "math/rand/v2"6)78type Puzzle struct {9 Width int10 Height int11 Cages []Cage12 Givens grid13 Solution grid14}1516type shapeBias int1718const (19 shapeBiasNeutral shapeBias = iota20 shapeBiasCompact21 shapeBiasWinding22)2324type generationProfile struct {25 cageWeights []int26 frontierSamples int27 shapeBias shapeBias28 minGivensByCage []int29}3031func GeneratePuzzle(width, height, maxCage int, givenRatio float64) (Puzzle, error) {32 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))33 return GeneratePuzzleSeeded(width, height, maxCage, givenRatio, rng)34}3536func GeneratePuzzleSeeded(width, height, maxCage int, givenRatio float64, rng *rand.Rand) (Puzzle, error) {37 return generatePuzzleSeededWithProfile(width, height, maxCage, givenRatio, defaultGenerationProfile(maxCage), rng)38}3940func generatePuzzleSeededWithProfile(width, height, maxCage int, givenRatio float64, profile generationProfile, rng *rand.Rand) (Puzzle, error) {41 const maxAttempts = 2442 profile = profile.withDefaults(maxCage)43 for range maxAttempts {44 cages := generateCages(width, height, maxCage, profile, rng)45 geo, err := buildGeometry(width, height, cages)46 if err != nil {47 continue48 }4950 solution, ok := generateSolution(geo, rng)51 if !ok {52 continue53 }5455 givens := removeClues(geo, solution, givenRatio, profile, rng)56 if countSolutions(geo, givens, 2) != 1 {57 continue58 }5960 return Puzzle{61 Width: width,62 Height: height,63 Cages: cages,64 Givens: givens,65 Solution: solution,66 }, nil67 }6869 return Puzzle{}, fmt.Errorf("generate ripple effect puzzle %dx%d: exceeded retry budget", width, height)70}7172func defaultGenerationProfile(maxCage int) generationProfile {73 return generationProfile{74 cageWeights: defaultCageWeights(maxCage),75 frontierSamples: 1,76 shapeBias: shapeBiasNeutral,77 minGivensByCage: make([]int, maxCage+1),78 }79}8081func defaultCageWeights(maxCage int) []int {82 base := []int{0, 2, 4, 5, 4, 3, 2, 1, 1, 1}83 weights := make([]int, maxCage+1)84 for size := range len(weights) {85 if size == 0 {86 continue87 }88 weights[size] = base[min(size, len(base)-1)]89 }90 return weights91}9293func (p generationProfile) withDefaults(maxCage int) generationProfile {94 if len(p.cageWeights) == 0 {95 p.cageWeights = defaultCageWeights(maxCage)96 }97 if p.frontierSamples <= 0 {98 p.frontierSamples = 199 }100 if len(p.minGivensByCage) == 0 {101 p.minGivensByCage = make([]int, maxCage+1)102 }103 if len(p.minGivensByCage) <= maxCage {104 p.minGivensByCage = growIntSlice(p.minGivensByCage, maxCage+1)105 }106 return p107}108109func growIntSlice(values []int, size int) []int {110 grown := make([]int, size)111 copy(grown, values)112 return grown113}114115func generateCages(width, height, maxCage int, profile generationProfile, rng *rand.Rand) []Cage {116 assigned := make([][]bool, height)117 for y := range height {118 assigned[y] = make([]bool, width)119 }120121 cages := make([]Cage, 0, width*height/2)122 for {123 start, ok := firstUnassigned(assigned)124 if !ok {125 return cages126 }127128 target := chooseCageSize(maxCage, remainingUnassigned(assigned), profile.cageWeights, rng)129 shape := growCageShape(start, target, assigned, profile, rng)130 for _, cell := range shape {131 assigned[cell.y][cell.x] = true132 }133134 cells := make([]Cell, len(shape))135 for i, cell := range shape {136 cells[i] = Cell{X: cell.x, Y: cell.y}137 }138 cages = append(cages, Cage{139 ID: len(cages),140 Size: len(cells),141 Cells: cells,142 })143 }144}145146func firstUnassigned(assigned [][]bool) (point, bool) {147 for y := range len(assigned) {148 for x := range len(assigned[y]) {149 if !assigned[y][x] {150 return point{x: x, y: y}, true151 }152 }153 }154 return point{}, false155}156157func remainingUnassigned(assigned [][]bool) int {158 count := 0159 for y := range len(assigned) {160 for x := range len(assigned[y]) {161 if !assigned[y][x] {162 count++163 }164 }165 }166 return count167}168169func chooseCageSize(maxCage, remaining int, weights []int, rng *rand.Rand) int {170 if remaining < maxCage {171 maxCage = remaining172 }173 totalWeight := 0174 for size := 1; size <= maxCage; size++ {175 totalWeight += weights[min(size, len(weights)-1)]176 }177 if totalWeight == 0 {178 return 1179 }180181 pick := rng.IntN(totalWeight)182 for size := 1; size <= maxCage; size++ {183 pick -= weights[min(size, len(weights)-1)]184 if pick < 0 {185 return size186 }187 }188 return 1189}190191func growCageShape(start point, target int, assigned [][]bool, profile generationProfile, rng *rand.Rand) []point {192 shape := []point{start}193 inShape := map[point]struct{}{start: {}}194 height := len(assigned)195 width := len(assigned[0])196197 for len(shape) < target {198 frontier := make([]point, 0, 4)199 seen := make(map[point]struct{})200 for _, cell := range shape {201 for _, next := range orthogonalNeighbors(cell, width, height) {202 if assigned[next.y][next.x] {203 continue204 }205 if _, ok := inShape[next]; ok {206 continue207 }208 if _, ok := seen[next]; ok {209 continue210 }211 frontier = append(frontier, next)212 seen[next] = struct{}{}213 }214 }215 if len(frontier) == 0 {216 break217 }218 next := chooseFrontierPoint(frontier, inShape, assigned, profile, rng)219 shape = append(shape, next)220 inShape[next] = struct{}{}221 }222223 return shape224}225226func chooseFrontierPoint(frontier []point, inShape map[point]struct{}, assigned [][]bool, profile generationProfile, rng *rand.Rand) point {227 if len(frontier) == 1 || profile.shapeBias == shapeBiasNeutral {228 return frontier[rng.IntN(len(frontier))]229 }230231 sampleCount := min(profile.frontierSamples, len(frontier))232 best := frontier[rng.IntN(len(frontier))]233 bestScore := frontierScore(best, inShape, assigned)234235 for pick := 1; pick < sampleCount; pick++ {236 candidate := frontier[rng.IntN(len(frontier))]237 score := frontierScore(candidate, inShape, assigned)238 if prefersFrontierScore(profile.shapeBias, score, bestScore) {239 best = candidate240 bestScore = score241 }242 }243244 return best245}246247func frontierScore(candidate point, inShape map[point]struct{}, assigned [][]bool) int {248 score := 0249 for _, neighbor := range orthogonalNeighbors(candidate, len(assigned[0]), len(assigned)) {250 if assigned[neighbor.y][neighbor.x] {251 continue252 }253 if _, ok := inShape[neighbor]; ok {254 score++255 }256 }257 return score258}259260func prefersFrontierScore(bias shapeBias, candidate, current int) bool {261 switch bias {262 case shapeBiasCompact:263 return candidate > current264 case shapeBiasWinding:265 return candidate < current266 default:267 return false268 }269}270271func generateSolution(geo *geometry, rng *rand.Rand) (grid, bool) {272 state := newGrid(geo.width, geo.height)273 if fillSolution(geo, state, rng) {274 return state, true275 }276 return nil, false277}278279func fillSolution(geo *geometry, state grid, rng *rand.Rand) bool {280 cell, candidates, ok := chooseNextFillCell(geo, state, rng)281 if !ok {282 return true283 }284 if len(candidates) == 0 {285 return false286 }287288 for _, value := range candidates {289 state[cell.y][cell.x] = value290 if fillSolution(geo, state, rng) {291 return true292 }293 state[cell.y][cell.x] = 0294 }295296 return false297}298299func chooseNextFillCell(geo *geometry, state grid, rng *rand.Rand) (point, []int, bool) {300 best := point{}301 bestCandidates := []int(nil)302 bestCount := 10303 ties := 0304305 for y := range geo.height {306 for x := range geo.width {307 if state[y][x] != 0 {308 continue309 }310 cell := point{x: x, y: y}311 candidates := candidatesForCell(geo, state, cell)312 if len(candidates) < bestCount {313 best = cell314 bestCandidates = candidates315 bestCount = len(candidates)316 ties = 1317 continue318 }319 if len(candidates) == bestCount {320 ties++321 if rng.IntN(ties) == 0 {322 best = cell323 bestCandidates = candidates324 }325 }326 }327 }328329 if bestCount == 10 {330 return point{}, nil, false331 }332333 rng.Shuffle(len(bestCandidates), func(i, j int) {334 bestCandidates[i], bestCandidates[j] = bestCandidates[j], bestCandidates[i]335 })336 return best, bestCandidates, true337}338339func removeClues(geo *geometry, solution grid, givenRatio float64, profile generationProfile, rng *rand.Rand) grid {340 givens := cloneGrid(solution)341 totalCells := geo.width * geo.height342 target := int(float64(totalCells) * givenRatio)343344 remainingByCage := make([]int, len(geo.cages))345 minimumByCage := make([]int, len(geo.cages))346 minimumTotal := 0347 for cageIdx, cells := range geo.cageCells {348 remainingByCage[cageIdx] = len(cells)349 minimumByCage[cageIdx] = minGivensForCage(profile, len(cells))350 minimumTotal += minimumByCage[cageIdx]351 }352353 if target < minimumTotal {354 target = minimumTotal355 }356357 cells := make([]point, 0, totalCells)358 for y := range geo.height {359 for x := range geo.width {360 cells = append(cells, point{x: x, y: y})361 }362 }363 rng.Shuffle(len(cells), func(i, j int) {364 cells[i], cells[j] = cells[j], cells[i]365 })366367 remaining := totalCells368 for _, cell := range cells {369 if remaining <= target {370 break371 }372373 cageIdx := geo.cageGrid[cell.y][cell.x]374 if remainingByCage[cageIdx] <= minimumByCage[cageIdx] {375 continue376 }377378 value := givens[cell.y][cell.x]379 givens[cell.y][cell.x] = 0380 remainingByCage[cageIdx]--381 if countSolutions(geo, givens, 2) != 1 {382 givens[cell.y][cell.x] = value383 remainingByCage[cageIdx]++384 continue385 }386 remaining--387 }388389 return givens390}391392func minGivensForCage(profile generationProfile, cageSize int) int {393 if cageSize <= 0 {394 return 0395 }396 if cageSize >= len(profile.minGivensByCage) {397 return max(1, profile.minGivensByCage[len(profile.minGivensByCage)-1])398 }399 return max(1, min(profile.minGivensByCage[cageSize], cageSize))400}