termdoku/internal/solver/solver.go

package solver

import "time"

// Grid matches generator's grid representation
type Grid [9][9]uint8

// Solve attempts to fill the grid in-place using backtracking.
// Returns whether a solution was found before timeout.
func Solve(g *Grid, timeout time.Duration) bool {
	deadline := time.Now().Add(timeout)
	return solveBacktrack(g, deadline)
}

// CountSolutions counts up to maxCount solutions for uniqueness check.
func CountSolutions(g Grid, timeout time.Duration, maxCount int) int {
	deadline := time.Now().Add(timeout)
	count := 0
	var dfs func(*Grid) bool
	dfs = func(cur *Grid) bool {
		if time.Now().After(deadline) {
			return true
		}
		// Use most-constrained heuristic for faster counting
		row, col, ok := findMostConstrained(*cur)
		if !ok {
			count++
			return count >= maxCount
		}
		cands := candidates(*cur, row, col)
		if len(cands) == 0 {
			return false
		}
		for _, v := range cands {
			cur[row][col] = v
			if dfs(cur) {
				return true
			}
			cur[row][col] = 0
		}
		return false
	}
	copyGrid := g
	dfs(&copyGrid)
	return count
}

func solveBacktrack(g *Grid, deadline time.Time) bool {
	if time.Now().After(deadline) {
		return false
	}
	// Use most-constrained-first heuristic for better performance
	row, col, ok := findMostConstrained(*g)
	if !ok {
		return true
	}
	cands := candidates(*g, row, col)
	// If no candidates available, this path is invalid
	if len(cands) == 0 {
		return false
	}
	for _, v := range cands {
		g[row][col] = v
		if solveBacktrack(g, deadline) {
			return true
		}
		g[row][col] = 0
	}
	return false
}

func findEmpty(g Grid) (int, int, bool) {
	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if g[r][c] == 0 {
				return r, c, true
			}
		}
	}
	return 0, 0, false
}

// findMostConstrained finds the empty cell with the fewest candidates.
// This heuristic significantly improves solving performance.
func findMostConstrained(g Grid) (int, int, bool) {
	minCands := 10
	bestRow, bestCol := -1, -1
	found := false

	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if g[r][c] == 0 {
				cands := candidates(g, r, c)
				if len(cands) < minCands {
					minCands = len(cands)
					bestRow = r
					bestCol = c
					found = true
					// If we find a cell with only one candidate, use it immediately
					if minCands == 1 {
						return bestRow, bestCol, true
					}
				}
			}
		}
	}

	return bestRow, bestCol, found
}

func candidates(g Grid, row, col int) []uint8 {
	used := [10]bool{}
	for i := 0; i < 9; i++ {
		used[g[row][i]] = true
		used[g[i][col]] = true
	}
	r0 := (row / 3) * 3
	c0 := (col / 3) * 3
	for r := r0; r < r0+3; r++ {
		for c := c0; c < c0+3; c++ {
			used[g[r][c]] = true
		}
	}
	var out []uint8
	for v := 1; v <= 9; v++ {
		if !used[v] {
			out = append(out, uint8(v))
		}
	}
	return out
}

// IsValid checks if the grid is in a valid state (no conflicts).
func IsValid(g Grid) bool {
	// Check rows
	for r := 0; r < 9; r++ {
		seen := [10]bool{}
		for c := 0; c < 9; c++ {
			v := g[r][c]
			if v == 0 {
				continue
			}
			if seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	// Check columns
	for c := 0; c < 9; c++ {
		seen := [10]bool{}
		for r := 0; r < 9; r++ {
			v := g[r][c]
			if v == 0 {
				continue
			}
			if seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	// Check 3x3 blocks
	for br := 0; br < 3; br++ {
		for bc := 0; bc < 3; bc++ {
			seen := [10]bool{}
			for r := br * 3; r < br*3+3; r++ {
				for c := bc * 3; c < bc*3+3; c++ {
					v := g[r][c]
					if v == 0 {
						continue
					}
					if seen[v] {
						return false
					}
					seen[v] = true
				}
			}
		}
	}

	return true
}

// IsSolved checks if the grid is completely filled and valid.
func IsSolved(g Grid) bool {
	if !IsValid(g) {
		return false
	}

	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if g[r][c] == 0 {
				return false
			}
		}
	}

	return true
}

// SolveStep represents a single step in the solving process.
type SolveStep struct {
	Row        int
	Col        int
	Value      uint8
	Candidates []uint8
	StepNumber int
}

// SolveWithSteps solves the puzzle and returns all steps taken.
func SolveWithSteps(g Grid, timeout time.Duration) ([]SolveStep, bool) {
	deadline := time.Now().Add(timeout)
	var steps []SolveStep
	stepNum := 0

	var solve func(*Grid) bool
	solve = func(cur *Grid) bool {
		if time.Now().After(deadline) {
			return false
		}
		row, col, ok := findMostConstrained(*cur)
		if !ok {
			return true
		}
		cands := candidates(*cur, row, col)
		if len(cands) == 0 {
			return false
		}
		for _, v := range cands {
			stepNum++
			steps = append(steps, SolveStep{
				Row:        row,
				Col:        col,
				Value:      v,
				Candidates: cands,
				StepNumber: stepNum,
			})
			cur[row][col] = v
			if solve(cur) {
				return true
			}
			cur[row][col] = 0
		}
		return false
	}

	copyGrid := g
	success := solve(&copyGrid)
	return steps, success
}

// GetAllSolutions returns all possible solutions for a puzzle (up to maxSolutions).
func GetAllSolutions(g Grid, timeout time.Duration, maxSolutions int) []Grid {
	deadline := time.Now().Add(timeout)
	var solutions []Grid

	var dfs func(*Grid)
	dfs = func(cur *Grid) {
		if time.Now().After(deadline) || len(solutions) >= maxSolutions {
			return
		}
		row, col, ok := findMostConstrained(*cur)
		if !ok {
			// Found a solution, save a copy
			var solution Grid
			for r := 0; r < 9; r++ {
				for c := 0; c < 9; c++ {
					solution[r][c] = cur[r][c]
				}
			}
			solutions = append(solutions, solution)
			return
		}
		cands := candidates(*cur, row, col)
		for _, v := range cands {
			cur[row][col] = v
			dfs(cur)
			cur[row][col] = 0
		}
	}

	copyGrid := g
	dfs(&copyGrid)
	return solutions
}