1package shikaku23import (4 "errors"5 "math/rand/v2"6)78const maxGenerateAttempts = 100910// genRect is used during generation to track grid partitions.11type genRect struct {12 x, y, w, h int13}1415type dim struct {16 w, h int17}1819type templateCacheKey struct {20 x, y int21 maxW int22 maxH int23 maxArea int24}2526type failedStateKey struct {27 x, y int28 maxW int29 maxH int30 remaining int31}3233type partitionSearchState struct {34 templateCache map[templateCacheKey][]dim35 failedStates map[failedStateKey]bool36}3738// GeneratePuzzle creates a Shikaku puzzle with random RNG.39func GeneratePuzzle(width, height, maxRectSize int) (Puzzle, error) {40 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))41 return GeneratePuzzleSeeded(width, height, maxRectSize, rng)42}4344// GeneratePuzzleSeeded creates a Shikaku puzzle with a deterministic RNG.45func GeneratePuzzleSeeded(width, height, maxRectSize int, rng *rand.Rand) (Puzzle, error) {46 for range maxGenerateAttempts {47 p := tryGenerate(width, height, maxRectSize, rng)48 if p != nil {49 return *p, nil50 }51 }52 return Puzzle{}, errors.New("failed to generate shikaku puzzle after maximum attempts")53}5455func tryGenerate(width, height, maxRectSize int, rng *rand.Rand) *Puzzle {56 // Grid tracks which partition each cell belongs to (-1 = uncovered).57 grid := make([][]int, height)58 for y := range height {59 grid[y] = make([]int, width)60 for x := range width {61 grid[y][x] = -162 }63 }6465 partitions := make([]genRect, 0, width*height/2)66 if !partitionGrid(grid, width, height, maxRectSize, &partitions, rng) {67 return nil68 }6970 // Place clues: pick a random cell within each partition.71 clues := make([]Clue, len(partitions))72 allSingles := true73 for i, r := range partitions {74 cx := r.x + rng.IntN(r.w)75 cy := r.y + rng.IntN(r.h)76 area := r.w * r.h77 if area > 1 {78 allSingles = false79 }80 clues[i] = Clue{81 ID: i,82 X: cx,83 Y: cy,84 Value: area,85 }86 }87 if allSingles {88 return nil89 }9091 return &Puzzle{92 Width: width,93 Height: height,94 Clues: clues,95 }96}9798func isAnchorCell(grid [][]int, x, y int) bool {99 if grid[y][x] != -1 {100 return false101 }102 if x > 0 && grid[y][x-1] == -1 {103 return false104 }105 if y > 0 && grid[y-1][x] == -1 {106 return false107 }108 return true109}110111func anchorExtents(grid [][]int, x, y, width, height int) (maxW, maxH int) {112 maxW = 0113 for cx := x; cx < width && grid[y][cx] == -1; cx++ {114 maxW++115 }116 maxH = 0117 for cy := y; cy < height && grid[cy][x] == -1; cy++ {118 maxH++119 }120 return maxW, maxH121}122123func candidateTemplatesForAnchor(124 state *partitionSearchState,125 x,126 y,127 maxW,128 maxH,129 maxRectSize int,130) []dim {131 key := templateCacheKey{132 x: x,133 y: y,134 maxW: maxW,135 maxH: maxH,136 maxArea: maxRectSize,137 }138 if templates, ok := state.templateCache[key]; ok {139 return templates140 }141142 templates := make([]dim, 0, maxW*maxH)143 for w := 1; w <= maxW; w++ {144 for h := 1; h <= maxH; h++ {145 if w*h > maxRectSize {146 continue147 }148 templates = append(templates, dim{w: w, h: h})149 }150 }151152 state.templateCache[key] = templates153 return templates154}155156func selectMostConstrainedAnchor(157 grid [][]int,158 width,159 height,160 maxRectSize int,161 state *partitionSearchState,162) (x, y, maxW, maxH int, candidates []dim, found bool) {163 bestCount := width*height + 1164 bestX, bestY := -1, -1165 bestW, bestH := 0, 0166167 for y := range height {168 for x := range width {169 if !isAnchorCell(grid, x, y) {170 continue171 }172173 curW, curH := anchorExtents(grid, x, y, width, height)174 templates := candidateTemplatesForAnchor(state, x, y, curW, curH, maxRectSize)175 valid := make([]dim, 0, len(templates))176 for _, c := range templates {177 if fits(grid, x, y, c.w, c.h) {178 valid = append(valid, c)179 }180 }181182 if len(valid) == 0 {183 return x, y, curW, curH, nil, true184 }185 if len(valid) < bestCount {186 bestCount = len(valid)187 bestX, bestY = x, y188 bestW, bestH = curW, curH189 candidates = valid190 found = true191 }192 if bestCount == 1 {193 return bestX, bestY, bestW, bestH, candidates, true194 }195 }196 }197198 if !found {199 return 0, 0, 0, 0, nil, false200 }201 return bestX, bestY, bestW, bestH, candidates, true202}203204// partitionGrid recursively fills the grid with non-overlapping rectangles.205func partitionGrid(grid [][]int, width, height, maxRectSize int, partitions *[]genRect, rng *rand.Rand) bool {206 state := partitionSearchState{207 templateCache: make(map[templateCacheKey][]dim, width*height),208 failedStates: make(map[failedStateKey]bool, width*height),209 }210 return partitionGridRec(grid, width, height, maxRectSize, partitions, rng, &state, width*height)211}212213func partitionGridRec(214 grid [][]int,215 width,216 height,217 maxRectSize int,218 partitions *[]genRect,219 rng *rand.Rand,220 state *partitionSearchState,221 remaining int,222) bool {223 x, y, maxW, maxH, candidates, found := selectMostConstrainedAnchor(224 grid,225 width,226 height,227 maxRectSize,228 state,229 )230 if !found {231 return true // all cells covered232 }233234 failKey := failedStateKey{x: x, y: y, maxW: maxW, maxH: maxH, remaining: remaining}235 if state.failedStates[failKey] {236 return false237 }238 if len(candidates) == 0 {239 state.failedStates[failKey] = true240 return false241 }242243 order := make([]dim, len(candidates))244 copy(order, candidates)245 rng.Shuffle(len(order), func(i, j int) {246 order[i], order[j] = order[j], order[i]247 })248249 id := len(*partitions)250 for _, c := range order {251 // Place rectangle.252 place(grid, x, y, c.w, c.h, id)253 *partitions = append(*partitions, genRect{x, y, c.w, c.h})254255 if partitionGridRec(256 grid,257 width,258 height,259 maxRectSize,260 partitions,261 rng,262 state,263 remaining-(c.w*c.h),264 ) {265 return true266 }267268 // Backtrack.269 *partitions = (*partitions)[:len(*partitions)-1]270 clearGrid(grid, x, y, c.w, c.h)271 }272273 state.failedStates[failKey] = true274 return false275}276277// fits checks if a rectangle of size w*h can be placed at (x, y) without overlap.278func fits(grid [][]int, x, y, w, h int) bool {279 for dy := range h {280 for dx := range w {281 if grid[y+dy][x+dx] != -1 {282 return false283 }284 }285 }286 return true287}288289// place marks cells in the grid with the given partition ID.290func place(grid [][]int, x, y, w, h, id int) {291 for dy := range h {292 for dx := range w {293 grid[y+dy][x+dx] = id294 }295 }296}297298// clearGrid resets cells in the grid back to uncovered.299func clearGrid(grid [][]int, x, y, w, h int) {300 for dy := range h {301 for dx := range w {302 grid[y+dy][x+dx] = -1303 }304 }305}