A Sudoku board can be represented as a 9x9 matrix. It is valid if the following three conditions are met:
An empty Sudoku board is also valid.
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
View all Courses