I was reading this book from Skiena, Programming Challenges and after the backtracking chapter there was a question about solving the 15-puzzle with backtracking, which I reduce it to 8-puzzle just experimenting. I have this recursive code and I am wondering whether it have a chance to find the solution ever. The code is kind of ugly (be warned):
#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;
}
My question is, is there a chance with this code to find the solution and second, can anybody how the puzzle can be solved in reasonable time?
You have five problems. First, the
isReady
function is incorrect. It should look like this:Second, you are exceeding your puzzle bounds with
diffX
anddiffY
. You need to change this:to this:
Third, your
findRow
function also exceeds the puzzle bounds. Change all of the4
to3
.Fourth, you should check your victory condition only after you have made your move. So move your victory check below the swap:
Fifth, you should change your initial call from this:
to this:
The way you have it, you are always forcing a move to the upper left as your first move. The modified way keeps the 0 in the center so it doesn't force your first move. When I ran this code with all of the modifications I made, it found 3 solutions. When I further modified the code to check for solutions at any depth, it found 2 solutions at depth 8 and 3 solutions at depth 9.