function isValid(grid, row, col, num) {
  for (let c = 0; c < 9; c++) if (grid[row][c] === num) return false;
  for (let r = 0; r < 9; r++) if (grid[r][col] === num) return false;
  const br = Math.floor(row / 3) * 3;
  const bc = Math.floor(col / 3) * 3;
  for (let r = br; r < br + 3; r++)
    for (let c = bc; c < bc + 3; c++)
      if (grid[r][c] === num) return false;
  return true;
}

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

function fillBox(grid, startRow, startCol) {
  const nums = shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9]);
  let idx = 0;
  for (let r = startRow; r < startRow + 3; r++)
    for (let c = startCol; c < startCol + 3; c++)
      grid[r][c] = nums[idx++];
}

function solve(grid) {
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (grid[r][c] === 0) {
        for (const num of shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9])) {
          if (isValid(grid, r, c, num)) {
            grid[r][c] = num;
            if (solve(grid)) return true;
            grid[r][c] = 0;
          }
        }
        return false;
      }
    }
  }
  return true;
}

function generateSolution() {
  const grid = Array.from({ length: 9 }, () => Array(9).fill(0));
  // Seed diagonal boxes first (no inter-box constraints) for faster solve
  fillBox(grid, 0, 0);
  fillBox(grid, 3, 3);
  fillBox(grid, 6, 6);
  solve(grid);
  return grid;
}

function cloneGrid(g) {
  return g.map(row => [...row]);
}

function countGivens(grid) {
  return grid.flat().filter(v => v !== 0).length;
}

const GIVENS = {
  'very-easy': 50,
  'easy':      36,
  'regular':   28,
  'hard':      24,
  'brutal':    18,
};

function digHoles(solution, targetGivens) {
  const grid = cloneGrid(solution);
  const positions = [];
  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++)
      positions.push([r, c]);

  shuffle(positions);

  for (const [r, c] of positions) {
    if (countGivens(grid) <= targetGivens) break;
    const mr = 8 - r, mc = 8 - c;
    if (grid[r][c] === 0 && grid[mr][mc] === 0) continue;
    grid[r][c] = 0;
    if (r !== mr || c !== mc) grid[mr][mc] = 0;
  }

  return grid;
}

export function generatePuzzle(difficulty) {
  const target = GIVENS[difficulty] ?? 28;
  const solution = generateSolution();
  const grid = digHoles(solution, target);
  return { grid, solution, difficulty };
}