Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Sudoku Solver LeetCode Solution
Problem – 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-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-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 == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Sudoku Solver LeetCode Solution in Java
public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell
if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}
Sudoku Solver LeetCode Solution in Python
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
def solveSudoku(self, board):
self.board = board
self.solve()
def findUnassigned(self):
for row in range(9):
for col in range(9):
if self.board[row][col] == ".":
return row, col
return -1, -1
def solve(self):
row, col = self.findUnassigned()
#no unassigned position is found, puzzle solved
if row == -1 and col == -1:
return True
for num in ["1","2","3","4","5","6","7","8","9"]:
if self.isSafe(row, col, num):
self.board[row][col] = num
if self.solve():
return True
self.board[row][col] = "."
return False
def isSafe(self, row, col, ch):
boxrow = row - row%3
boxcol = col - col%3
if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
return True
return False
def checkrow(self, row, ch):
for col in range(9):
if self.board[row][col] == ch:
return False
return True
def checkcol(self, col, ch):
for row in range(9):
if self.board[row][col] == ch:
return False
return True
def checksquare(self, row, col, ch):
for r in range(row, row+3):
for c in range(col, col+3):
if self.board[r][c] == ch:
return False
return True
Sudoku Solver LeetCode Solution in C++
class Solution {
struct cell // encapsulates a single cell on a Sudoku board
{
uint8_t value; // cell value 1..9 or 0 if unset
// number of possible (unconstrained) values for the cell
uint8_t numPossibilities;
// if bitset[v] is 1 then value can't be v
bitset<10> constraints;
cell() : value(0), numPossibilities(9),constraints() {};
};
array<array<cell,9>,9> cells;
// sets the value of the cell to [v]
// the function also propagates constraints to other cells and deduce new values where possible
bool set(int i, int j, int v)
{
// updating state of the cell
cell& c = cells[i][j];
if (c.value == v)
return true;
if (c.constraints[v])
return false;
c.constraints = bitset<10>(0x3FE); // all 1s
c.constraints.reset(v);
c.numPossibilities = 1;
c.value = v;
// propagating constraints
for (int k = 0; k<9; k++) {
// to the row:
if (i != k && !updateConstraints(k, j, v))
return false;
// to the column:
if (j != k && !updateConstraints(i, k, v))
return false;
// to the 3x3 square:
int ix = (i / 3) * 3 + k / 3;
int jx = (j / 3) * 3 + k % 3;
if (ix != i && jx != j && !updateConstraints(ix, jx, v))
return false;
}
return true;
}
// update constraints of the cell i,j by excluding possibility of 'excludedValue'
// once there's one possibility left the function recurses back into set()
bool updateConstraints(int i, int j, int excludedValue)
{
cell& c = cells[i][j];
if (c.constraints[excludedValue]) {
return true;
}
if (c.value == excludedValue) {
return false;
}
c.constraints.set(excludedValue);
if (--c.numPossibilities > 1)
return true;
for (int v = 1; v <= 9; v++) {
if (!c.constraints[v]) {
return set(i, j, v);
}
}
assert(false);
}
// backtracking state - list of empty cells
vector<pair<int, int>> bt;
// find values for empty cells
bool findValuesForEmptyCells()
{
// collecting all empty cells
bt.clear();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (!cells[i][j].value)
bt.push_back(make_pair(i, j));
}
}
// making backtracking efficient by pre-sorting empty cells by numPossibilities
sort(bt.begin(), bt.end(), [this](const pair<int, int>&a, const pair<int, int>&b) {
return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities; });
return backtrack(0);
}
// Finds value for all empty cells with index >=k
bool backtrack(int k)
{
if (k >= bt.size())
return true;
int i = bt[k].first;
int j = bt[k].second;
// fast path - only 1 possibility
if (cells[i][j].value)
return backtrack(k + 1);
auto constraints = cells[i][j].constraints;
// slow path >1 possibility.
// making snapshot of the state
array<array<cell,9>,9> snapshot(cells);
for (int v = 1; v <= 9; v++) {
if (!constraints[v]) {
if (set(i, j, v)) {
if (backtrack(k + 1))
return true;
}
// restoring from snapshot,
// note: computationally this is cheaper
// than alternative implementation with undoing the changes
cells = snapshot;
}
}
return false;
}
public:
void solveSudoku(vector<vector<char>> &board) {
cells = array<array<cell,9>,9>(); // clear array
// Decoding input board into the internal cell matrix.
// As we do it - constraints are propagated and even additional values are set as we go
// (in the case if it is possible to unambiguously deduce them).
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.' && !set(i, j, board[i][j] - '0'))
return; // sudoku is either incorrect or unsolvable
}
}
// if we're lucky we've already got a solution,
// however, if we have empty cells we need to use backtracking to fill them
if (!findValuesForEmptyCells())
return; // sudoku is unsolvable
// copying the solution back to the board
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++) {
if (cells[i][j].value)
board[i][j] = cells[i][j].value + '0';
}
}
}
};
Sudoku Solver LeetCode Solution Review:
In our experience, we suggest you solve this Sudoku Solver LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Sudoku Solver LeetCode Solution
Conclusion:
I hope this Sudoku Solver LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
