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