Sudoku Solver

Solve the sudoku by filling up the empty places. Any number you place should not be part of its row , colums or the current box

Problem Statement

Write a program to solve a Sudoku puzzle by filling in the empty cells.

A valid Sudoku solution must follow these rules:

• Each of the digits 1-9 must appear exactly once in every row.
• Each of the digits 1-9 must appear exactly once in every column.
• Each of the digits 1-9 must appear exactly once in each of the nine 3x3 sub-boxes of the grid.

The '.' character marks an empty cell.

Example

Input:

board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

Output:

[
  ["5","3","4","6","7","8","9","1","2"],
  ["6","7","2","1","9","5","3","4","8"],
  ["1","9","8","3","4","2","5","6","7"],
  ["8","5","9","7","6","1","4","2","3"],
  ["4","2","6","8","5","3","7","9","1"],
  ["7","1","3","9","2","4","8","5","6"],
  ["9","6","1","5","3","7","2","8","4"],
  ["2","8","7","4","1","9","6","3","5"],
  ["3","4","5","2","8","6","1","7","9"]
]

Explanation: The board shown above has only one valid solution, shown in the output.

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It's guaranteed that the input board has exactly one solution.

Solution

We solve this using backtracking, moving through the board cell by cell, from left to right, top to bottom. Once we reach past the last row, the puzzle is solved.

Steps

• We use a helper function, solver(board, row, col):
  • If row reaches 9, it means we've successfully filled in every row. The puzzle is solved, so we return true.
  • We calculate the next cell to move to: usually the next column over, but if we're at the last column, we move to the next row, starting back at column 0.
  • If the current cell is already filled in (not '.'), we skip it and move straight to the next cell.
  • Otherwise, we try placing each number from 1 to 9 in the current cell:
    • We check if placing this number is safe, using the safe helper function.
    • If it is safe, we place the number, then recursively try to solve the rest of the board from the next cell.
    • If that recursive call succeeds, we're done — we return true all the way up.
    • If it doesn't succeed, we undo our placement (reset the cell back to '.') and try the next number instead. This is the "backtracking" step.
  • If none of the numbers 1 through 9 work for this cell, we return false, so the previous cell can try a different number.
• The safe function checks three things before allowing a number to be placed:
  • The number doesn't already exist anywhere in the same row.
  • The number doesn't already exist anywhere in the same column.
  • The number doesn't already exist anywhere in the same 3x3 sub-box.

Code

var solveSudoku = function(board) {
    solver(board, 0, 0);

    function solver(board, row, col) {
        // All rows are completed
        if (row === 9) {
            return true;
        }

        // Calculate next cell
        let nextRow = row;
        let nextCol = col + 1;

        if (nextCol === 9) {
            nextRow = row + 1;
            nextCol = 0;
        }

        // If cell is already filled, move to next cell
        if (board[row][col] !== '.') {
            return solver(board, nextRow, nextCol);
        }

        // Try numbers 1 to 9
        for (let i = 1; i <= 9; i++) {

            if (safe(board, row, col, i)) {

                // Place number
                board[row][col] = String(i);

                // Recursively solve next cell
                if (solver(board, nextRow, nextCol)) {
                    return true;
                }

                // Backtrack
                board[row][col] = '.';
            }
        }

        return false;
    }

    function safe(board, row, col, val) {
        let ch = String(val);

        // Check row
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === ch) {
                return false;
            }
        }

        // Check column
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === ch) {
                return false;
            }
        }

        // Check 3x3 box
        let sr = Math.floor(row / 3) * 3;
        let sc = Math.floor(col / 3) * 3;

        for (let i = sr; i < sr + 3; i++) {
            for (let j = sc; j < sc + 3; j++) {
                if (board[i][j] === ch) {
                    return false;
                }
            }
        }

        return true;
    }
};