Блог

Главная - Вопросы по программированию - Проблема в Knights Tour с использованием обратного отслеживания

Проблема в Knights Tour с использованием обратного отслеживания

#c #recursion #backtracking #knights-tour

#c #рекурсия #обратное отслеживание #knights-tour

Вопрос:

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

Мой код решения: Ссылка:https://ideone.com/Ud92vF код:

 #include <bits/stdc  .h> 
using namespace std;
bool valid(int arr[8][8],int r,int c)
{
    if(r>=0 and r<8 and c>=0 and c<8 and arr[r][c]== -1)
        return true;
    return false;
}
void fun(int arr[8][8],int r,int c,int x)
{
    if(x==64){
    cout<<"***********************ARRAY FOUND***********************n";
    for(int i=0;i<8;i  ){
        for(int j=0;j<8;j  )
            cout<<arr[i][j]<<" ";
        cout<<"n";
        }
        return;
    }
    if(!valid(arr,r,c))
    return;
    arr[r][c] = x;
    fun(arr,r-2,c 1,x 1); fun(arr,r-2,c-1,x 1);
    fun(arr,r-2,c 2,x 1); fun(arr,r-2,c-2,x 1);
    fun(arr,r 2,c 1,x 1); fun(arr,r 2,c-1,x 1);
    fun(arr,r 1,c 2,x 1); fun(arr,r 1,c-2,x 1);
    arr[r][c] = -1;
} 

int main() 
{
    int arr[8][8] ;
    for(int i=0;i<8;i  ){
        for(int j=0;j<8;j  )
            arr[i][j] = -1;
    }
    int r=0,c=0,x=0; fun(arr,r,c,x);
}

Комментарии:

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

2. fun(arr,r-2,c 2,x 1); fun(arr,r-2,c-2,x 1); выглядит неправильно.

3. вот почему я использую bool valid() для связанных проверок

Ответ №1:

Убедитесь, что ваш массив перемещений правильный:

 fun(arr,r-2,c-1,x 1); fun(arr,r-2,c 1,x 1);
fun(arr,r-1,c-2,x 1); fun(arr,r-1,c 2,x 1);
fun(arr,r 1,c-2,x 1); fun(arr,r 1,c 2,x 1);
fun(arr,r 2,c-1,x 1); fun(arr,r 2,c 1,x 1);

С этим я получаю правильный ответ:

 ***********************ARRAY FOUND***********************
0 11 8 5 2 13 16 19
9 6 1 12 17 20 3 14
30 27 10 7 4 15 18 21
63 24 31 28 35 22 47 44
32 29 26 23 48 45 36 57
25 62 51 34 39 56 43 46
52 33 60 49 54 41 58 37
61 50 53 40 59 38 55 42

Обратите внимание, что при использовании 65-го хода для проверки вашего ответа вы получите 8 одинаковых правильных ответов подряд. А затем еще 8. И т.д. Вы можете исправить это, напечатав после вашего 64-го хода:

 void fun(int arr[8][8],int r,int c,int x)
{
    if(!valid(arr,r,c))
    return;

    arr[r][c] = x;

    if(x==63){
    cout<<"***********************ARRAY FOUND***********************n";
    for(int i=0;i<8;i  ){
        for(int j=0;j<8;j  )
            cout<<arr[i][j]<<" ";
        cout<<"n";
        }
    }
    else
    {
        fun(arr,r-2,c-1,x 1); fun(arr,r-2,c 1,x 1);
        fun(arr,r-1,c-2,x 1); fun(arr,r-1,c 2,x 1);
        fun(arr,r 1,c-2,x 1); fun(arr,r 1,c 2,x 1);
        fun(arr,r 2,c-1,x 1); fun(arr,r 2,c 1,x 1);
    }
    arr[r][c] = -1;
}

И последняя проблема заключается в том, что вы начинаете только с {0,0}, поэтому вы найдете только knights tours, которые начинаются на этом квадрате. Вы действительно хотите начать с каждого квадрата, чтобы найти все возможные рыцарские туры. Или, если вы чувствуете себя умным, вам нужно только проверить подмножество начальных квадратов и использовать симметрию для генерации остальных.