本文共 5417 字，大约阅读时间需要 18 分钟。
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 1213 14 15 xwhere 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 1213 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, several descriptions of configuration of the 8 puzzle. One 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 8Output
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. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
因为最多只有9!种状态，一开始我想到的是直接暴力搜索起始状态到123456789x的状态，写完之后发现超时。
这里粘一下代码：
#include#include #include #include #include #include using namespace std;typedef long long ll;const int maxn=362885;char a[10];int pos[4]={-3,3,-1,1};char mea[6]="udlr";char ans[maxn];struct node{ int id; char a[10]; int pre; int px; char op;}b[maxn];int cnt;int cnt2;set Set;ll change (char s[]){ ll t=0; for (int i=0;i<9;i++) { t=t*10+(s[i]-'0'); } return t;}int judge (ll t){ if(Set.count(t)) return 0; Set.insert(t); return 1;}int bfs (int x){ queue q; strcpy(b[0].a,a); b[0].pre=-1; b[0].px=x; b[0].op=-1; b[0].id=0; q.push(b[0]); cnt++; ll t=change(b[0].a); judge(t); node now,next; while(!q.empty()) { now=q.front(); q.pop(); ll t=change(now.a); if(t==123456780) { //printf("----\n"); node x=now; while(x.pre!=-1) { ans[cnt2++]=x.op; x=b[x.pre]; } return 1; } for (int i=0;i<4;i++) { next=now; int ch=now.px+pos[i]; if((i==2&&now.px%3==0)||(i==3&&now.px%3==2)) continue; if(ch>=0&&ch<9) { swap(next.a[next.px],next.a[ch]); next.px=ch; ll t=change(next.a); if(judge(t)) { next.id=cnt; next.pre=now.id; next.op=i; b[cnt++]=next; q.push(next); } } } } return -1;}int main(){ while(scanf("%c ",&a[0])!=EOF) { int x; for (int i=1;i<8;i++) scanf("%c ",&a[i]); scanf("%c",&a[8]); for (int i=0;i<9;i++) { if(a[i]=='x') { a[i]='0'; x=i; } } getchar(); cnt=0; cnt2=0; Set.clear(); if(bfs(x)!=-1) { for (int i=cnt2-1;i>=0;i--) { printf("%c",mea[ans[i]]); } printf("\n"); } else { printf("unsolvable\n"); } }}
之后上网上搜了一下，发现应该从12345678x进行搜索，相当于进行打表，之后看看输入给出的状态是否可以从123456789x走到，这里需要储存走过的状态，网上普遍用了康托扩展，康托扩展确实使寻找状态快了很多，但是这个题目用set的话应该也能过，我感觉这个题目的侧重点应该是在打表上，康托扩展只是起到了锦上添花的效果。
这里贴一下AC代码，用了康托扩展。