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 maxSingletonCages int30}3132func GeneratePuzzle(width, height, maxCage int, givenRatio float64) (Puzzle, error) {33 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))34 return GeneratePuzzleSeeded(width, height, maxCage, givenRatio, rng)35}3637func GeneratePuzzleSeeded(width, height, maxCage int, givenRatio float64, rng *rand.Rand) (Puzzle, error) {38 return generatePuzzleSeededWithProfile(width, height, maxCage, givenRatio, defaultGenerationProfile(maxCage), rng)39}4041func generatePuzzleSeededWithProfile(width, height, maxCage int, givenRatio float64, profile generationProfile, rng *rand.Rand) (Puzzle, error) {42 const maxAttempts = 4843 profile = profile.withDefaults(maxCage)44 for range maxAttempts {45 cages := generateCages(width, height, maxCage, profile, rng)46 cages = normalizeSingletonCages(width, height, maxCage, cages, profile, rng)47 geo, err := buildGeometry(width, height, cages)48 if err != nil {49 continue50 }5152 solution, ok := generateSolution(geo, rng)53 if !ok {54 continue55 }5657 givens := removeClues(geo, solution, givenRatio, profile, rng)58 if countSolutions(geo, givens, 2) != 1 {59 continue60 }61 if hasOversizeCage(cages, maxCage) {62 continue63 }64 if profile.maxSingletonCages >= 0 && countSingletonCages(cages) > profile.maxSingletonCages {65 continue66 }6768 return Puzzle{69 Width: width,70 Height: height,71 Cages: cages,72 Givens: givens,73 Solution: solution,74 }, nil75 }7677 return Puzzle{}, fmt.Errorf("generate ripple effect puzzle %dx%d: exceeded retry budget", width, height)78}7980func defaultGenerationProfile(maxCage int) generationProfile {81 return generationProfile{82 cageWeights: defaultCageWeights(maxCage),83 frontierSamples: 1,84 shapeBias: shapeBiasNeutral,85 minGivensByCage: make([]int, maxCage+1),86 maxSingletonCages: -1,87 }88}8990func defaultCageWeights(maxCage int) []int {91 base := []int{0, 2, 4, 5, 4, 3, 2, 1, 1, 1}92 weights := make([]int, maxCage+1)93 for size := range len(weights) {94 if size == 0 {95 continue96 }97 weights[size] = base[min(size, len(base)-1)]98 }99 return weights100}101102func (p generationProfile) withDefaults(maxCage int) generationProfile {103 if len(p.cageWeights) == 0 {104 p.cageWeights = defaultCageWeights(maxCage)105 }106 if p.frontierSamples <= 0 {107 p.frontierSamples = 1108 }109 if len(p.minGivensByCage) == 0 {110 p.minGivensByCage = make([]int, maxCage+1)111 }112 if len(p.minGivensByCage) <= maxCage {113 p.minGivensByCage = growIntSlice(p.minGivensByCage, maxCage+1)114 }115 return p116}117118func growIntSlice(values []int, size int) []int {119 grown := make([]int, size)120 copy(grown, values)121 return grown122}123124func normalizeSingletonCages(width, height, maxCage int, cages []Cage, profile generationProfile, rng *rand.Rand) []Cage {125 if profile.maxSingletonCages < 0 {126 return cages127 }128129 normalized := append([]Cage(nil), cages...)130 for countSingletonCages(normalized) > profile.maxSingletonCages {131 singletons := singletonCageIndices(normalized)132 if len(singletons) == 0 {133 break134 }135 singletonIdx := singletons[rng.IntN(len(singletons))]136 targetIdx, ok := chooseSingletonMergeTarget(width, height, maxCage, normalized, singletonIdx, rng)137 if !ok {138 break139 }140141 cell := normalized[singletonIdx].Cells[0]142 normalized[targetIdx].Cells = append(normalized[targetIdx].Cells, cell)143 normalized[targetIdx].Size = len(normalized[targetIdx].Cells)144 normalized = append(normalized[:singletonIdx], normalized[singletonIdx+1:]...)145 }146147 return renumberCages(normalized)148}149150func hasOversizeCage(cages []Cage, maxCage int) bool {151 for _, cage := range cages {152 if len(cage.Cells) > maxCage {153 return true154 }155 }156 return false157}158159func countSingletonCages(cages []Cage) int {160 count := 0161 for _, cage := range cages {162 if len(cage.Cells) == 1 {163 count++164 }165 }166 return count167}168169func singletonCageIndices(cages []Cage) []int {170 indices := make([]int, 0)171 for idx, cage := range cages {172 if len(cage.Cells) == 1 {173 indices = append(indices, idx)174 }175 }176 return indices177}178179func chooseSingletonMergeTarget(width, height, maxCage int, cages []Cage, singletonIdx int, rng *rand.Rand) (int, bool) {180 singleton := cages[singletonIdx]181 if len(singleton.Cells) != 1 {182 return 0, false183 }184185 cageGrid := buildCageIndexGrid(width, height, cages)186 cell := singleton.Cells[0]187 neighbors := make([]int, 0, 4)188 seen := make(map[int]struct{}, 4)189 for _, next := range orthogonalNeighbors(point{x: cell.X, y: cell.Y}, width, height) {190 cageIdx := cageGrid[next.y][next.x]191 if cageIdx < 0 || cageIdx == singletonIdx {192 continue193 }194 if _, exists := seen[cageIdx]; exists {195 continue196 }197 seen[cageIdx] = struct{}{}198 neighbors = append(neighbors, cageIdx)199 }200 if len(neighbors) == 0 {201 return 0, false202 }203204 allowed := make([]int, 0, len(neighbors))205 for _, idx := range neighbors {206 if len(cages[idx].Cells)+1 <= maxCage {207 allowed = append(allowed, idx)208 }209 }210 if len(allowed) > 0 {211 neighbors = allowed212 }213214 minSize := len(cages[neighbors[0]].Cells)215 best := make([]int, 0, len(neighbors))216 for _, idx := range neighbors {217 size := len(cages[idx].Cells)218 if size < minSize {219 minSize = size220 best = best[:0]221 }222 if size == minSize {223 best = append(best, idx)224 }225 }226227 return best[rng.IntN(len(best))], true228}229230func buildCageIndexGrid(width, height int, cages []Cage) [][]int {231 grid := make([][]int, height)232 for y := range height {233 grid[y] = make([]int, width)234 for x := range width {235 grid[y][x] = -1236 }237 }238239 for cageIdx, cage := range cages {240 for _, cell := range cage.Cells {241 grid[cell.Y][cell.X] = cageIdx242 }243 }244245 return grid246}247248func renumberCages(cages []Cage) []Cage {249 renumbered := make([]Cage, len(cages))250 for idx, cage := range cages {251 renumbered[idx] = Cage{252 ID: idx,253 Size: len(cage.Cells),254 Cells: append([]Cell(nil), cage.Cells...),255 }256 }257 return renumbered258}259260func generateCages(width, height, maxCage int, profile generationProfile, rng *rand.Rand) []Cage {261 assigned := make([][]bool, height)262 for y := range height {263 assigned[y] = make([]bool, width)264 }265266 cages := make([]Cage, 0, width*height/2)267 for {268 start, ok := firstUnassigned(assigned)269 if !ok {270 return cages271 }272273 target := chooseCageSize(maxCage, remainingUnassigned(assigned), profile.cageWeights, rng)274 shape := growCageShape(start, target, assigned, profile, rng)275 for _, cell := range shape {276 assigned[cell.y][cell.x] = true277 }278279 cells := make([]Cell, len(shape))280 for i, cell := range shape {281 cells[i] = Cell{X: cell.x, Y: cell.y}282 }283 cages = append(cages, Cage{284 ID: len(cages),285 Size: len(cells),286 Cells: cells,287 })288 }289}290291func firstUnassigned(assigned [][]bool) (point, bool) {292 for y := range len(assigned) {293 for x := range len(assigned[y]) {294 if !assigned[y][x] {295 return point{x: x, y: y}, true296 }297 }298 }299 return point{}, false300}301302func remainingUnassigned(assigned [][]bool) int {303 count := 0304 for y := range len(assigned) {305 for x := range len(assigned[y]) {306 if !assigned[y][x] {307 count++308 }309 }310 }311 return count312}313314func chooseCageSize(maxCage, remaining int, weights []int, rng *rand.Rand) int {315 if remaining < maxCage {316 maxCage = remaining317 }318 totalWeight := 0319 for size := 1; size <= maxCage; size++ {320 totalWeight += weights[min(size, len(weights)-1)]321 }322 if totalWeight == 0 {323 return 1324 }325326 pick := rng.IntN(totalWeight)327 for size := 1; size <= maxCage; size++ {328 pick -= weights[min(size, len(weights)-1)]329 if pick < 0 {330 return size331 }332 }333 return 1334}335336func growCageShape(start point, target int, assigned [][]bool, profile generationProfile, rng *rand.Rand) []point {337 shape := []point{start}338 inShape := map[point]struct{}{start: {}}339 height := len(assigned)340 width := len(assigned[0])341342 for len(shape) < target {343 frontier := make([]point, 0, 4)344 seen := make(map[point]struct{})345 for _, cell := range shape {346 for _, next := range orthogonalNeighbors(cell, width, height) {347 if assigned[next.y][next.x] {348 continue349 }350 if _, ok := inShape[next]; ok {351 continue352 }353 if _, ok := seen[next]; ok {354 continue355 }356 frontier = append(frontier, next)357 seen[next] = struct{}{}358 }359 }360 if len(frontier) == 0 {361 break362 }363 next := chooseFrontierPoint(frontier, inShape, assigned, profile, rng)364 shape = append(shape, next)365 inShape[next] = struct{}{}366 }367368 return shape369}370371func chooseFrontierPoint(frontier []point, inShape map[point]struct{}, assigned [][]bool, profile generationProfile, rng *rand.Rand) point {372 if len(frontier) == 1 || profile.shapeBias == shapeBiasNeutral {373 return frontier[rng.IntN(len(frontier))]374 }375376 sampleCount := min(profile.frontierSamples, len(frontier))377 best := frontier[rng.IntN(len(frontier))]378 bestScore := frontierScore(best, inShape, assigned)379380 for pick := 1; pick < sampleCount; pick++ {381 candidate := frontier[rng.IntN(len(frontier))]382 score := frontierScore(candidate, inShape, assigned)383 if prefersFrontierScore(profile.shapeBias, score, bestScore) {384 best = candidate385 bestScore = score386 }387 }388389 return best390}391392func frontierScore(candidate point, inShape map[point]struct{}, assigned [][]bool) int {393 score := 0394 for _, neighbor := range orthogonalNeighbors(candidate, len(assigned[0]), len(assigned)) {395 if assigned[neighbor.y][neighbor.x] {396 continue397 }398 if _, ok := inShape[neighbor]; ok {399 score++400 }401 }402 return score403}404405func prefersFrontierScore(bias shapeBias, candidate, current int) bool {406 switch bias {407 case shapeBiasCompact:408 return candidate > current409 case shapeBiasWinding:410 return candidate < current411 default:412 return false413 }414}415416func generateSolution(geo *geometry, rng *rand.Rand) (grid, bool) {417 state := newGrid(geo.width, geo.height)418 if fillSolution(geo, state, rng) {419 return state, true420 }421 return nil, false422}423424func fillSolution(geo *geometry, state grid, rng *rand.Rand) bool {425 cell, candidates, ok := chooseNextFillCell(geo, state, rng)426 if !ok {427 return true428 }429 if len(candidates) == 0 {430 return false431 }432433 for _, value := range candidates {434 state[cell.y][cell.x] = value435 if fillSolution(geo, state, rng) {436 return true437 }438 state[cell.y][cell.x] = 0439 }440441 return false442}443444func chooseNextFillCell(geo *geometry, state grid, rng *rand.Rand) (point, []int, bool) {445 best := point{}446 bestCandidates := []int(nil)447 bestCount := 10448 ties := 0449450 for y := range geo.height {451 for x := range geo.width {452 if state[y][x] != 0 {453 continue454 }455 cell := point{x: x, y: y}456 candidates := candidatesForCell(geo, state, cell)457 if len(candidates) < bestCount {458 best = cell459 bestCandidates = candidates460 bestCount = len(candidates)461 ties = 1462 continue463 }464 if len(candidates) == bestCount {465 ties++466 if rng.IntN(ties) == 0 {467 best = cell468 bestCandidates = candidates469 }470 }471 }472 }473474 if bestCount == 10 {475 return point{}, nil, false476 }477478 rng.Shuffle(len(bestCandidates), func(i, j int) {479 bestCandidates[i], bestCandidates[j] = bestCandidates[j], bestCandidates[i]480 })481 return best, bestCandidates, true482}483484func removeClues(geo *geometry, solution grid, givenRatio float64, profile generationProfile, rng *rand.Rand) grid {485 givens := cloneGrid(solution)486 totalCells := geo.width * geo.height487 target := int(float64(totalCells) * givenRatio)488489 remainingByCage := make([]int, len(geo.cages))490 minimumByCage := make([]int, len(geo.cages))491 minimumTotal := 0492 for cageIdx, cells := range geo.cageCells {493 remainingByCage[cageIdx] = len(cells)494 minimumByCage[cageIdx] = minGivensForCage(profile, len(cells))495 minimumTotal += minimumByCage[cageIdx]496 }497498 if target < minimumTotal {499 target = minimumTotal500 }501502 cells := make([]point, 0, totalCells)503 for y := range geo.height {504 for x := range geo.width {505 cells = append(cells, point{x: x, y: y})506 }507 }508 rng.Shuffle(len(cells), func(i, j int) {509 cells[i], cells[j] = cells[j], cells[i]510 })511512 remaining := totalCells513 for _, cell := range cells {514 if remaining <= target {515 break516 }517518 cageIdx := geo.cageGrid[cell.y][cell.x]519 if remainingByCage[cageIdx] <= minimumByCage[cageIdx] {520 continue521 }522523 value := givens[cell.y][cell.x]524 givens[cell.y][cell.x] = 0525 remainingByCage[cageIdx]--526 if countSolutions(geo, givens, 2) != 1 {527 givens[cell.y][cell.x] = value528 remainingByCage[cageIdx]++529 continue530 }531 remaining--532 }533534 return givens535}536537func minGivensForCage(profile generationProfile, cageSize int) int {538 if cageSize <= 0 {539 return 0540 }541 if cageSize >= len(profile.minGivensByCage) {542 return max(0, min(profile.minGivensByCage[len(profile.minGivensByCage)-1], cageSize))543 }544 return max(0, min(profile.minGivensByCage[cageSize], cageSize))545}