StackOverflow после 27 прогонов

Question

При запуске моего генератора Судоку после 27-кратного переполнения стека.

void start(int todel){ 
int number; 
for (int x=0; x<9; x++) { 
    for (int y=0; y<9; y++) { 

     number = GenN(x, y); 
     osudoku[x][y]=number; 
    } 
} 
replace(todel); 
output(); 
} 


int GenZ(int x, int y){ 
    int number; 
    bool duplication = true; 
    Randomize(); 
    number = Random(9)+1; 
    duplication = check(number,x,y); 
    if (duplication==true){ 
     return GenZ(x,y); 
    } 
    else if (duplication==false) { 
     return number; 
    } 
} 

Я думаю, что-то с этим кодом. Это порождает такие вещи, как:

758 431 629 
913 267 485 
642 985 317 
Stack Overflow 

Так я получаю 1/3 Sudoku.

Answer 1

Вам необходимо добавить backtracking в ваше решение.

Рассмотрим такой сценарий: (что может произойти в какой-то момент в вашем алгоритме)

1 2 3 | 4 5 6 | 7 8 9 
4 5 6 | 1 2 3 | ? _ _ 
... 

Ваша программа будет просто держать пытается найти значение, которое соответствует в ?, но нет такого значения не существует.

Вместо ваша программа должна видеть, что значения не подходит, и попробовать другое значение для 3, который также не будет работать, то 2, то 1 в этом случае он должен в конечном итоге положить 7, 8 и 9 в второй блок, например:

1 2 3 | 4 5 6 | 7 8 9 
4 5 6 | 7 8 9 | ? _ _ 
... 

В этом случае он может продолжить успешно.

И это:

zahl = Random(9)+1; 

не будет действительно работать, как вы можете продолжать получать значения, которые не подходят (как в приведенном выше примере). Вы не узнаете, когда вернуться. Лучше прокрутить все 9 значений. После того, как вы пройдете все 9 значений, вы поймете, что никакое значение не подходит, и вы узнаете, что должны вернуться.

Answer 2

если дублирование == true в GenZ, он будет вызывать его снова с тем же x, y, который снова будет продуцировать дублирование == true? тем более, что я не могу видеть вас изменения «номер», так что может быть это инициализируется значение как 0.

Answer 3

if (duplication==true){ 
    return GenZ(x,y); 
} 

Я не уверен, что это реальный способ создать судоку, скотина форсирования может занять в то время как независимо от того, как вы его реализуете, но вы, вероятно, можете избавиться от ошибки stackoverflow, не используя рекурсию и имея цикл.

while (duplication){