8 Puzzle with Backtracking

Question

Я читал эту книгу из Skiena, Programming Challenges, и после главы о возврате назад возник вопрос о решении 15-головоломки с возвратом, который я свожу к 8-головоломке, просто экспериментирую. У меня есть этот рекурсивный код, и мне интересно, есть ли у него шанс найти решение когда-либо. Код рода некрасиво (имейте в виду):

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int arr[20][20]={ 
    {3,1,2}, 
    {4,0,5}, 
    {6,8,7} 
}; 

int moveX[20]={1,1,1,0,0,-1,-1,-1}; 
int moveY[20]={0,1,-1,1,-1,0,1,-1}; 
int depth=0; 

int findRow(){ 
    int i,j; 
    for(i=0;i<4;i++){ 
     for(j=0;j<4;j++){ 
      if(arr[i][j]==0){ 
       return i; 
      } 
     } 
    } 
} 

int findCol(){ 
    int i,j; 
    for(i=0;i<3;i++){ 
     for(j=0;j<3;j++){ 
      if(arr[i][j]==0){ 
       return j; 
      } 
     } 
    } 
} 

void print(){ 
    int i,j; 
    for(i=0;i<3;i++){ 
     for(j=0;j<3;j++){ 
      printf("%i ",arr[i][j]); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
} 

int isReady(){ 
    if(arr[0]==1 && arr[1]==2 && arr[2]==3 && arr[3]==4 && arr[4]==5 && arr[5]==6 && arr[6]==7 && arr[7]==8){ 
     return 1; 
    } 
    else return 0; 
} 

void perm(int row,int col,int n){ 
    if(n>=9){ 
     print(); 
     if(isReady()) 
      printf("Finished"); 
     depth++; 

     return; 
    } 

    int i=0;int diffX,diffY,temp; 
    int r=findRow(); 
    int c=findCol(); 
    temp=arr[r][c]; 
    arr[r][c]=arr[row][col]; 
    arr[row][col]=temp; 
    for(i=0;i<8;i++){ 
     diffX=row+moveX[i]; 
     diffY=col+moveY[i]; 
     if(diffX>=0 && diffX<4 && diffY>=0 && diffY<4){ 
      perm(diffX,diffY,n+1); 
     } 
    } 
    temp=arr[r][c]; 
    arr[r][c]=arr[row][col]; 
    arr[row][col]=temp; 
} 

int main() 
{ 
    perm(0,0,0); 
    return 0; 
} 

Мой вопрос, есть ли шанс с этим кодом, чтобы найти решение и второй, может кто-нибудь, как головоломка может быть решена в разумные сроки?

Answer 1

У вас есть пять проблем. Во-первых, функция isReady неверна. Он должен выглядеть следующим образом:

int isReady(){ 
    if(arr[0][0]==1 && arr[0][1]==2 && arr[0][2]==3 && 
      arr[1][0]==4 && arr[1][1]==5 && arr[1][2]==6 && 
      arr[2][0]==7 && arr[2][1]==8){ 
     return 1; 
    } 
    else return 0; 
} 

Во-вторых, вы превышая головоломки ограничивающая с diffX и diffY. Вы должны изменить это:

if(diffX>=0 && diffX<4 && diffY>=0 && diffY<4){ 

к этому:

if(diffX>=0 && diffX<3 && diffY>=0 && diffY<3){ 

В-третьих, ваша findRow функция также превышает головоломки границы. Измените все 4 на 3.

В-четвертых, вы должны проверить свое состояние победы только после того, как совершили свой ход. Так двигаться чек победы под своп:

temp=arr[r][c]; 
arr[r][c]=arr[row][col]; 
arr[row][col]=temp; 
// This victory check is now below the move. 
if(n>=9){ 
    print(); 
    if(isReady()) 
     printf("Finished"); 
    depth++; 

    return; 
} 

Пятую, вы должны изменить свой первоначальный вызов от этого:

perm(0,0,0); 

к этому:

perm(1,1,0); 

так, как вы есть, вы всегда заставляете двигаться в верхнем левом углу вашего первого хода. Измененный способ удерживает 0 в центре, чтобы он не заставлял ваш первый ход. Когда я запускал этот код со всеми изменениями, которые я сделал, он нашел 3 решения. Когда я дополнительно модифицировал код для проверки решений на любой глубиной, он нашел 2 решения на глубинах 8 и 3 решений на глубине 9.