Sudoku Generator

sudoku.js

/**
 * Sudoku Puzzle Generator Module
 */
const SudokuPuzzle = (() => {
    /**
     * Generates a blank Sudoku board of given size.
     * @param {number} size - The size of the Sudoku puzzle, along one axis.
     * @returns {number[][]} A two-dimensional array representing the Sudoku board.
     */
    const generateBoard = (size) => {
      return Array.from({ length: size }, () => Array(size).fill(0));
    };
  
    /**
     * Checks if a number can be safely placed in the specified row.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} row - The row index.
     * @param {number} num - The number to check.
     * @param {number} size - The size of the Sudoku puzzle, along one axis.
     * @returns {boolean} True if the number can be placed, false otherwise.
     */
    const isRowSafe = (board, row, num, size) => {
      return board[row].slice(0, size).every((cell) => cell !== num);
    };
  
    /**
     * Checks if a number can be safely placed in the specified column.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} col - The column index.
     * @param {number} num - The number to check.
     * @param {number} size - The size of the Sudoku puzzle, along one axis.
     * @returns {boolean} True if the number can be placed, false otherwise.
     */
    const isColSafe = (board, col, num, size) => {
      return board.slice(0, size).every((row) => row[col] !== num);
    };
  
    /**
     * Checks if a number can be safely placed in the specified 3x3 box.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} startRow - The starting row index of the box.
     * @param {number} startCol - The starting column index of the box.
     * @param {number} num - The number to check.
     * @param {number} size - The size of the Sudoku puzzle, along one axis.
     * @returns {boolean} True if the number can be placed, false otherwise.
     */
    const isBoxSafe = (board, startRow, startCol, num, boxSize) => {
      for (let row = 0; row < boxSize; row++) {
        for (let col = 0; col < boxSize; col++) {
          if (board[startRow + row][startCol + col] === num) return false;
        }
      }
      return true;
    };
  
    /**
     * Combines the checks for row, column, and box safety.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} row - The row index.
     * @param {number} col - The column index.
     * @param {number} num - The number to check.
     * @param {number} size - The total size of the Sudoku puzzle grid.
     * @returns {boolean} True if the number can be safely placed, false otherwise.
     */
    const isSafe = (board, row, col, num, size) => {
      const boxSize = Math.sqrt(size);
      const boxRow = row - (row % boxSize);
      const boxCol = col - (col % boxSize);
      return (
        isRowSafe(board, row, num, size) &&
        isColSafe(board, col, num, size) &&
        isBoxSafe(board, boxRow, boxCol, num, boxSize)
      );
    };
  
    /**
     * Finds the first empty location on the Sudoku board.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} size - The total size of the Sudoku puzzle grid.
     * @returns {{row: number, col: number} | null} The coordinates of the empty cell, or null if the board is full.
     */
    const findEmptyLocation = (board, size) => {
      for (let row = 0; row < size; row++) {
        for (let col = 0; col < size; col++) {
          if (board[row][col] === 0) return { row, col };
        }
      }
      return null;
    };
  
    /**
     * Solves the Sudoku puzzle using a backtracking algorithm.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} size - The total size of the Sudoku puzzle grid.
     * @returns {boolean} True if the puzzle is solvable, false otherwise.
     */
    const solveSudoku = (board, size) => {
      const emptyCell = findEmptyLocation(board, size);
      if (!emptyCell) return true;
  
      for (let num = 1; num <= size; num++) {
        if (isSafe(board, emptyCell.row, emptyCell.col, num, size)) {
          board[emptyCell.row][emptyCell.col] = num;
  
          if (solveSudoku(board, size)) return true;
  
          board[emptyCell.row][emptyCell.col] = 0;
        }
      }
      return false;
    };
  
    /**
     * Checks if the Sudoku board has multiple solutions.
     * @param {number[][]} board - The Sudoku board.
     * @param {number} count - The number of empty cells to check.
     * @param {number} size - The size of the smaller box in the Sudoku puzzle.
     * @returns {boolean} True if there are multiple solutions, false otherwise.
     */
    const hasMultipleSolutions = (board, count, size) => {
        if (count === 0) return false;

        const emptyCell = findEmptyLocation(board, size);
        if (!emptyCell) return true;

        for (let num = 1; num <= size; num++) {
        if (isSafe(board, emptyCell.row, emptyCell.col, num, size)) {
            board[emptyCell.row][emptyCell.col] = num;

            if (hasMultipleSolutions(board, count - 1, size)) return true;

            board[emptyCell.row][emptyCell.col] = 0;
        }
        }
        return false;
    };


    /**
     * Removes a specified number of digits from the Sudoku board.
     * @param {number[][]} originalBoard - The original Sudoku board.
     * @param {number} percentage - The percentage of digits to remove.
     * @param {number} size - The size of the smaller box in the Sudoku puzzle.
     * @returns {number[][]} The modified Sudoku board with digits removed.
     */
    const removeDigits = (originalBoard, percentage, size) => {
      const board = originalBoard.map((row) => row.slice());
      const totalCells = size * size;
      let count = Math.floor(totalCells * (percentage / 100));
      let attempts = 0;
  
      while (count > 0 && attempts < 100) {
        const row = Math.floor(Math.random() * size);
        const col = Math.floor(Math.random() * size);
        if (board[row][col] !== 0) {
          board[row][col] = 0;
  
          let copy = board.map((inner) => inner.slice());
          if (hasMultipleSolutions(copy, 0, size)) {
            board[row][col] = originalBoard[row][col];
            attempts++;
          } else {
            count--;
          }
        }
      }
  
      return board;
    };
  
    /**
     * Seeds the Sudoku board with a set number of initial numbers.
     * @param {number[][]} originalBoard - The original Sudoku board.
     * @param {number} size - The total size of the Sudoku puzzle grid.
     * @returns {number[][]} The Sudoku board with initial numbers seeded.
     */
    const seedBoard = (originalBoard, size) => {
      const board = originalBoard.map((row) => row.slice());
  
      for (let i = 0; i < size; i++) {
        const row = Math.floor(Math.random() * size);
        const col = Math.floor(Math.random() * size);
        const num = Math.floor(Math.random() * size) + 1;
        if (isSafe(board, row, col, num, size)) {
          board[row][col] = num;
        }
      }
  
      return board;
    };
  
    /**
     * Generates a Sudoku puzzle of a given size and difficulty.
     * The difficulty is determined by the percentage of digits removed from the solved puzzle.
     * @param {number} size - The size of the smaller box in the Sudoku puzzle.
     * @param {number} percentage - The percentage of digits to remove from the solved puzzle.
     * @returns {{solvedBoard: number[][], initialBoard: number[][]}} An object containing the solved board and the initial puzzle with digits removed.
     */
    const generate = (size, percentage) => {
      let solvedBoard;
  
      while (!solvedBoard) {
        let board = generateBoard(size);
        board = seedBoard(board, size);
  
        if (solveSudoku(board, size)) {
          solvedBoard = board;
        }
      }
  
      const initialBoard = removeDigits(solvedBoard, percentage, size);
  
      return {
        solvedBoard,
        initialBoard,
      };
    };
  
    return {
      generate,
    };
  })();
  
  // Generating a new puzzle and printing it
  const { solvedBoard, initialBoard } = SudokuPuzzle.generate(9, 80);
  console.log("Solved Puzzle:", solvedBoard);
  console.log("Initial Puzzle:", initialBoard);