51isoft's ACM Journey

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  5 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks

Description

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
 1  2  3  4

5 6 7 8
9 10 11 12
13 14 15 x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
 1  2  3  4    1  2  3  4    1  2  3  4    1  2  3  4

5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.

Input

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
 1  2  3

x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

 2  3  4  1  5  x  7  6  8 

Sample Output

ullddrurdllurdruldr

Source


八数码问题,目标状态固定,给数据用的是一维。

A*算法+二叉堆。估价函数写的是位移差的和。
#include <stdio.h>
#include 
<string.h>
#include 
<math.h>

struct Eight {
    
int value;
    
int status[3][3];
    
char walked[60];
    
char str[15];
    
int xx,xy;
};

struct EightExtented {
    
bool left,right;
};

EightExtented eighte[
370000];
Eight eight[
370000];
bool hashtable[363000]={false};
bool solved=false;
int jc[10]={1,1,2,6,24,120,720,5040,40320,362880};
int tail=0;
char start[10];
int hmove[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

int cvalue();

void init()
{
    
int i;
    
char temp;
    
for (i=0;i<9;i++)
    {
        
do
        {
            scanf(
"%c",&temp);
        }
while (temp==' ');
        start[i]
=temp;
        
if (start[i]!='x') eight[0].status[i/3][i%3]=start[i]-'0';
        
else {
            eight[
0].status[i/3][i%3]=9;
            eight[
0].xx=i/3;eight[0].xy=i%3;
        }
    }
    eight[
0].value=cvalue();
    tail
++;
}

int hash()
{
    
int rev[10]={0};
    
int i,j;
    
int loc;
    
int hashvalue=0;
    
for (i=0;i<9;i++)
    {
        
if (eight[tail].str[i]=='x') {
            loc
=i;
            
continue;
        }
        
for (j=i+1;j<9;j++)
        {
            
if ((eight[tail].str[j]!='x')&&(eight[tail].str[i]>eight[tail].str[j])) rev[eight[tail].str[i]-'0'-1]++;
        }
    }
    
for (i=0;i<9;i++) hashvalue+=rev[i]*jc[i];
    hashvalue
+=jc[8]*(9-loc-1);
    
return hashvalue;
}

bool able()
{
    
int i,j;
    
int sum=0;
    
for (i=0;i<8;i++)
        
for (j=i+1;j<9;j++)
        
if ((start[i]!='x')&&(start[j]!='x')&&(start[i]>start[j])) sum++;
    
if (sum%2==0return true;
    
else return false;
}

int cvalue()
{
    
int i,j;
    
int value=0;
    
for (i=0;i<3;i++)
        
for (j=0;j<3;j++)
        value
+=fabs((eight[tail].status[i][j]-1)/3-i)+fabs((eight[tail].status[i][j]-1)%3-j);
    
return value;
}

//0 right, 1 left, 2 up, 3 down
bool move(int way)
{
    
int x,y;
    
int i,j,l;
    
char temp;
    
if (strlen(eight[0].walked)>=50) {
        
return false;
    }
    x
=eight[0].xx+hmove[way][0];
    y
=eight[0].xy+hmove[way][1];
    
if (!((x>=0)&&(x<3)&&(y>=0)&&(y<3))) return false;
    
for (i=0;i<3;i++)
        
for (j=0;j<3;j++) eight[tail].status[i][j]=eight[0].status[i][j];
    eight[tail].status[eight[
0].xx][eight[0].xy]=eight[tail].status[x][y];
    eight[tail].status[x][y]
=9;
    eight[tail].xx
=x;eight[tail].xy=y;
    
for (i=0;i<3;i++)
        
for (j=0;j<3;j++if (eight[tail].status[i][j]!=9) eight[tail].str[i*3+j]=eight[tail].status[i][j]+'0';
                            
else eight[tail].str[i*3+j]='x';
    eight[tail].str[
9]=0;
    
if (hashtable[hash()]) return false;
    
else hashtable[hash()]=true;
    strcpy(eight[tail].walked,eight[
0].walked);
    
switch (way)
    {
        
case 0: temp='r';break;
        
case 1: temp='l';break;
        
case 2: temp='u';break;
        
case 3: temp='d';break;
    }
    l
=strlen(eight[tail].walked);
    eight[tail].walked[l]
=temp;
    eighte[tail].left
=-1;eighte[tail].right=-1;
    eight[tail].walked[l
+1]=0;
    eight[tail].value
=cvalue()*10+l+1;
    eighte[tail].left
=false;eighte[tail].right=false;
    
return true;
}

void solve()
{
    
int i,t;
    Eight temp;
    
while (!solved)
    {
        
for (i=0;i<4;i++)
        {
            
if (move(i)) {
                
if (tail>1) {
                    t
=tail;
                    
while ((t>1)&&(eight[t].value<eight[t/2].value))
                    {
                        temp
=eight[t/2];
                        eight[t
/2]=eight[t];
                        eight[t]
=temp;
                        t
/=2;
                    }
                }
                
if (tail%2==0) eighte[tail/2].left=true;
                    
else eighte[tail/2].right=true;
                tail
++;
            }
        }
        
if (eight[0].value-strlen(eight[0].walked)==0) {
            printf(
"%s\n",eight[0].walked);
            solved
=true;
        }
        eight[
0]=eight[1];
        eight[
1]=eight[tail-1];
        
//printf("%s %s %d\n",eight[0].str,eight[0].walked,eight[0].value);
        tail--;
        
if (tail%2==0) eighte[tail/2].left=false;
            
else eighte[tail/2].right=false;
        t
=1;
        
while (t*2<tail)
        {
            
if (eight[t].value>eight[t*2].value) {
                
if (eighte[t*2+1].right&&eight[t*2+1].value<eight[t*2].value) {
                    temp
=eight[t];
                    eight[t]
=eight[t*2+1];
                    eight[t
*2+1]=temp;
                    t
=t*2+1;
                }
                
else {
                    temp
=eight[t];
                    eight[t]
=eight[t*2];
                    eight[t
*2]=temp;
                    t
=t*2;
                }
            }
            
else if (eighte[t*2+1].right&&eight[t].value>eight[t*2+1].value) {
                temp
=eight[t];
                eight[t]
=eight[t*2+1];
                eight[t
*2+1]=temp;
                t
=t*2+1;
            }
            
else break;
        }
    }
}

int main()
{
    
//freopen("test.out","w",stdout);
    init();
    
if (!able()) {
        printf(
"unsolvable\n");
        
return 0;
    }
    
else solve();
    
return 0;
}





posted on 2008-09-18 17:31 51isoft 阅读(1612) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理