A Sudoku puzzle is a 9 × 9 grid with some numbers between 1 and 9 in it, that has to be filled in so that
- every row,
- every column, and
- each of the nine 3 × 3 blocks
contain all the numbers from 1 to 9.
For example the following matrix is not a valid solution of a Sudoku puzzle: the fourth column contains two 7's, block 4 contains also two 7's, and block 5 contains two 9's (there are more reasons why this matrix is not a valid solution but we will not list all them):
1 8 2 | 3 5 9 | 4 7 6 7 5 3 | 2 6 4 | 9 8 1 6 4 9 | 7 1 8 | 2 5 3 ------+-------+------ 2 6 4 | 9 7 3 | 8 1 5 9 1 7 | 4 8 5 | 9 3 2 8 3 5 | 7 2 1 | 7 4 9 ------+-------+------ 5 9 6 | 1 4 7 | 3 2 8 4 2 8 | 5 3 6 | 1 9 7 3 7 1 | 8 9 2 | 5 6 4
Write a program to determine if a given 9 × 9 matrix is the solution of a Sudoku puzzle.
In the example above we have marked the limits of the 9 blocks to make the example easier to follow, but the delimiter characters do not appear in the input.
Important: the only structures I can use are struct
s and the defined in the vector
library. I cannot use class
es (as I have not studied them yet).
#include <iostream>
#include <vector>
//I know I should not include std
//but I am restricted to do so.
using namespace std;
const int sdk_size = 9;
const int sdk_blocks = 3;
typedef vector<int> permutation;
typedef vector<permutation> sdk;
sdk read_sdk()
{
sdk v(sdk_size, permutation(sdk_size));
for (int y = 0; y < sdk_size; ++y) {
for (int x = 0; x < sdk_size; ++x) {
cin >> v[y][x];
}
}
return v;
}
//Checks if a permutation *is* a permutation, i.e.
//it contains every number in 1..sdk_size once and only once.
bool is_permutation(const permutation& per)
{
vector<bool> used(sdk_size + 1, false);
for (int i = 0; i < sdk_size; ++i) {
if (per[i] < 1 or per[i] > sdk_size or used[per[i]]) {
return false;
}
used[per[i]] = true;
}
return true;
}
bool has_valid_rows(const sdk& v)
{
for (int y = 0; y < sdk_size; ++y) {
if (not is_permutation(v[y])) return false;
}
return true;
}
bool has_valid_cols(const sdk& v)
{
for (int x = 0; x < sdk_size; ++x) {
permutation col(sdk_size);
for (int y = 0; y < sdk_size; ++y) {
col[y] = v[y][x];
}
if (not is_permutation(col)) return false;
}
return true;
}
bool has_valid_blocks(const sdk& v)
{
//A block is a submatrice of v with start point (y0,x0)
//and height and width of sdk_size.
for (int y_0 = 0; y_0 < sdk_size; y_0 += sdk_blocks) {
for (int x_0 = 0; x_0 < sdk_size; x_0 += sdk_blocks) {
permutation block;
for (int dy = 0; dy < sdk_blocks; ++dy) {
for (int dx = 0; dx < sdk_blocks; ++dx) {
block.push_back(v[y_0+dy][x_0+dx]);
}
}
if (not is_permutation(block)) return false;
}
}
return true;
}
bool is_valid_sdk(const sdk& v)
{
if (not has_valid_rows(v)) return false;
if (not has_valid_cols(v)) return false;
if (not has_valid_blocks(v)) return false;
return true;
}
int main()
{
sdk v = read_sdk();
if (is_valid_sdk(v)) {
cout << "The sudoku is well-formed" << endl;
} else {
cout << "The sudoku is not well-formed" << endl;
}
}
struct
can be every bit as powerful as aclass
. \$\endgroup\$ – 200_success Jan 25 '16 at 6:56std::vector
is aclass
. Andstruct
is implemented pretty much the same asclass
. \$\endgroup\$ – Pharap Jan 25 '16 at 7:26std::vector
is certainly aclass
- just a templated one. Astruct
and aclass
are functionally the same things in C++ - the only difference being default access of members (and inheritance) beingprivate
for aclass
andpublic
for astruct
. \$\endgroup\$ – Peter Jan 25 '16 at 11:15