1package takuzu23import (4 "context"5 "crypto/sha256"6 "encoding/binary"7 "math"8 "math/rand/v2"9 "strconv"1011 "github.com/FelineStateMachine/puzzletea/difficulty"12 "github.com/FelineStateMachine/puzzletea/game"13)1415var (16 _ game.EloSpawner = TakuzuMode{}17 _ game.CancellableEloSpawner = TakuzuMode{}18)1920type takuzuEloCounterStats struct {21 Nodes int22 Branches int23 MaxDepth int24}2526func (t TakuzuMode) SpawnElo(seed string, elo difficulty.Elo) (game.Gamer, difficulty.Report, error) {27 return t.SpawnEloContext(context.Background(), seed, elo)28}2930func (t TakuzuMode) SpawnEloContext(ctx context.Context, seed string, elo difficulty.Elo) (game.Gamer, difficulty.Report, error) {31 if err := difficulty.ValidateElo(elo); err != nil {32 return nil, difficulty.Report{}, err33 }34 if err := ctx.Err(); err != nil {35 return nil, difficulty.Report{}, err36 }3738 mode := takuzuModeForElo(t, elo)39 rng := takuzuEloRNG(seed, elo)40 complete := GenerateCompleteGridSeeded(mode.Size, rng)41 puzzle, provided := GeneratePuzzleFromCompleteSeeded(complete, mode.Size, mode.Prefilled, rng)4243 gamer, err := New(mode, puzzle, provided)44 if err != nil {45 return nil, difficulty.Report{}, err46 }47 report := scoreTakuzuElo(ctx, elo, puzzle, provided, mode.Prefilled)48 return gamer, report, nil49}5051func takuzuModeForElo(base TakuzuMode, elo difficulty.Elo) TakuzuMode {52 score := difficulty.Score01(elo)53 prefilled := 0.52 - score*0.2454 mode := base55 mode.Prefilled = prefilled56 return mode57}5859func takuzuEloRNG(seed string, elo difficulty.Elo) *rand.Rand {60 sum := sha256.Sum256([]byte("takuzu\x00" + seed + "\x00" + strconv.Itoa(int(elo))))61 return rand.New(rand.NewPCG(62 binary.LittleEndian.Uint64(sum[0:8]),63 binary.LittleEndian.Uint64(sum[8:16]),64 ))65}6667func scoreTakuzuElo(ctx context.Context, target difficulty.Elo, puzzle [][]rune, provided [][]bool, targetPrefilled float64) difficulty.Report {68 solutions, stats := countTakuzuSolutionsWithEloStats(ctx, grid(puzzle).clone(), len(puzzle), 2)69 metrics := takuzuDifficultyMetrics(puzzle, provided, targetPrefilled, solutions, stats)70 confidence := difficulty.ConfidenceHigh71 if solutions < 0 {72 confidence = difficulty.ConfidenceLow73 metrics["solver_limited"] = 174 } else if solutions != 1 {75 confidence = difficulty.ConfidenceLow76 }7778 return difficulty.Report{79 TargetElo: target,80 ActualElo: takuzuActualElo(metrics),81 Confidence: confidence,82 Metrics: metrics,83 }84}8586func takuzuDifficultyMetrics(87 puzzle [][]rune,88 provided [][]bool,89 targetPrefilled float64,90 solutions int,91 stats takuzuEloCounterStats,92) difficulty.Metrics {93 size := len(puzzle)94 cells := size * size95 clues := 096 for y := range provided {97 for x := range provided[y] {98 if provided[y][x] {99 clues++100 }101 }102 }103 empties := cells - clues104105 return difficulty.Metrics{106 "size": float64(size),107 "cells": float64(cells),108 "clue_count": float64(clues),109 "empty_count": float64(empties),110 "clue_density": takuzuRatio(clues, cells),111 "target_prefilled": targetPrefilled,112 "solution_count": float64(solutions),113 "solver_nodes": float64(stats.Nodes),114 "branches": float64(stats.Branches),115 "max_depth": float64(stats.MaxDepth),116 }117}118119func countTakuzuSolutionsWithEloStats(ctx context.Context, g grid, size, limit int) (int, takuzuEloCounterStats) {120 if limit <= 0 {121 return 0, takuzuEloCounterStats{}122 }123 stats := newLineStats(g, size)124 var counter takuzuEloCounterStats125 count := countTakuzuSolutionsRecWithEloStats(ctx, g, size, limit, stats, 0, &counter)126 return count, counter127}128129func countTakuzuSolutionsRecWithEloStats(130 ctx context.Context,131 g grid,132 size int,133 limit int,134 lineStats *lineStats,135 depth int,136 counter *takuzuEloCounterStats,137) int {138 if ctx.Err() != nil {139 return -1140 }141 counter.Nodes++142 if depth > counter.MaxDepth {143 counter.MaxDepth = depth144 }145146 choice := selectMRVCell(g, size, lineStats, nil)147 if choice.x < 0 {148 if hasUniqueLines(g, size) {149 return 1150 }151 return 0152 }153 if choice.count == 0 {154 return 0155 }156 if choice.count > 1 {157 counter.Branches++158 }159160 total := 0161 for i := range choice.count {162 v := choice.vals[i]163 g[choice.y][choice.x] = v164 lineStats.apply(choice.x, choice.y, v, 1)165 n := countTakuzuSolutionsRecWithEloStats(ctx, g, size, limit-total, lineStats, depth+1, counter)166 lineStats.apply(choice.x, choice.y, v, -1)167 g[choice.y][choice.x] = emptyCell168 if n < 0 {169 return n170 }171 total += n172 if total >= limit {173 return total174 }175 }176177 return total178}179180func takuzuActualElo(metrics difficulty.Metrics) difficulty.Elo {181 score := 0.34*takuzuNormalize(metrics["size"], 6, 14) +182 0.28*(1-takuzuNormalize(metrics["clue_density"], 0.28, 0.52)) +183 0.18*takuzuNormalize(metrics["max_depth"], 0, metrics["empty_count"]) +184 0.12*takuzuNormalize(metrics["branches"], 0, metrics["empty_count"]) +185 0.08*takuzuNormalize(metrics["solver_nodes"], 1, math.Max(2, metrics["empty_count"]*3))186187 return difficulty.ClampElo(difficulty.Elo(math.Round(score * float64(difficulty.SoftCapElo))))188}189190func takuzuNormalize(value, low, high float64) float64 {191 if high <= low || value <= low {192 return 0193 }194 if value >= high {195 return 1196 }197 return (value - low) / (high - low)198}199200func takuzuRatio(numerator, denominator int) float64 {201 if denominator == 0 {202 return 0203 }204 return float64(numerator) / float64(denominator)205}