1package nonogram23import (4 "context"5 "math/rand/v2"6 "strconv"7 "strings"8 "sync"9 "time"10)1112const (13 maxAttempts = 10014 maxPossibilities = 2000015 maxCacheEntries = 1638416 maxCacheCells = 500_000_00017)1819type lineCacheKey struct {20 length int21 hint string22}2324type possibilitiesCacheEntry struct {25 possibilities [][]cellState26 cellCost int27}2829var (30 possibilitiesCache = make(map[lineCacheKey]*possibilitiesCacheEntry)31 possibilitiesOrder = make([]lineCacheKey, 0, maxCacheEntries)32 possibilitiesOrderHead = 033 possibilitiesCacheSize int34 possibilitiesMu sync.Mutex35)3637func cacheKey(length int, hint []int) lineCacheKey {38 return lineCacheKey{39 length: length,40 hint: encodeHint(hint),41 }42}4344func encodeHint(hint []int) string {45 if len(hint) == 0 {46 return ""47 }48 var b strings.Builder49 b.Grow(len(hint) * 3)50 for i, v := range hint {51 if i > 0 {52 b.WriteByte(',')53 }54 b.WriteString(strconv.Itoa(v))55 }56 return b.String()57}5859func GenerateRandomTomography(mode NonogramMode) Hints {60 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))61 return GenerateRandomTomographySeeded(mode, rng)62}6364func GenerateRandomTomographySeeded(mode NonogramMode, rng *rand.Rand) Hints {65 maxDim := max(mode.Width, mode.Height)66 timeout := time.Duration(maxDim) * time.Second6768 for attempt := range maxAttempts {69 density := lerp(mode.Density, 0.5, float64(attempt)*0.02)70 s := generateRandomStateSeeded(mode.Height, mode.Width, density, rng)71 g := newGrid(s)72 hints := generateTomography(g)73 if !isValidPuzzle(hints, mode.Height, mode.Width) {74 continue75 }76 ctx, cancel := context.WithTimeout(context.Background(), timeout)77 count := countSolutions(hints, mode.Width, mode.Height, 2, ctx)78 cancel()79 if count == 1 {80 return hints81 }82 }83 return Hints{}84}8586func lerp(a, b, t float64) float64 {87 return a + (b-a)*t88}8990func generateRandomStateSeeded(h, w int, density float64, rng *rand.Rand) state {91 if h <= 0 || w <= 0 {92 return ""93 }9495 density = max(0.1, min(0.9, density))9697 var b strings.Builder98 b.Grow((w + 1) * h)99100 for i := range h {101 rowDensity := density + (rng.Float64()-0.5)*0.3102 rowDensity = max(0.05, min(0.95, rowDensity))103 for range w {104 if rng.Float64() < rowDensity {105 b.WriteRune(filledTile)106 } else {107 b.WriteRune(emptyTile)108 }109 }110 if i < h-1 {111 b.WriteRune('\n')112 }113 }114115 return state(b.String())116}117118func isValidPuzzle(hints Hints, height, width int) bool {119 for _, rh := range hints.rows {120 if len(rh) == 1 && (rh[0] == 0 || rh[0] == width) {121 return false122 }123 }124 for _, ch := range hints.cols {125 if len(ch) == 1 && (ch[0] == 0 || ch[0] == height) {126 return false127 }128 }129 return true130}131132type cellState int133134const (135 cellUnknown cellState = iota136 cellEmpty137 cellFilled138)139140type solutionGrid struct {141 cells [][]cellState142 w, h int143}144145type cellChange struct {146 x, y int147 prev cellState148}149150type undoStack struct {151 changes []cellChange152}153154func newSolutionGrid(w, h int) solutionGrid {155 cells := make([][]cellState, h)156 for y := range h {157 cells[y] = make([]cellState, w)158 for x := range w {159 cells[y][x] = cellUnknown160 }161 }162 return solutionGrid{cells: cells, w: w, h: h}163}164165func (g *solutionGrid) isComplete() bool {166 for y := range g.h {167 for x := range g.w {168 if g.cells[y][x] == cellUnknown {169 return false170 }171 }172 }173 return true174}175176func countSolutions(hints Hints, w, h, limit int, ctx context.Context) int {177 g := newSolutionGrid(w, h)178 stack := undoStack{179 changes: make([]cellChange, 0, w*h),180 }181 return countSolutionsRecursive(&g, hints, limit, ctx, &stack)182}183184func countSolutionsRecursive(185 g *solutionGrid,186 hints Hints,187 limit int,188 ctx context.Context,189 stack *undoStack,190) int {191 if limit <= 0 {192 return 0193 }194 select {195 case <-ctx.Done():196 return -1197 default:198 }199200 mark := stack.mark()201 if !propagateInPlace(g, hints, ctx, stack) {202 stack.revert(g, mark)203 return 0204 }205206 if g.isComplete() {207 stack.revert(g, mark)208 return 1209 }210211 x, y, ok := pickMostConstrainedCell(*g, hints)212 if !ok {213 stack.revert(g, mark)214 return 0215 }216217 count := 0218 branchOrder := [2]cellState{cellFilled, cellEmpty}219 for _, value := range branchOrder {220 branchMark := stack.mark()221 if stack.set(g, x, y, value) {222 n := countSolutionsRecursive(g, hints, limit-count, ctx, stack)223 if n < 0 {224 stack.revert(g, mark)225 return n226 }227 count += n228 if count >= limit {229 stack.revert(g, mark)230 return count231 }232 }233 stack.revert(g, branchMark)234 }235236 stack.revert(g, mark)237 return count238}239240func propagateInPlace(g *solutionGrid, hints Hints, ctx context.Context, stack *undoStack) bool {241 rowBuf := make([]cellState, g.w)242 colBuf := make([]cellState, g.h)243244 changed := true245 for changed {246 select {247 case <-ctx.Done():248 return false249 default:250 }251 changed = false252253 for y := range g.h {254 for x := range g.w {255 rowBuf[x] = g.cells[y][x]256 }257258 newRow, valid := propagateLine(rowBuf[:g.w], hints.rows[y])259 if !valid {260 return false261 }262263 for x := range g.w {264 if g.cells[y][x] == cellUnknown && newRow[x] != cellUnknown {265 if !stack.set(g, x, y, newRow[x]) {266 return false267 }268 changed = true269 }270 }271 }272273 for x := range g.w {274 for y := range g.h {275 colBuf[y] = g.cells[y][x]276 }277278 newCol, valid := propagateLine(colBuf[:g.h], hints.cols[x])279 if !valid {280 return false281 }282283 for y := range g.h {284 if g.cells[y][x] == cellUnknown && newCol[y] != cellUnknown {285 if !stack.set(g, x, y, newCol[y]) {286 return false287 }288 changed = true289 }290 }291 }292 }293294 return true295}296297func (s *undoStack) mark() int {298 return len(s.changes)299}300301func (s *undoStack) set(g *solutionGrid, x, y int, state cellState) bool {302 current := g.cells[y][x]303 if current == state {304 return true305 }306 if current != cellUnknown {307 return false308 }309 s.changes = append(s.changes, cellChange{x: x, y: y, prev: current})310 g.cells[y][x] = state311 return true312}313314func (s *undoStack) revert(g *solutionGrid, mark int) {315 for i := len(s.changes) - 1; i >= mark; i-- {316 change := s.changes[i]317 g.cells[change.y][change.x] = change.prev318 }319 s.changes = s.changes[:mark]320}321322func pickMostConstrainedCell(g solutionGrid, hints Hints) (x, y int, ok bool) {323 firstX, firstY := -1, -1324 bestNeighborScore := -1325 bestHintWeight := -1326327 for yy := range g.h {328 for xx := range g.w {329 if g.cells[yy][xx] != cellUnknown {330 continue331 }332 if firstX < 0 {333 firstX, firstY = xx, yy334 }335336 neighborScore := 0337 if yy > 0 && g.cells[yy-1][xx] != cellUnknown {338 neighborScore++339 }340 if yy+1 < g.h && g.cells[yy+1][xx] != cellUnknown {341 neighborScore++342 }343 if xx > 0 && g.cells[yy][xx-1] != cellUnknown {344 neighborScore++345 }346 if xx+1 < g.w && g.cells[yy][xx+1] != cellUnknown {347 neighborScore++348 }349350 hintWeight := len(hints.rows[yy]) + len(hints.cols[xx])351 if neighborScore > bestNeighborScore ||352 (neighborScore == bestNeighborScore && hintWeight > bestHintWeight) {353 bestNeighborScore = neighborScore354 bestHintWeight = hintWeight355 x, y = xx, yy356 ok = true357 }358 }359 }360361 if firstX < 0 {362 return 0, 0, false363 }364 if bestNeighborScore <= 0 {365 return firstX, firstY, true366 }367 return x, y, ok368}369370func propagateLine(line []cellState, hint []int) ([]cellState, bool) {371 n := len(line)372 possibilities := getCachedPossibilities(n, hint)373374 if len(possibilities) > maxPossibilities {375 return line, true376 }377378 filtered := make([][]cellState, 0, len(possibilities))379 for _, poss := range possibilities {380 if matchesLine(poss, line) {381 filtered = append(filtered, poss)382 }383 }384385 if len(filtered) == 0 {386 return nil, false387 }388389 result := make([]cellState, n)390 for i := range n {391 allFilled := true392 allEmpty := true393 for _, poss := range filtered {394 if poss[i] != cellFilled {395 allFilled = false396 }397 if poss[i] != cellEmpty {398 allEmpty = false399 }400 }401 if allFilled {402 result[i] = cellFilled403 } else if allEmpty {404 result[i] = cellEmpty405 } else {406 result[i] = cellUnknown407 }408 }409410 return result, true411}412413func getCachedPossibilities(length int, hint []int) [][]cellState {414 key := cacheKey(length, hint)415416 possibilitiesMu.Lock()417 if entry, ok := possibilitiesCache[key]; ok {418 cached := entry.possibilities419 possibilitiesMu.Unlock()420 return cached421 }422 possibilitiesMu.Unlock()423424 possibilities := generateLinePossibilities(length, hint)425 cellCost := len(possibilities) * length426 if cellCost <= 0 || cellCost > maxCacheCells {427 return possibilities428 }429430 possibilitiesMu.Lock()431 if entry, ok := possibilitiesCache[key]; ok {432 possibilitiesMu.Unlock()433 return entry.possibilities434 }435 possibilitiesCache[key] = &possibilitiesCacheEntry{436 possibilities: possibilities,437 cellCost: cellCost,438 }439 possibilitiesOrder = append(possibilitiesOrder, key)440 possibilitiesCacheSize += cellCost441 trimPossibilitiesCacheLocked()442 possibilitiesMu.Unlock()443444 return possibilities445}446447func trimPossibilitiesCacheLocked() {448 for len(possibilitiesCache) > maxCacheEntries || possibilitiesCacheSize > maxCacheCells {449 if possibilitiesOrderHead >= len(possibilitiesOrder) {450 return451 }452 key := possibilitiesOrder[possibilitiesOrderHead]453 possibilitiesOrderHead++454 entry, ok := possibilitiesCache[key]455 if !ok {456 continue457 }458 possibilitiesCacheSize -= entry.cellCost459 delete(possibilitiesCache, key)460 }461462 if possibilitiesOrderHead > 1024 && possibilitiesOrderHead*2 > len(possibilitiesOrder) {463 compacted := make([]lineCacheKey, len(possibilitiesOrder)-possibilitiesOrderHead)464 copy(compacted, possibilitiesOrder[possibilitiesOrderHead:])465 possibilitiesOrder = compacted466 possibilitiesOrderHead = 0467 }468}469470func generateLinePossibilities(length int, hint []int) [][]cellState {471 if len(hint) == 0 || (len(hint) == 1 && hint[0] == 0) {472 result := make([]cellState, length)473 for i := range result {474 result[i] = cellEmpty475 }476 return [][]cellState{result}477 }478479 totalFilled := 0480 for _, h := range hint {481 totalFilled += h482 }483 minLength := totalFilled + len(hint) - 1484 if minLength > length {485 return nil486 }487488 return generateLinePossibilitiesRecursive(length, hint, 0, 0, make([]cellState, 0, length))489}490491func generateLinePossibilitiesRecursive(length int, hint []int, hintIdx, pos int, current []cellState) [][]cellState {492 if hintIdx == len(hint) {493 for len(current) < length {494 current = append(current, cellEmpty)495 }496 return [][]cellState{append([]cellState(nil), current...)}497 }498499 blockLen := hint[hintIdx]500 remainingHints := hint[hintIdx+1:]501 remainingFilled := 0502 for _, h := range remainingHints {503 remainingFilled += h504 }505 minRemaining := remainingFilled + len(remainingHints)506507 maxStart := length - blockLen - minRemaining508509 var results [][]cellState510511 for start := pos; start <= maxStart; start++ {512 newCurrent := append([]cellState(nil), current...)513514 for i := len(current); i < start; i++ {515 newCurrent = append(newCurrent, cellEmpty)516 }517518 for range blockLen {519 newCurrent = append(newCurrent, cellFilled)520 }521522 if hintIdx < len(hint)-1 {523 newCurrent = append(newCurrent, cellEmpty)524 }525 results = append(results, generateLinePossibilitiesRecursive(length, hint, hintIdx+1, len(newCurrent), newCurrent)...)526 }527528 return results529}530531func matchesLine(possibility, line []cellState) bool {532 if len(possibility) != len(line) {533 return false534 }535 for i, p := range possibility {536 if line[i] != cellUnknown && line[i] != p {537 return false538 }539 }540 return true541}