The objective of Soduku game is to fill a \(9 \times 9\) grid with digits so that each column, each row, and each of the nine \(3 \times 3\) sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. A solved Soduku game is like:
To check if a \(9 \times 9\) grid is a valid solution, we need to check every row, every column and \(3 \times 3\) subgrids. It is not hard to check rows and columns, but checking subgrids is little tricky. When considering going through the grid only one time, it will be much harder.
My solution is define a 9-item-long vector to count the occurrences of each element in a row, a 9-item-long vector to count the occurrences of each element in a column, and a \(3 \times 9\) matrix to count the occurrences of elements in the 3 nearby subgrids. The value of each element in grid can be used as the indices of the counting vectors, because they are supposed to be in the range of 0~9. If found one occurrence greater than one in the vectors, then return false.
bool isSoduku(vector<vector<int>> grid) {
const int dim=3;
vector<vector<int>> subGridCnt(grid[0].size()/dim,vector<int>(dim*dim+1,0)); // count the occurrences of elements in 3 nearby 3x3 subgrids.
// check row,column, subgrids
for(int i=0;i<grid.size();++i) {
if(i%3==0) { // reset subGridCnt
subGridCnt.clear();
for(int cnt=0;cnt<grid[0].size()/dim;++cnt)
subGridCnt.push_back(vector<int>(dim*dim+1,0));
}
vector<int> rowCnt(grid[0].size()+1,0); // count the occurrences of elements in one row.
vector<int> colCnt(grid.size()+1,0); // count the occurrences of elements in one column.
for(int j=0;j<grid[i].size();++j) {
rowCnt[grid[i][j]]++;
colCnt[grid[j][i]]++;
subGridCnt[j/3][grid[i][j]]++;
if(rowCnt[grid[i][j]]>1) {
cout<<"Error: "<<rowCnt[grid[i][j]]<<" "<<grid[i][j]<<"s found in row "<<i+1<<"."<<endl;
return false;
}
if(colCnt[grid[j][i]]>1) {
cout<<"Error: "<<colCnt[grid[j][i]]<<" "<<grid[j][i]<<"s found in column "<<i+1<<"."<<endl;
return false;
}
if(subGridCnt[j/3][grid[i][j]]>1) {
cout<<"Error: duplicate elements found in subgrid <"<<i/3+1<<","<<j/3+1<<">: "<<grid[i][j]<<"."<<endl;
return false;
}
}
}
return true;
}
To test above funciton, following code segment can be used:
int main() {
vector<vector<int>> grid={
{6,5,7,2,9,1,8,4,3},
{8,9,4,6,7,3,2,1,5},
{1,2,3,5,8,4,7,9,6},
{5,6,8,3,4,7,1,8,2},
{7,3,1,9,2,8,5,6,4},
{4,8,2,1,6,5,3,7,9},
{2,7,6,8,3,9,4,5,1},
{3,4,5,7,1,6,9,2,8},
{9,1,8,4,5,2,6,3,7}
};
for(int i=0;i<grid.size();++i) {
for(int j=0;j<grid[i].size();++j) {
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
if(isSoduku(grid))
cout<<"A valid solution!"<<endl;
else
cout<<"Not a solution!"<<endl;
}