php - php Peg Puzzle 解算器超时

Question

第一次来。

我正在使用递归开发 Peg Puzzle php 求解器。对于小型且简单的板，我得到了所需的结果(脚本正确地解决了难题)，但对于较大且完整的板(即除一个插槽外所有插槽都被占用)我得到了 php 超时。我需要让它与 7x7 板配合使用，布局如下:

x x 1 1 1 x x
x x 1 1 1 x x
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
x x 1 1 1 x x
x x 1 1 1 x x

其中“x”不可用，“1”是带有 Hook 的插槽，“0”是空闲插槽。

棋盘由 7x7 数组(数组的数组)表示。我一次一个键地遍历它，进行以下检查:

该键的值是“1”吗？ 如果是，那么后面的键的值是否也是“1”以及后面的“0”？ (这意味着有一个钉子可以拿，并且有空间可以移动第一个钉子)。 如果是，那么我将创建该板的副本并应用这些更改，然后将其重新发送到该函数。 如果没有，我检查另一个方向(当前检查顺序是:右、左、上、下)。

当脚本无法从该位置找到有效路径时，递归结束。 然后，我检查是否只剩下一个钉子(这意味着该板已解决)，或者是否还剩下一个钉子(这意味着该板未解决)。在后者中，整个路径应该被丢弃。

我会复制并粘贴我的代码，但由于它仍然有点困惑，我更愿意解释一下。

我尝试了 Rodolphe Courtier 算法 ( here )，得到了相同的结果。

提前致谢!

编辑:好的，到目前为止，使 DFS 非递归并没有太大帮助(仍然涉及很多步骤)。所以现在我正在考虑首先检查棋盘上是否存在会产生无法解决的难题的模式，如果是这种情况，我会指示脚本首先不要费心遍历它。和以前一样，将发布我的发现。

Answer 1

我之前用 C++ 和 C# 写过这个。我可以告诉你，7x7 阵列并不是最好的。考虑标准深度优先搜索算法和作为位板的板表示。如果您愿意，我可能可以在 C 语言中发布完整的解决方案，但可以针对不同的板。

此外，考虑到该解决方案需要深度优先搜索，您确实无法绕过递归。我的第一次尝试做了类似你正在做的事情，但速度很慢。位板实现在几秒钟​​内完成，而不是几分钟。

编辑:

这是我对三角形 15 钉板的解决方案。起始板已将除三角形顶部之外的所有钉子就位，获胜的解决方案被定义为最后一个钉子最终位于顶部位置。该算法对您来说应该是相同的，只是您需要重新定义表来确定哪些 Action 可用以及哪些 Action 合法。

基本说明:棋盘排列如下:

        p1
      p2  p3
    p4  p5  p6
  p7  p8  p9  pa
pb  pc  pd  pe  pf

每个位置都映射到 16 位 int 上的一位。该板开始时除 p1 之外的所有位均打开。 “移动”是三位的三元组。例如，(p1, p2, p4) 是可能的移动。如果 p1,p2 位被设置且 p4 被清除，或者 p2,p4 被设置且 p1 被清除，则该移动是“合法的”。有所有 Action 的查找表以及合法的 Action 定义。

为了进行深度优先搜索，我们需要:

• 最终状态(一点点打开:我通过将其定义为仅 p1 打开来“作弊”，这很简单)
• 进行和撤消移动(将当前棋盘与候选移动进行异或，同样微不足道)
• 生成候选移动集(同样，一些二进制异或/与运算。唯一复杂的部分，如果需要的话我可以稍后详细说明......)

代码:

#include <vector>
#include <iostream>
using namespace std;

typedef short state_t;

struct Move {
short move;
const char * desc;
};
typedef Move move_t;

struct Options {
short moves[4];
int size;
};

// name the bits
# define P1 1
# define P2 1 << 1
# define P3 1 << 2
# define P4 1 << 3
# define P5 1 << 4
# define P6 1 << 5
# define P7 1 << 6
# define P8 1 << 7
# define P9 1 << 8
# define P10 1 << 9
# define P11 1 << 10
# define P12 1 << 11
# define P13 1 << 12
# define P14 1 << 13 
# define P15 1 << 14

// not valid location
# define P16 1 << 15

