Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
sudoku

# How to check if a sudoku board is valid

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.

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