尖峰时刻 如果你不熟悉它，该游戏由大小不等的车的集合，设置水平或垂直，在N×M个网格，只有一个出口的。照片 每节车厢可向前/向后移动，它被设置在方向，只要另一辆车没有阻止它。你可以永远换汽车的方向。照片 有一个特殊的车，一般是红色的。它被设置在同一行的退出是在和游戏的目标是找到的一系列动作（​​一动 - 动车n步前进或后退），将允许红旗轿车驶出迷宫。

Rush Hour if you're not familiar with it, the game consists of a collection of cars of varying sizes, set either horizontally or vertically, on a NxM grid that has a single exit. Each car can move forward/backward in the directions it's set in, as long as another car is not blocking it. You can never change the direction of a car. There is one special car, usually it's the red one. It's set in the same row that the exit is in, and the objective of the game is to find a series of moves (a move - moving a car N steps back or forward) that will allow the red car to drive out of the maze.

我一直试图想怎么计算解决这个问题，我也真的想不到什么好的解决办法。 我想出了几个：

I've been trying to think how to solve this problem computationally, and I can really not think of any good solution. I came up with a few:

回溯。这是pretty的简单 - 递归和一些递归，直到你找到答案。然而，每节车厢可移动几个不同的方式，并在每场比赛状态的几辆车可以移动，产生的博弈树将是巨大的。 在某种约束的算法，将顾及什么需要移动，并以某种方式递归工作。这是一个非常粗略的想法，但它是一个想法。 图？模型中的游戏状态为图形和应用某种变化对着色算法，解决依赖关系？再次，这是一个非常粗略的概念。 在一个朋友建议遗传算法。这是某种可能的，但不容易。我想不出一个好办法来进行评估的功能，并没有说什么都没了。

所以，问题是 - 如何建立一个程序，需要一个网格和车辆的布局，并输出了一系列需要得到红色的车出的步骤？

So the question is - How to create a program that takes a grid and the vehicle layout, and outputs a series of steps needed to get the red car out?

次级问题：

查找部分解决方案。 找到一个优化溶液（移动最小数量） 在评估如何好当前的状态， Finding some solution. Finding an optimal solution (minimal number of moves) Evaluating how good a current state is

例如：你怎么能在这个设置移动汽车，使红色汽车可以退出，通过右边的退出迷宫？

Example: How can you move the cars in this setting, so that the red car can "exit" the maze through the exit on the right?

推荐答案

有关经典的尖峰时刻，这个问题很容易处理一个简单的广度优先搜索。所要求保护的已知最硬的初始配置要求93移动到解决，总的只有24132可达配置。即使是一个天真的实现广度优先搜索算法可以探索整个搜索空间在1秒以内即使是温和的机器上。

For classic Rush Hour, this problem is very tractable with a simple breadth first search. The claimed hardest known initial configuration requires 93 moves to solve, with a total of only 24132 reachable configurations. Even a naively implemented breadth-first search algorithm can explore the entire search space in under 1 second on even a modest machine.

维基/尖峰时刻（棋盘游戏） 尖峰时刻的初始配置 - 这些都是自称是最困难的问题 求解源在ideone.com - 与输出的最难输入 Wikipedia/Rush Hour (board game) Rush Hour Initial Configurations -- these are claimed to be the "hardest" problems Solver source at ideone.com - with output for the "hardest" input

下面是一个广度优先搜索详尽的求解器的全部源$ C ​​$ C，C语言编写的风格。

Here's the complete source code of a breadth-first search exhaustive solver, written in C-style.

import java.util.*;

public class RushHour {
    // classic Rush Hour parameters
    static final int N = 6;
    static final int M = 6;
    static final int GOAL_R = 2;
    static final int GOAL_C = 5;

    // the transcription of the 93 moves, total 24132 configurations problem
    // from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
    static final String INITIAL =   "333BCC" +
                                    "B22BCC" +
                                    "B.XXCC" +
                                    "22B..." +
                                    ".BB.22" +
                                    ".B2222";

    static final String HORZS = "23X";  // horizontal-sliding cars
    static final String VERTS = "BC";   // vertical-sliding cars
    static final String LONGS = "3C";   // length 3 cars
    static final String SHORTS = "2BX"; // length 2 cars
    static final char GOAL_CAR = 'X';
    static final char EMPTY = '.';      // empty space, movable into
    static final char VOID = '@';       // represents everything out of bound

