Sudoku Solver in C++ weekend challenge

Question

I am very new to programming (using C++) and coded a sudoku solver as a weekend challenge. I guess there are so many things to criticize, but I would really appreciate some constructive criticism. Just what strikes you the most. If you want to run the code, a "sudoku.txt" has to be in the same directory. It's content are 9 lines with 9 numbers, representing the whole field. Zeroes are empty fields.

Here some brief explanation of what's going on: The field is represented by an 1D int array with 81 elements. Used fields and left possibilities are counted throughout. There is also another array with 81 elements, but those are arrays themselves with 9 elements. They represent the possible numbers for every block. 0-8 is mapped to the numbers 1-9. When the value at [5] is 1, that means that the number 5+1 is a possible number for that block. In the last array there are attributes for each block. When reading the file, the possible numbers for every block are calculated. The recursive function first checks if it is already finished or can't be finished. Then it looks for the block with the least possibilities (best case 1 possibility). Then the function is called recursively as many times as there are possibilities for this block. If it returns the solution, that's the field we want.

I compared the runtime to other implementations http://www.sanfoundry.com/cpp-program-solve-sudoku-problem-backtracking/ and Sudoku Solver in C and figured that my one is quite fast. Am I missing something or is my one actually okayish fast?

Please no flame answers :)

#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <ctime>
#include <iomanip> 

// SUDOKU SOLVER v1.337

struct blockAttributes
{
    int row, column, box, possibilities = 0;
};

struct sudokuField
{
    int usedFields{ 0 };
    int possibilities{ 0 };
    int values[9 * 9];
    int possField[9 * 9][9];
    blockAttributes attributeField[9 * 9];
};

void calcPossMove(int x, int y, sudokuField &field)
{

    int i{ x + y * 9 };

    if (field.values[i] != 0) { return; }

    int row{ field.attributeField[i].row };
    int column{ field.attributeField[i].column };
    int box{ field.attributeField[i].box };
    int numbers[9]{ 0 };

    int tmp{ 0 };
    for (int j = 0; j < 9; ++j) {
        // check horizontally and vertically
        tmp = field.values[j + (row * 9)];
        if (tmp != 0) {
            numbers[tmp - 1]++;
        }
        tmp = field.values[column + (j * 9)];
        if (tmp != 0) {
            numbers[tmp - 1]++;
        }
        // check 3x3 box
        tmp = field.values[((box / 3) * 27) + ((box % 3) * 3) + (j % 3) + ((j / 3) * 9)];
        if (tmp != 0) {
            numbers[tmp - 1]++;
        }
    }

    // write possibilities to field
    for (int j = 0; j < 9; ++j) {
        if (numbers[j] == 0) {
            field.possField[i][j]++;
            field.attributeField[i].possibilities++;
            field.possibilities++;
        }
    }
}

void updatePoss(int x, int y, int n, sudokuField &field)
{
    int i{ x + y * 9 };
    int row{ field.attributeField[i].row };
    int column{ field.attributeField[i].column };
    int box{ field.attributeField[i].box };

    // update block itself
    for (int j = 0; j < 9; ++j) {
        if (field.possField[i][j] != 0) {
            field.possField[i][j] = 0;
            field.attributeField[i].possibilities--;
            field.possibilities--;
        }
    }

    int tmp{ 0 };
    for (int j = 0; j < 9; ++j) {
        // update horizontally and vertically
        tmp = j + (row * 9);
        if (field.possField[tmp][n - 1] != 0) {
            field.possField[tmp][n - 1] = 0;
            field.attributeField[tmp].possibilities--;
            field.possibilities--;
        }
        tmp = column + (j * 9);
        if (field.possField[tmp][n - 1] != 0) {
            field.possField[tmp][n - 1] = 0;
            field.attributeField[tmp].possibilities--;
            field.possibilities--;
        }
        // update 3x3 box
        tmp = ((box / 3) * 27) + ((box % 3) * 3) + (j % 3) + ((j / 3) * 9);
        if (field.possField[tmp][n - 1] != 0) {
            field.possField[tmp][n - 1] = 0;
            field.attributeField[tmp].possibilities--;
            field.possibilities--;
        }
    }
}

