Redirecting to
NADOS

Sudoku Using Bit Manipulation

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are give a partially filled 9*9 2-D array(arr) which represents an incomplete sudoku state.
2. You are required to assign the digits from 1 to 9 to the empty cells following some rules.
Rule 1 -> Digits from 1-9 must occur exactly once in each row.
Rule 2 -> Digits from 1-9 must occur exactly once in each column.
Rule 3 -> Digits from 1-9 must occur exactly once in each 3x3 sub-array 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.
Input Format 
9*9 integers ranging from 1 to 9.
0 represents an empty cell.
Output Format 
You have to print the solved sudoku.
Question Video
Constraints 
0 <= arr[i][j] <= 9
Sample Input 
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
Sample 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


  • 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 sub-matrix

    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 sub-matrix 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 sub-matrix 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






Video Solution

Code Solution

Run
 
Run
Id Name