1package takuzuplus23import (4 "cmp"5 "image"6 "math"7 "math/rand/v2"8 "slices"910 "github.com/FelineStateMachine/puzzletea/takuzu"11)1213type cellPos struct{ x, y int }1415type relationCandidate struct {16 horizontal bool17 x, y int18}1920type relationChoice struct {21 candidate relationCandidate22 remove cellPos23 additive bool24 endpointClass int25 symbol rune26 score int27}2829func generateComplete(size int) grid {30 return grid(takuzu.GenerateCompleteGrid(size))31}3233func generateCompleteSeeded(size int, rng *rand.Rand) grid {34 return grid(takuzu.GenerateCompleteGridSeeded(size, rng))35}3637func generatePuzzle(complete grid, size int, prefilled float64, profile relationProfile) (grid, [][]bool, relations) {38 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))39 return generatePuzzleSeeded(complete, size, prefilled, profile, rng)40}4142func generatePuzzleSeeded(complete grid, size int, prefilled float64, profile relationProfile, rng *rand.Rand) (grid, [][]bool, relations) {43 maxAttempts := 1044 switch {45 case size >= 14:46 maxAttempts = 347 case size >= 12:48 maxAttempts = 649 }5051 bestPenalty := math.MaxInt52 var bestPuzzle grid53 var bestProvided [][]bool54 var bestRelations relations5556 for attempt := 0; attempt < maxAttempts; attempt++ {57 desiredRelations := profile.targetCount(rng)58 puzzle, provided, rels := generatePuzzleAttempt(complete, size, prefilled, profile, desiredRelations, rng)59 penalty := relationPenalty(profile, size, rels, provided)60 if penalty < bestPenalty {61 bestPenalty = penalty62 bestPuzzle = puzzle.clone()63 bestProvided = cloneProvided(provided)64 bestRelations = rels.clone()65 }66 if penalty == 0 {67 return puzzle, provided, rels68 }69 }7071 return bestPuzzle, bestProvided, bestRelations72}7374func generatePuzzleAttempt(75 complete grid,76 size int,77 prefilled float64,78 profile relationProfile,79 desiredRelations int,80 rng *rand.Rand,81) (grid, [][]bool, relations) {82 puzzle := complete.clone()83 provided := make([][]bool, size)84 for y := range size {85 provided[y] = make([]bool, size)86 for x := range size {87 provided[y][x] = true88 }89 }90 rels := newRelations(size)9192 targetFilled := int(prefilled * float64(size*size))93 filled := size * size9495 for filled > targetFilled {96 progress := false97 cells := providedCells(provided)98 rng.Shuffle(len(cells), func(i, j int) {99 cells[i], cells[j] = cells[j], cells[i]100 })101102 for _, cell := range cells {103 if !provided[cell.y][cell.x] || filled <= targetFilled {104 continue105 }106107 remainingRemovals := filled - targetFilled108 relationShortage := desiredRelations - countRelations(rels)109 preferRelation := countRelations(rels) < profile.MaxRelations &&110 shouldPreferRelationRemoval(relationShortage, remainingRemovals, rng)111112 if preferRelation {113 if tryRelationRemoval(puzzle, complete, provided, rels, size, profile, cell, rng) {114 filled--115 progress = true116 continue117 }118 }119120 if tryDirectRemoval(puzzle, provided, rels, size, cell) {121 filled--122 progress = true123 continue124 }125126 if !preferRelation && countRelations(rels) < profile.MaxRelations &&127 tryRelationRemoval(puzzle, complete, provided, rels, size, profile, cell, rng) {128 filled--129 progress = true130 }131 }132133 if !progress {134 break135 }136 }137138 for countRelations(rels) < desiredRelations {139 if !tryPostPassRelationRemoval(puzzle, complete, provided, rels, size, profile, rng) {140 break141 }142 filled--143 }144145 for countRelations(rels) < profile.MinRelations || additiveRelationsNeeded(profile, size, rels, provided) {146 if countRelations(rels) >= profile.MaxRelations {147 break148 }149 if !tryAdditiveRelation(complete, provided, rels, size, profile, rng) {150 break151 }152 }153154 return puzzle, provided, rels155}156157func shouldPreferRelationRemoval(relationShortage, remainingRemovals int, rng *rand.Rand) bool {158 if relationShortage <= 0 || remainingRemovals <= 0 {159 return false160 }161 if remainingRemovals <= relationShortage {162 return true163 }164 return rng.IntN(remainingRemovals) < relationShortage165}166167func tryDirectRemoval(puzzle grid, provided [][]bool, rels relations, size int, cell cellPos) bool {168 saved := puzzle[cell.y][cell.x]169 puzzle[cell.y][cell.x] = emptyCell170 if countSolutions(puzzle, size, 2, rels) == 1 {171 provided[cell.y][cell.x] = false172 return true173 }174 puzzle[cell.y][cell.x] = saved175 return false176}177178func tryRelationRemoval(179 puzzle, complete grid,180 provided [][]bool,181 rels relations,182 size int,183 profile relationProfile,184 remove cellPos,185 rng *rand.Rand,186) bool {187 choices := scoredRelationChoices(complete, provided, rels, size, profile, remove, false)188 if len(choices) == 0 {189 return false190 }191 shuffleTopTies(choices, rng)192193 for _, choice := range choices {194 applyRelationCandidate(rels, choice.candidate, complete)195 saved := puzzle[remove.y][remove.x]196 puzzle[remove.y][remove.x] = emptyCell197 if countSolutions(puzzle, size, 2, rels) == 1 {198 provided[remove.y][remove.x] = false199 return true200 }201 puzzle[remove.y][remove.x] = saved202 clearRelationCandidate(rels, choice.candidate)203 }204205 return false206}207208func tryPostPassRelationRemoval(209 puzzle, complete grid,210 provided [][]bool,211 rels relations,212 size int,213 profile relationProfile,214 rng *rand.Rand,215) bool {216 cells := providedCells(provided)217 rng.Shuffle(len(cells), func(i, j int) {218 cells[i], cells[j] = cells[j], cells[i]219 })220221 for _, cell := range cells {222 if tryRelationRemoval(puzzle, complete, provided, rels, size, profile, cell, rng) {223 return true224 }225 }226 return false227}228229func tryAdditiveRelation(230 complete grid,231 provided [][]bool,232 rels relations,233 size int,234 profile relationProfile,235 rng *rand.Rand,236) bool {237 choices := additiveRelationChoices(complete, provided, rels, size, profile)238 if len(choices) == 0 {239 return false240 }241 shuffleTopTies(choices, rng)242 applyRelationCandidate(rels, choices[0].candidate, complete)243 return true244}245246func scoredRelationChoices(247 complete grid,248 provided [][]bool,249 rels relations,250 size int,251 profile relationProfile,252 remove cellPos,253 additive bool,254) []relationChoice {255 candidates := adjacentRelationCandidates(rels, remove.x, remove.y, size)256 if len(candidates) == 0 {257 return nil258 }259260 metrics := analyzeRelations(rels, provided, size)261 choices := make([]relationChoice, 0, len(candidates))262 for _, candidate := range candidates {263 ax, ay, bx, by := relationEndpoints(candidate)264 otherProvided := false265 if ax == remove.x && ay == remove.y {266 otherProvided = provided[by][bx]267 } else {268 otherProvided = provided[ay][ax]269 }270271 endpoint := endpointZeroProvided272 if otherProvided {273 endpoint = endpointOneProvided274 }275276 choice := relationChoice{277 candidate: candidate,278 remove: remove,279 additive: additive,280 endpointClass: endpoint,281 symbol: relationSymbol(complete, candidate),282 }283 choice.score = relationChoiceScore(choice, profile, metrics, size)284 choices = append(choices, choice)285 }286287 slices.SortFunc(choices, func(a, b relationChoice) int {288 return cmp.Compare(b.score, a.score)289 })290 return choices291}292293func additiveRelationChoices(294 complete grid,295 provided [][]bool,296 rels relations,297 size int,298 profile relationProfile,299) []relationChoice {300 metrics := analyzeRelations(rels, provided, size)301 choices := make([]relationChoice, 0, 2*size*(size-1))302 for _, candidate := range allUnusedRelationCandidates(rels, size) {303 ax, ay, bx, by := relationEndpoints(candidate)304 endpoint := endpointClass(boolInt(provided[ay][ax]) + boolInt(provided[by][bx]))305 choice := relationChoice{306 candidate: candidate,307 additive: true,308 endpointClass: endpoint,309 symbol: relationSymbol(complete, candidate),310 }311 choice.score = relationChoiceScore(choice, profile, metrics, size)312 if endpoint == endpointTwoProvided {313 choice.score += 5314 }315 choices = append(choices, choice)316 }317318 slices.SortFunc(choices, func(a, b relationChoice) int {319 return cmp.Compare(b.score, a.score)320 })321 return choices322}323324func relationChoiceScore(choice relationChoice, profile relationProfile, metrics relationMetrics, size int) int {325 score := 0326 score += profile.EndpointWeights[choice.endpointClass] * 10327328 band := profile.EndpointBands[choice.endpointClass]329 currentRatio := ratioForCount(metrics.EndpointCounts[choice.endpointClass], metrics.Total)330 targetMid := (band.Min + band.Max) / 2331 if currentRatio < band.Min {332 score += 18333 } else {334 score -= int(math.Round(math.Abs(currentRatio-targetMid) * 20))335 }336337 if metrics.Total > 0 {338 if choice.symbol == relationSame && metrics.SameCount < metrics.DifferentCount {339 score += 6340 }341 if choice.symbol == relationDiff && metrics.DifferentCount < metrics.SameCount {342 score += 6343 }344 if choice.candidate.horizontal && metrics.HorizontalCount < metrics.VerticalCount {345 score += 4346 }347 if !choice.candidate.horizontal && metrics.VerticalCount < metrics.HorizontalCount {348 score += 4349 }350 }351352 pos := relationPosition(choice.candidate)353 if profile.MinSpacing > 0 {354 minGap := minDistance(metrics.Positions, pos)355 if minGap >= profile.MinSpacing {356 score += minGap357 } else {358 score -= 12 * (profile.MinSpacing - minGap + 1)359 }360 }361362 if profile.MinRegions > 0 {363 bit := relationRegionBit(size, pos)364 if metrics.RegionMask&bit == 0 {365 score += 8366 }367 }368369 rowSpreadBonus := 0370 if choice.candidate.horizontal {371 rowSpreadBonus = 2372 }373 score += rowSpreadBonus374375 return score376}377378func additiveRelationsNeeded(profile relationProfile, size int, rels relations, provided [][]bool) bool {379 metrics := analyzeRelations(rels, provided, size)380 if metrics.Total < profile.MinRelations {381 return true382 }383 if metrics.Total == 0 {384 return false385 }386 twoBand := profile.EndpointBands[endpointTwoProvided]387 if !ratioWithinBand(metrics.EndpointCounts[endpointTwoProvided], metrics.Total, twoBand) &&388 ratioForCount(metrics.EndpointCounts[endpointTwoProvided], metrics.Total) < twoBand.Min {389 return true390 }391 return false392}393394func adjacentRelationCandidates(rels relations, x, y, size int) []relationCandidate {395 candidates := make([]relationCandidate, 0, 4)396 if x > 0 && rels.horizontal[y][x-1] == relationNone {397 candidates = append(candidates, relationCandidate{horizontal: true, x: x - 1, y: y})398 }399 if x < size-1 && rels.horizontal[y][x] == relationNone {400 candidates = append(candidates, relationCandidate{horizontal: true, x: x, y: y})401 }402 if y > 0 && rels.vertical[y-1][x] == relationNone {403 candidates = append(candidates, relationCandidate{horizontal: false, x: x, y: y - 1})404 }405 if y < size-1 && rels.vertical[y][x] == relationNone {406 candidates = append(candidates, relationCandidate{horizontal: false, x: x, y: y})407 }408 return candidates409}410411func allUnusedRelationCandidates(rels relations, size int) []relationCandidate {412 candidates := make([]relationCandidate, 0, 2*size*(size-1))413 for y := range size {414 for x := range size - 1 {415 if rels.horizontal[y][x] == relationNone {416 candidates = append(candidates, relationCandidate{horizontal: true, x: x, y: y})417 }418 }419 }420 for y := range size - 1 {421 for x := range size {422 if rels.vertical[y][x] == relationNone {423 candidates = append(candidates, relationCandidate{horizontal: false, x: x, y: y})424 }425 }426 }427 return candidates428}429430func applyRelationCandidate(rels relations, candidate relationCandidate, complete grid) {431 if candidate.horizontal {432 rels.horizontal[candidate.y][candidate.x] = relationForValues(complete[candidate.y][candidate.x], complete[candidate.y][candidate.x+1])433 return434 }435 rels.vertical[candidate.y][candidate.x] = relationForValues(complete[candidate.y][candidate.x], complete[candidate.y+1][candidate.x])436}437438func clearRelationCandidate(rels relations, candidate relationCandidate) {439 if candidate.horizontal {440 rels.horizontal[candidate.y][candidate.x] = relationNone441 return442 }443 rels.vertical[candidate.y][candidate.x] = relationNone444}445446func relationEndpoints(candidate relationCandidate) (ax, ay, bx, by int) {447 if candidate.horizontal {448 return candidate.x, candidate.y, candidate.x + 1, candidate.y449 }450 return candidate.x, candidate.y, candidate.x, candidate.y + 1451}452453func relationPosition(candidate relationCandidate) image.Point {454 if candidate.horizontal {455 return horizontalRelationPosition(candidate.x, candidate.y)456 }457 return verticalRelationPosition(candidate.x, candidate.y)458}459460func relationSymbol(complete grid, candidate relationCandidate) rune {461 ax, ay, bx, by := relationEndpoints(candidate)462 return relationForValues(complete[ay][ax], complete[by][bx])463}464465func providedCells(provided [][]bool) []cellPos {466 size := len(provided)467 cells := make([]cellPos, 0, size*size)468 for y := range size {469 for x := range size {470 if provided[y][x] {471 cells = append(cells, cellPos{x: x, y: y})472 }473 }474 }475 return cells476}477478func cloneProvided(provided [][]bool) [][]bool {479 clone := make([][]bool, len(provided))480 for y := range provided {481 clone[y] = append([]bool(nil), provided[y]...)482 }483 return clone484}485486func minDistance(existing []image.Point, pos image.Point) int {487 if len(existing) == 0 {488 return profileDistanceUnset()489 }490 best := math.MaxInt491 for _, prior := range existing {492 dist := abs(pos.X-prior.X) + abs(pos.Y-prior.Y)493 if dist < best {494 best = dist495 }496 }497 return best498}499500func ratioForCount(count, total int) float64 {501 if total == 0 {502 return 0503 }504 return float64(count) / float64(total)505}506507func shuffleTopTies(choices []relationChoice, rng *rand.Rand) {508 if len(choices) < 2 {509 return510 }511 topScore := choices[0].score512 limit := 1513 for limit < len(choices) && choices[limit].score == topScore {514 limit++515 }516 rng.Shuffle(limit, func(i, j int) {517 choices[i], choices[j] = choices[j], choices[i]518 })519}