Below are the rules for a Sudoku to be valid:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the 9 3×3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Example 1: Input: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: true
Solution Explanation:
The solution is very simple as explained below:
Here we have to check 3 condition for each field.
- Every row should have numbers from 1 to 9 without repetition.
- Every column should have numbers from 1 to 9 without repetition.
- Every square should have numbers from 1 to 9 without repetition.
To do this, we take 3 Boolean 9 by 9 matrix for storing the value of Row, Column and Square, and initialize all of it to false.
Now we iterate through the board, and update our Boolean matrix as below:
- For any numeric value “n”, we check if the value of value of row[i], column[j], square[k] is true, then it means that, the number “n” has appeared before. Hence we return false.
else
- Set row[i][n], column[j][n], square[k][n] to true.
- Similarly, we iterate through out the board, and if there are no duplicates, then we return true.
Important:
We can get the row from outer for loop.
We can get the column from inner for loop.
But, how to get the value of the square?
Below is the calculation on getting the value of the square, that a particular number resides in.
1. i controls which group of squares we fall in 2. j controls which square within the group See below for reference Rows 0 - 2 -> Squares 0 - 2 | Col 0 - 2 -> Square 0, Col 3 - 5 -> Square 1, Col 6 - 8 -> Square 2 Rows 3 - 5 -> Squares 3 - 5 | Col 0 - 2 -> Square 3, Col 3 - 5 -> Square 4, Col 6 - 8 -> Square 5 Rows 6 - 8 -> Squares 6 - 8 | Col 0 - 2 -> Square 6, Col 3 - 5 -> Square 7, Col 6 - 8 -> Square 8
Hence:
i/3*3 will give the segment of the block. j/3 will give the column inside the segment of the block.
Solution in C++
#include<iostream> #include<vector> using namespace std; bool isValidSudoku(vector<vector<char> > &board) { int row[9][9] = {0}; int column[9][9] = {0}; int square[9][9] = {0}; for(int i = 0; i < board.size(); ++ i) for(int j = 0; j < board[i].size(); ++ j) if(board[i][j] != '.') { //get the integer value of the number by doing board[i][j] - '0' //need -1 because the index of array is 0~8 by subtracting 1 from the above int value int num = board[i][j] - '0' - 1; int k = i / 3 * 3 + j / 3; if(row[i][num] || column[j][num] || square[k][num]) return false; row[i][num] = column[j][num] = square[k][num] = 1; } return true; } int main() { vector<vector<char> > board = { { '5', '3', '.', '.', '7', '.', '.', '.', '.' }, { '6', '.', '.', '1', '9', '5', '.', '.', '.' }, { '.', '9', '8', '.', '.', '.', '.', '6', '.' }, { '8', '.', '.', '.', '6', '.', '.', '.', '3' }, { '4', '.', '.', '8', '.', '3', '.', '.', '1' }, { '7', '.', '.', '.', '2', '.', '.', '.', '6' }, { '.', '6', '.', '.', '.', '.', '2', '8', '.' }, { '.', '.', '.', '4', '1', '9', '.', '.', '5' }, { '.', '.', '.', '.', '1', '.', '.', '7', '9' } }; bool result = isValidSudoku(board); if (result) cout<<"The sudoku is valid"<<endl; else cout<<"The sudoku is not valid"<<endl; return 0; }
Output:
The sudoku is not valid
No Responses