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 return GenerateRandomTomographySeededContext(context.Background(), mode, rng)66}6768func GenerateRandomTomographySeededContext(ctx context.Context, mode NonogramMode, rng *rand.Rand) Hints {69 maxDim := max(mode.Width, mode.Height)70 timeout := time.Duration(maxDim) * time.Second7172 for attempt := range maxAttempts {73 if ctx.Err() != nil {74 return Hints{}75 }76 density := lerp(mode.Density, 0.5, float64(attempt)*0.02)77 s := generateRandomStateSeeded(mode.Height, mode.Width, density, rng)78 g := newGrid(s)79 hints := generateTomography(g)80 if !isValidPuzzle(hints, mode.Height, mode.Width) {81 continue82 }83 attemptCtx, cancel := context.WithTimeout(ctx, timeout)84 count := countSolutions(hints, mode.Width, mode.Height, 2, attemptCtx)85 cancel()86 if count == 1 {87 return hints88 }89 }90 return Hints{}91}9293func GenerateRandomTomographySeededFastContext(ctx context.Context, mode NonogramMode, rng *rand.Rand) Hints {94 for attempt := range maxAttempts {95 if ctx.Err() != nil {96 return Hints{}97 }98 density := lerp(mode.Density, 0.5, float64(attempt)*0.02)99 s := generateRandomStateSeeded(mode.Height, mode.Width, density, rng)100 g := newGrid(s)101 hints := generateTomography(g)102 if isValidPuzzle(hints, mode.Height, mode.Width) {103 return hints104 }105 }106 return Hints{}107}108109func lerp(a, b, t float64) float64 {110 return a + (b-a)*t111}112113func generateRandomStateSeeded(h, w int, density float64, rng *rand.Rand) state {114 if h <= 0 || w <= 0 {115 return ""116 }117118 density = max(0.1, min(0.9, density))119120 var b strings.Builder121 b.Grow((w + 1) * h)122123 for i := range h {124 rowDensity := density + (rng.Float64()-0.5)*0.3125 rowDensity = max(0.05, min(0.95, rowDensity))126 for range w {127 if rng.Float64() < rowDensity {128 b.WriteRune(filledTile)129 } else {130 b.WriteRune(emptyTile)131 }132 }133 if i < h-1 {134 b.WriteRune('\n')135 }136 }137138 return state(b.String())139}140141func isValidPuzzle(hints Hints, height, width int) bool {142 for _, rh := range hints.rows {143 if len(rh) == 1 && (rh[0] == 0 || rh[0] == width) {144 return false145 }146 }147 for _, ch := range hints.cols {148 if len(ch) == 1 && (ch[0] == 0 || ch[0] == height) {149 return false150 }151 }152 return true153}154155type cellState int156157const (158 cellUnknown cellState = iota159 cellEmpty160 cellFilled161)162163type solutionGrid struct {164 cells [][]cellState165 w, h int166}167168type cellChange struct {169 x, y int170 prev cellState171}172173type undoStack struct {174 changes []cellChange175}176177func newSolutionGrid(w, h int) solutionGrid {178 cells := make([][]cellState, h)179 for y := range h {180 cells[y] = make([]cellState, w)181 for x := range w {182 cells[y][x] = cellUnknown183 }184 }185 return solutionGrid{cells: cells, w: w, h: h}186}187188func (g *solutionGrid) isComplete() bool {189 for y := range g.h {190 for x := range g.w {191 if g.cells[y][x] == cellUnknown {192 return false193 }194 }195 }196 return true197}198199func countSolutions(hints Hints, w, h, limit int, ctx context.Context) int {200 g := newSolutionGrid(w, h)201 stack := undoStack{202 changes: make([]cellChange, 0, w*h),203 }204 return countSolutionsRecursive(&g, hints, limit, ctx, &stack)205}206207func countSolutionsRecursive(208 g *solutionGrid,209 hints Hints,210 limit int,211 ctx context.Context,212 stack *undoStack,213) int {214 if limit <= 0 {215 return 0216 }217 select {218 case <-ctx.Done():219 return -1220 default:221 }222223 mark := stack.mark()224 if !propagateInPlace(g, hints, ctx, stack) {225 stack.revert(g, mark)226 return 0227 }228229 if g.isComplete() {230 stack.revert(g, mark)231 return 1232 }233234 x, y, ok := pickMostConstrainedCell(*g, hints)235 if !ok {236 stack.revert(g, mark)237 return 0238 }239240 count := 0241 branchOrder := [2]cellState{cellFilled, cellEmpty}242 for _, value := range branchOrder {243 branchMark := stack.mark()244 if stack.set(g, x, y, value) {245 n := countSolutionsRecursive(g, hints, limit-count, ctx, stack)246 if n < 0 {247 stack.revert(g, mark)248 return n249 }250 count += n251 if count >= limit {252 stack.revert(g, mark)253 return count254 }255 }256 stack.revert(g, branchMark)257 }258259 stack.revert(g, mark)260 return count261}262263func propagateInPlace(g *solutionGrid, hints Hints, ctx context.Context, stack *undoStack) bool {264 rowBuf := make([]cellState, g.w)265 colBuf := make([]cellState, g.h)266267 changed := true268 for changed {269 select {270 case <-ctx.Done():271 return false272 default:273 }274 changed = false275276 for y := range g.h {277 for x := range g.w {278 rowBuf[x] = g.cells[y][x]279 }280281 newRow, valid := propagateLine(rowBuf[:g.w], hints.rows[y])282 if !valid {283 return false284 }285286 for x := range g.w {287 if g.cells[y][x] == cellUnknown && newRow[x] != cellUnknown {288 if !stack.set(g, x, y, newRow[x]) {289 return false290 }291 changed = true292 }293 }294 }295296 for x := range g.w {297 for y := range g.h {298 colBuf[y] = g.cells[y][x]299 }300301 newCol, valid := propagateLine(colBuf[:g.h], hints.cols[x])302 if !valid {303 return false304 }305306 for y := range g.h {307 if g.cells[y][x] == cellUnknown && newCol[y] != cellUnknown {308 if !stack.set(g, x, y, newCol[y]) {309 return false310 }311 changed = true312 }313 }314 }315 }316317 return true318}319320func (s *undoStack) mark() int {321 return len(s.changes)322}323324func (s *undoStack) set(g *solutionGrid, x, y int, state cellState) bool {325 current := g.cells[y][x]326 if current == state {327 return true328 }329 if current != cellUnknown {330 return false331 }332 s.changes = append(s.changes, cellChange{x: x, y: y, prev: current})333 g.cells[y][x] = state334 return true335}336337func (s *undoStack) revert(g *solutionGrid, mark int) {338 for i := len(s.changes) - 1; i >= mark; i-- {339 change := s.changes[i]340 g.cells[change.y][change.x] = change.prev341 }342 s.changes = s.changes[:mark]343}344345func pickMostConstrainedCell(g solutionGrid, hints Hints) (x, y int, ok bool) {346 firstX, firstY := -1, -1347 bestNeighborScore := -1348 bestHintWeight := -1349350 for yy := range g.h {351 for xx := range g.w {352 if g.cells[yy][xx] != cellUnknown {353 continue354 }355 if firstX < 0 {356 firstX, firstY = xx, yy357 }358359 neighborScore := 0360 if yy > 0 && g.cells[yy-1][xx] != cellUnknown {361 neighborScore++362 }363 if yy+1 < g.h && g.cells[yy+1][xx] != cellUnknown {364 neighborScore++365 }366 if xx > 0 && g.cells[yy][xx-1] != cellUnknown {367 neighborScore++368 }369 if xx+1 < g.w && g.cells[yy][xx+1] != cellUnknown {370 neighborScore++371 }372373 hintWeight := len(hints.rows[yy]) + len(hints.cols[xx])374 if neighborScore > bestNeighborScore ||375 (neighborScore == bestNeighborScore && hintWeight > bestHintWeight) {376 bestNeighborScore = neighborScore377 bestHintWeight = hintWeight378 x, y = xx, yy379 ok = true380 }381 }382 }383384 if firstX < 0 {385 return 0, 0, false386 }387 if bestNeighborScore <= 0 {388 return firstX, firstY, true389 }390 return x, y, ok391}392393func propagateLine(line []cellState, hint []int) ([]cellState, bool) {394 n := len(line)395 possibilities := getCachedPossibilities(n, hint)396397 if len(possibilities) > maxPossibilities {398 return line, true399 }400401 filtered := make([][]cellState, 0, len(possibilities))402 for _, poss := range possibilities {403 if matchesLine(poss, line) {404 filtered = append(filtered, poss)405 }406 }407408 if len(filtered) == 0 {409 return nil, false410 }411412 result := make([]cellState, n)413 for i := range n {414 allFilled := true415 allEmpty := true416 for _, poss := range filtered {417 if poss[i] != cellFilled {418 allFilled = false419 }420 if poss[i] != cellEmpty {421 allEmpty = false422 }423 }424 if allFilled {425 result[i] = cellFilled426 } else if allEmpty {427 result[i] = cellEmpty428 } else {429 result[i] = cellUnknown430 }431 }432433 return result, true434}435436func getCachedPossibilities(length int, hint []int) [][]cellState {437 key := cacheKey(length, hint)438439 possibilitiesMu.Lock()440 if entry, ok := possibilitiesCache[key]; ok {441 cached := entry.possibilities442 possibilitiesMu.Unlock()443 return cached444 }445 possibilitiesMu.Unlock()446447 possibilities := generateLinePossibilities(length, hint)448 cellCost := len(possibilities) * length449 if cellCost <= 0 || cellCost > maxCacheCells {450 return possibilities451 }452453 possibilitiesMu.Lock()454 if entry, ok := possibilitiesCache[key]; ok {455 possibilitiesMu.Unlock()456 return entry.possibilities457 }458 possibilitiesCache[key] = &possibilitiesCacheEntry{459 possibilities: possibilities,460 cellCost: cellCost,461 }462 possibilitiesOrder = append(possibilitiesOrder, key)463 possibilitiesCacheSize += cellCost464 trimPossibilitiesCacheLocked()465 possibilitiesMu.Unlock()466467 return possibilities468}469470func trimPossibilitiesCacheLocked() {471 for len(possibilitiesCache) > maxCacheEntries || possibilitiesCacheSize > maxCacheCells {472 if possibilitiesOrderHead >= len(possibilitiesOrder) {473 return474 }475 key := possibilitiesOrder[possibilitiesOrderHead]476 possibilitiesOrderHead++477 entry, ok := possibilitiesCache[key]478 if !ok {479 continue480 }481 possibilitiesCacheSize -= entry.cellCost482 delete(possibilitiesCache, key)483 }484485 if possibilitiesOrderHead > 1024 && possibilitiesOrderHead*2 > len(possibilitiesOrder) {486 compacted := make([]lineCacheKey, len(possibilitiesOrder)-possibilitiesOrderHead)487 copy(compacted, possibilitiesOrder[possibilitiesOrderHead:])488 possibilitiesOrder = compacted489 possibilitiesOrderHead = 0490 }491}492493func generateLinePossibilities(length int, hint []int) [][]cellState {494 if len(hint) == 0 || (len(hint) == 1 && hint[0] == 0) {495 result := make([]cellState, length)496 for i := range result {497 result[i] = cellEmpty498 }499 return [][]cellState{result}500 }501502 totalFilled := 0503 for _, h := range hint {504 totalFilled += h505 }506 minLength := totalFilled + len(hint) - 1507 if minLength > length {508 return nil509 }510511 return generateLinePossibilitiesRecursive(length, hint, 0, 0, make([]cellState, 0, length))512}513514func generateLinePossibilitiesRecursive(length int, hint []int, hintIdx, pos int, current []cellState) [][]cellState {515 if hintIdx == len(hint) {516 for len(current) < length {517 current = append(current, cellEmpty)518 }519 return [][]cellState{append([]cellState(nil), current...)}520 }521522 blockLen := hint[hintIdx]523 remainingHints := hint[hintIdx+1:]524 remainingFilled := 0525 for _, h := range remainingHints {526 remainingFilled += h527 }528 minRemaining := remainingFilled + len(remainingHints)529530 maxStart := length - blockLen - minRemaining531532 var results [][]cellState533534 for start := pos; start <= maxStart; start++ {535 newCurrent := append([]cellState(nil), current...)536537 for i := len(current); i < start; i++ {538 newCurrent = append(newCurrent, cellEmpty)539 }540541 for range blockLen {542 newCurrent = append(newCurrent, cellFilled)543 }544545 if hintIdx < len(hint)-1 {546 newCurrent = append(newCurrent, cellEmpty)547 }548 results = append(results, generateLinePossibilitiesRecursive(length, hint, hintIdx+1, len(newCurrent), newCurrent)...)549 }550551 return results552}553554func matchesLine(possibility, line []cellState) bool {555 if len(possibility) != len(line) {556 return false557 }558 for i, p := range possibility {559 if line[i] != cellUnknown && line[i] != p {560 return false561 }562 }563 return true564}