Sudoku recursive rollback, reboot too early

Question

So, I am writing sudoku solver in C ++ and a bit confused. Below is my advice. It works for the first 3 rows of the puzzle, but is not taken when it hits the end of the 4th row. Looking at the code on gdb, it gets to the end of the 4th row, returns to the 6th column, tries, and then frees itself to the end.

A few other notes about the code are the matrix that holds the sudoku board starting at 1.1, not 0.0. Therefore, when solveBoard is initially called parameters (1, 1, 0). I also added the functions setCell and checkConflicts for more information. I have three vectors rowConf, colConf and squConf to store values ​​that have already been placed in the corresponding row, column or square. I do this for hours and cannot get him to pass the 3rd row. Any help is greatly facilitated. Thank you

EDIT: added clearCell ()

bool board::solveBoard(int i, int j, int count) { if (j > 9) { j = 1; i++; printBoard(); if (isSolved()) { printBoard(); cout <<"The Board has been solved!" <<endl <<" The number of recursive calls was: " <<count <<endl; return true; } } if (isBlank(i, j)) { for (int n = 1; n < 10; n++) { if (setCell(i, j, (char)n + '0')) { if (solveBoard(i, j + 1, count + 1)) { return true; } } } } else { return (solveBoard(i, j + 1, count + 1)); } clearCell(i, j); return false; } bool board::setCell(int i, int j, char val) { int intVal; intVal = atoi(&val); if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize && intVal >= 1 && intVal <= BoardSize) { if (!(checkConflicts(intVal, i, j, squareNumber(i, j)))) { return false; } value[i][j] = intVal; // Set flags of the conflicts rowConf[i][intVal] = true; colConf[j][intVal] = true; squConf[squareNumber(i, j)][intVal] = true; return true; } else { throw rangeError("bad value in setCell"); } } bool board::checkConflicts(int val, int i, int j, int k) { if (i < 1 && i > BoardSize && j < 1 && j > BoardSize && k < 1 && k > BoardSize && val < 1 && val > BoardSize) { throw rangeError("bad value in checkConflicts()"); } if (rowConf[i][val] || colConf[j][val] || squConf[k][val]) { return false; } else { return true; } } Initial Board: ----------------------------- | 3 | 8 | ----------------------------- | | 7 | 5 ----------------------------- | 1 | | ----------------------------- ----------------------------- | | | 3 6 ----------------------------- | 2 | 4 | ----------------------------- | 7 | | ----------------------------- ----------------------------- | | 6 | 1 3 ----------------------------- | 4 5 | 2 | ----------------------------- | | | 8 ----------------------------- ----------------------------- Final Output: ----------------------------- | 3 2 4 | 1 8 5 | 6 7 9 ----------------------------- | 6 8 9 | 7 2 3 | 4 1 5 ----------------------------- | 1 5 7 | 4 9 6 | 2 8 3 ----------------------------- ----------------------------- | | | 3 6 ----------------------------- | 2 | 4 | ----------------------------- | 7 | | ----------------------------- ----------------------------- | | 6 | 1 3 ----------------------------- | 4 5 | 2 | ----------------------------- | | | 8 ----------------------------- ----------------------------- void board::clearCell(int i, int j) { int intVal; if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize) { if (value[i][j] != -1) { intVal = value[i][j]; rowConf[i][intVal] = false; colConf[j][intVal] = false; squConf[squareNumber(i, j)][intVal] = false; value[i][j] = -1; } } else { throw rangeError("bad value in setCell"); } } 

Answer 1

Your problem is most likely here:

 if (isBlank(i, j)) { for (int n = 1; n < 10; n++) { if (setCell(i, j, (char)n + '0')) { if (solveBoard(i, j + 1, count + 1)) { return true; } } } } 

Somehow it goes through this section, so it does not go through the else at the end, but since it has not returned yet, it gets stuck.

This requires additional debugging, but here is an idea that might lead to a solution:

 if (isBlank(i, j)) { for (int n = 1; n < 10; n++) { if (setCell(i, j, (char)n + '0')) { if (solveBoard(i, j + 1, count + 1)) { return true; } else { echo 'Looks like it ended on the farthest-level..'; } } else { echo 'Looks like it ended on the second-farthest level.'; } } 

Answer 2

The atoi function expects a string as an argument, that is, an array of characters terminated by the character '\0' , ASCII NUL. You specify a parameter that is a pointer to a character (equivalent to some character binding), but does not guarantee it ends with zero. Please replace intVal = atoi(&val); on intVal = (int)val - '0';

And your checkConflicts should have || operators instead of && in the first if .

This is probably not the cause of the error, but, of course, a correction is needed.