void addNumberAt(int x, int y, int n, sudokuField &field)
{
    field.values[x + y * 9] = n;
    field.usedFields++;
    updatePoss(x, y, n, field);
}

sudokuField readSudoko(std::string fileName)
{
    sudokuField field;

    // get input and calc usedFields
    std::ifstream file(fileName);
    int y{ 0 };
    int i{ 0 };
    for (std::string line; std::getline(file, line); ++y) {
        for (int x = 0; x < 9; ++x) {
            i = x + y * 9;
            field.attributeField[i].row = i / 9;
            field.attributeField[i].column = i % 9;
            field.attributeField[i].box = ((i / 3) % 3) + ((i / (3 * 3 * 3)) * 3);
            field.values[i] = line[x] - 48;
            if (line[x] - 48 != 0) {
                field.usedFields++;
            }
        }
    }

    // calc possible moves for every block
    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x) {
            calcPossMove(x, y, field);
        }
    }
    return field;
}

void printField(const sudokuField &field)
{
    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x) {
            std::cout << field.values[x + y * 9] << ((x == 2 || x == 5) ? '|' : ' ');
        }
        std::cout << ((y == 2 || y == 5) ? "\n=================\n" : "\n");
    }
    std::cout << '\n';
}

sudokuField solveSudoku(sudokuField field, int x, int y, int n)
{
    if (field.possibilities == 0 || field.usedFields == 9 * 9) { return field; }
    if (x != -1 && y != -1) {
        addNumberAt(x, y, n, field);
        if (field.possibilities == 0 || field.usedFields == 9 * 9) { return field; }
    }

    int smallest{ 1377 };
    int index{ -1 };
    int tmpPos{ 0 };
    for (int i = 0; i < 9 * 9; ++i) {
        tmpPos = field.attributeField[i].possibilities;
        if (smallest > tmpPos && tmpPos != 0) {
            smallest = tmpPos;
            index = i;
        }
    }

    sudokuField tmp;
    int lastTry{ 0 };
    for (int j = 0; j < field.attributeField[index].possibilities; ++j) {
        for (int t = lastTry; t < 9; ++t) {
            if (field.possField[index][t] == 1) {
                lastTry = t;
                break;
            }
        }
        tmp = solveSudoku(field, index % 9, index / 9, lastTry + 1);
        if (tmp.usedFields == 9 * 9) { return tmp; }
        lastTry++;
    }
    return field;
}

int main()
{
    std::cout << std::setprecision(9);
    long int start = GetTickCount();
    sudokuField field = readSudoko("sudoku.txt");
    printField(field);
    field = solveSudoku(field, -1, -1, -1);
    long int end = GetTickCount();
    std::cout << "\n";
    printField(field);
    std::cout << "solved in: " << float(end - start) / 1000 << " seconds";
    std::cin.get();
    return 0;
}

Answer 1

I see a number of things that could help you improve your program.

Fix the initialization

There is a subtle but real bug lurking in this code. The code contains this structure:

struct sudokuField
{
    int usedFields{ 0 };
    int possibilities{ 0 };
    int values[9 * 9];
    int possField[9 * 9][9];
    blockAttributes attributeField[9 * 9];
};

Because you have specified initialization values for usedFields and possibilities, those will both recieve values, but the other fields will be uninitialized. This does not pose a problem in this code except for possField. Specifically, within the solveSudoku routine, there is a conditional statment:

if (field.possField[index][t] == 1) {
    lastTry = t;
    break;
}

The problem is that the possField is being examined but may never have been initialized to any particular value. This is a bug which should be fixed. There are many ways to address the problem, but the simplest is to simply initialize the field:

    int possField[9 * 9][9]{};    // add default initialization

It's a subtle change, but the C++ standard will now interpret this to zero-initialize each member of the array, fixing this particular problem. However, as I mention later, I think that this could be better handled by turning this into a class instead of a simple struct.

Sanitize user input

If the input file does not exist or is malformed, the program crashes. There are a number of ways that this could be fixed. First is that any character other than 1-9 could simply considered empty or zero. This could be inserted into readSudoku:

if (line[x] < '0' || line[x] > '9') {
    line[x] = '0';
}

