8 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 가지 해결책을 발견했습니다. 의 코드가 인 깊이를 확인하기 위해 코드를 추가로 수정하면 깊이 8에 솔루션 2 개, 깊이 9에 솔루션 3 개가 있습니다.