Судоку рекурсивный откат, не возвращаясь слишком рано

Поэтому я пишу решатель судоку на C ++ и столкнулся с небольшим затруднением. Ниже приведен код моего решения. Он работает для первых 3-х рядов головоломки, но не повторяется при попадании в конец 4-го ряда. Глядя на код в gdb, он попадает в конец 4-й строки, возвращается к 6-му столбцу, пытается, а затем возвращается к концу.

Пара других замечаний о коде — матрица, в которой находится доска судоку, начинается с 1,1, а не с 0,0. Поэтому при первоначальном вызове executeBoard параметры равны (1, 1, 0). Я также прикрепил функции setCell и checkConflicts для большего понимания. У меня есть три вектора rowConf, colConf и squConf для хранения значений, которые уже были помещены в соответствующую строку, столбец или квадрат. Я занимаюсь этим часами и не могу пройти мимо 3-го ряда. Любая помощь очень ценится. Спасибо!

РЕДАКТИРОВАТЬ: Добавлено 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");
}
}

4

Решение

Ваша проблема, скорее всего, здесь:

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 в конце концов, но так как он не вернулся раньше, он застрял.

Это требует дополнительной отладки, но вот идея, которая может привести к решению:

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.';
}
}
0

Другие решения

atoi функция ожидает строка в качестве аргумента, это массив символов, заканчивающийся символом '\0', ASCII NUL. Вы задаете параметр, являющийся указателем на символ (эквивалентный некоторому массиву символов), но не гарантировать это заканчивается нулем. Пожалуйста, замените intVal = atoi(&val); с intVal = (int)val - '0';

И ваш checkConflicts должен иметь || операторы вместо && во-первых if,

Это, вероятно, не причины ошибки, но, безусловно, нуждаются в исправлении.

0

По вопросам рекламы [email protected]