    // breaks a string into lines of length N using regex
    static String prettify(String state) {
        String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N));
        return state.replaceAll(EVERY_NTH, "\n");
    }

    // conventional row major 2D-1D index transformation
    static int rc2i(int r, int c) {
        return r * N + c;
    }

    // checks if an entity is of a given type
    static boolean isType(char entity, String type) {
        return type.indexOf(entity) != -1;
    }

    // finds the length of a car
    static int length(char car) {
        return
            isType(car, LONGS) ? 3 :
            isType(car, SHORTS) ? 2 :
            0/0; // a nasty shortcut for throwing IllegalArgumentException
    }

    // in given state, returns the entity at a given coordinate, possibly out of bound
    static char at(String state, int r, int c) {
        return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID;
    }
    static boolean inBound(int v, int max) {
        return (v >= 0) && (v < max);
    }

    // checks if a given state is a goal state
    static boolean isGoal(String state) {
        return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
    }

    // in a given state, starting from given coordinate, toward the given direction,
    // counts how many empty spaces there are (origin inclusive)
    static int countSpaces(String state, int r, int c, int dr, int dc) {
        int k = 0;
        while (at(state, r + k * dr, c + k * dc) == EMPTY) {
            k++;
        }
        return k;
    }

    // the predecessor map, maps currentState => previousState
    static Map<String,String> pred = new HashMap<String,String>();
    // the breadth first search queue
    static Queue<String> queue = new LinkedList<String>();
    // the breadth first search proposal method: if we haven't reached it yet,
    // (i.e. it has no predecessor), we map the given state and add to queue
    static void propose(String next, String prev) {
        if (!pred.containsKey(next)) {
            pred.put(next, prev);
            queue.add(next);
        }
    }

    // the predecessor tracing method, implemented using recursion for brevity;
    // guaranteed no infinite recursion, but may throw StackOverflowError on
    // really long shortest-path trace (which is infeasible in standard Rush Hour)
    static int trace(String current) {
        String prev = pred.get(current);
        int step = (prev == null) ? 0 : trace(prev) + 1;
        System.out.println(step);
        System.out.println(prettify(current));
        return step;
    }

    // in a given state, from a given origin coordinate, attempts to find a car of a given type
    // at a given distance in a given direction; if found, slide it in the opposite direction
    // one spot at a time, exactly n times, proposing those states to the breadth first search
    //
    // e.g.
    //    direction = -->
    //    __n__
    //   /     \
    //   ..o....c
    //      \___/
    //      distance
    //
    static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) {
        r += distance * dr;
        c += distance * dc;
        char car = at(current, r, c);
        if (!isType(car, type)) return;
        final int L = length(car);
        StringBuilder sb = new StringBuilder(current);
        for (int i = 0; i < n; i++) {
            r -= dr;
            c -= dc;
            sb.setCharAt(rc2i(r, c), car);
            sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY);
            propose(sb.toString(), current);
            current = sb.toString(); // comment to combo as one step
        }
    }

    // explores a given state; searches for next level states in the breadth first search
    //
    // Let (r,c) be the intersection point of this cross:
    //
    //     @       nU = 3     '@' is not a car, 'B' and 'X' are of the wrong type;
    //     .       nD = 1     only '2' can slide to the right up to 5 spaces
    //   2.....B   nL = 2
    //     X       nR = 4
    //
    // The n? counts how many spaces are there in a given direction, origin inclusive.
    // Cars matching the type will then slide on these "alleys".
    //
    static void explore(String current) {
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (at(current, r, c) != EMPTY) continue;
                int nU = countSpaces(current, r, c, -1, 0);
                int nD = countSpaces(current, r, c, +1, 0);
                int nL = countSpaces(current, r, c, 0, -1);
                int nR = countSpaces(current, r, c, 0, +1);
                slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
                slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1);
                slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
                slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1);
            }
        }
    }
    public static void main(String[] args) {
        // typical queue-based breadth first search implementation
        propose(INITIAL, null);
        boolean solved = false;
        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (isGoal(current) && !solved) {
                solved = true;
                trace(current);
                //break; // comment to continue exploring entire space
            }
            explore(current);
        }
        System.out.println(pred.size() + " explored");
    }
}

有源$ C ​​$ C两注，值得行：

There are two note-worthy lines in the source code:

的打破; 当找到解决方法 这是现在评论，这样的广度优先搜索探索的全部的搜索空间，以确认该链接的网站上面给出号码 The break; when a solution is found This is now commented so that the breadth first search explores the entire search space, to confirm the numbers given in the linked website above 在本质上，这计数任何汽车的每一个动作的一招。如果汽车被移动3位到左侧，这是3移动。连击这是一招（因为它涉及同一辆车朝着同一个方向），简单地注释此行。链接的网站不承认的组合，所以这条线现在取消注释相匹配的特定动作的最小数量。随着组合计数，93-移动问题只需要49组合动作。也就是说，如果有一个停车场服务员在周围移动这些车的很多，他只只需要进出汽车的49倍。

该算法本质上是一个广度优先搜索，与队列是典型实现。一个predecessor图保持使任何状态可以追溯到到初始状态。一键将永远不会被重新映射，并作为条目插入广度优先搜索顺序，最短路径有保证。

The algorithm is essentially a breadth first search, implemented with a queue as is typical. A predecessor map is maintained so that any state can be traced back to the initial state. A key will never be remapped, and as entries are inserted in breadth-first search order, shortest path is guaranteed.

一个状态重新psented为 N×M个 - 长度字符串 $ P $。每个字符重presents在黑板上的实体，存储在行主顺序。

A state is represented as an NxM-length String. Each char represents an entity on the board, stored in row-major order.

邻国通过扫描所有4个方向，从一个空的空间，寻找一个合适的车型，滑动它作为室内可容纳找到。

Neighboring states are found by scanning all 4 directions from an empty space, looking for an appropriate car type, sliding it as room accommodates.

有大量的冗余这里工作（如长小巷进行扫描多次），但正如前面提到的，虽然广义的版本是PSPACE完全的，经典的尖峰时刻变体是由暴力很容易处理的。

There is plenty of redundant work here (e.g. long "alleys" are scanned multiple times), but as mentioned before, although the generalized version is PSPACE-complete, the classic Rush Hour variant is very tractable by brute force.

广度优先搜索 行优先的顺序 Breadth-first search Row-major order