In the Leetcode Sudoku Solver problem solution 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 3×3 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.
Solution in C Programming
#define UNASSIGNED "."
bool findUnassigned(char **board, int *row, int *col);
bool UsedInRow(char **board, int row, int num);
bool UsedInCol(char **board, int col, int num);
bool UsedInBox(char **board, int boxStartRow, int boxStartCol, int num);
bool IsSafe(char **board, int row, int col, int num);
bool findUnassigned(char **board, int *row, int *col){
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
*row = i;
*col = j;
return true;
}
}
}
return false;
}
bool UsedInRow(char **board, int row, int num) {
for (int i = 0; i < 9; i++) {
if (board[row][i] - '0' == num) {
return true;
}
}
return false;
}
bool UsedInCol(char **board, int col, int num) {
for (int i = 0; i < 9; i++) {
if (board[i][col] - '0' == num)
return true;
}
return false;
}
bool UsedInBox(char **board, int boxStartRow, int boxStartCol, int num) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[boxStartRow+i][boxStartCol+j] - '0' == num)
return true;
}
}
return false;
}
bool IsSafe(char **board, int row, int col, int num) {
if ((board[row][col] == '.')
&& (!UsedInRow(board, row, num))
&& (!UsedInCol(board, col, num))
&& (!UsedInBox(board, row - row%3, col - col%3, num))) {
return true;
}
return false;
}
int helper(char** board){
int row, col, num;
if (!findUnassigned(board, &row, &col))
return true;
for (num = 1; num <= 9; num++) {
if (IsSafe(board, row, col, num)) {
board[row][col] = num+'0';
if (helper(board))
return true;
board[row][col] = '.';
}
}
// printf("backtracking \n");
return false;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
helper(board);
}Solution in C++ Programming
class Solution {
public:
bool isEmpty(vector<vector<char>>& board,int &x,int &y){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.'){
x=i;
y=j;
return true;
}
}
}
return false;
}
bool isValid(int val,vector<vector<char>>& board, int x, int y){
for(int i=0;i<9;i++){
if(board[i][y]==val) return false;
}
for(int j=0;j<9;j++){
if(board[x][j]==val) return false;
}
int cur_row=(x/3)*3;
int cur_col=(y/3)*3;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(board[i+cur_row][j+cur_col]==val) return false;
}
}
return true;
}
bool dfs(vector<vector<char>>& board){
int x,y;
if(!isEmpty(board,x,y)){
return true;
}
for(int i=1;i<=9;i++){
if(isValid(i+'0',board,x,y)){
board[x][y]=i+'0';
if(dfs(board)){
return true;
}
board[x][y]='.';
}
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
dfs(board);
}
};Solution in Java Programming
class Solution {
public void solveSudoku(char[][] board) {
helper(board);
}
public boolean helper(char [][]board){
for(int i =0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
if(board[i][j]=='.'){//if the board would be empty then only we will be able to fill it
for(char ch='1';ch<='9';ch++){
if(IsValid(board,i,j,ch)){
board[i][j]=ch;
if(helper(board)==true){
return true;
}
else{
board[i][j]='.';//if false comes then remove the no empty as backtrack hote waqt uss number ko waha se hatana hoga
}
}
}
return false;//i.e none of the number can be filled from 1 to 9 in that particular spot so return false;
}
}
}
return true;//if every thing is filled so no more '.' would be present in the array
}
public boolean IsValid(char [][]board,int row,int col,char ch){
for(int i =0;i<9;i++){
if(board[row][i]==ch){
return false;
}
if(board[i][col]==ch){
return false;
}
if(board[3*(row/3) + (i/3)][3*(col/3) + (i%3)]==ch){
return false;
}
}
return true;
}
}Solution in Python Programming
import itertools
import copy
class Solution:
def solveSudoku(self, board):
if not any(['.' in x for x in board]):
return
minset = set(range(10))
mx,my = 0,0
for (i,j) in itertools.product(range(9),range(9)):
if board[i][j] == '.':
rset = set(board[i])
cset = set([board[x][j] for x in range(9)])
blockset = set([board[x][y] for (x,y) in itertools.product(range(int(i/3)*3,int(i/3)*3+3),range(int(j/3)*3,int(j/3)*3+3))])
ac = set()
for d in range(1,10):
d = str(d)
if d not in rset and d not in cset and d not in blockset:
# board[i][j] = d
ac.add(d)
if len(ac) < len(minset):
minset = ac
mx,my = i,j
for x in minset:
board[mx][my] = x
self.solveSudoku(board)
if not any(['.' in x for x in board]):
return
board[mx][my]='.'Solution in C# Programming
public class Solution {
public void SolveSudoku(char[][] board) {
if(board==null) return;
backtrack(board, 0, 0);
}
private bool backtrack(char[][] board, int row, int col){
if(col==9)
{
col = 0; ++row;
if(row==9) return true;
}
if(board[row][col]!='.')
return backtrack(board, row, col+1);
for(char v = '1' ; v <='9' ; v++)
{
if(isValid(board, row, col, v))
{
board[row][col] = v;
if(backtrack(board, row,col+1)) return true;
else board[row][col] = '.';
}
}
return false;
}
private bool isValid(char[][] board, int row, int col,char val){
//check if value is present in column
for(int r = 0 ; r < 9 ; r++)
if(board[r][col]==val) return false;
//check if value is present in the row
for(int c = 0 ; c < 9 ; c++)
if(board[row][c]==val) return false;
//check for the value in the 3 X 3 block
int I = row/3; int J = col/3;
for(int a = 0 ; a < 3 ; a++)
for(int b = 0 ; b < 3 ; b++)
if(val==board[3*I+a][3*J+b]) return false;
return true;
}
}Also read,