#37 Leetcode Sudoku Solver Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Algorithm

Problem Name: 37. Sudoku Solver

Problem Link: https://leetcode.com/problems/sudoku-solver/

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

A sudoku solution must satisfy all of the following rules:

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

The '.' character indicates empty cells.

Example 1:

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 input board is shown above and the only valid solution is shown below:

Constraints:

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


#define IDX(I, J) ((I) / 3 * (boardColSize + 2) / 3 + (J) / 3)

int find_next_bit(int b, int k) {
    k ++;
    while (k  <  9 && (b & (1 << k))) {
        k ++;
    }
    return k;
}

int dfs(char **board, int boardRowSize, int boardColSize, int *bits_on_row, int *bits_on_col, int *bits_on_square) {
    int i, j, b, t, k;
    char c;

    for (i = 0; i  <  boardRowSize; i ++) {
        for (j = 0; j  <  boardColSize; j ++) {
            c = board[i][j];
            if (c != '.') continue;
                    
            b = bits_on_row[i] |
                bits_on_col[j] |
                bits_on_square[IDX(i, j)];
            k = -1;
            while ((k = find_next_bit(b, k))  <  9) {
                t = 1 << k;
                            
                board[i][j] = '1' + k;
                bits_on_row[i] |= t;
                bits_on_col[j] |= t;
                bits_on_square[IDX(i, j)] |= t;
                            
                if (dfs(board, boardRowSize, boardColSize, bits_on_row, bits_on_col, bits_on_square)) return 1;
                            
                board[i][j] = '.';
                bits_on_row[i] &= ~t;
                bits_on_col[j] &= ~t;
                bits_on_square[IDX(i, j)] &= ~t;
            }
                    
            return 0;
        }
    }
         
    return 1;
}

void solveSudoku(char** board, int boardRowSize, int boardColSize) {
    int *buff, *bits_on_row, *bits_on_col, *bits_on_square;
    int i, j, b;
    char c;

    buff = calloc(boardRowSize +
                            boardColSize +
                            (boardRowSize + 2) / 3 * (boardColSize + 2) / 3, sizeof(int));
    //assert(buff);

    bits_on_row = &buff[0];
    bits_on_col = &buff[boardRowSize];
    bits_on_square = &buff[boardRowSize + boardColSize];

    for (i = 0; i  <  boardRowSize; i ++) {
        for (j = 0; j  <  boardColSize; j ++) {
            c = board[i][j];
            if (c == '.') continue;
            b = 1 << (c - '1');
            bits_on_row[i] |= b;
            bits_on_col[j] |= b;
            bits_on_square[IDX(i, j)] |= b;
        }
    }

    dfs(board, boardRowSize, boardColSize, bits_on_row, bits_on_col, bits_on_square);

    free(buff);
}

Copy The Code & Try With Live Editor

Input

–

cmd

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

–

cmd

[["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"]]

#2 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 108 ms
class Solution0 {
public:
    struct Trace {
        int i;
        int j;
        int s;
        Trace() : i(0), j(0), s(0) {}
        Trace(int _i, int _j, int _s) : i(_i), j(_j), s(_s) {}
    };

    void solveSudoku(vector < vector<char>>& board) {
        vector < vector<bool>> rowFlag(9, vector < bool>(9, false));
        vector<vector<bool>> colFlag(9, vector < bool>(9, false));
        vector<vector<bool>> boxFlag(9, vector < bool>(9, false));
        vector<vector<bool>> occupied(9, vector < bool>(9, false));
        int i, j;
        int remains = 0;
        for (i = 0; i  <  9; i++) {
            for (j = 0; j  <  9; j++) {
                if (board[i][j] != '.') {
                    int k = board[i][j] - '1';
                    rowFlag[i][k] = true;
                    colFlag[j][k] = true;
                    boxFlag[(i / 3) * 3 + j / 3][k] = true;
                    occupied[i][j] = true;
                }
                else {
                    remains++;
                }
            }
        }

        bool found = false;
        vector < Trace> ans(remains);
        placeNumber(board, found, ans, 0, remains, occupied, rowFlag, colFlag, boxFlag);
    }

