Check if the given board is valid Sudoku or not explanation with solution in CPP

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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

 

Example 2:

Input:
[
  ["8","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: false

 

Explanation:

The solution is very simple as explained below:

Here we have to check 3 condition for each field.
1. Every row should have numbers from 1 to 9 without repetition.
2. Every column should have numbers from 1 to 9 without repetition.
3. 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:

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

2. Set row[i][n], column[j][n], square[k][n] to true.

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

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

/*
* File     : valid_sudoku.cpp
*/

#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; 
}