Что не так с моей функцией решения судоку? - PullRequest
Новая
       21

Что не так с моей функцией решения судоку?

4 голосов
/ 18 ноября 2011

хорошо, поэтому я изменил свою функцию на функцию возврата (которую я нашел в Интернете).Он все еще читает из файла и вводит его в массив, функция проверки работает правильно, поэтому я не изменил это.Если вам интересно, вот загадка, которую я пытаюсь решить (где нули - это пустые места).

0 5 0 0 2 0 0 7 0
7 2 0 4 0 3 0 0 0
9 0 0 0 5 0 6 2 0
0 0 5 0 8 6 0 0 0
1 0 0 0 4 0 0 0 8
0 0 0 2 3 0 4 0 0
0 9 3 0 1 0 0 0 2
0 0 0 3 0 2 0 4 6
0 8 0 0 0 0 0 1 0

// backtracking function
void Sudoku::solvePuzzle()
{
int x = 0;
int y = 0;
int r = 0;
bool back_flag;

while (r < 81) {
    back_flag = true; 
    x = r/9;
    y = r%9;

    for(int num = arr[x][y]; num < 10 && back_flag; num++) {

        if(check(x,y,num)) {
            arr[x][y] = num;
            back_flag=false;
            break;
        }
        else if(num >= 9) {
            arr[x][y] = 0;
        }
    }
    if(back_flag) {
        r--;
    }
    else {
        r++;
    }
}
}

1 Ответ

1 голос
/ 18 ноября 2011

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

    if (count == 1 && arr[r][c] == 0) {
         tempNum = num;
    }
    else {
        tempNum = 0;
    }
    count++;

это должно быть 

    count++;
    if (count == 1) {
         tempNum = num;
    }

и вместо 

    if (count == 1 && check(r, c, num) && arr[r][c] == 0) {
         arr[r][c] = tempNum;

это должно быть 

    if (count == 1 && check(r, c, tempNum)) {
         arr[r][c] = tempNum;

или просто 

    if (count == 1 ) {
         arr[r][c] = tempNum;

, поскольку, если count==1, то check(r, c, tempNum) не может быть ложным, если ваш check функция не имеет побочных эффектов.

Кстати, код становится намного лучше читаемым, если вы организуете его следующим образом: 

for (int r = 0; r < MAX_ROW; r++) {
   for (int c  = 0; c < MAX_COL; c++) {
       if(arr[r][c] != 0)
           continue;

           // ** no tests for arr[r][c] == 0 in this code block any more
           // ...
    }
}

И еще одна вещь: вы должны остановить алгоритм, есличисло нулей во внешнем цикле больше не меняется от одной итерации к следующей, будет SuDoKus, который ваш решатель не может решить, и вы, я думаю, не хотите заводить свою программу в бесконечный цикл для них.

...