For the problem of a missing, one simple way to address that problem would be to more fully initialize the sudokuField structure:

struct sudokuField
{
    int usedFields{ 0 };
    int possibilities{ 0 };
    int values[9 * 9]{};
    int possField[9 * 9][9]{};
    blockAttributes attributeField[9 * 9]{};
};

This much will prevent it from crashing, but it will produce an obviously wrong result:

1 2 3|4 5 6|7 8 9 
0 0 0|1 1 1|1 1 1 
0 0 0|1 1 1|1 1 1 
=================
0 1 1|1 1 1|1 1 1 
0 1 1|1 1 1|1 1 1 
0 1 1|1 1 1|1 1 1 
=================
0 1 1|1 1 1|1 1 1 
0 1 1|1 1 1|1 1 1 
0 1 1|1 1 1|1 1 1 

Next is the possibility of a short line. Because the code reads each line into a string and then indexes into it, if there aren't 9 characters on a line, this will access off the end of the string and possibly crash.

Lastly, there is the problem of a grid like this one:

1...1....
.........
.........
.........
.........
.........
.........
.........
.........

That will cause the program to infinitely recurse until the stack is exhausted and again, the program crashes.

Use objects

Most of your functions operate ono a sudokuField structure and wouldn't make much sense without it. This strongly suggests that the functions would be better implemented as member functions of a class named sudokuField. One way to do that would be to simply convert the functions you have. One way to do that might look like this:

class sudokuField
{
public:
    void read(std::string fileName);
    sudokuField solve(int x=-1, int y=-1, int n=-1) const;
    void printField() const;
protected:
    void calcPossMove(int x, int y);
    void updatePoss(int x, int y, int n);
    void addNumberAt(int x, int y, int n);
private:
    int usedFields{ 0 };
    int possibilities{ 0 };
    int values[9 * 9]{};
    int possField[9 * 9][9]{};
    blockAttributes attributeField[9 * 9]{};
};

However, this still leaves us with the obviously wrong result as above because the values are not all initialized to coherent values. We could fix that by adding a constructor:

sudokuField() :
    usedFields{}, 
    possibilities{9*9},
    values{},
    possField{},
    attributeField{}
{
    int i=0;
    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x, ++i) {
            attributeField[i].row = y;
            attributeField[i].column = x;
            attributeField[i].box = x/3 + 3*(y/3);
        }
    }
}

Eliminate "magic numbers"

There are many numbers in the code, such as 3 and 9 that have a specific meaning in their particular context. By using named constants such as BlocksPerRow or Dimension, the program becomes easier to read and maintain. For cases in which the constant only has sense with respect to a particular object, consider making that constant part of the object.

Consider simplifying data structure

The values of row, column and box within the blockAttributes structure are always the same for every puzzle. Further, everyplace they're referenced, we already have the x and y values and can easily calculate box on the fly. For that reason, the blockAttributes structure can be completely eliminated and the field in the sudokuField class could be

int possCount[9 * 9]{}; 

This stores the number of possibilities for each square and is rationally initialized to 9. One might think that this would do the trick:

int possCount[9 * 9]{9};   // won't work as intended!

However, that would only initialize the first possCount and leave the other 80 initialized to 0.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

Answer 2

I don't know if the algorithm is any good, but here are my comments on your coding style.

There are no comments to explain things. OK its throw away code, but writing comments every time helps it become automatic and makes your code much more readable.

You are using big arrays inside structures and then doing calculations to index the correct cell. Why not use class Cell, class Row, class Column and class Grid.

Use meaningful names for variables, tmp, i, l, etc. don't say why they are there. Use them when you right the code if you have to, but replaces them as soon as you know what they are for.

Pass parameters as constant references unless you are going to change them. This shows that it was your intention that they shouldn't be changed. Also make class functions const where possible, again its an extra level of documentation for the code.

Get rid of the 'magic' numbers, the literals. Factor them all out into static constants. I would argue even 9 should be factored out, because then you could do Mayan Sudoku grids (up to 19).

If you aren't going to change a number make it a const, start and end within main.

Why are you casting an integer to a float and dividing it by an int? (float(end - start)/1000)

Sorry if any of that sounds harsh, its meant to be constructive but its Monday :)