Sudoku solution without the use of classes

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 structs and the defined in the vector library. I cannot use classes (as I have not studied them yet).

```
#include
#include
//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 permutation;
typedef vector sdk;

sdk read_sdk()
{
sdk v(sdk_size, permutation(sdk_size));
for (int y = 0; y > 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 used(sdk_size + 1, false);
for (int i = 0; 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(c

I see some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

The comment in the code seems to indicate you know this and can't change it for some reason, but others who may read this question and answer may benefit

Simplify your code

The current code has this function:

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;
}

However, this could be considerably shorter and easier to read and understand if written like this:

bool is_valid_sdk(const sdk& v)
{
  return has_valid_rows(v) and has_valid_cols(v) and has_valid_blocks(v);
}

Reconsider the design

Although the current code works, it's not very efficient in that it makes a copy of each vector in order to check it. An alternative approach would be to allow checking in place without making a copy. One way to do that would be to separate the iteration through the rows/columns/blocks into a separate function that could be passed to the is_permutation function. For example:

bool is_permutation(const sdk& v, int x, int y, 
                    int(*next)(const sdk& v, int& x, int& y))
{
  vector used(sdk_size, false);
  for (int i = 0; i  sdk_size or used[val-1]) {
      return false;
    }
    used[val-1] = true;
  }
  return true;
}

int next_in_blk(const sdk& v, int &x, int &y) 
{
    int val = v[x][y];
    if (++y % sdk_blocks == 0) {
        y -= sdk_blocks;
        ++x;
    }
    return val;
}

bool has_valid_blocks(const sdk& v)
{
  for (int i = 0; i < sdk_size; ++i) {
    int x = sdk_blocks * (i / sdk_blocks);
    int y = sdk_blocks * (i % sdk_blocks);
    if (not is_permutation(v, x, y, next_in_blk)) return false;
  }
  return true;
}

The corresponding functions for row and col are even simpler.

StackExchange Code Review Q#117763, answer score: 17