1package hitori23func propagateRequiredMarks(numbers grid, userMarks [][]cellMark, size int) [][]cellMark {4 marks := cloneMarks(userMarks)5 forceWhiteNeighborsFromDrivers(marks, userMarks, size)6 forceDuplicateGroupsInRows(numbers, marks, userMarks, size)7 forceDuplicateGroupsInCols(numbers, marks, userMarks, size)8 return marks9}1011func forceWhiteNeighborsFromDrivers(marks, drivers [][]cellMark, size int) {12 dirs := [4]cellPos{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}1314 for y := range size {15 for x := range size {16 if drivers[y][x] != shaded {17 continue18 }1920 for _, d := range dirs {21 nx, ny := x+d.x, y+d.y22 if nx < 0 || nx >= size || ny < 0 || ny >= size {23 continue24 }25 if marks[ny][nx] != unmarked {26 continue27 }28 marks[ny][nx] = circled29 }30 }31 }32}3334func forceDuplicateGroupsInRows(numbers grid, marks, drivers [][]cellMark, size int) {35 for y := range size {36 seen := map[rune][]cellPos{}37 for x := range size {38 num := numbers[y][x]39 seen[num] = append(seen[num], cellPos{x, y})40 }41 for _, positions := range seen {42 forceDuplicateGroup(marks, drivers, positions)43 }44 }45}4647func forceDuplicateGroupsInCols(numbers grid, marks, drivers [][]cellMark, size int) {48 for x := range size {49 seen := map[rune][]cellPos{}50 for y := range size {51 num := numbers[y][x]52 seen[num] = append(seen[num], cellPos{x, y})53 }54 for _, positions := range seen {55 forceDuplicateGroup(marks, drivers, positions)56 }57 }58}5960func forceDuplicateGroup(marks, drivers [][]cellMark, positions []cellPos) {61 if len(positions) <= 1 {62 return63 }6465 anyCircled := false66 nonShadedCount := 067 survivor := cellPos{-1, -1}6869 for _, p := range positions {70 switch drivers[p.y][p.x] {71 case circled:72 anyCircled = true73 nonShadedCount++74 survivor = p75 case unmarked:76 nonShadedCount++77 survivor = p78 }79 }8081 if anyCircled {82 for _, p := range positions {83 if marks[p.y][p.x] != unmarked {84 continue85 }86 marks[p.y][p.x] = shaded87 }88 }8990 if nonShadedCount == 1 && survivor.x >= 0 && marks[survivor.y][survivor.x] == unmarked {91 marks[survivor.y][survivor.x] = circled92 }93}9495// hasNoDuplicatesInRows returns true if no row contains a duplicate number96// among the non-shaded cells.97func hasNoDuplicatesInRows(numbers grid, marks [][]cellMark, size int) bool {98 for y := range size {99 seen := map[rune]bool{}100 for x := range size {101 if marks[y][x] == shaded {102 continue103 }104 num := numbers[y][x]105 if seen[num] {106 return false107 }108 seen[num] = true109 }110 }111 return true112}113114// hasNoDuplicatesInCols returns true if no column contains a duplicate number115// among the non-shaded cells.116func hasNoDuplicatesInCols(numbers grid, marks [][]cellMark, size int) bool {117 for x := range size {118 seen := map[rune]bool{}119 for y := range size {120 if marks[y][x] == shaded {121 continue122 }123 num := numbers[y][x]124 if seen[num] {125 return false126 }127 seen[num] = true128 }129 }130 return true131}132133// hasNoAdjacentShaded returns true if no two shaded cells share an edge.134func hasNoAdjacentShaded(marks [][]cellMark, size int) bool {135 for y := range size {136 for x := range size {137 if marks[y][x] != shaded {138 continue139 }140 if x > 0 && marks[y][x-1] == shaded {141 return false142 }143 if x < size-1 && marks[y][x+1] == shaded {144 return false145 }146 if y > 0 && marks[y-1][x] == shaded {147 return false148 }149 if y < size-1 && marks[y+1][x] == shaded {150 return false151 }152 }153 }154 return true155}156157// allWhiteConnected returns true if all non-shaded cells form a single158// orthogonally connected region. Uses BFS.159func allWhiteConnected(marks [][]cellMark, size int) bool {160 startX, startY := -1, -1161 whiteCount := 0162 for y := range size {163 for x := range size {164 if marks[y][x] != shaded {165 whiteCount++166 if startX == -1 {167 startX, startY = x, y168 }169 }170 }171 }172173 if whiteCount <= 1 {174 return true175 }176177 // BFS from the first white cell.178 type pos struct{ x, y int }179 visited := make([][]bool, size)180 for y := range size {181 visited[y] = make([]bool, size)182 }183184 queue := []pos{{startX, startY}}185 visited[startY][startX] = true186 visitedCount := 1187188 dirs := [4]pos{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}189 for len(queue) > 0 {190 curr := queue[0]191 queue = queue[1:]192193 for _, d := range dirs {194 nx, ny := curr.x+d.x, curr.y+d.y195 if nx >= 0 && nx < size && ny >= 0 && ny < size &&196 !visited[ny][nx] && marks[ny][nx] != shaded {197 visited[ny][nx] = true198 visitedCount++199 queue = append(queue, pos{nx, ny})200 }201 }202 }203204 return visitedCount == whiteCount205}206207// isValidSolution checks all three Hitori constraints.208func isValidSolution(numbers grid, marks [][]cellMark, size int) bool {209 return hasNoDuplicatesInRows(numbers, marks, size) &&210 hasNoDuplicatesInCols(numbers, marks, size) &&211 hasNoAdjacentShaded(marks, size) &&212 allWhiteConnected(marks, size)213}214215// computeConflicts returns a grid of booleans indicating which cells are216// involved in a rule violation. A cell is flagged if it participates in a217// row/column duplicate among unshaded cells, if it is a shaded cell adjacent218// to another shaded cell, or if it is an unshaded cell disconnected from the219// largest connected white region.220func computeConflicts(numbers grid, marks [][]cellMark, size int) [][]bool {221 conflicts := make([][]bool, size)222 for y := range size {223 conflicts[y] = make([]bool, size)224 }225226 markDuplicateConflicts(numbers, marks, conflicts, size)227 markAdjacentShadedConflicts(marks, conflicts, size)228 markDisconnectedWhiteConflicts(marks, conflicts, size)229230 return conflicts231}232233// markDuplicateConflicts flags unshaded cells that share a number with234// another unshaded cell in the same row or column. A duplicate group is235// only flagged when at least one cell in the group is circled, so that236// the initial board is not immediately flooded with conflict markers.237func markDuplicateConflicts(numbers grid, marks [][]cellMark, conflicts [][]bool, size int) {238 for y := range size {239 seen := map[rune][]int{}240 for x := range size {241 if marks[y][x] == shaded {242 continue243 }244 num := numbers[y][x]245 seen[num] = append(seen[num], x)246 }247 for _, positions := range seen {248 if len(positions) <= 1 {249 continue250 }251 anyCircled := false252 for _, x := range positions {253 if marks[y][x] == circled {254 anyCircled = true255 break256 }257 }258 if anyCircled {259 for _, x := range positions {260 conflicts[y][x] = true261 }262 }263 }264 }265266 for x := range size {267 seen := map[rune][]int{}268 for y := range size {269 if marks[y][x] == shaded {270 continue271 }272 num := numbers[y][x]273 seen[num] = append(seen[num], y)274 }275 for _, positions := range seen {276 if len(positions) <= 1 {277 continue278 }279 anyCircled := false280 for _, y := range positions {281 if marks[y][x] == circled {282 anyCircled = true283 break284 }285 }286 if anyCircled {287 for _, y := range positions {288 conflicts[y][x] = true289 }290 }291 }292 }293}294295// markAdjacentShadedConflicts flags shaded cells that share an edge with296// another shaded cell.297func markAdjacentShadedConflicts(marks [][]cellMark, conflicts [][]bool, size int) {298 for y := range size {299 for x := range size {300 if marks[y][x] != shaded {301 continue302 }303 if x > 0 && marks[y][x-1] == shaded {304 conflicts[y][x] = true305 conflicts[y][x-1] = true306 }307 if y > 0 && marks[y-1][x] == shaded {308 conflicts[y][x] = true309 conflicts[y-1][x] = true310 }311 }312 }313}314315// markDisconnectedWhiteConflicts flags unshaded cells that are not part of the316// largest orthogonally connected white region.317func markDisconnectedWhiteConflicts(marks [][]cellMark, conflicts [][]bool, size int) {318 // Find all connected components of unshaded cells via BFS.319 type pos struct{ x, y int }320 visited := make([][]bool, size)321 for y := range size {322 visited[y] = make([]bool, size)323 }324325 dirs := [4]pos{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}326 var components [][]pos327328 for sy := range size {329 for sx := range size {330 if marks[sy][sx] == shaded || visited[sy][sx] {331 continue332 }333 // BFS to find this component.334 var component []pos335 queue := []pos{{sx, sy}}336 visited[sy][sx] = true337 for len(queue) > 0 {338 curr := queue[0]339 queue = queue[1:]340 component = append(component, curr)341 for _, d := range dirs {342 nx, ny := curr.x+d.x, curr.y+d.y343 if nx >= 0 && nx < size && ny >= 0 && ny < size &&344 !visited[ny][nx] && marks[ny][nx] != shaded {345 visited[ny][nx] = true346 queue = append(queue, pos{nx, ny})347 }348 }349 }350 components = append(components, component)351 }352 }353354 if len(components) <= 1 {355 return356 }357358 // Find the largest component.359 largest := 0360 for i, comp := range components {361 if len(comp) > len(components[largest]) {362 largest = i363 }364 }365366 // Mark all cells NOT in the largest component as conflicts.367 for i, comp := range components {368 if i == largest {369 continue370 }371 for _, p := range comp {372 conflicts[p.y][p.x] = true373 }374 }375}