Sudoku Using Bit Manipulation
1. You are give a partially filled 9*9 2D array(arr) which represents an incomplete sudoku state.Input Format
2. You are required to assign the digits from 1 to 9 to the empty cells following some rules.
Rule 1 > Digits from 19 must occur exactly once in each row.
Rule 2 > Digits from 19 must occur exactly once in each column.
Rule 3 > Digits from 19 must occur exactly once in each 3x3 subarray of the given 2D array.
Assumption > The given Sudoku puzzle will have a single unique solution.
Note > You have to Solve this problem using bits.
9*9 integers ranging from 1 to 9.Output Format
0 represents an empty cell.
You have to print the solved sudoku.Question Video
0 <= arr[i][j] <= 9Sample Input
3 0 6 5 0 8 4 0 0Sample Output
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
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

Editorial
The problem here deals with solving a N*N Sudoku board using the bit manipulation technique. Earlier we have implemented Sudoku using recursion and backtracking. Here we will implement the concepts of bit manipulation to solve Sudoku.
A Sudoku is a N*N board with sum spaces already filled in. One has to fill up all the remaining spaces with the numbers in the range of 1 to N keeping in mind the following rules:
1. No same number in a row
2. No same number in a column
3. No same number in its corresponding submatrix
It is highly recommended to first understand the solution using recursion as this solution will highly rely on the recursive solution.
To abide by the Sudoku number placing rules we will make use of bit manipulation. Here, we will be maintaining a row array and a column array of size N which at any instant will store the numbers already present in that particular row or column. Here, we will represent the number 1 to N in the form of bits by setting the bit at the corresponding position. Also, we will be maintaining a submatrix array of size N1/2 * N1/2 which will be storing the numbers that are already filled up in the submatrix. So now instead of checking for every number by searching in the entire row, column and submatrix by iterating here we can just check for respective bit value. This henceforth makes our code efficient but at the cost of space as we are creating three arrays.
The rest implementation is similar to that of a recursive solution.
Time Complexity: O(NN*N)
For every unassigned position, there are N options available.
Space Complexity: O(N)
The space complexity for the function is linear as we are maintaining three arrays for storing bit manipulation results.
Notes: Recursive space complexity is not taken into account here.

Asked in Companies

Related Topics