`{"id":"f6766f28-baf5-4607-aaa2-ea740df0cc38","name":"Sudoku Using Bit Manipulation","description":"1. You are give a partially filled 9*9 2-D array(arr) which represents an incomplete sudoku state.\r\n2. You are required to assign the digits from 1 to 9 to the empty cells following some rules.\r\nRule 1 -> Digits from 1-9 must occur exactly once in each row.\r\nRule 2 -> Digits from 1-9 must occur exactly once in each column.\r\nRule 3 -> Digits from 1-9 must occur exactly once in each 3x3 sub-array of the given 2D array.\r\n\r\nAssumption -> The given Sudoku puzzle will have a single unique solution.\r\nNote -> You have to Solve this problem using bits.","inputFormat":"9*9 integers ranging from 1 to 9.\r\n0 represents an empty cell.","outputFormat":"You have to print the solved sudoku. ","constraints":"0 &lt;= arr[i][j] &lt;= 9","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvoid display(vector<vector<int>>& arr){\n \n for(int i=0;i<arr.size();i++){\n for(int j=0;j<arr[i].size();j++){\n cout<<arr[i][j]<<\" \";\n }\n cout<<endl;\n }\n cout<<endl;\n \n}\n\n\nvoid solveSudoku(vector<vector<int>>& arr,vector<int>&rows,vector<int>& cols,vector<vector<int>>& grid,int i,int j){\n \n}\n\n\n\nint main(){\n \n vector<vector<int>>arr(9,vector<int>(9,0));\n vector<int>rows(9,0);\n vector<int>cols(9,0);\n vector<vector<int>>grid(3,vector<int>(3,0));\n \n for(int i=0;i<9;i++){\n for(int j=0;j<9;j++){\n int digit;\n cin>>digit;\n \n arr[i][j]=digit;\n rows[i]|=(1<<digit);\n cols[j]|=(1<<digit);\n grid[i/3][j/3]|=(1<<digit);\n }\n }\n \n solveSudoku(arr,rows,cols,grid,0,0);\n}"},"java":{"code":"// import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void display(int[][] arr){\r\n for (int ii = 0; ii < arr.length; ii++) {\r\n for (int jj = 0; jj < arr.length; jj++) {\r\n System.out.print(arr[ii][jj] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void solveSudoku(int[][] arr, int[] rows, int[] cols, int[][] grid, int i, int j) {\r\n // write your code here. Use display function to display arr\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int[][] arr = new int[9][9];\r\n int[] rows = new int[9];\r\n int[] cols = new int[9];\r\n int[][] grid = new int[3][3];\r\n\r\n for (int i = 0; i < 9; i++) {\r\n for (int j = 0; j < 9; j++) {\r\n int digit = scn.nextInt();\r\n arr[i][j] = digit;\r\n rows[i] |= (1 << digit);\r\n cols[j] |= (1 << digit);\r\n grid[i / 3][j / 3] |= (1 << digit);\r\n }\r\n }\r\n\r\n solveSudoku(arr, rows, cols, grid, 0, 0);\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3 0 6 5 0 8 4 0 0\r\n5 2 0 0 0 0 0 0 0\r\n0 8 7 0 0 0 0 3 1\r\n0 0 3 0 1 0 0 8 0\r\n9 0 0 8 6 3 0 0 5\r\n0 5 0 0 9 0 6 0 0\r\n1 3 0 0 0 0 2 5 0\r\n0 0 0 0 0 0 0 7 4\r\n0 0 5 2 0 6 3 0 0","sampleOutput":"3 1 6 5 7 8 4 9 2 \r\n5 2 9 1 3 4 7 6 8 \r\n4 8 7 6 2 9 5 3 1 \r\n2 6 3 4 1 5 9 8 7 \r\n9 7 4 8 6 3 1 2 5 \r\n8 5 1 7 9 2 6 4 3 \r\n1 3 8 9 4 7 2 5 6 \r\n6 9 2 3 5 1 8 7 4 \r\n7 4 5 2 8 6 3 1 9 \r\n","questionVideo":"https://www.youtube.com/embed/SXimkBvg50Q?end=90","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"f3e3dbef-d2b7-4f6d-b357-2ef3738e6c91","name":"Bit Manipulation For Intermediate","slug":"bit-manipulation-for-intermediate-9995","type":0},{"id":"d181057b-2c65-4016-bdc9-9ea2833f0d2f","name":"Sudoku Using Bit Manipulation","slug":"sudoku-using-bit-manipulation","type":1}],"next":{"id":"0b10cfe2-31a8-434a-bfa9-07cf3cec0946","name":"Sudoku Using Bit Manipulation MCQ","type":0,"slug":"sudoku-using-bit-manipulation-mcq"},"prev":{"id":"0ce55761-de73-4dbf-8861-bccd18e1a1ed","name":"UTF-8 ENCODING","type":3,"slug":"utf-8-encoding"}}}`

Sudoku Using Bit Manipulation

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.

