Eight
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 23815 | Accepted: 10518 | Special Judge | ||
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:
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:
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.
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
is described by this list:
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
解题:这题比杭电那题要容易一点，本代码可以过poj的，但是过不了hdu的1043，正在学习IDA*以及如何破解1043.本题代码是来自某牛人的博客！学习IDA*时看了很多关于八数码的代码，只有这份代码，思路清晰，代码量少，拿来学习研究IDA*那是极好的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 #define SIZE 3 6 char board[SIZE][SIZE]; 7 int goal_state[9][2] = {{0,0}, {0,1}, {0,2},{1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}}; 8 int h(char board[][SIZE]) { 9 int cost = 0; 10 for(int i=0; i<SIZE; ++i) 11 for(int j=0; j<SIZE; ++j) { 12 if(board[i][j] != SIZE*SIZE) { 13 cost += abs(i - goal_state[board[i][j]-1][0]) + 14 abs(j - goal_state[board[i][j]-1][1]); 15 } 16 } 17 return cost; 18 } 19 int step[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};//u, l, r, d 20 char op[4] = {'u', 'l', 'r', 'd'}; 21 char solution[1000]; 22 int bound; 23 bool ans; 24 int DFS(int x, int y, int dv, char pre_move) { 25 int hv = h(board); 26 if(hv + dv > bound) return dv + hv; 27 if(hv == 0) {ans = true;return dv;} 28 int next_bound = 1e9; 29 for(int i = 0; i < 4; ++i) { 30 if(i + pre_move == 3) continue; 31 int nx = x + step[i][0]; 32 int ny = y + step[i][1]; 33 if(0 <= nx && nx < SIZE && 0 <= ny && ny < SIZE) { 34 solution[dv] = i; 35 swap(board[x][y], board[nx][ny]); 36 int new_bound = DFS(nx, ny, dv+1, i); 37 if(ans) return new_bound; 38 next_bound = min(next_bound, new_bound); 39 swap(board[x][y], board[nx][ny]); 40 } 41 } 42 return next_bound; 43 } 44 void IDA_star(int sx, int sy) { 45 ans = false; 46 bound = h(board); 47 while(!ans && bound <= 100) bound = DFS(sx, sy, 0, -10); 48 } 49 int main() { 50 int sx, sy; 51 char c; 52 for(int i=0; i<SIZE; ++i) 53 for(int j=0; j<SIZE; ++j) { 54 cin>>c; 55 if(c == 'x') { 56 board[i][j] = SIZE * SIZE; 57 sx = i; 58 sy = j; 59 } else board[i][j] = c - '0'; 60 } 61 IDA_star(sx, sy); 62 if(ans) { 63 for(int i = 0; i < bound; ++i) 64 cout<<op[solution[i]]; 65 } else cout<<"unsolvable"; 66 return 0; 67 }