Sudoku solution without the use of classes

Question

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

Answer 1

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<bool> used(sdk_size, false);
  for (int i = 0; i < sdk_size; ++i) {
    int val = next(v, x, y);
    if (val < 1 or val > 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.

Answer 2

On the overall, your code looks ok. Some points you could improve:

• Be more consistent with indentation (you use 2 spaces and 4 spaces inconsistently. I would suggest using 4 spaces everywhere).
• Be more consistent with spacing. Around the + operator, you sometimes use spaces and sometimes not. I would suggest always using spaces.
• You should add error handling when reading data from stdin (the call to cin can fail).
• Try not to use abbreviations when not necessary; it lowers the readability of your code. sdk is typically used for "software development kit". I would suggest naming your function readSudoku instead of read_sdk.
• Send error messages to cerr, and normal log messages to cout. For small programs this does not change a lot, but for big programs it is useful to be able to print errors only.
• Do not write if conditions on a single line; this lowers readability: (if (...) return false). It is easier to read when this is on two lines.
• Do not use single letter names for parameters like sdk v. Now your code is very small so this does not change a lot, but v does not have any meaning. Naming it e.g. grid would be a lot better.
• Do not use and, or and not. Prefer &&, || and ! (the written versions of the operators exist only for backwards compatibility and historical reason, they should not be used in new code, see this).

Answer 3

• It's usually preferred to capitalize custom types, such as Permutation. This will help distinguish them from variables and functions.

• There's no need for this duplication:

  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;
  

  Just use the || operator so that only one return false is needed:

  if (!has_valid_rows(v)
     || !has_valid_cols(v)
     || !has_valid_blocks(v))
  {
      return false;
  }
  
  return true;
  

  (I've also replaced not with ! as mentioned in a comment.)

• For added protection and self-documentation, you can add const to v's initialization.

Answer 4

1. Well, I really abhor using namespace std;, but you already know why it is bad, so we'll let that pass.

2. Let's look at your function-names:

   has_valid_rows
   has_valid_cols
   has_valid_blocks
   

   According to the name, those functions answer the question:
   Does the input have any valid rows/columns/blocks?

   Unfortunately, that's not the question they actually answer:
   Are all the rows/columns/blocks valid?

   A better name would beall_X_valid or with negated output has_invalid_X.

3. Yes, C++ has and, or, not and the like. And you should know about them, because someone might use them. Still, consider abstaining, as they are uncommon, and don't actually buy you anything.

4. You should axe is_permutation and do the test directly in the function.
   Just the delegation has the same complexity (or more) than doing it directly on average, so it is a net loss according to any metric.

   That's certainly no less efficient than Edward's suggestion even if that should be inlined, and might be more maintainable.

   You could explore std::bitset as the set's length is a compile-time constant.
   Or just go with an unsigned, and depend on that always having at least 16 value-bits.

5. Your program does actually give a sensible output on input-failure, namely "The sudoku is not well-formed". But I'm not sure that's anything but serendipity.
   Are you sure you shouldn't explicitly handle that?

6. Don't use std::endl unless you might need an explicit flush.
   Admittedly, doing that once, at the end of your program, doesn't really cost much performance or space, but it's a bad habit to get into.

7. Regarding your constants:

   Take a hard look at them, and think about how to generalize to bigger (or smaller, though that's boring) sudokus, and you will see that the only fundamental constant for a sudoku is length of a block.

   Length of each side, count of different symbols, and blocksize, is blocklength squared.
   Size of the whole sudoku is the product of the sides, or blocklength to the 4th power.

Answer 5

The program looks good to me, i.e. I cannot imagine cases for false positives or negatives.

I have only some minor remarks:

• used vector in is_permutation is one element too big (in other words, its element at position 0 is never used); you could declare the vector of the right size, and always access element at index per[i]] - 1, instead of per[i]].

• I suggest your main function does return a value, e.g. 0 on success, 1 on error.

• I recommend always using brackets for if/else/loops etc. statements, e.g. in places like if (not is_permutation(v[y])) return false;. In this way, you avoid confusion if you would like to add other statements to the if/else clause later.

• Although not a problem in any way, I had never seen the operator not used like this in C++ (I knew only about !). However, I just discovered that operator not does, in fact, exist. I learnt something new today as well.

EDIT: As pointed out in comments: it is not a good practice to use the verbose form of the operators (e.g. and instead of &&) since they are provided only for compatibility with old keyboards, and virtually never used in a productive environment.

Answer 6

Simplification

Every time you use is_permutation you negate it so I suggest you change it to:

bool is_not_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 true;
    }
    used[per[i]] = true;
  }
  return false;
}

Which effectively negates the output at the function instead of at function reference.

Answer 7

I think the best and easy way to validate a Sudoku grid is by constructing a new vector for row, column, square separately from the main matrix like this:

bool checkSudokuStatus(const std::vector<std::vector<int>>& grid)
{
    for (int i = 0; i < SudokuSize; i++)
    {
        std::vector<int> row(SudokuSize);
        std::vector<int> square(SudokuSize);
        std::vector<int> column(SudokuSize);

        for (int j = 0; j < SudokuSize; j++)
        {
            row[j] = grid[j][i];
            column[j] = grid[i][j];
            square[j] = grid[(i / BlockSize) * BlockSize + j / BlockSize][i * BlockSize % SudokuSize + j % BlockSize];
        }
        if (!(validate(column) && validate(row) && validate(square)))
            return false;
    }

    return true;
}

In order to validate each vector, simply sort it just to check if it is equal to the index counter. If you are allowed to use STL <algorithm> functions like std::sort, it would be very easy to implement it like this:

bool validate(std::vector<int> check)
{
    int i = 0;
    std::sort(check.begin(), check.end());
    for (int number : check)
    {
        if (number != ++i)
            return false;
    }
    return true;
}

Putting the code together:

#include <iostream>
#include <vector>
#include <algorithm>

constexpr unsigned SudokuSize = 9;
constexpr unsigned BlockSize = 3;

bool validate(std::vector<int> check)
{
    int i = 0;
    std::sort(check.begin(), check.end());
    for (int number : check)
    {
        if (number != ++i)
            return false;
    }
    return true;
}

bool checkSudokuStatus(const std::vector<std::vector<int>>& grid)
{
    for (int i = 0; i < SudokuSize; i++)
    {
        std::vector<int> row(SudokuSize);
        std::vector<int> square(SudokuSize);
        std::vector<int> column(SudokuSize);

        for (int j = 0; j < SudokuSize; j++)
        {
            row[j] = grid[j][i];
            column[j] = grid[i][j];
            square[j] = grid[(i / BlockSize) * BlockSize + j / BlockSize][i * BlockSize % SudokuSize + j % BlockSize];
        }
        if (!(validate(column) && validate(row) && validate(square)))
            return false;
    }

    return true;
}

int main()
{
    std::vector<std::vector<int>> v
    {
        {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,  6, 3, 2},
        {8, 3, 5,  6, 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}
    };

    if (checkSudokuStatus(v))
        std::cout << "The sudoku is well-formed" << std::endl;
    else
        std::cout << "The sudoku is not well-formed" << std::endl;
}