1package hashiwokakero23// Island represents a numbered node on the grid.4type Island struct {5 ID int6 X, Y int7 Required int // target bridge count (1-8)8}910// Bridge represents a connection between two islands.11type Bridge struct {12 Island1, Island2 int // island IDs (Island1 < Island2)13 Count int // 1 or 214}1516// cellKind describes what occupies a grid cell.17type cellKind int1819const (20 cellEmpty cellKind = iota21 cellIsland22 cellBridgeH // horizontal bridge segment23 cellBridgeV // vertical bridge segment24)2526// cellInfo is the rendering info for a single grid cell.27type cellInfo struct {28 Kind cellKind29 IslandID int // valid when Kind == cellIsland30 BridgeIdx int // index into Puzzle.Bridges, valid for bridge cells31 BridgeCount int // 1 or 232}3334// Puzzle holds the full game state.35type Puzzle struct {36 Width, Height int37 Islands []Island38 Bridges []Bridge39 cellCache [][]cellInfo // lazily built, invalidated on bridge changes40 posIndex map[[2]int]int // (x,y) → island slice index; lazily built41 bridgeCounts []int // per-island bridge count; lazily built42 bridgeIndex map[[2]int]int // (island1,island2) -> Bridges index; lazily built43}4445// FindIslandAt returns the island at (x,y), or nil.46func (p *Puzzle) FindIslandAt(x, y int) *Island {47 if p.posIndex == nil {48 p.buildPosIndex()49 }50 if idx, ok := p.posIndex[[2]int{x, y}]; ok {51 return &p.Islands[idx]52 }53 return nil54}5556func (p *Puzzle) buildPosIndex() {57 p.posIndex = make(map[[2]int]int, len(p.Islands))58 for i, isl := range p.Islands {59 p.posIndex[[2]int{isl.X, isl.Y}] = i60 }61}6263func bridgeKey(id1, id2 int) [2]int {64 a, b := id1, id265 if a > b {66 a, b = b, a67 }68 return [2]int{a, b}69}7071func (p *Puzzle) buildBridgeIndex() {72 p.bridgeIndex = make(map[[2]int]int, len(p.Bridges))73 for i, b := range p.Bridges {74 p.bridgeIndex[bridgeKey(b.Island1, b.Island2)] = i75 }76}7778// FindIslandByID returns the island with the given ID, or nil.79func (p *Puzzle) FindIslandByID(id int) *Island {80 if id >= 0 && id < len(p.Islands) && p.Islands[id].ID == id {81 return &p.Islands[id]82 }83 // Fallback for non-sequential IDs84 for i := range p.Islands {85 if p.Islands[i].ID == id {86 return &p.Islands[i]87 }88 }89 return nil90}9192// GetBridge returns the bridge between two islands (by ID), or nil.93func (p *Puzzle) GetBridge(id1, id2 int) *Bridge {94 if p.bridgeIndex == nil {95 p.buildBridgeIndex()96 }9798 if idx, ok := p.bridgeIndex[bridgeKey(id1, id2)]; ok {99 if idx >= 0 && idx < len(p.Bridges) {100 return &p.Bridges[idx]101 }102 }103 return nil104}105106// BridgeCount returns the total number of bridges connected to an island.107func (p *Puzzle) BridgeCount(islandID int) int {108 if p.bridgeCounts == nil {109 p.buildBridgeCounts()110 }111 if islandID >= 0 && islandID < len(p.bridgeCounts) {112 return p.bridgeCounts[islandID]113 }114 return 0115}116117func (p *Puzzle) buildBridgeCounts() {118 p.bridgeCounts = make([]int, len(p.Islands))119 for _, b := range p.Bridges {120 if b.Island1 >= 0 && b.Island1 < len(p.bridgeCounts) {121 p.bridgeCounts[b.Island1] += b.Count122 }123 if b.Island2 >= 0 && b.Island2 < len(p.bridgeCounts) {124 p.bridgeCounts[b.Island2] += b.Count125 }126 }127}128129// FindAdjacentIsland casts a ray from the island at fromID in direction (dx,dy)130// and returns the first island hit, or nil. dx/dy must be (0,1),(0,-1),(1,0),(-1,0).131// Stops if a perpendicular bridge crosses the path.132func (p *Puzzle) FindAdjacentIsland(fromID, dx, dy int) *Island {133 from := p.FindIslandByID(fromID)134 if from == nil {135 return nil136 }137 x, y := from.X+dx, from.Y+dy138 for x >= 0 && x < p.Width && y >= 0 && y < p.Height {139 if isl := p.FindIslandAt(x, y); isl != nil {140 return isl141 }142 ci := p.CellContent(x, y)143 if dx == 0 && ci.Kind == cellBridgeH {144 return nil // horizontal bridge blocks vertical ray145 }146 if dy == 0 && ci.Kind == cellBridgeV {147 return nil // vertical bridge blocks horizontal ray148 }149 x += dx150 y += dy151 }152 return nil153}154155// WouldCross checks if adding a bridge between id1 and id2 would cross any existing bridge.156func (p *Puzzle) WouldCross(id1, id2 int) bool {157 isl1 := p.FindIslandByID(id1)158 isl2 := p.FindIslandByID(id2)159 if isl1 == nil || isl2 == nil {160 return true161 }162163 horizontal := isl1.Y == isl2.Y164 vertical := isl1.X == isl2.X165 if !horizontal && !vertical {166 return true // not a valid bridge direction167 }168169 if horizontal {170 y := isl1.Y171 minX, maxX := isl1.X, isl2.X172 if minX > maxX {173 minX, maxX = maxX, minX174 }175 for x := minX + 1; x < maxX; x++ {176 ci := p.CellContent(x, y)177 if ci.Kind == cellIsland || ci.Kind == cellBridgeV {178 return true179 }180 }181 } else {182 x := isl1.X183 minY, maxY := isl1.Y, isl2.Y184 if minY > maxY {185 minY, maxY = maxY, minY186 }187 for y := minY + 1; y < maxY; y++ {188 ci := p.CellContent(x, y)189 if ci.Kind == cellIsland || ci.Kind == cellBridgeH {190 return true191 }192 }193 }194 return false195}196197// SetBridge sets or removes the bridge between two islands.198// count=0 removes the bridge. count must be 0, 1, or 2.199func (p *Puzzle) SetBridge(id1, id2, count int) {200 a, b := id1, id2201 if a > b {202 a, b = b, a203 }204205 p.invalidateBridgeCaches()206 if p.bridgeIndex == nil {207 p.buildBridgeIndex()208 }209 key := bridgeKey(a, b)210211 if count == 0 {212 // Remove bridge213 idx, ok := p.bridgeIndex[key]214 if !ok {215 return216 }217218 p.Bridges = append(p.Bridges[:idx], p.Bridges[idx+1:]...)219 delete(p.bridgeIndex, key)220 for i := idx; i < len(p.Bridges); i++ {221 p.bridgeIndex[bridgeKey(p.Bridges[i].Island1, p.Bridges[i].Island2)] = i222 }223 return224 }225226 // Update or create bridge227 if idx, ok := p.bridgeIndex[key]; ok {228 p.Bridges[idx].Count = count229 return230 }231232 p.Bridges = append(p.Bridges, Bridge{Island1: a, Island2: b, Count: count})233 p.bridgeIndex[key] = len(p.Bridges) - 1234}235236// CellContent returns what occupies the given grid cell, using a lazily-built cache.237func (p *Puzzle) CellContent(x, y int) cellInfo {238 if p.cellCache == nil {239 p.rebuildCellCache()240 }241 return p.cellCache[y][x]242}243244// rebuildCellCache recomputes the full cell grid from islands and bridges.245func (p *Puzzle) rebuildCellCache() {246 cache := make([][]cellInfo, p.Height)247 for y := range cache {248 cache[y] = make([]cellInfo, p.Width)249 }250251 for _, isl := range p.Islands {252 cache[isl.Y][isl.X] = cellInfo{Kind: cellIsland, IslandID: isl.ID}253 }254255 for i, b := range p.Bridges {256 isl1 := p.FindIslandByID(b.Island1)257 isl2 := p.FindIslandByID(b.Island2)258 if isl1 == nil || isl2 == nil {259 continue260 }261262 if isl1.Y == isl2.Y {263 // Horizontal bridge264 minX, maxX := isl1.X, isl2.X265 if minX > maxX {266 minX, maxX = maxX, minX267 }268 for x := minX + 1; x < maxX; x++ {269 cache[isl1.Y][x] = cellInfo{Kind: cellBridgeH, BridgeIdx: i, BridgeCount: b.Count}270 }271 } else if isl1.X == isl2.X {272 // Vertical bridge273 minY, maxY := isl1.Y, isl2.Y274 if minY > maxY {275 minY, maxY = maxY, minY276 }277 for y := minY + 1; y < maxY; y++ {278 cache[y][isl1.X] = cellInfo{Kind: cellBridgeV, BridgeIdx: i, BridgeCount: b.Count}279 }280 }281 }282283 p.cellCache = cache284}285286// invalidateCache marks all lazy caches as stale.287func (p *Puzzle) invalidateCache() {288 p.cellCache = nil289 p.posIndex = nil290 p.bridgeCounts = nil291 p.bridgeIndex = nil292}293294// invalidateBridgeCaches marks bridge-derived caches as stale.295func (p *Puzzle) invalidateBridgeCaches() {296 p.cellCache = nil297 p.bridgeCounts = nil298}299300// IsConnected checks if all islands form a single connected component via bridges.301func (p *Puzzle) IsConnected() bool {302 n := len(p.Islands)303 if n <= 1 {304 return true305 }306 if len(p.Bridges) == 0 {307 return false308 }309310 // Build adjacency list from bridges311 adj := make(map[int][]int, n)312 for _, b := range p.Bridges {313 adj[b.Island1] = append(adj[b.Island1], b.Island2)314 adj[b.Island2] = append(adj[b.Island2], b.Island1)315 }316317 visited := make([]bool, n)318 queue := []int{p.Islands[0].ID}319 visited[p.Islands[0].ID] = true320 count := 1321322 for len(queue) > 0 {323 cur := queue[0]324 queue = queue[1:]325 for _, nb := range adj[cur] {326 if !visited[nb] {327 visited[nb] = true328 count++329 queue = append(queue, nb)330 }331 }332 }333334 return count == n335}336337// IsSolved returns true if the puzzle is completely and correctly solved.338func (p *Puzzle) IsSolved() bool {339 for _, isl := range p.Islands {340 if p.BridgeCount(isl.ID) != isl.Required {341 return false342 }343 }344 return p.IsConnected()345}