// move triplets
Options options[15] = {
{{P1|P2|P4, P1|P3|P6}, 2},
{{P2|P4|P7, P2|P5|P9},2},
{{P3|P5|P8, P3|P6|P10},2},
{{P1|P2|P4, P4|P7|P11, P4|P5|P6, P4|P8|P13},4},
{{P5|P8|P12, P5|P9|P14},2},
{{P1|P3|P6, P4|P5|P6, P6|P9|P13, P6|P10|P15},4},
{{P7|P4|P2, P7|P8|P9},2},
{{P8|P5|P3,P8|P9|P10},2},
{{P9|P8|P7,P9|P5|P2},2},
{{P10|P6|P3,P10|P9|P8},2},
{{P11|P7|P4,P11|P12|P13},2},
{{P12|P8|P5,P12|P13|P14},2},
{{P13|P12|P11,P13|P14|P15,P13|P8|P4,P13|P9|P6},4},
{{P14|P9|P5,P14|P13|P12},2},
{{P15|P10|P6,P15|P14|P13},2}
};

// legal moves
Options legal[15] = {
{{P1|P2, P1|P3}, 2},
{{P2|P4, P2|P5},2},
{{P3|P5, P3|P6},2},
{{P4|P2, P4|P7, P4|P5, P4|P8},4},
{{P5|P8,P5|P9},2},
{{P6|P3, P6|P5, P6|P9, P6|P10}, 4},
{{P7|P4, P7|P8},2},
{{P8|P5, P8|P9},2},
{{P9|P8,P9|P5},2},
{{P10|P6,P10|P9},2},
{{P11|P7,P11|P12},2},
{{P12|P8,P12|P13},2},
{{P13|P12,P13|P14,P13|P8,P13|P9},4},
{{P14|P9,P14|P13},2},
{{P15|P10,P15|P14},2}
};

// for printing solution
struct OptionDesc {
const char* name[4];
int size;
};
OptionDesc desc[15] = {
{{"p1 => p4", "p1 => p6"}, 2},
{{"p2 => p7", "p2 => p9"}, 2},
{{"p3 => p8", "p3 => p10"}, 2},
{{"p4 => p1", "p4 => p11", "p4 => p6", "p4 => p13"}, 4},
{{"p5 => p12", "p5 => p14"}, 2},
{{"p6 => p1", "p6 => p4", "p6 => p13", "p6 => p15"}, 4},
{{"p7 => p2", "p7 => p9"}, 2},
{{"p8 => p3", "p8 => p10"}, 2},
{{"p9 => p7", "p9 => p2"}, 2},
{{"p10 => p3", "p10 => p8"}, 2},
{{"p11 => p4", "p11 => p13"}, 2},
{{"p12 => p5", "p12 => p14"}, 2},
{{"p13 => p11", "p13 => p15", "p13 => p4", "p13 => p6"}, 4},
{{"p14 => p5", "p14 => p12"}, 2},
{{"p15 => p6", "p15 => p13"}, 2}
};

int LEGAL_COUNT = sizeof (legal) / sizeof (Options);

state_t START = P2|P3|P4|P5|P6|P7|P8|P9|P10|P11|P12|P13|P14|P15;

// make move: just xor
inline void make_move(state_t& s, move_t m) 
{
s ^= m.move;
}

// undo move: just xor
inline void unmake_move (state_t& s, move_t m)
{
s ^= m.move;
}

// define end state as peg in top position
inline bool end_state (state_t s)
{
return (s ^ START) == (START|P1);
}

// generates moves from table of legal moves, and table of all possible move options
inline void generate_moves(state_t s, vector<move_t>& moves) 
{
for (int i = 0; i < LEGAL_COUNT; i++) {
    for (int j = 0; j < legal[i].size; j++) {
        short L = legal[i].moves[j];
        short M = L ^ options[i].moves[j];
        if ((s & L) == L && (s & M) == 0) {
            move_t m;
            m.move = options[i].moves[j];
            m.desc = desc[i].name[j];
            moves.push_back(m);
        }
    }
}
}

// basic depth first search:
bool dfs (state_t& s, int& count)
{
bool found = false;

if (end_state(s)) {
    count++;
    return true;
}

vector<move_t> moves;
generate_moves(s, moves);

for (vector<move_t>::iterator it = moves.begin();
    it != moves.end(); it++) {
        make_move (s, *it);
        found = dfs(s,count);
        unmake_move(s, *it);
        if (found && 0) {
            cout << it->desc << endl;
            return true;
        }
}
return false;
}

void init(state_t& s)
{
s = START;
}

int main(int argc, char* argv[])
{
state_t s;
int count = 0;
init(s);
bool solved = dfs (s, count);
//cout << "solved = " << solved << endl;
cout << "solutions = " << count << endl;
char c;
cin >> c;
return 0;
}