I wrote a sudoku solving program and compiled it, but it seems doesnt work.
It seems totally alright while I print the sudoku on console every step by using the printSuduku function, but the program eventually outputs nothing, I guess the problem may lies in the recursion part Sudoku::solveSudoku. Can you take a look at the code? Thanks for help!
// sudoku.cpp
#include <iostream>
#include "Sudoku.h"
//int Sudoku::sudoku[] = {
// 3, 4, 0, 7, 0, 6, 0, 0, 1,
// 8, 7, 0, 0, 0, 0, 9, 0, 6,
// 0, 0, 0, 8, 9, 1, 0, 0, 3,
// 0, 0, 0, 0, 0, 3, 5, 6, 8,
// 6, 8, 0, 0, 5, 4, 0, 0, 7,
// 9, 1, 0, 6, 0, 0, 0, 0, 0,
// 0, 3, 0, 4, 0, 0, 0, 8, 0,
// 5, 9, 0, 0, 0, 0, 7, 3, 0,
// 7, 0, 0, 5, 3, 8, 0, 1, 9,
//};
int Sudoku::sudoku[] = { // sudoku on wiki
5, 3, 0, 0, 7, 0, 0, 0, 0,
6, 0, 0, 1, 9, 5, 0, 0, 0,
0, 9, 8, 0, 0, 0, 0, 6, 0,
8, 0, 0, 0, 6, 0, 0, 0, 3,
4, 0, 0, 8, 0, 3, 0, 0, 1,
7, 0, 0, 0, 2, 0, 0, 0, 6,
0, 6, 0, 0, 0, 0, 2, 8, 0,
0, 0, 0, 4, 1, 9, 0, 0, 5,
0, 0, 0, 0, 8, 0, 0, 7, 9,
};
//int Sudoku::sudoku[] = {
// 0, 9, 0, 6, 0, 0, 0, 0, 5,
// 0, 6, 3, 0, 0, 5, 0, 7, 4,
// 0, 4, 1, 7, 0, 0, 0, 0, 0,
// 0, 0, 0, 3, 0, 0, 0, 9, 8,
// 0, 8, 4, 9, 6, 0, 0, 5, 1,
// 1, 0, 0, 0, 0, 7, 3, 0, 2,
// 7, 0, 0, 2, 0, 0, 0, 4, 0,
// 0, 0, 0, 0, 7, 9, 0, 3, 6,
// 0, 1, 0, 0, 4, 3, 0, 0, 0,
//};
bool Sudoku::solveSudoku(int subscript) {
for(int attempt = 1; attempt <= 9; attempt++) {
if(isSuitableAnswer(attempt, subscript)) {
sudoku[subscript] = attempt;
// printSudoku(subscript); // for test
if(subscript >= 80 || solveSudoku(findNextBlank(subscript))) {
return true;
}
}
}
sudoku[subscript] = 0;
return false;
}
bool Sudoku::isSuitableAnswer(int attempt, int subscript) {
return !hasSameInColumn(attempt, subscript) && !hasSameInRow(attempt, subscript) && !hasSameInBigBlock(attempt, subscript);
}
int Sudoku::findNextBlank(int subscript) {
while(sudoku[subscript] != 0 || subscript >= 81) {
subscript++;
}
return subscript;
}
bool Sudoku::hasSameInRow(int attempt, int subscript) {
int beginSubscript = subscript / 9 * 9;
int endSubscript = beginSubscript + 9;
for(int i = beginSubscript; i < endSubscript; i++) {
if(sudoku[i] == attempt) {
return true;
}
}
return false;
}
bool Sudoku::hasSameInColumn(int attempt, int subscript) {
int beginSubscript = subscript % 9;
int endSubscript = beginSubscript + 72;
for(int i = beginSubscript; i <= endSubscript; i += 9) {
if(sudoku[i] == attempt) {
return true;
}
}
return false;
}
bool Sudoku::hasSameInBigBlock(int attempt, int subscript) {
int rowBeginSubscript = subscript % 9 / 3 * 3; // x
int rowEndSubscript = rowBeginSubscript + 3; // y
int columnBeginSubscript = subscript / 9 / 3 * 3;
int columnEndSubscript = columnBeginSubscript + 3;
for(int i = rowBeginSubscript; i < rowEndSubscript; i++) {
for(int j = columnBeginSubscript; i < columnEndSubscript; i++) {
if(sudoku[i + 9 * j] == attempt) {
return true;
}
}
}
return false;
}
void Sudoku::printSudoku(int subscript) {
int i = 0;
std::string str;
while(i < 81) {
str += std::to_string(sudoku[i]);
if(subscript != -1 && i == subscript) {
str += "!";
} else {
str += " ";
}
if(i % 9 == 8) {
str += '\n';
}
i++;
}
str += '\n';
std::cout << str;
}
Sudoku::Sudoku() = default;
//sudoku.h
#ifndef SIMPLE_SUDOKU_SOLVER_SUDOKU_H
#define SIMPLE_SUDOKU_SOLVER_SUDOKU_H
class Sudoku {
private:
static int sudoku[81];
public:
/**
* constructor
*/
Sudoku();
/**
* todo
* read in sudoku to array sudoku
*/
void getSudokuContent();
/**
*
* @param attempt
* @param subscript
* @return if there is another same number in current row
*/
static bool hasSameInRow(int attempt, int subscript);
/**
*
* @param attempt
* @param subscript
* @return if there is another same number in current column
*/
static bool hasSameInColumn(int attempt, int subscript);
/**
*
* @param attempt
* @param subscript
* @return if there is another same number in current big block made up by nine blocks
*/
static bool hasSameInBigBlock(int attempt, int subscript);
/**
* solve sudoku
* @param subscript array subscript of sudoku
* @return is the array solved or not
*/
bool solveSudoku(int subscript = findNextBlank(0));
/**
*
* @param attempt
* @param subscript
* @return if this attempt suitable for current position
*/
static bool isSuitableAnswer(int attempt, int subscript);
/**
*
* @param subscript
* @return the subscript of next blank in array sudoku
*/
static int findNextBlank(int subscript);
/**
* prints out sudoku in console
* only for testing or printing result
* @param subscript the subscript that needs to be marked
*/
static void printSudoku(int subscript = -1);
};
#endif //SIMPLE_SUDOKU_SOLVER_SUDOKU_H
// main
#include "Sudoku.h"
int main() {
Sudoku a;
if(a.solveSudoku()) {
a.printSudoku();
}
}
Try a smaller/easier example. In your case you can take the known solution from Wikipedia and only leave out one number. (This brought me right to your first bug)
int Sudoku::sudoku[] = {
5,3,4,6,7,8,9,1,2,
6,7,2,1,9,5,3,4,8,
1,9,8,3,4,2,5,6,7,
8,5,9,7,6,1,4,2,3,
4,2,6,8,5,3,7,9,1,
7,1,3,9,2,4,8,5,6,
9,6,1,5,3,7,2,8,4,
2,8,7,4,1,9,6,3,5,
3,4,5,2,8,6,0,7,9
};
Then work your way back by leaving out more and more numbers. Some additional instrumentation may help you. For example print out why an attempt wasn't a fit, maybe like so:
bool Sudoku::isSuitableAnswer(int attempt, int subscript) {
bool col = hasSameInColumn(attempt, subscript);
bool row = hasSameInRow(attempt, subscript);
bool big = hasSameInBigBlock(attempt, subscript);
if (col)
std::cout << std::to_string(attempt) << " fails the col\n";
if (row)
std::cout << std::to_string(attempt) << " fails the row\n";
if (big)
std::cout << std::to_string(attempt) << " fails the big\n";
return !col && !row && !big;
}