Sudoku using Bit Masks
This method is a slight optimization to the above 2 methods. For each row/column/box create a bitmask and for each element in the grid set the bit at position ‘value’ to 1 in the corresponding bitmasks, for O(1) checks.
Follow the steps below to solve the problem:
- Create 3 arrays of size N (one for rows, columns, and boxes).
- The boxes are indexed from 0 to 8. (in order to find the box index of an element we use the following formula: row / 3 * 3 + column / 3).
- Map the initial values of the grid first.
- Each time we add/remove an element to/from the grid set the bit to 1/0 to the corresponding bitmasks.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; #define N 9 // Bitmasks for each row/column/box int row[N], col[N], box[N]; bool seted = false ; // Utility function to find the box index // of an element at position [i][j] in the grid int getBox( int i, int j) { return i / 3 * 3 + j / 3; } // Utility function to check if a number // is present in the corresponding row/column/box bool isSafe( int i, int j, int number) { return !((row[i] >> number) & 1) && !((col[j] >> number) & 1) && !((box[getBox(i, j)] >> number) & 1); } // Utility function to set the initial values of a Sudoku // board (map the values in the bitmasks) void setInitialValues( int grid[N][N]) { for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) row[i] |= 1 << grid[i][j], col[j] |= 1 << grid[i][j], box[getBox(i, j)] |= 1 << grid[i][j]; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku( int grid[N][N], int i, int j) { // Set the initial values if (!seted) seted = true , setInitialValues(grid); if (i == N - 1 && j == N) return true ; if (j == N) j = 0, i++; if (grid[i][j]) return SolveSudoku(grid, i, j + 1); for ( int nr = 1; nr <= N; nr++) { if (isSafe(i, j, nr)) { /* Assign nr in the current (i, j) position and add nr to each bitmask */ grid[i][j] = nr; row[i] |= 1 << nr; col[j] |= 1 << nr; box[getBox(i, j)] |= 1 << nr; if (SolveSudoku(grid, i, j + 1)) return true ; // Remove nr from each bitmask // and search for another possibility row[i] &= ~(1 << nr); col[j] &= ~(1 << nr); box[getBox(i, j)] &= ~(1 << nr); } grid[i][j] = 0; } return false ; } // Utility function to print the solved grid void print( int grid[N][N]) { for ( int i = 0; i < N; i++, cout << '\n' ) for ( int j = 0; j < N; j++) cout << grid[i][j] << ' ' ; } // Driver Code int main() { // 0 means unassigned cells int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; if (SolveSudoku(grid, 0, 0)) print(grid); else cout << "No solution exists\n" ; return 0; } // This code is contributed // by Gatea David |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { static int N = 9 ; // Bitmasks for each row/column/box static int row[] = new int [N], col[] = new int [N], box[] = new int [N]; static Boolean seted = false ; // Utility function to find the box index // of an element at position [i][j] in the grid static int getBox( int i, int j) { return i / 3 * 3 + j / 3 ; } // Utility function to check if a number // is present in the corresponding row/column/box static Boolean isSafe( int i, int j, int number) { return ((row[i] >> number) & 1 ) == 0 && ((col[j] >> number) & 1 ) == 0 && ((box[getBox(i, j)] >> number) & 1 ) == 0 ; } // Utility function to set the initial values of a // Sudoku board (map the values in the bitmasks) static void setInitialValues( int grid[][]) { for ( int i = 0 ; i < grid.length; i++) { for ( int j = 0 ; j < grid.length; j++) { row[i] |= 1 << grid[i][j]; col[j] |= 1 << grid[i][j]; box[getBox(i, j)] |= 1 << grid[i][j]; } } } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static Boolean SolveSudoku( int grid[][], int i, int j) { // Set the initial values if (!seted) { seted = true ; setInitialValues(grid); } if (i == N - 1 && j == N) return true ; if (j == N) { j = 0 ; i++; } if (grid[i][j] > 0 ) return SolveSudoku(grid, i, j + 1 ); for ( int nr = 1 ; nr <= N; nr++) { if (isSafe(i, j, nr)) { /* Assign nr in the current (i, j) position and add nr to each bitmask */ grid[i][j] = nr; row[i] |= 1 << nr; col[j] |= 1 << nr; box[getBox(i, j)] |= 1 << nr; if (SolveSudoku(grid, i, j + 1 )) return true ; // Remove nr from each bitmask // and search for another possibility row[i] &= ~( 1 << nr); col[j] &= ~( 1 << nr); box[getBox(i, j)] &= ~( 1 << nr); } grid[i][j] = 0 ; } return false ; } // Utility function to print the solved grid static void print( int grid[][]) { for ( int i = 0 ; i < grid.length; i++) { for ( int j = 0 ; j < grid[ 0 ].length; j++) { System.out.printf( "%d " , grid[i][j]); } System.out.println(); } } // Driver code public static void main(String args[]) { // 0 means unassigned cells int grid[][] = { { 3 , 0 , 6 , 5 , 0 , 8 , 4 , 0 , 0 }, { 5 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 }, { 0 , 8 , 7 , 0 , 0 , 0 , 0 , 3 , 1 }, { 0 , 0 , 3 , 0 , 1 , 0 , 0 , 8 , 0 }, { 9 , 0 , 0 , 8 , 6 , 3 , 0 , 0 , 5 }, { 0 , 5 , 0 , 0 , 9 , 0 , 6 , 0 , 0 }, { 1 , 3 , 0 , 0 , 0 , 0 , 2 , 5 , 0 }, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 4 }, { 0 , 0 , 5 , 2 , 0 , 6 , 3 , 0 , 0 } }; if (SolveSudoku(grid, 0 , 0 )) print(grid); else System.out.println( "No solution exists" ); } } // This code is contributed by shinjanpatra. |
Python3
# N is the size of the 2D matrix N*N N = 9 # A utility function to print grid def printing(arr): for i in range (N): for j in range (N): print (arr[i][j], end = " " ) print () # Checks whether it will be # legal to assign num to the # given row, col def isSafe(grid, row, col, num): # Check if we find the same num # in the similar row , we # return false for x in range ( 9 ): if grid[row][x] = = num: return False # Check if we find the same num in # the similar column , we # return false for x in range ( 9 ): if grid[x][col] = = num: return False # Check if we find the same num in # the particular 3*3 matrix, # we return false startRow = row - row % 3 startCol = col - col % 3 for i in range ( 3 ): for j in range ( 3 ): if grid[i + startRow][j + startCol] = = num: return False return True # Takes a partially filled-in grid and attempts # to assign values to all unassigned locations in # such a way to meet the requirements for # Sudoku solution (non-duplication across rows, # columns, and boxes) */ def solveSudoku(grid, row, col): # Check if we have reached the 8th # row and 9th column (0 # indexed matrix) , we are # returning true to avoid # further backtracking if (row = = N - 1 and col = = N): return True # Check if column value becomes 9 , # we move to next row and # column start from 0 if col = = N: row + = 1 col = 0 # Check if the current position of # the grid already contains # value >0, we iterate for next column if grid[row][col] > 0 : return solveSudoku(grid, row, col + 1 ) for num in range ( 1 , N + 1 , 1 ): # Check if it is safe to place # the num (1-9) in the # given row ,col ->we # move to next column if isSafe(grid, row, col, num): # Assigning the num in # the current (row,col) # position of the grid # and assuming our assigned # num in the position # is correct grid[row][col] = num # Checking for next possibility with next # column if solveSudoku(grid, row, col + 1 ): return True # Removing the assigned num , # since our assumption # was wrong , and we go for # next assumption with # diff num value grid[row][col] = 0 return False # Driver Code # 0 means unassigned cells grid = [[ 3 , 0 , 6 , 5 , 0 , 8 , 4 , 0 , 0 ], [ 5 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ], [ 0 , 8 , 7 , 0 , 0 , 0 , 0 , 3 , 1 ], [ 0 , 0 , 3 , 0 , 1 , 0 , 0 , 8 , 0 ], [ 9 , 0 , 0 , 8 , 6 , 3 , 0 , 0 , 5 ], [ 0 , 5 , 0 , 0 , 9 , 0 , 6 , 0 , 0 ], [ 1 , 3 , 0 , 0 , 0 , 0 , 2 , 5 , 0 ], [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 4 ], [ 0 , 0 , 5 , 2 , 0 , 6 , 3 , 0 , 0 ]] if (solveSudoku(grid, 0 , 0 )): printing(grid) else : print ( "no solution exists " ) # This code is contributed by sanjoy_62. |
C#
// C# program for above approach using System; class GFG { // N is the size of the 2D matrix N*N static int N = 9; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static bool solveSudoku( int [, ] grid, int row, int col) { /*if we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row, col] != 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num < 10; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row, col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1)) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row, col] = 0; } return false ; } /* A utility function to print grid */ static void print( int [, ] grid) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write(grid[i, j] + " " ); Console.WriteLine(); } } // Check whether it will be legal // to assign num to the // given row, col static bool isSafe( int [, ] grid, int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0; x <= 8; x++) if (grid[row, x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for ( int x = 0; x <= 8; x++) if (grid[x, col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow, j + startCol] == num) return false ; return true ; } // Driver code static void Main() { int [, ] grid = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; if (solveSudoku(grid, 0, 0)) print(grid); else Console.WriteLine( "No Solution exists" ); } } // This code is contributed by code_hunt. |
Javascript
<script> const N = 9 // Bitmasks for each row/column/box let row = new Array(N), col = new Array(N), box = new Array(N); let seted = false ; // Utility function to find the box index // of an element at position [i][j] in the grid function getBox(i,j) { return Math.floor(i / 3) * 3 + Math.floor(j / 3); } // Utility function to check if a number // is present in the corresponding row/column/box function isSafe(i,j,number) { return !((row[i] >> number) & 1) && !((col[j] >> number) & 1) && !((box[getBox(i,j)] >> number) & 1); } // Utility function to set the initial values of a Sudoku board // (map the values in the bitmasks) function setInitialValues(grid) { for (let i = 0; i < N;i++) for (let j = 0; j < N; j++) row[i] |= 1 << grid[i][j], col[j] |= 1 << grid[i][j], box[getBox(i, j)] |= 1 << grid[i][j]; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ function SolveSudoku(grid ,i, j) { // Set the initial values if (!seted){ seted = true , setInitialValues(grid); } if (i == N - 1 && j == N) return true ; if (j == N){ j = 0; i++; } if (grid[i][j]) return SolveSudoku(grid, i, j + 1); for (let nr = 1; nr <= N;nr++) { if (isSafe(i, j, nr)) { /* Assign nr in the current (i, j) position and add nr to each bitmask */ grid[i][j] = nr; row[i] |= 1 << nr; col[j] |= 1 << nr; box[getBox(i, j)] |= 1 << nr; if (SolveSudoku(grid, i,j + 1)) return true ; // Remove nr from each bitmask // and search for another possibility row[i] &= ~(1 << nr); col[j] &= ~(1 << nr); box[getBox(i, j)] &= ~(1 << nr); } grid[i][j] = 0; } return false ; } // Utility function to print the solved grid function print(grid) { for (let i = 0; i < N; i++){ for (let j = 0; j < N; j++){ document.write(grid[i][j], " " ); } document.write( "</br>" ); } } // Driver Code // 0 means unassigned cells let grid = [ [ 3, 0, 6, 5, 0, 8, 4, 0, 0 ], [ 5, 2, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 8, 7, 0, 0, 0, 0, 3, 1 ], [ 0, 0, 3, 0, 1, 0, 0, 8, 0 ], [ 9, 0, 0, 8, 6, 3, 0, 0, 5 ], [ 0, 5, 0, 0, 9, 0, 6, 0, 0 ], [ 1, 3, 0, 0, 0, 0, 2, 5, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 7, 4 ], [ 0, 0, 5, 2, 0, 6, 3, 0, 0 ]]; if (SolveSudoku(grid,0 ,0)) print(grid); else document.write( "No solution exists" , "</br>" ); // This code is contributed by shinjanpatra </script> |
3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9
Time complexity: O(9(N*N)). For every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)). The time complexity remains the same but checking if a number is safe to use is much faster, O(1).
Space Complexity: O(N*N). To store the output array a matrix is needed, and 3 extra arrays of size n are needed for the bitmasks.
Algorithm to Solve Sudoku | Sudoku Solver
Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
Examples:
Input: grid
{ {3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0} }
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Explanation: Each row, column and 3*3 box of the output matrix contains unique numbers.Input: grid
{ { 3, 1, 6, 5, 7, 8, 4, 9, 2 },
{ 5, 2, 9, 1, 3, 4, 7, 6, 8 },
{ 4, 8, 7, 6, 2, 9, 5, 3, 1 },
{ 2, 6, 3, 0, 1, 5, 9, 8, 7 },
{ 9, 7, 4, 8, 6, 0, 1, 2, 5 },
{ 8, 5, 1, 7, 9, 2, 6, 4, 3 },
{ 1, 3, 8, 0, 4, 7, 2, 0, 6 },
{ 6, 9, 2, 3, 5, 1, 8, 7, 4 },
{ 7, 4, 5, 0, 8, 6, 3, 1, 0 } };
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Explanation: Each row, column and 3*3 box of the output matrix contains unique numbers.
Naive Approach:
The naive approach is to generate all possible configurations of numbers from 1 to 9 to fill the empty cells. Try every configuration one by one until the correct configuration is found, i.e. for every unassigned position fill the position with a number from 1 to 9. After filling all the unassigned positions check if the matrix is safe or not. If safe print else recurs for other cases.
Follow the steps below to solve the problem:
- Create a function that checks if the given matrix is valid sudoku or not. Keep Hashmap for the row, column and boxes. If any number has a frequency greater than 1 in the hashMap return false else return true;
- Create a recursive function that takes a grid and the current row and column index.
- Check some base cases.
- If the index is at the end of the matrix, i.e. i=N-1 and j=N then check if the grid is safe or not, if safe print the grid and return true else return false.
- The other base case is when the value of column is N, i.e j = N, then move to next row, i.e. i++ and j = 0.
- If the current index is not assigned then fill the element from 1 to 9 and recur for all 9 cases with the index of next element, i.e. i, j+1. if the recursive call returns true then break the loop and return true.
- If the current index is assigned then call the recursive function with the index of the next element, i.e. i, j+1
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; // N is the size of the 2D matrix N*N #define N 9 /* A utility function to print grid */ void print( int arr[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << arr[i][j] << " " ; cout << endl; } } // Checks whether it will be // legal to assign num to the // given row, col bool isSafe( int grid[N][N], int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0; x <= 8; x++) if (grid[row][x] == num) return false ; // Check if we find the same num in // the similar column , we // return false for ( int x = 0; x <= 8; x++) if (grid[x][col] == num) return false ; // Check if we find the same num in // the particular 3*3 matrix, // we return false int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool solveSudoku( int grid[N][N], int row, int col) { // Check if we have reached the 8th // row and 9th column (0 // indexed matrix) , we are // returning true to avoid // further backtracking if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row and // column start from 0 if (col == N) { row++; col = 0; } // Check if the current position of // the grid already contains // value >0, we iterate for next column if (grid[row][col] > 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num <= N; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we // move to next column if (isSafe(grid, row, col, num)) { /* Assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next possibility with next // column if (solveSudoku(grid, row, col + 1)) return true ; } // Removing the assigned num , // since our assumption // was wrong , and we go for // next assumption with // diff num value grid[row][col] = 0; } return false ; } // Driver Code int main() { // 0 means unassigned cells int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; if (solveSudoku(grid, 0, 0)) print(grid); else cout << "no solution exists " << endl; return 0; // This is code is contributed by Pradeep Mondal P } |
C
#include <stdio.h> #include <stdlib.h> // N is the size of the 2D matrix N*N #define N 9 /* A utility function to print grid */ void print( int arr[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) printf ( "%d " ,arr[i][j]); printf ( "\n" ); } } // Checks whether it will be legal // to assign num to the // given row, col int isSafe( int grid[N][N], int row, int col, int num) { // Check if we find the same num // in the similar row , we return 0 for ( int x = 0; x <= 8; x++) if (grid[row][x] == num) return 0; // Check if we find the same num in the // similar column , we return 0 for ( int x = 0; x <= 8; x++) if (grid[x][col] == num) return 0; // Check if we find the same num in the // particular 3*3 matrix, we return 0 int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return 0; return 1; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ int solveSudoku( int grid[N][N], int row, int col) { // Check if we have reached the 8th row // and 9th column (0 // indexed matrix) , we are // returning true to avoid // further backtracking if (row == N - 1 && col == N) return 1; // Check if column value becomes 9 , // we move to next row and // column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already contains // value >0, we iterate for next column if (grid[row][col] > 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num <= N; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)==1) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next possibility with next // column if (solveSudoku(grid, row, col + 1)==1) return 1; } // Removing the assigned num , // since our assumption // was wrong , and we go for next // assumption with // diff num value grid[row][col] = 0; } return 0; } int main() { // 0 means unassigned cells int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; if (solveSudoku(grid, 0, 0)==1) print(grid); else printf ( "No solution exists" ); return 0; // This is code is contributed by Pradeep Mondal P } |
Java
// Java program for above approach public class Sudoku { // N is the size of the 2D matrix N*N static int N = 9 ; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static boolean solveSudoku( int grid[][], int row, int col) { /*if we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0 ; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row][col] != 0 ) return solveSudoku(grid, row, col + 1 ); for ( int num = 1 ; num < 10 ; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1 )) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row][col] = 0 ; } return false ; } /* A utility function to print grid */ static void print( int [][] grid) { for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.print(grid[i][j] + " " ); System.out.println(); } } // Check whether it will be legal // to assign num to the // given row, col static boolean isSafe( int [][] grid, int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0 ; x <= 8 ; x++) if (grid[row][x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for ( int x = 0 ; x <= 8 ; x++) if (grid[x][col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false int startRow = row - row % 3 , startCol = col - col % 3 ; for ( int i = 0 ; i < 3 ; i++) for ( int j = 0 ; j < 3 ; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } // Driver Code public static void main(String[] args) { int grid[][] = { { 3 , 0 , 6 , 5 , 0 , 8 , 4 , 0 , 0 }, { 5 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 }, { 0 , 8 , 7 , 0 , 0 , 0 , 0 , 3 , 1 }, { 0 , 0 , 3 , 0 , 1 , 0 , 0 , 8 , 0 }, { 9 , 0 , 0 , 8 , 6 , 3 , 0 , 0 , 5 }, { 0 , 5 , 0 , 0 , 9 , 0 , 6 , 0 , 0 }, { 1 , 3 , 0 , 0 , 0 , 0 , 2 , 5 , 0 }, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 4 }, { 0 , 0 , 5 , 2 , 0 , 6 , 3 , 0 , 0 } }; if (solveSudoku(grid, 0 , 0 )) print(grid); else System.out.println( "No Solution exists" ); } // This is code is contributed by Pradeep Mondal P } |
Python3
# N is the size of the 2D matrix N*N N = 9 # A utility function to print grid def printing(arr): for i in range (N): for j in range (N): print (arr[i][j], end = " " ) print () # Checks whether it will be # legal to assign num to the # given row, col def isSafe(grid, row, col, num): # Check if we find the same num # in the similar row , we # return false for x in range ( 9 ): if grid[row][x] = = num: return False # Check if we find the same num in # the similar column , we # return false for x in range ( 9 ): if grid[x][col] = = num: return False # Check if we find the same num in # the particular 3*3 matrix, # we return false startRow = row - row % 3 startCol = col - col % 3 for i in range ( 3 ): for j in range ( 3 ): if grid[i + startRow][j + startCol] = = num: return False return True # Takes a partially filled-in grid and attempts # to assign values to all unassigned locations in # such a way to meet the requirements for # Sudoku solution (non-duplication across rows, # columns, and boxes) */ def solveSudoku(grid, row, col): # Check if we have reached the 8th # row and 9th column (0 # indexed matrix) , we are # returning true to avoid # further backtracking if (row = = N - 1 and col = = N): return True # Check if column value becomes 9 , # we move to next row and # column start from 0 if col = = N: row + = 1 col = 0 # Check if the current position of # the grid already contains # value >0, we iterate for next column if grid[row][col] > 0 : return solveSudoku(grid, row, col + 1 ) for num in range ( 1 , N + 1 , 1 ): # Check if it is safe to place # the num (1-9) in the # given row ,col ->we # move to next column if isSafe(grid, row, col, num): # Assigning the num in # the current (row,col) # position of the grid # and assuming our assigned # num in the position # is correct grid[row][col] = num # Checking for next possibility with next # column if solveSudoku(grid, row, col + 1 ): return True # Removing the assigned num , # since our assumption # was wrong , and we go for # next assumption with # diff num value grid[row][col] = 0 return False # Driver Code # 0 means unassigned cells grid = [[ 3 , 0 , 6 , 5 , 0 , 8 , 4 , 0 , 0 ], [ 5 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ], [ 0 , 8 , 7 , 0 , 0 , 0 , 0 , 3 , 1 ], [ 0 , 0 , 3 , 0 , 1 , 0 , 0 , 8 , 0 ], [ 9 , 0 , 0 , 8 , 6 , 3 , 0 , 0 , 5 ], [ 0 , 5 , 0 , 0 , 9 , 0 , 6 , 0 , 0 ], [ 1 , 3 , 0 , 0 , 0 , 0 , 2 , 5 , 0 ], [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 4 ], [ 0 , 0 , 5 , 2 , 0 , 6 , 3 , 0 , 0 ]] if (solveSudoku(grid, 0 , 0 )): printing(grid) else : print ( "no solution exists " ) # This code is contributed by sudhanshgupta2019a |
C#
// C# program for above approach using System; class GFG { // N is the size of the 2D matrix N*N static int N = 9; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static bool solveSudoku( int [,] grid, int row, int col) { /*if we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row,col] != 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num < 10; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row,col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1)) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row,col] = 0; } return false ; } /* A utility function to print grid */ static void print( int [,] grid) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write(grid[i,j] + " " ); Console.WriteLine(); } } // Check whether it will be legal // to assign num to the // given row, col static bool isSafe( int [,] grid, int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0; x <= 8; x++) if (grid[row,x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for ( int x = 0; x <= 8; x++) if (grid[x,col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow,j + startCol] == num) return false ; return true ; } // Driver code static void Main() { int [,] grid = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; if (solveSudoku(grid, 0, 0)) print(grid); else Console.WriteLine( "No Solution exists" ); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for above approach // N is the size of the 2D matrix N*N let N = 9; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ function solveSudoku(grid, row, col) { /* If we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row][col] != 0) return solveSudoku(grid, row, col + 1); for (let num = 1; num < 10; num++) { // Check if it is safe to place // the num (1-9) in the given // row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1)) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row][col] = 0; } return false ; } /* A utility function to print grid */ function print(grid) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write(grid[i][j] + " " ); document.write( "<br>" ); } } // Check whether it will be legal // to assign num to the // given row, col function isSafe(grid, row, col, num) { // Check if we find the same num // in the similar row , we // return false for (let x = 0; x <= 8; x++) if (grid[row][x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for (let x = 0; x <= 8; x++) if (grid[x][col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false let startRow = row - row % 3, startCol = col - col % 3; for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } // Driver Code let grid = [ [ 3, 0, 6, 5, 0, 8, 4, 0, 0 ], [ 5, 2, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 8, 7, 0, 0, 0, 0, 3, 1 ], [ 0, 0, 3, 0, 1, 0, 0, 8, 0 ], [ 9, 0, 0, 8, 6, 3, 0, 0, 5 ], [ 0, 5, 0, 0, 9, 0, 6, 0, 0 ], [ 1, 3, 0, 0, 0, 0, 2, 5, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 7, 4 ], [ 0, 0, 5, 2, 0, 6, 3, 0, 0 ] ] if (solveSudoku(grid, 0, 0)) print(grid) else document.write( "no solution exists " ) // This code is contributed by rag2127 </script> |
3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9
Time complexity: O(9(N*N)), For every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)).
Space Complexity: O(N*N), To store the output array a matrix is needed.