[UVA][IDA*] 10181 - 15-Puzzle Problem＠Morris' Blog

2012-11-26 14:17:26| 人氣3,196| 回應0 | 上一篇 | 下一篇

[UVA][IDA*] 10181 - 15-Puzzle Problem

推薦 0 收藏 0 轉貼0 訂閱站台

Problem N

15-Puzzle Problem

Input: standard input

Output: standard output

Time Limit: 45 seconds

The 15-puzzle is a very popular game; 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. The object of the puzzle is to arrange the tiles so that they are ordered as below:

Here the only legal operation is to exchange missing tile with one of the tiles with which it shares an edge. As an example, the following sequence of moves changes the status of a puzzle


A random puzzle position	The missing Tile moves to right. Denoted by R	The missing Tile moves upwards. Denoted by U	The missing Tile moves to the left. Denoted by L

The letters in the previous row indicate which neighbor of the missing tile is swapped with it at each step; legal values are 'R','L','U' and 'D', for RIGHT, LEFT, UP, and DOWN, respectively.

Given an initial configuration of a 15-puzzle you will have to determine the steps that would make you reach the final stage. The input 15-puzzles requires at most 45 steps to be solved with our judge solution. So you will not be allowed to use more than 50 steps to solve a puzzle. If the given initial configuration is not solvable you just need to print the line “This puzzle is not solvable.”

Input

The first line of the input contains one integer N, which indicates how many sets of puzzle, will be given as input. Next 4N lines contain N sets of inputs. It means four lines make one set of input. Zero denotes the missing tile.

Output

For each set of input you will have to give one line of output. If the input puzzle is not solvable then print the line “This puzzle is not solvable.” If the puzzle is solvable then print the move sequence as described above to solve the puzzle.

Sample Input:

2
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14

Sample Output:

LLLDRDRDR
This puzzle is not solvable.

對於
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
輸出 48 步的走法如下
UULURDRDDLLUURURDLDRRULLULDDRRULLDRRRDLLURRULDDR
但是討論區卻顯示 50 步的做法。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct status {
    int board[4][4];
    int ix, iy;
} init;
int pos[16][2], mxdep;
int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};/*u,l,r,d*/
char dirc[4] = {'U', 'L', 'R', 'D'}, path[100];
int solved;
bool solvable() {
    int sum = 0, row, i, j;
    for(i = 0; i < 16; i++) {
        if(init.board[i/4][i%4] == 0) {
            row = i/4 + 1;
            continue;
        }
        for(j = i+1; j < 16; j++) {
            if(init.board[j/4][j%4] < init.board[i/4][i%4]) {
                if(init.board[j/4][j%4])
                    sum++;
            }
        }
    }
    return 1-(sum+row)%2;
}
int H() {
    static int i, j, sum, num;
    sum = 0;
    for(i = 0; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            num = init.board[i][j];
            if(num == 0)
                continue;
            sum += abs(i-pos[num][0]) + abs(j-pos[num][1]);
        }
    }
    return sum;
}
int singleH(int x, int y, int num) {
    return abs(x - pos[num][0]) + abs(y - pos[num][1]);
}
int IDA(int dep, int hv, int prestep) {
    if(hv == 0) {
        solved = dep;
        path[dep] = '\0';
        puts(path);
        return dep;
    }
    if(dep+hv > mxdep) return dep+hv;
    int i, tx, ty, x = init.ix, y = init.iy;
    int submxdep = 0xffff, val, shv;/*
    for(int i = 0; i < 4; i++, puts(""))
        for(int j = 0; j < 4; j++)
            printf("%d ", init.board[i][j]);
    getchar();*/
    for(i = 0; i < 4; i++) {
        if(i + prestep == 3)    continue;
        tx = x + dir[i][0], ty = y + dir[i][1];
        if(tx < 0 || ty < 0 || tx > 3 || ty > 3)
            continue;
        shv = hv;
        shv -= singleH(tx, ty, init.board[tx][ty]);
        shv += singleH( x, y, init.board[tx][ty]);
        init.ix = tx, init.iy = ty;
        swap(init.board[x][y], init.board[tx][ty]);
        path[dep] = dirc[i];
        val = IDA(dep+1, shv, i);
        swap(init.board[x][y], init.board[tx][ty]);
        init.ix = x, init.iy = y;
        if(solved) return solved;
        submxdep = min(submxdep, val);
    }
    return submxdep;
}
int main() {
    int test, i, j, k, initH;
    int cases = 0;
    for(i = 0, k = 0; i < 4; i++)
        for(j = 0; j < 4; j++)
            pos[++k][0] = i, pos[k][1] = j;
    scanf("%d", &test);
    while(test--) {
        cases++;
        for(i = 0; i < 4; i++) {
            for(j = 0; j < 4; j++) {
                scanf("%d", &init.board[i][j]);
                if(init.board[i][j] == 0) {
                    init.ix = i, init.iy = j;
                }
            }
        }
        if(solvable()) {
            solved = 0, initH = mxdep = H();
            if(!mxdep) {
                puts("");
                continue;
            }
            while(solved == 0 && mxdep <= 100) {
                mxdep = IDA(0, initH, -1);
            }
            if(solved);
            else    while(1);
        }else {
            puts("This puzzle is not solvable.");
        }
    }
    return 0;
}
/*
2
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
0 1 3 8
5 7 4 6
9 2 10 11
13 14 15 12

*/

我要檢舉

#10181#15-Puzzle Problem#IDA

台長： Morris

您可能對以下文章有興趣

[UVA][math][JAVA] 10643 - Facing Problem With Trees

[UVA][TSP] 11643 - Knight Tour

[UVA][字串搜尋] 422 - Word-Search Wonder

[UVA][概率] 11680 - Dragster

人氣(3,196) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][IDA*][Faster] 10181 - 15-Puzzle Problem
此分類上一篇:[UVA][BFS+HASH] 652 - Eight

回應(0)