1package nurikabe23import (4 "context"5 "errors"6 "fmt"7 "slices"8)910var errNodeLimit = errors.New("solver node limit exceeded")1112type SolveStats struct {13 Nodes int14 Branches int15 MaxDepth int16}1718type point struct {19 x, y int20}2122type islandComponent struct {23 cells []point24 clueCount int25 clueValue int26 cluePos point27}2829var dirs = [4]point{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}3031type solverScratch struct {32 width int33 height int3435 compIdx [][]int36 seen [][]int37 seenMark int38 workQueue []point39}4041func newSolverScratch(width, height int) *solverScratch {42 s := &solverScratch{43 width: width,44 height: height,45 }46 if width <= 0 || height <= 0 {47 return s48 }4950 s.compIdx = make([][]int, height)51 s.seen = make([][]int, height)52 for y := range height {53 s.compIdx[y] = make([]int, width)54 s.seen[y] = make([]int, width)55 }56 return s57}5859func (s *solverScratch) resetComponentIndex() [][]int {60 for y := range s.height {61 for x := range s.width {62 s.compIdx[y][x] = -163 }64 }65 return s.compIdx66}6768func (s *solverScratch) nextSeenMark() int {69 s.seenMark++70 if s.seenMark > 0 {71 return s.seenMark72 }73 for y := range s.height {74 for x := range s.width {75 s.seen[y][x] = 076 }77 }78 s.seenMark = 179 return s.seenMark80}8182func CountSolutions(puzzle Puzzle, limit, nodeLimit int) (int, SolveStats, error) {83 return CountSolutionsContext(context.Background(), puzzle, limit, nodeLimit)84}8586func CountSolutionsContext(ctx context.Context, puzzle Puzzle, limit, nodeLimit int) (int, SolveStats, error) {87 if ctx == nil {88 ctx = context.Background()89 }90 if limit <= 0 {91 return 0, SolveStats{}, nil92 }93 if nodeLimit <= 0 {94 nodeLimit = 25000095 }96 if err := validateClues(puzzle.Clues, puzzle.Width, puzzle.Height); err != nil {97 return 0, SolveStats{}, err98 }99100 state := newGrid(puzzle.Width, puzzle.Height, unknownCell)101 for y := range puzzle.Height {102 for x := range puzzle.Width {103 if puzzle.Clues[y][x] > 0 {104 state[y][x] = islandCell105 }106 }107 }108109 stats := SolveStats{}110 solutions := 0111 scratch := newSolverScratch(puzzle.Width, puzzle.Height)112 var dfs func(grid, int) error113 dfs = func(g grid, depth int) error {114 if err := ctx.Err(); err != nil {115 return err116 }117 if stats.Nodes >= nodeLimit {118 return errNodeLimit119 }120 stats.Nodes++121 if depth > stats.MaxDepth {122 stats.MaxDepth = depth123 }124125 if err := propagateWithScratch(g, puzzle.Clues, scratch); err != nil {126 return nil127 }128 if err := validatePartialWithScratch(g, puzzle.Clues, scratch); err != nil {129 return nil130 }131132 x, y, ok := pickUnknown(g, puzzle.Clues)133 if !ok {134 if isSolvedGridWithScratch(g, puzzle.Clues, scratch) {135 solutions++136 }137 return nil138 }139140 order := candidateOrder(g, puzzle.Clues, x, y)141 stats.Branches++142 for _, candidate := range order {143 if err := ctx.Err(); err != nil {144 return err145 }146 next := g.clone()147 next[y][x] = candidate148 if err := dfs(next, depth+1); err != nil {149 if errors.Is(err, errNodeLimit) ||150 errors.Is(err, context.Canceled) ||151 errors.Is(err, context.DeadlineExceeded) {152 return err153 }154 continue155 }156 if solutions >= limit {157 return nil158 }159 }160161 return nil162 }163164 err := dfs(state, 0)165 if errors.Is(err, errNodeLimit) ||166 errors.Is(err, context.Canceled) ||167 errors.Is(err, context.DeadlineExceeded) {168 return solutions, stats, err169 }170 return solutions, stats, nil171}172173func propagateWithScratch(g grid, clues clueGrid, scratch *solverScratch) error {174 height := len(g)175 if height == 0 {176 return nil177 }178 width := len(g[0])179180 for {181 changed := false182 comps, compIdx := islandComponentsWithScratch(g, clues, scratch)183184 for _, comp := range comps {185 if comp.clueCount == 1 && len(comp.cells) == comp.clueValue {186 for _, c := range comp.cells {187 for _, d := range dirs {188 nx, ny := c.x+d.x, c.y+d.y189 if nx < 0 || nx >= width || ny < 0 || ny >= height {190 continue191 }192 if g[ny][nx] == unknownCell {193 g[ny][nx] = seaCell194 changed = true195 }196 }197 }198 }199 }200201 for y := range height {202 for x := range width {203 if g[y][x] != unknownCell {204 continue205 }206 firstClueComp := -1207 clashes := false208 for _, d := range dirs {209 nx, ny := x+d.x, y+d.y210 if nx < 0 || nx >= width || ny < 0 || ny >= height {211 continue212 }213 if g[ny][nx] != islandCell {214 continue215 }216 idx := compIdx[ny][nx]217 if idx < 0 || idx >= len(comps) {218 continue219 }220 comp := comps[idx]221 if comp.clueCount == 1 {222 if firstClueComp == -1 {223 firstClueComp = idx224 continue225 }226 if firstClueComp != idx {227 clashes = true228 break229 }230 }231 }232 if clashes {233 g[y][x] = seaCell234 changed = true235 }236 }237 }238239 if err := validatePartialWithScratch(g, clues, scratch); err != nil {240 return err241 }242 if !changed {243 return nil244 }245 }246}247248func validatePartialWithScratch(g grid, clues clueGrid, scratch *solverScratch) error {249 if hasSeaSquare(g) {250 return fmt.Errorf("contains 2x2 sea block")251 }252 if !seaCanRemainConnectedWithScratch(g, scratch) {253 return fmt.Errorf("sea components cannot be connected")254 }255256 comps, _ := islandComponentsWithScratch(g, clues, scratch)257 for _, comp := range comps {258 size := len(comp.cells)259 switch {260 case comp.clueCount > 1:261 return fmt.Errorf("island has multiple clues")262 case comp.clueCount == 1 && size > comp.clueValue:263 return fmt.Errorf("island exceeds clue size")264 case comp.clueCount == 0 && !componentCanReachClueWithScratch(g, clues, comp, scratch):265 return fmt.Errorf("orphan island component")266 case comp.clueCount == 1 && maxReachableForComponentWithScratch(g, clues, comp, scratch) < comp.clueValue:267 return fmt.Errorf("clue cannot reach required size")268 }269 }270271 return nil272}273274func isSolvedGrid(g grid, clues clueGrid) bool {275 if len(g) == 0 || len(g[0]) == 0 {276 return false277 }278 scratch := newSolverScratch(len(g[0]), len(g))279 return isSolvedGridWithScratch(g, clues, scratch)280}281282func isSolvedGridWithScratch(g grid, clues clueGrid, scratch *solverScratch) bool {283 normalized := normalizeSolvedGrid(g, clues)284 return isNormalizedSolvedGridWithScratch(normalized, clues, scratch)285}286287func normalizeSolvedGrid(g grid, clues clueGrid) grid {288 normalized := g.clone()289 for y := range normalized {290 for x := range normalized[y] {291 if clues[y][x] > 0 || normalized[y][x] != seaCell {292 normalized[y][x] = islandCell293 }294 }295 }296 return normalized297}298299func isNormalizedSolvedGridWithScratch(g grid, clues clueGrid, scratch *solverScratch) bool {300 if len(g) == 0 || len(g[0]) == 0 {301 return false302 }303304 height := len(g)305 width := len(g[0])306 for y := range height {307 for x := range width {308 if clues[y][x] > 0 && g[y][x] != islandCell {309 return false310 }311 if g[y][x] == unknownCell {312 return false313 }314 }315 }316317 if hasSeaSquare(g) {318 return false319 }320 if !isSeaConnectedWithScratch(g, scratch) {321 return false322 }323324 comps, _ := islandComponentsWithScratch(g, clues, scratch)325 seenClues := 0326 for _, comp := range comps {327 if comp.clueCount != 1 {328 return false329 }330 if len(comp.cells) != comp.clueValue {331 return false332 }333 seenClues++334 }335336 return seenClues == countClues(clues)337}338339func pickUnknown(g grid, clues clueGrid) (x, y int, ok bool) {340 bestScore := -1341 for yy, row := range g {342 for xx := range row {343 if g[yy][xx] != unknownCell {344 continue345 }346 if clues[yy][xx] > 0 {347 continue348 }349 score := 0350 for _, d := range dirs {351 nx, ny := xx+d.x, yy+d.y352 if nx < 0 || ny < 0 || ny >= len(g) || nx >= len(row) {353 continue354 }355 switch g[ny][nx] {356 case islandCell:357 score += 3358 case seaCell:359 score += 1360 }361 if clues[ny][nx] > 0 {362 score += 4363 }364 }365 if score > bestScore {366 bestScore = score367 x, y = xx, yy368 ok = true369 }370 }371 }372 return x, y, ok373}374375func candidateOrder(g grid, clues clueGrid, x, y int) []cellState {376 islandFirst := false377 for _, d := range dirs {378 nx, ny := x+d.x, y+d.y379 if nx < 0 || ny < 0 || ny >= len(g) || nx >= len(g[0]) {380 continue381 }382 if g[ny][nx] == islandCell || clues[ny][nx] > 0 {383 islandFirst = true384 break385 }386 }387388 if islandFirst {389 return []cellState{islandCell, seaCell}390 }391 return []cellState{seaCell, islandCell}392}393394func seaCanRemainConnectedWithScratch(g grid, scratch *solverScratch) bool {395 height := len(g)396 if height == 0 {397 return true398 }399 width := len(g[0])400401 start := point{-1, -1}402 seaCount := 0403 for y := range height {404 for x := range width {405 if g[y][x] == seaCell {406 seaCount++407 if start.x == -1 {408 start = point{x, y}409 }410 }411 }412 }413 if seaCount <= 1 {414 return true415 }416417 seenMark := scratch.nextSeenMark()418 scratch.workQueue = scratch.workQueue[:0]419 scratch.workQueue = append(scratch.workQueue, start)420 scratch.seen[start.y][start.x] = seenMark421422 for len(scratch.workQueue) > 0 {423 p := scratch.workQueue[0]424 scratch.workQueue = scratch.workQueue[1:]425 for _, d := range dirs {426 nx, ny := p.x+d.x, p.y+d.y427 if nx < 0 || ny < 0 || nx >= width || ny >= height {428 continue429 }430 if scratch.seen[ny][nx] == seenMark || g[ny][nx] == islandCell {431 continue432 }433 scratch.seen[ny][nx] = seenMark434 scratch.workQueue = append(scratch.workQueue, point{nx, ny})435 }436 }437438 for y := range height {439 for x := range width {440 if g[y][x] == seaCell && scratch.seen[y][x] != seenMark {441 return false442 }443 }444 }445 return true446}447448func isSeaConnectedWithScratch(g grid, scratch *solverScratch) bool {449 height := len(g)450 if height == 0 {451 return false452 }453 width := len(g[0])454455 start := point{-1, -1}456 seaCount := 0457 for y := range height {458 for x := range width {459 if g[y][x] == seaCell {460 seaCount++461 if start.x == -1 {462 start = point{x, y}463 }464 }465 }466 }467 if seaCount == 0 {468 return false469 }470471 seenMark := scratch.nextSeenMark()472 scratch.workQueue = scratch.workQueue[:0]473 scratch.workQueue = append(scratch.workQueue, start)474 scratch.seen[start.y][start.x] = seenMark475 seen := 1476477 for len(scratch.workQueue) > 0 {478 p := scratch.workQueue[0]479 scratch.workQueue = scratch.workQueue[1:]480 for _, d := range dirs {481 nx, ny := p.x+d.x, p.y+d.y482 if nx < 0 || ny < 0 || nx >= width || ny >= height {483 continue484 }485 if scratch.seen[ny][nx] == seenMark || g[ny][nx] != seaCell {486 continue487 }488 scratch.seen[ny][nx] = seenMark489 seen++490 scratch.workQueue = append(scratch.workQueue, point{nx, ny})491 }492 }493494 return seen == seaCount495}496497func hasSeaSquare(g grid) bool {498 height := len(g)499 if height == 0 {500 return false501 }502 width := len(g[0])503 for y := 0; y < height-1; y++ {504 for x := 0; x < width-1; x++ {505 if g[y][x] == seaCell && g[y][x+1] == seaCell && g[y+1][x] == seaCell && g[y+1][x+1] == seaCell {506 return true507 }508 }509 }510 return false511}512513func islandComponents(g grid, clues clueGrid) ([]islandComponent, [][]int) {514 if len(g) == 0 || len(g[0]) == 0 {515 return nil, nil516 }517 scratch := newSolverScratch(len(g[0]), len(g))518 return islandComponentsWithScratch(g, clues, scratch)519}520521func islandComponentsWithScratch(g grid, clues clueGrid, scratch *solverScratch) ([]islandComponent, [][]int) {522 height := len(g)523 width := len(g[0])524 idx := scratch.resetComponentIndex()525526 components := make([]islandComponent, 0)527 for y := range height {528 for x := range width {529 if g[y][x] != islandCell || idx[y][x] >= 0 {530 continue531 }532533 compIndex := len(components)534 comp := islandComponent{535 cluePos: point{-1, -1},536 cells: make([]point, 0, 16),537 }538 scratch.workQueue = scratch.workQueue[:0]539 scratch.workQueue = append(scratch.workQueue, point{x, y})540 idx[y][x] = compIndex541542 for len(scratch.workQueue) > 0 {543 p := scratch.workQueue[0]544 scratch.workQueue = scratch.workQueue[1:]545 comp.cells = append(comp.cells, p)546 if clues[p.y][p.x] > 0 {547 comp.clueCount++548 comp.clueValue = clues[p.y][p.x]549 comp.cluePos = p550 }551552 for _, d := range dirs {553 nx, ny := p.x+d.x, p.y+d.y554 if nx < 0 || ny < 0 || nx >= width || ny >= height {555 continue556 }557 if g[ny][nx] != islandCell || idx[ny][nx] >= 0 {558 continue559 }560 idx[ny][nx] = compIndex561 scratch.workQueue = append(scratch.workQueue, point{nx, ny})562 }563 }564565 components = append(components, comp)566 }567 }568569 return components, idx570}571572func componentCanReachClue(g grid, clues clueGrid, comp islandComponent) bool {573 if len(g) == 0 || len(g[0]) == 0 {574 return false575 }576 scratch := newSolverScratch(len(g[0]), len(g))577 return componentCanReachClueWithScratch(g, clues, comp, scratch)578}579580func componentCanReachClueWithScratch(581 g grid,582 clues clueGrid,583 comp islandComponent,584 scratch *solverScratch,585) bool {586 height := len(g)587 width := len(g[0])588 seenMark := scratch.nextSeenMark()589 scratch.workQueue = scratch.workQueue[:0]590 for _, c := range comp.cells {591 scratch.seen[c.y][c.x] = seenMark592 scratch.workQueue = append(scratch.workQueue, c)593 }594595 for len(scratch.workQueue) > 0 {596 p := scratch.workQueue[0]597 scratch.workQueue = scratch.workQueue[1:]598 if clues[p.y][p.x] > 0 {599 return true600 }601 for _, d := range dirs {602 nx, ny := p.x+d.x, p.y+d.y603 if nx < 0 || ny < 0 || nx >= width || ny >= height {604 continue605 }606 if scratch.seen[ny][nx] == seenMark || g[ny][nx] == seaCell {607 continue608 }609 scratch.seen[ny][nx] = seenMark610 scratch.workQueue = append(scratch.workQueue, point{nx, ny})611 }612 }613614 return false615}616617func maxReachableForComponentWithScratch(618 g grid,619 clues clueGrid,620 comp islandComponent,621 scratch *solverScratch,622) int {623 if comp.clueCount != 1 {624 return 0625 }626627 height := len(g)628 width := len(g[0])629 seenMark := scratch.nextSeenMark()630 scratch.workQueue = scratch.workQueue[:0]631 for _, c := range comp.cells {632 scratch.seen[c.y][c.x] = seenMark633 scratch.workQueue = append(scratch.workQueue, c)634 }635636 count := len(comp.cells)637 for len(scratch.workQueue) > 0 {638 p := scratch.workQueue[0]639 scratch.workQueue = scratch.workQueue[1:]640 for _, d := range dirs {641 nx, ny := p.x+d.x, p.y+d.y642 if nx < 0 || ny < 0 || nx >= width || ny >= height {643 continue644 }645 if scratch.seen[ny][nx] == seenMark || g[ny][nx] == seaCell {646 continue647 }648 if clues[ny][nx] > 0 && (nx != comp.cluePos.x || ny != comp.cluePos.y) {649 continue650 }651 scratch.seen[ny][nx] = seenMark652 count++653 scratch.workQueue = append(scratch.workQueue, point{nx, ny})654 }655 }656657 return count658}659660func hasAnyUnknown(g grid) bool {661 for _, row := range g {662 if slices.Contains(row, unknownCell) {663 return true664 }665 }666 return false667}668669func computeConflicts(marks grid, clues clueGrid) [][]bool {670 height := len(marks)671 width := len(marks[0])672 conflicts := make([][]bool, height)673 for y := range height {674 conflicts[y] = make([]bool, width)675 }676677 for y := 0; y < height-1; y++ {678 for x := 0; x < width-1; x++ {679 if marks[y][x] == seaCell && marks[y][x+1] == seaCell && marks[y+1][x] == seaCell && marks[y+1][x+1] == seaCell {680 conflicts[y][x] = true681 conflicts[y][x+1] = true682 conflicts[y+1][x] = true683 conflicts[y+1][x+1] = true684 }685 }686 }687688 comps, _ := islandComponents(marks, clues)689 for _, comp := range comps {690 bad := false691 size := len(comp.cells)692 if comp.clueCount > 1 {693 bad = true694 }695 if comp.clueCount == 1 && size > comp.clueValue {696 bad = true697 }698 if comp.clueCount == 0 && !componentCanReachClue(marks, clues, comp) {699 bad = true700 }701 if !hasAnyUnknown(marks) && comp.clueCount == 1 && size != comp.clueValue {702 bad = true703 }704 if bad {705 for _, c := range comp.cells {706 conflicts[c.y][c.x] = true707 }708 }709 }710711 if !hasAnyUnknown(marks) {712 markDisconnectedSeaConflicts(marks, conflicts)713 }714715 return conflicts716}717718func markDisconnectedSeaConflicts(marks grid, conflicts [][]bool) {719 height := len(marks)720 width := len(marks[0])721 visited := make([][]bool, height)722 for y := range height {723 visited[y] = make([]bool, width)724 }725726 var components [][]point727 for y := range height {728 for x := range width {729 if marks[y][x] != seaCell || visited[y][x] {730 continue731 }732 queue := []point{{x, y}}733 visited[y][x] = true734 component := []point{}735 for len(queue) > 0 {736 p := queue[0]737 queue = queue[1:]738 component = append(component, p)739 for _, d := range dirs {740 nx, ny := p.x+d.x, p.y+d.y741 if nx < 0 || ny < 0 || nx >= width || ny >= height {742 continue743 }744 if visited[ny][nx] || marks[ny][nx] != seaCell {745 continue746 }747 visited[ny][nx] = true748 queue = append(queue, point{nx, ny})749 }750 }751 components = append(components, component)752 }753 }754755 if len(components) <= 1 {756 return757 }758759 largestIdx := 0760 largestSize := len(components[0])761 for i := 1; i < len(components); i++ {762 if len(components[i]) > largestSize {763 largestSize = len(components[i])764 largestIdx = i765 }766 }767768 for i, component := range components {769 if i == largestIdx {770 continue771 }772 for _, c := range component {773 conflicts[c.y][c.x] = true774 }775 }776}