    void placeNumber(vector < vector<char>>& board, bool &found,
                     vector < Trace> &ans, int count, int remains,
                     vector<vector<bool>> &occupied, vector < vector<bool>> &rowFlag,
                     vector < vector<bool>> &colFlag, vector < vector<bool>> &boxFlag)
       {
        if (count == remains) {
            found = true;
            int k = 0;
            for (i = 0; i  <  9; i++) {
                for (j = 0; j  <  9; j++) {
                    if (board[i][j] == '.') {
                        board[i][j] = ans[k++].s + '1';
                    }
                }
            }
            return;
        }

        for (i = 0; i  <  9; i++) {
            for (j = 0; j  <  9; j++) {
                if (occupied[i][j] == false) {
                    for (int s = 0; s  <  9; s++) {
                       
                        if (!rowFlag[i][s] && !colFlag[j][s] && !boxFlag[(i / 3) * 3 + j / 3][s]) {
                            rowFlag[i][s] = true;
                            colFlag[j][s] = true;
                            boxFlag[(i / 3) * 3 + j / 3][s] = true;
                            occupied[i][j] = true;
                            placeNumber(board, found, ans, count + 1, remains, occupied, rowFlag, colFlag, boxFlag);
                        }
                    }
                    
                    if (count  < = 0) return;
                    Trace t = ans[count - 1];
                    rowFlag[t.i][t.s] = false;
                    colFlag[t.j][t.s] = false;
                    boxFlag[(t.i / 3) * 3 + t.j / 3][t.s] = false;
                    occupied[t.i][t.j] = false;
                    return;
                }
            }
        }
    }
};

// 36 ms
class Solution {
public:
    void solveSudoku(vector < vector<char>>& board) {
        vector < vector<bool>> rowFlag(10, vector < bool>(10, false));
        vector<vector<bool>> colFlag(10, vector < bool>(10, false));
        vector<vector<bool>> boxFlag(10, vector < bool>(10, false));
        int i, j;
        for (i = 0; i  <  9; i++) {
            for (j = 0; j  <  9; j++) {
                if (board[i][j] != '.') {
                    int k = board[i][j] - '1';
                    rowFlag[i][k] = true;
                    colFlag[j][k] = true;
                    boxFlag[(i / 3) * 3 + j / 3][k] = true;
                }
            }
        }

        bool found = false;
        placeNumber(board, found, 0, rowFlag, colFlag, boxFlag);
    }

