Facebook 示例拼图：河内塔

这是 Facebook 招聘样本测试中的一个问题。

有 K 个钉子。当从桩的底部到顶部观察时，每个桩可以按半径递减的顺序容纳圆盘。有N个圆盘，半径为1到N；给定钉子的初始配置和钉子的最终配置，输出从初始配置转换到最终配置所需的移动。您需要以最少的移动次数完成转换。

移动包括拾取任何一个钉子的最上面的圆盘并将其放置在任何其他钉子的顶部。 在任何时间点，必须保持所有桩的半径递减特性。

限制条件：

1

3

输入格式：

N K

第 2 行包含 N 个整数。每个整数都在 1 到 K 的范围内，其中第 i 个整数表示在初始配置中半径为 i 的圆盘所在的栓钉。

第三行表示最终配置，格式与初始配置类似。

输出格式：

第一行包含 M - 完成变换所需的最少移动次数。

下面的 M 行通过要选取的桩号和要放置的桩号来描述移动。 如果有多个解决方案，则输出其中任何一个就足够了。你可以假设，总是有一个少于 7 步的解决方案，并且初始配置不会与最终配置相同。

输入示例#00：

2 3

1 1

2 2

示例输出#00：

3

1 3

1 2

3 2

输入示例#01：

6 4

4 2 4 3 1 1

1 1 1 1 1 1

示例输出#01：

5

3 1

4 3

4 1

2 1

3 1

讨论这个问题的解决方案没有什么害处，因为它是一个示例问题。

经典河内塔问题的解决方案编写起来非常简单：

void hanoi(char s, char i, char d, int n)
{
     if(n>0)
     {
            hanoi(s, d, i, n-1);
            cout<<s<<":"<<d<<endl;
            hanoi(i, s, d, n-1);
     }        
}

上述也可以扩展到河内的一般“k”钉塔。但是，事实证明，这些知识对于设计这个示例难题的解决方案根本没有用处。关于将来如何解决此类问题和类似问题有什么建议吗？

这是我的动态编程解决方案，最多可以在 O(K^N) 步骤中找到最佳的移动顺序，K = 5、N = 8 的运行时间不到一秒。由于懒惰，我对输入数据进行了硬编码。

它是一个通过状态空间的 BFS，永远不会访问同一个状态两次。然后从头到尾回溯得到实际路径（这部分与最优序列的长度成线性关系）。基本上，它是“穿过迷宫的最短路径”算法，但“迷宫”是问题的状态空间，起始“位置”是初始状态，结束“位置”是期望状态。

许多类似的问题都可以通过这种方式解决，只要您可以定义一个有限的状态空间，您的目标是最小化两个状态之间的“距离”，以及计算可以从当前状态移动到哪些状态的方法。

例如，具有任意数量的“传教士和食人者”问题可以使用相同的算法来解决。

另外，如果您需要“所有最优解”而不是“任何最优解”，则可以轻松修改算法来提供它们。

class Program
{
    static int N = 8;
    static int K = 5;
    static List<int> StartState = new List<int> { 3, 3, 2, 1, 4, 1, 5, 2 };
    static List<int> EndState = new List<int> { 1, 4, 2, 2, 3, 4, 4, 3 };

    static LinkedList<int> StateQueue = new LinkedList<int>();
    static int[] MovesToState = new int[(int)Math.Pow(K, N)];


    static void Main(string[] args)
    {
        for (int i = 0; i < StartState.Count; i++)
        {
            StartState[i]--;
            EndState[i]--;
        }

        int startStateIndex = StateToNum(StartState);
        int endStateIndex = StateToNum(EndState);

        for (int i = 0; i < MovesToState.Length; i++)
            MovesToState[i] = -1;

        MovesToState[startStateIndex] = 0;

        StateQueue.AddFirst(startStateIndex);
        while (StateQueue.Count > 0 && MovesToState[endStateIndex] == -1)
        {
            var legalMoves = LegalMoves(StateQueue.Last.Value);
            foreach (var newStateIndex in legalMoves)
            {
                int currMoves = MovesToState[StateQueue.Last.Value];
                if (MovesToState[newStateIndex] == -1)
                {
                    MovesToState[newStateIndex] = currMoves + 1;
                    StateQueue.AddFirst(newStateIndex);
                }
            }
            StateQueue.RemoveLast();
        }

        var currStateIndex = endStateIndex;
        var moves = new List<Tuple<int, int>>();
        while (currStateIndex != startStateIndex)
        {
            var legalMoves = LegalMoves(currStateIndex);
            int currMoves = MovesToState[currStateIndex];
            foreach (var prevStateIndex in legalMoves)
            {
                if (MovesToState[prevStateIndex] == MovesToState[currStateIndex] - 1)
                {
                    var currState = NumToState(currStateIndex);
                    var prevState = NumToState(prevStateIndex);
                    for (int i = 0; i < N; i++)
                    {
                        if (currState[i] != prevState[i])
                        {
                            moves.Add(new Tuple<int, int>(prevState[i] + 1, currState[i] + 1));
                            currStateIndex = prevStateIndex;
                            break;
                        }
                    }
                }
            }
        }
        Console.WriteLine(MovesToState[endStateIndex]);
        moves.Reverse();
        foreach (var move in moves)
        {
            Console.WriteLine("{0} {1}", move.Item1, move.Item2);
        }

        Console.Read();
    }

    static List<int> LegalMoves(int stateIndex)
    {
        var legalMoves = new List<int>();

        var state = NumToState(stateIndex);

        int[] minOnPeg = new int[K];
        for (int i = 0; i < minOnPeg.Length; i++)
            minOnPeg[i] = N;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < K; j++)
                if (state[i] == j && i < minOnPeg[j])
                    minOnPeg[j] = i;

        bool[] isTop = new bool[N];
        for (int i = 0; i < isTop.Length; i++)
            isTop[i] = false;
        for (int i = 0; i < K; i++)
            if (minOnPeg[i] < N)
                isTop[minOnPeg[i]] = true;

        for (int i = 0; i < N; i++)
        {
            if (!isTop[i])
                continue;

            for (int j = 0; j < K; j++)
            {
                if (minOnPeg[j] <= i)
                    continue;

                var tmp = state[i];
                state[i] = j;
                var newStateIndex = StateToNum(state);
                legalMoves.Add(newStateIndex);
                state[i] = tmp;
            }
        }
        return legalMoves;
    }

    static int StateToNum(List<int> state)
    {
        int r = 0;
        int f = 1;
        foreach (var peg in state)
        {
            r += f * peg;
            f *= K;
        }
        return r;
    }

    static List<int> NumToState(int num)
    {
        var r = new List<int>();
        for (int i = 0; i < N; i++)
        {
            r.Add(num % K);
            num = num / K;
        }
        return r;
    }
}