`{"id":"f6766f28-baf5-4607-aaa2-ea740df0cc38","name":"Sudoku Using Bit Manipulation","description":"1. You are give a partially filled 9*9 2-D array(arr) which represents an incomplete sudoku state.\r\n2. You are required to assign the digits from 1 to 9 to the empty cells following some rules.\r\nRule 1 -> Digits from 1-9 must occur exactly once in each row.\r\nRule 2 -> Digits from 1-9 must occur exactly once in each column.\r\nRule 3 -> Digits from 1-9 must occur exactly once in each 3x3 sub-array of the given 2D array.\r\n\r\nAssumption -> The given Sudoku puzzle will have a single unique solution.\r\nNote -> You have to Solve this problem using bits.","inputFormat":"9*9 integers ranging from 1 to 9.\r\n0 represents an empty cell.","outputFormat":"You have to print the solved sudoku. ","constraints":"0 &lt;= arr[i][j] &lt;= 9","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvoid display(vector<vector<int>>& arr){\n \n for(int i=0;i<arr.size();i++){\n for(int j=0;j<arr[i].size();j++){\n cout<<arr[i][j]<<\" \";\n }\n cout<<endl;\n }\n cout<<endl;\n \n}\n\n\nvoid solveSudoku(vector<vector<int>>& arr,vector<int>&rows,vector<int>& cols,vector<vector<int>>& grid,int i,int j){\n \n}\n\n\n\nint main(){\n \n vector<vector<int>>arr(9,vector<int>(9,0));\n vector<int>rows(9,0);\n vector<int>cols(9,0);\n vector<vector<int>>grid(3,vector<int>(3,0));\n \n for(int i=0;i<9;i++){\n for(int j=0;j<9;j++){\n int digit;\n cin>>digit;\n \n arr[i][j]=digit;\n rows[i]|=(1<<digit);\n cols[j]|=(1<<digit);\n grid[i/3][j/3]|=(1<<digit);\n }\n }\n \n solveSudoku(arr,rows,cols,grid,0,0);\n}"},"java":{"code":"// import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void display(int[][] arr){\r\n for (int ii = 0; ii < arr.length; ii++) {\r\n for (int jj = 0; jj < arr.length; jj++) {\r\n System.out.print(arr[ii][jj] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void solveSudoku(int[][] arr, int[] rows, int[] cols, int[][] grid, int i, int j) {\r\n // write your code here. Use display function to display arr\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int[][] arr = new int[9][9];\r\n int[] rows = new int[9];\r\n int[] cols = new int[9];\r\n int[][] grid = new int[3][3];\r\n\r\n for (int i = 0; i < 9; i++) {\r\n for (int j = 0; j < 9; j++) {\r\n int digit = scn.nextInt();\r\n arr[i][j] = digit;\r\n rows[i] |= (1 << digit);\r\n cols[j] |= (1 << digit);\r\n grid[i / 3][j / 3] |= (1 << digit);\r\n }\r\n }\r\n\r\n solveSudoku(arr, rows, cols, grid, 0, 0);\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3 0 6 5 0 8 4 0 0\r\n5 2 0 0 0 0 0 0 0\r\n0 8 7 0 0 0 0 3 1\r\n0 0 3 0 1 0 0 8 0\r\n9 0 0 8 6 3 0 0 5\r\n0 5 0 0 9 0 6 0 0\r\n1 3 0 0 0 0 2 5 0\r\n0 0 0 0 0 0 0 7 4\r\n0 0 5 2 0 6 3 0 0","sampleOutput":"3 1 6 5 7 8 4 9 2 \r\n5 2 9 1 3 4 7 6 8 \r\n4 8 7 6 2 9 5 3 1 \r\n2 6 3 4 1 5 9 8 7 \r\n9 7 4 8 6 3 1 2 5 \r\n8 5 1 7 9 2 6 4 3 \r\n1 3 8 9 4 7 2 5 6 \r\n6 9 2 3 5 1 8 7 4 \r\n7 4 5 2 8 6 3 1 9 \r\n","questionVideo":"https://www.youtube.com/embed/SXimkBvg50Q?end=90","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"f3e3dbef-d2b7-4f6d-b357-2ef3738e6c91","name":"Bit Manipulation For Intermediate","slug":"bit-manipulation-for-intermediate-9995","type":0},{"id":"d181057b-2c65-4016-bdc9-9ea2833f0d2f","name":"Sudoku Using Bit Manipulation","slug":"sudoku-using-bit-manipulation","type":1}],"next":{"id":"0b10cfe2-31a8-434a-bfa9-07cf3cec0946","name":"Sudoku Using Bit Manipulation MCQ","type":0,"slug":"sudoku-using-bit-manipulation-mcq"},"prev":{"id":"0ce55761-de73-4dbf-8861-bccd18e1a1ed","name":"UTF-8 ENCODING","type":3,"slug":"utf-8-encoding"}}}`

Editor

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 -> 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.

Constraints

0 <= arr[i][j] <= 9

Format

Input

9*9 integers ranging from 1 to 9. 0 represents an empty cell.

Output

You have to print the solved sudoku.

Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}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

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}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 ```

Question Video

Discussions

Show Discussion

Related Resources