1package hashiwokakero23import (4 "errors"5 "math/rand/v2"6)78const maxGenerateAttempts = 200910type islandPair struct {11 id1 int12 id2 int13}1415// GeneratePuzzle creates a solvable hashiwokakero puzzle for the given mode.16func GeneratePuzzle(mode HashiMode) (Puzzle, error) {17 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))18 return GeneratePuzzleSeeded(mode, rng)19}2021func GeneratePuzzleSeeded(mode HashiMode, rng *rand.Rand) (Puzzle, error) {22 islandCount := mode.MinIslands + rng.IntN(mode.MaxIslands-mode.MinIslands+1)2324 for range maxGenerateAttempts {25 p := tryGenerateSeeded(mode.Width, mode.Height, islandCount, rng)26 if p != nil {27 return *p, nil28 }29 }30 return Puzzle{}, errors.New("failed to generate puzzle after maximum attempts")31}3233func tryGenerateSeeded(width, height, islandCount int, rng *rand.Rand) *Puzzle {34 islands := placeIslandsSeeded(width, height, islandCount, rng)35 if islands == nil {36 return nil37 }3839 p := &Puzzle{40 Width: width,41 Height: height,42 Islands: islands,43 }4445 pairs := connectableIslandPairs(p)46 if !buildSpanningTreeWithPairsSeeded(p, pairs, rng) {47 return nil48 }4950 addExtraBridgesWithPairsSeeded(p, pairs, rng)5152 for i := range p.Islands {53 p.Islands[i].Required = p.BridgeCount(p.Islands[i].ID)54 }5556 for _, isl := range p.Islands {57 if isl.Required < 1 {58 return nil59 }60 }6162 p.Bridges = nil63 p.invalidateCache()6465 return p66}6768// placeIslands randomly places islands on the grid.69// Islands must share rows or columns with at least one other island to allow bridges.70func placeIslands(width, height, count int) []Island {71 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))72 return placeIslandsSeeded(width, height, count, rng)73}7475func placeIslandsSeeded(width, height, count int, rng *rand.Rand) []Island {76 if count <= 0 {77 return nil78 }7980 type pos struct{ x, y int }81 occupied := make(map[pos]bool)82 islands := make([]Island, 0, count)8384 for i := range count {85 placed := false86 for range 200 {87 x := rng.IntN(width)88 y := rng.IntN(height)89 p := pos{x, y}9091 if occupied[p] {92 continue93 }9495 // Ensure minimum spacing of 2 cells from existing islands96 // (unless they share a row/column, which is required for bridges)97 tooClose := false98 for _, other := range islands {99 dx := abs(x - other.X)100 dy := abs(y - other.Y)101 // Adjacent diagonal — too close and can't bridge102 if dx <= 1 && dy <= 1 && !(dx == 0 || dy == 0) {103 tooClose = true104 break105 }106 // Same position as existing (already checked by occupied map)107 }108 if tooClose {109 continue110 }111112 occupied[p] = true113 islands = append(islands, Island{ID: i, X: x, Y: y})114 placed = true115 break116 }117 if !placed {118 return nil // couldn't place enough islands119 }120 }121122 return islands123}124125// buildSpanningTreeSeeded connects all islands using a randomized approach.126// Returns false if unable to connect all islands.127func buildSpanningTreeSeeded(p *Puzzle, rng *rand.Rand) bool {128 return buildSpanningTreeWithPairsSeeded(p, connectableIslandPairs(p), rng)129}130131func connectableIslandPairs(p *Puzzle) []islandPair {132 pairs := make([]islandPair, 0, len(p.Islands)*2)133 for i := range len(p.Islands) {134 for j := i + 1; j < len(p.Islands); j++ {135 a := p.Islands[i]136 b := p.Islands[j]137138 if a.X != b.X && a.Y != b.Y {139 continue // not aligned140 }141142 if isDirectlyConnectable(p, a, b) {143 pairs = append(pairs, islandPair{id1: a.ID, id2: b.ID})144 }145 }146 }147 return pairs148}149150func buildSpanningTreeWithPairsSeeded(p *Puzzle, pairs []islandPair, rng *rand.Rand) bool {151 if len(p.Islands) <= 1 {152 return true153 }154 if len(pairs) == 0 {155 return false156 }157158 order := make([]islandPair, len(pairs))159 copy(order, pairs)160161 rng.Shuffle(len(order), func(i, j int) {162 order[i], order[j] = order[j], order[i]163 })164165 // Union-Find to build spanning tree166 parent := make(map[int]int)167 rank := make(map[int]int)168 for _, isl := range p.Islands {169 parent[isl.ID] = isl.ID170 }171172 var find func(int) int173 find = func(x int) int {174 if parent[x] != x {175 parent[x] = find(parent[x])176 }177 return parent[x]178 }179 union := func(a, b int) bool {180 ra, rb := find(a), find(b)181 if ra == rb {182 return false183 }184 if rank[ra] < rank[rb] {185 ra, rb = rb, ra186 }187 parent[rb] = ra188 if rank[ra] == rank[rb] {189 rank[ra]++190 }191 return true192 }193194 edgesAdded := 0195 for _, pr := range order {196 if find(pr.id1) == find(pr.id2) {197 continue198 }199 // Check if this bridge would cross existing ones200 if p.WouldCross(pr.id1, pr.id2) {201 continue202 }203 count := 1 + rng.IntN(2) // 1 or 2 bridges204 p.SetBridge(pr.id1, pr.id2, count)205 union(pr.id1, pr.id2)206 edgesAdded++207 if edgesAdded == len(p.Islands)-1 {208 break209 }210 }211212 return p.IsConnected()213}214215// addExtraBridgesSeeded adds additional bridges beyond the spanning tree for complexity.216func addExtraBridgesSeeded(p *Puzzle, rng *rand.Rand) {217 addExtraBridgesWithPairsSeeded(p, connectableIslandPairs(p), rng)218}219220func addExtraBridgesWithPairsSeeded(p *Puzzle, pairs []islandPair, rng *rand.Rand) {221 eligible := make([]islandPair, 0, len(pairs))222 degrees := make(map[int]int, len(p.Islands))223 for _, bridge := range p.Bridges {224 degrees[bridge.Island1] += bridge.Count225 degrees[bridge.Island2] += bridge.Count226 }227228 for _, pr := range pairs {229 existing := p.GetBridge(pr.id1, pr.id2)230 if existing != nil && existing.Count >= 2 {231 continue // already maxed232 }233 eligible = append(eligible, pr)234 }235236 rng.Shuffle(len(eligible), func(i, j int) {237 eligible[i], eligible[j] = eligible[j], eligible[i]238 })239240 // Add bridges to ~30% of eligible pairs241 limit := len(eligible) / 3242 added := 0243 for _, pr := range eligible {244 if added >= limit {245 break246 }247248 existing := p.GetBridge(pr.id1, pr.id2)249 if existing != nil && existing.Count >= 2 {250 continue251 }252253 if existing == nil && p.WouldCross(pr.id1, pr.id2) {254 continue255 }256257 newCount := 1258 if existing != nil {259 newCount = existing.Count + 1260 }261262 // Don't let any island exceed 8 bridges263 addAmount := newCount264 if existing != nil {265 addAmount = newCount - existing.Count266 }267 if degrees[pr.id1]+addAmount > 8 || degrees[pr.id2]+addAmount > 8 {268 continue269 }270271 p.SetBridge(pr.id1, pr.id2, newCount)272 degrees[pr.id1] += addAmount273 degrees[pr.id2] += addAmount274 added++275 }276}277278// isDirectlyConnectable checks if two aligned islands can be connected279// (no other island sits between them).280func isDirectlyConnectable(p *Puzzle, a, b Island) bool {281 if a.X == b.X {282 // Vertical alignment283 minY, maxY := a.Y, b.Y284 if minY > maxY {285 minY, maxY = maxY, minY286 }287 for _, isl := range p.Islands {288 if isl.X == a.X && isl.Y > minY && isl.Y < maxY {289 return false290 }291 }292 return true293 }294 if a.Y == b.Y {295 // Horizontal alignment296 minX, maxX := a.X, b.X297 if minX > maxX {298 minX, maxX = maxX, minX299 }300 for _, isl := range p.Islands {301 if isl.Y == a.Y && isl.X > minX && isl.X < maxX {302 return false303 }304 }305 return true306 }307 return false308}309310func abs(x int) int {311 if x < 0 {312 return -x313 }314 return x315}