Sudoku Using Bit Manipulation

medium

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 -&gt; Digits from 1-9 must occur exactly once in each row.
Rule 2 -&gt; Digits from 1-9 must occur exactly once in each column.
Rule 3 -&gt; Digits from 1-9 must occur exactly once in each 3x3 sub-array of the given 2D array.

Assumption -&gt; The given Sudoku puzzle will have a single unique solution.
Note -&gt; 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.

Constraints

0 &lt;= arr[i][j] &lt;= 9

Notice

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.

Example

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

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

Utf - 8 Encoding

N Queens Using Bit