Почему моя программа Судоку не возвращает результат?
Поэтому я попытался реализовать судоку с помощью алгоритма возврата. Я не понимаю, почему мой код не дает ожидаемого результата.
Я создал цикл, в котором он проверяет пустую ячейку (обозначенную 0) в судоку. Как он находит, координаты для него передаются в функцию под названием возможный Entriescheck(). Эта функция записывает в глобально объявленный массив с именем возможным Entries[9], цифры, которые могут быть, возможно, заполнены в ячейке, координаты которой переданы первоначально.
Я узнал этот алгоритм из этих видео: https://www.youtube.com/watch?v=NuodN41aK3g https://www.youtube.com/watch?v=QI0diwmx3OY
Ожидаемый результат - решенное судоку. Это не работает ожидаемым образом. Скорее, он замерзает. Небольшая помощь будет много значить. Спасибо.
#include <stdio.h>
#include <stdlib.h>
int board[9][9] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0},
};
int possibleEntries[9];
void possibleEntriescheck(int i, int j)
{
int x,a=0,k,l,y;
for(x=0;x<9;x++)
possibleEntries[x]=0;
for(x=0;x<9;x++)
{
if(board[i][x]!=0)
possibleEntries[board[i][x]-1]=1;
}
for(x=0;x<9;x++)
{
if(board[x][j]!=0)
possibleEntries[board[x][j]-1]=1;
}
if(i==0 || i==1 || i==2)
k=0;
else if(i==3 || i==4 || i==5)
k=3;
else
k=6;
if(j==0 || j==1 || j==2)
l=0;
else if(j==3 || j==4 || j==5)
l=3;
else
l=6;
for(x=k;x<k+3;x++)
{
for(y=l;y<l+3;y++)
if(board[x][y]!=0)
possibleEntries[board[x][y]-1]=1;
}
for(x=0;x<9;x++)
{
if(possibleEntries[x]==0)
possibleEntries[x]=x+1;
else
possibleEntries[x]=0;
}
}
int isFull()
{
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(board[i][j]==0)
return 0;
}
}
return 1;
}
void solveSudoku()
{
int i,j,x,b=0,k;
if(isFull())
{
printf("The sudoku board is:\n");
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("\t%d",board[i][j]);
printf("\n");
}
}
else
{
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(board[i][j]==0)
{
possibleEntriescheck(i,j);
for(x=0;x<9;x++)
{
if(possibleEntries[x]!=0)
{
board[i][j]=possibleEntries[x];
solveSudoku();
board[i][j]=0;
}
}
}
}
}
}
return;
}
int main()
{
solveSudoku();
}
1 ответ
Вы неправильно осуществили возврат. Как также объясняется в видео, фактический алгоритм должен выглядеть следующим образом:
solve():
if the sudoku is solved
print field
terminate
x,y = the next vacant field
for each possible value in that field
assign value to x,y
call solve() recursively to try with the assigned value
clear vacant field
Теперь то, что делает ваш код
solve():
if the sudoku is solved
print field
return
for each field in the sudoku
if field is vacant
for each possible value
assign value
solve recursively
reset field to unassigned
Теперь это действительно решает судоку. Но есть две проблемы с этим подходом:
A: Это не закончится, как только будет решено судоку. На самом деле эта ошибка была также в коде, представленном в видео. Просто return в рекурсивном вызове прервет метод текущего вызова и продолжит рекурсию "на один вызов выше". Таким образом, в основном алгоритм решает судоку всеми возможными способами (если их несколько, в противном случае он просто пытается любым возможным способом присвоить значения).
Б: Это намного серьезнее. Ваш алгоритм не только генерирует все возможные решения, но также пробует каждый порядок присвоения значений, которые он может найти. Затраты огромны и причина, по которой ваш код просто не заканчивается. Решение судоку один раз уже занимает довольно много времени, но ваш код делает это несколько миллиардов раз.
Если вы решите эти проблемы, ваш код должен найти, при условии, что все остальное реализовано правильно. Я также рекомендовал бы оптимизировать как поиск свободных полей, так и проверку, является ли поле пустым, поскольку это можно сделать довольно просто и обеспечит некоторое ускорение. Создайте список свободных полей в начале, выполните итерации по нему (одно поле для каждого уровня рекурсии) и завершите его, как только будет обработан весь список. Например:
solve(vacant, count):
if count == 0
print the field
terminate
x, y = vacant[count]
count++
for each possible value assignable to the field
assign value to x, y
call solve(vacant, count) recursively
clear field
Другая проблема, с которой вы столкнетесь, которая будет довольно уродливой, заключается в следующем:
int possibleEntries[9];
Глобальные переменные, которые используются и перезаписываются в рекурсии, по меньшей мере, плохая идея. Представьте себе возможный запуск программы следующим образом (идентификатор указывает на уровне рекурсии, где идентификатор не означает, что действие является глобальным):
solve
|
---> board empty? Nope
x,y <- next vacant field
possible values <- possible values for x, y
field[x, y] <- first value from possible values
solve
|
---> board empty? Nope
x, y <- next vacant field
possible values <- possible values for x, y (overwrites global variable!!!)
field[x, y] <- first value from possible values
solve
|
---> ...
<--- return
field[x, y] <- second value from possible values (WRONG!!!)
...
Последнее назначение не будет использовать список возможных значений, сгенерированных для поля, над которым вы сейчас работаете, но другого списка, который вы посетили где-то в рекурсии, прежде чем вернуться обратно. Вы можете решить это двумя способами:
- Выполните итерацию от 1 до 9 и проверьте для каждого номера отдельно, можно ли его назначить полю
- Ведение отдельного списка для каждого уровня рекурсии