imprimersudoku/app/lib/sudoku.ts

// Sudoku generator - generates valid, solvable puzzles

export type Grid = number[][]; // 0 = empty cell, 1-9 = filled

export type Difficulty = "facile" | "moyen" | "difficile" | "expert";

const DIFFICULTY_LABELS: Record<Difficulty, string> = {
  facile: "Facile",
  moyen: "Moyen",
  difficile: "Difficile",
  expert: "Expert",
};

export function getDifficultyLabel(d: Difficulty): string {
  return DIFFICULTY_LABELS[d];
}

// Number of cells to remove per difficulty
const CELLS_TO_REMOVE: Record<Difficulty, number> = {
  facile: 36,
  moyen: 46,
  difficile: 52,
  expert: 58,
};

function shuffleArray<T>(arr: T[]): T[] {
  const a = [...arr];
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function createEmptyGrid(): Grid {
  return Array.from({ length: 9 }, () => Array(9).fill(0));
}

function cloneGrid(grid: Grid): Grid {
  return grid.map((row) => [...row]);
}

function isValid(grid: Grid, row: number, col: number, num: number): boolean {
  // Check row
  for (let c = 0; c < 9; c++) {
    if (grid[row][c] === num) return false;
  }
  // Check column
  for (let r = 0; r < 9; r++) {
    if (grid[r][col] === num) return false;
  }
  // Check 3x3 box
  const boxRow = Math.floor(row / 3) * 3;
  const boxCol = Math.floor(col / 3) * 3;
  for (let r = boxRow; r < boxRow + 3; r++) {
    for (let c = boxCol; c < boxCol + 3; c++) {
      if (grid[r][c] === num) return false;
    }
  }
  return true;
}

// Fill the grid completely using backtracking with randomization
function fillGrid(grid: Grid): boolean {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (grid[row][col] === 0) {
        const nums = shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]);
        for (const num of nums) {
          if (isValid(grid, row, col, num)) {
            grid[row][col] = num;
            if (fillGrid(grid)) return true;
            grid[row][col] = 0;
          }
        }
        return false;
      }
    }
  }
  return true;
}

// Count solutions (stop at 2 to check uniqueness)
function countSolutions(grid: Grid, limit: number = 2): number {
  let count = 0;

  function solve(g: Grid): boolean {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (g[row][col] === 0) {
          for (let num = 1; num <= 9; num++) {
            if (isValid(g, row, col, num)) {
              g[row][col] = num;
              if (solve(g)) {
                if (count >= limit) return true;
              }
              g[row][col] = 0;
            }
          }
          return false;
        }
      }
    }
    count++;
    return count >= limit;
  }

  solve(cloneGrid(grid));
  return count;
}

// Generate a puzzle by removing cells from a complete grid
function generatePuzzle(
  solution: Grid,
  difficulty: Difficulty
): Grid {
  const puzzle = cloneGrid(solution);
  const toRemove = CELLS_TO_REMOVE[difficulty];

  // Create list of all cell positions and shuffle
  const positions: [number, number][] = [];
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      positions.push([r, c]);
    }
  }
  const shuffled = shuffleArray(positions);

  let removed = 0;
  for (const [r, c] of shuffled) {
    if (removed >= toRemove) break;

    const backup = puzzle[r][c];
    puzzle[r][c] = 0;

    // For easier difficulties, always verify uniqueness
    // For expert, we relax after enough removals to speed up generation
    if (difficulty === "expert" && removed > 45) {
      removed++;
      continue;
    }

    if (countSolutions(puzzle) !== 1) {
      puzzle[r][c] = backup; // restore - would create multiple solutions
    } else {
      removed++;
    }
  }

  return puzzle;
}

export interface SudokuPuzzle {
  puzzle: Grid;
  solution: Grid;
}

// Generate a single sudoku puzzle
export function generateSudoku(difficulty: Difficulty): SudokuPuzzle {
  const solution = createEmptyGrid();
  fillGrid(solution);
  const puzzle = generatePuzzle(solution, difficulty);
  return { puzzle, solution };
}

// Generate multiple sudoku puzzles
export function generateSudokus(
  difficulty: Difficulty,
  count: number = 6
): SudokuPuzzle[] {
  const puzzles: SudokuPuzzle[] = [];
  for (let i = 0; i < count; i++) {
    puzzles.push(generateSudoku(difficulty));
  }
  return puzzles;
}