    bool placeNumber(vector < vector<char>>& board, bool &found,
                     int depth,
                     vector < vector<bool>> &rowFlag,
                     vector < vector<bool>> &colFlag, vector < vector<bool>> &boxFlag)
    {
        // suppose we have only one solution, if we found one, no need to continue
        if (found) return true;

        // found one solution! copy answers to the board
        if (depth == 81) {
            found = true;
            return true;
        }

        int i, j;
        i = depth / 9; j = depth % 9;

        if (board[i][j] != '.') {
            return placeNumber(board, found, depth + 1, rowFlag, colFlag, boxFlag);
        }
        else {
            for (int s = 0; s  <  9; s++) {
                // if it's valid, set flag and place another number
                if (!rowFlag[i][s] && !colFlag[j][s] && !boxFlag[(i / 3) * 3 + j / 3][s]) {
                    // try to place a number
                    board[i][j] = s + '1';
                    rowFlag[i][s] = true;
                    colFlag[j][s] = true;
                    boxFlag[(i / 3) * 3 + j / 3][s] = true;
                    if (placeNumber(board, found, depth + 1, rowFlag, colFlag, boxFlag)) return true;
                    // backtrack
                    rowFlag[i][s] = false;
                    colFlag[j][s] = false;
                    boxFlag[(i / 3) * 3 + j / 3][s] = false;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
};

int main() {
    vector < string> board0 = {
        "..9748...",
        "7........",
        ".2.1.9...",
        "..7...24.",
        ".64.1.59.",
        ".98...3..",
        "...8.3.2.",
        "........6",
        "...2759.."
    };

    vector<string> board1 = {
        "53..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79"
    };

    vector < vector<char> > board(9, vector<char>(9, 0));
    int i, j;

    // board0
    for (i = 0; i  <  board0.size(); i++) {
        for (j = 0; j  <  board0[i].length(); j++) {
            board[i][j] = board0[i][j];
        }
    }

    Solution s;
    s.solveSudoku(board);

    for (i = 0; i  <  board.size(); i++) {
        for (j = 0; j  <  board[i].size(); j++) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }

    printf("-----------------\n");

    // board1
    for (i = 0; i  <  board1.size(); i++) {
        for (j = 0; j  <  board1[i].length(); j++) {
            board[i][j] = board1[i][j];
        }
    }

    s.solveSudoku(board);

    for (i = 0; i  <  board.size(); i++) {
        for (j = 0; j  <  board[i].size(); j++) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

#3 Code Example with Javascript Programming

Code - Javascript Programming


const solveSudoku = function(board) {
  dfs(0, 0)
  function dfs(row, col) {
    if (row === 9) return true
    if (col === 9) return dfs(row + 1, 0)
    if (board[row][col] === ".") {
      for (let num = 1; num  < = 9; num++) {
        if (isValid(row, col, `${num}`)) {
          board[row][col] = `${num}`
          if (dfs(row, col + 1)) return true
          board[row][col] = "."
        }
      }
    } else {
      return dfs(row, col + 1)
    }
    return false
  }
  function isValid(row, col, num) {
    for (let rowIdx = 0; rowIdx  <  9; rowIdx++) if (board[rowIdx][col] === num) return false
    for (let colIdx = 0; colIdx  <  9; colIdx++) if (board[row][colIdx] === num) return false

    let squareRowStart = row - (row % 3)
    let squareColStart = col - (col % 3)
    for (let rIdx = 0; rIdx  <  3; rIdx++) {
      for (let cIdx = 0; cIdx  <  3; cIdx++) {
        if (board[squareRowStart + rIdx][squareColStart + cIdx] === num) return false
      }
    }
    return true
  }
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def solveSudoku(self, board):
        rows, cols, triples, visit = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set), collections.deque([])
        for r in range(9):
            for c in range(9):
                if board[r][c] != ".":
                    rows[r].add(board[r][c])
                    cols[c].add(board[r][c])
                    triples[(r // 3, c // 3)].add(board[r][c])
                else:
                    visit.append((r, c))
        def dfs():
            if not visit:
                return True
            r, c = visit[0]
            t = (r // 3, c // 3)
            for dig in {"1", "2", "3", "4", "5", "6", "7", "8", "9"}:
                if dig not in rows[r] and dig not in cols[c] and dig not in triples[t]:
                    board[r][c] = dig
                    rows[r].add(dig)
                    cols[c].add(dig)
                    triples[t].add(dig)
                    visit.popleft()
                    if dfs():
                        return True
                    else:
                        board[r][c] = "."
                        rows[r].discard(dig)
                        cols[c].discard(dig)
                        triples[t].discard(dig)
                        visit.appendleft((r, c))
            return False
        dfs()

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

#5 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _037_SudokuSolver
    {
        bool[,] colUsed = new bool[9, 9];
        bool[,] rowUsed = new bool[9, 9];
        bool[,] squareUsed = new bool[9, 9];

        public void SolveSudoku(char[,] board)
        {
            int row, column, squareId, value;
            for (row = 0; row  <  9; row++)
            {
                for (column = 0; column  <  9; column++)
                {
                    value = board[row, column] - '0' - 1;
                    if (value > 8 || value  <  0) { continue; }
                    squareId = (row / 3) * 3 + column / 3;
                    if (colUsed[column, value] || rowUsed[row, value] || squareUsed[squareId, value]) { return; }

                    colUsed[column, value] = rowUsed[row, value] = squareUsed[squareId, value] = true;
                }
            }

            RecursiveSolver(board, 0, 0);
        }

        bool RecursiveSolver(char[,] boarder, int row, int col)
        {
            if (row == 9) { return true; }
            if (col == 9) { return RecursiveSolver(boarder, row + 1, 0); }
            if (boarder[row, col] != '.') { return RecursiveSolver(boarder, row, col + 1); }

            int squareId;
            for (int i = 0; i  <  9; i++)
            {
                squareId = (row / 3) * 3 + col / 3;
                if (colUsed[col, i] || rowUsed[row, i] || squareUsed[squareId, i]) { continue; }

                boarder[row, col] = (char)('1' + i);
                colUsed[col, i] = rowUsed[row, i] = squareUsed[squareId, i] = true;
                if (RecursiveSolver(boarder, row, col + 1))
                {
                    return true;
                }

                boarder[row, col] = '.';
                colUsed[col, i] = rowUsed[row, i] = squareUsed[squareId, i] = false;
            }

            return false;
        }
    }
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

Demonstration

Previous
#36 Leetcode Valid Sudoku Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Next
#38 Leetcode Count and Say Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Try With Live Editor

Category - Leetcode Online Judge Maniruzzaman Akash 1 year ago 697 0