POJ 1198 / HDU 1401 Solitaire：搜索 + 剪枝解棋盤跳棋問題

問題描述

8×8 棋盤上有 4 個棋子，每步可移動一格或跳過一個棋子落地（類似跳棋）。給定初始和目標位置，問是否能在 8 步內達到目標。

搜索策略

• 狀態：4 個棋子坐標 (x1,y1)...(x4,y4)
• 動作：選一個棋子，向 4 方向移動 1 格或跳過 1 子移動 2 格
• 目標：所有棋子到達目標位置（順序無關）
• 深度限制：8 步

關鍵剪枝

1. 估價函數 h()：每個棋子到最近目標點的曼哈頓距離之和 / 2（因每步最多推進 2 格）
2. 單調性剪枝：搜索過程中 h() 應單調遞減，若當前 h() > 父節點 h() 剪枝
3. 深度限制：depth + h() >= 8 剪枝

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node { int x, y; } a[4], b[4];
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
bool ed[9][9];

bool no(int x, int y) { // 檢查位置是否空閒
    for (int i = 0; i < 4; ++i) if (a[i].x == x && a[i].y == y) return false;
    return true;
}

bool isok(int x, int y) { return x >= 1 && x <= 8 && y >= 1 && y <= 8; }

int h() { // 估價函數
    int cnt = 0;
    for (int i = 0; i < 4; ++i) {
        int mi = 10000;
        for (int j = 0; j < 4; ++j)
            mi = min(mi, abs(a[i].x - b[j].x) + abs(a[i].y - b[j].y));
        cnt += mi;
    }
    return cnt;
}

bool dfs(int dis, int last_h) {
    int t = h();
    if (t == 0) return true;
    t /= 2;
    if (dis + t >= 8 || t > last_h) return false; // 剪枝
    for (int i = 0; i < 4; ++i) {
        for (int d = 0; d < 4; ++d) {
            // 移動 1 格
            if (isok(a[i].x + dx[d], a[i].y + dy[d]) && no(a[i].x + dx[d], a[i].y + dy[d])) {
                a[i].x += dx[d]; a[i].y += dy[d];
                if (dfs(dis + 1, t)) return true;
                a[i].x -= dx[d]; a[i].y -= dy[d];
            }
            // 跳過 1 子移動 2 格
            else if (isok(a[i].x + 2*dx[d], a[i].y + 2*dy[d]) && no(a[i].x + 2*dx[d], a[i].y + 2*dy[d])) {
                a[i].x += 2*dx[d]; a[i].y += 2*dy[d];
                if (dfs(dis + 1, t)) return true;
                a[i].x -= 2*dx[d]; a[i].y -= 2*dy[d];
            }
        }
    }
    return false;
}

int main() {
    while (~scanf("%d%d", &a[0].x, &a[0].y)) {
        memset(ed, 0, sizeof(ed));
        for (int i = 1; i < 4; ++i) scanf("%d%d", &a[i].x, &a[i].y);
        for (int i = 0; i < 4; ++i) scanf("%d%d", &b[i].x, &b[i].y), ed[b[i].x][b[i].y] = true;
        if (dfs(0, 10000)) puts("YES"); else puts("NO");
    }
    return 0;
}

優化總結

• 初始版本僅用 h()/2 剪枝在 HDU TLE
• 加入「估價單調遞減」剪枝後 AC
• 狀態空間小，無需雙向 BFS 或記憶化