Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
sudoku

How to check if a sudoku board is valid

Educative Answers Team

A Sudoku board can be represented as a 9x9 matrix. It is valid if the following three conditions are met:

  • Each row contains unique values from 1-9.
  • Each column contains unique values from 1-9.
  • Each of the 9 sub-squares, of size 3x3, ​contains a unique value from 1-9.

An empty Sudoku board is also valid.

svg viewer

Algorithm

  1. Check if the rows and columns contain values 1-9, without repetition.
  2. If any row or column violates this condition, the Sudoku board is invalid.
  3. Check to see if each of the 9 sub-squares contains values 1-9, without repetition. If they do, the Sudoku board is valid; otherwise, it is invalid.

Implementation

Please note that a “0” denotes an empty cell in the implementation below:

#include <iostream>
#include <set>
using namespace std;
// Function to check if a given row is valid. It will return:
// -1 if the row contains an invalid value
// 0 if the row contains repeated values
// 1 is the row is valid.
int valid_row(int row, int grid[][9]){
  set<int> s;
  for(int i = 0; i < 9; i++){
    // Checking for values outside 0 and 9; 
    // 0 is considered valid because it 
    // denotes an empty cell.
    // Removing zeros and the checking for values and
    // outside 1 and 9 is another way of doing 
    // the same thing.
    if(grid[row][i] < 0 || grid[row][i] > 9){
      cout<<"Invalid value"<<endl;
      return -1;
    }
    else
    { //Checking for repeated values.
      if(grid[row][i] != 0){
        if(s.insert(grid[row][i]).second == false){
          return 0;
        }
      }
    }
  }
  return 1;
}
// Function to check if a given column is valid. It will return:
// -1 if the column contains an invalid value
// 0 if the column contains repeated values
// 1 is the column is valid.
int valid_col(int col, int grid[][9]){
  set<int> s;
  for(int i = 0; i < 9; i++){
    // Checking for values outside 0 and 9; 
    // 0 is considered valid because it 
    // denotes an empty cell.
    // Removing zeros and the checking for values and
    // outside 1 and 9 is another way of doing 
    // the same thing.
    if(grid[i][col] < 0 || grid[i][col] > 9){
      cout<<"Invalid value"<<endl;
      return -1;
    }
    else
    { // Checking for repeated values.
      if(grid[i][col] != 0){
        if(s.insert(grid[i][col]).second == false){
          return 0;
        }
      }
    }
  }
  return 1;
}
// Function to check if all the subsquares are valid. It will return:
// -1 if a subsquare contains an invalid value
// 0 if a subsquare contains repeated values
// 1 if the subsquares are valid.
int valid_subsquares(int grid [][9]){
  for(int row = 0; row < 9; row = row + 3){
    for(int col = 0; col < 9; col = col + 3){
        set<int> s;
        for(int r = row; r < row + 3; r++){
          for(int c = col; c < col + 3; c++){
            // Checking for values outside 0 and 9; 
            // 0 is considered valid because it 
            // denotes an empty cell.
            // Removing zeros and the checking for values and
            // outside 1 and 9 is another way of doing 
            // the same thing.
            if(grid[r][c] < 0 || grid[r][c] > 9){
              cout<<"Invalid value"<<endl;
              return -1;
            }
            else{
              // Checking for repeated values
              if(grid[r][c] != 0){
                if(s.insert(grid[r][c]).second == false){
                  return 0;
                }
              } 
            }
          }
        }    
    }
  }
  return 1;
}
//Function to check if the board invalid.
void valid_board(int grid [][9]){
  for(int i = 0; i < 9; i++){
    int res1 = valid_row(i, grid);
    int res2 = valid_col(i, grid);
    // If a row or a column is invalid, then the board is invalid.
    if(res1 < 1 || res2 < 1){
      cout<<"The board is invalid"<<endl;
      return;
    }
  }
  // if any one the subsquares is invalid, then the board is invalid.
  int res3 = valid_subsquares(grid);
  if(res3 < 1){
    cout<<"The board is invalid"<<endl;
  }
  else{
    cout<<"The board is valid"<<endl;
  }
}
// Function to print the board.
void print_board(int grid[] [9]){
  for( int row = 0; row < 9; row++){
    cout<<"[";
    for(int col = 0; col < 9; col++){
      cout<<grid[row][col]<<", ";
    }
    cout<<"]"<<endl;
  }
}
int main() {
  // A valid board.
  int board [9][9] = {
  {1, 4, 7, 0, 0, 0, 0, 0, 3},
  {2, 5, 0, 0, 0, 1, 0, 0, 0},
  {3, 0, 9, 0, 0, 0, 0, 0, 0},
  {0, 8, 0, 0, 2, 0, 0, 0, 4},
  {0, 0, 0, 4, 1, 0, 0, 2, 0},
  {9, 0, 0, 0, 0, 0, 6, 0, 0},
  {0, 0, 3, 0, 0, 0, 0, 0, 9},
  {4, 0, 0, 0, 0, 2, 0, 0, 0},
  {0, 0, 1, 0, 0, 8, 0, 0, 7},
  };
  print_board(board);
  valid_board(board);
  // An invalid board, the first row contains repeated values.
  int board2 [9][9] = {
  {1, 4, 4, 0, 0, 0, 0, 0, 3},
  {2, 5, 0, 0, 0, 1, 0, 0, 0},
  {3, 0, 9, 0, 0, 0, 0, 0, 0},
  {0, 8, 0, 0, 2, 0, 0, 0, 4},
  {0, 0, 0, 4, 1, 0, 0, 2, 0},
  {9, 0, 0, 0, 0, 0, 6, 0, 0},
  {0, 0, 3, 0, 0, 0, 0, 0, 9},
  {4, 0, 0, 0, 0, 2, 0, 0, 0},
  {0, 0, 1, 0, 0, 8, 0, 0, 7},
  };
  print_board(board2);
  valid_board(board2);
  return 0;
}

RELATED TAGS

c++
sudoku
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring