第一次在这里。
我正在使用递归开发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"是带挂钩的插槽，"0"是可用插槽。
该板由7x7阵列（阵列的阵列）表示。我一次遍历一个键，进行以下检查：
这个键的值是"1"吗？如果是，以下键的值"1"和以下的"0"是否也是？（这意味着有一个钉子可以拿，还有一个移动第一个钉子的空间）。如果是，那么我创建一个板的副本并应用这些更改，然后将其重新发送到函数。如果没有，我会朝另一个方向检查（当前的检查顺序是：右、左、上、下）。
当脚本找不到该位置的有效路径时，递归结束。然后，我做了一个检查，看看是否只剩下一个钉子（这意味着棋盘已经解决了），或者是否还有钉子（这表示棋盘没有解决）。在后者中，整个路径应该被丢弃。
我会复制&粘贴我的代码，但由于它仍然有点乱，我更喜欢解释它。
我尝试了Rodolphe Courtier的算法（此处），得到了相同的结果。
提前感谢！
编辑：好的，到目前为止，使DFS非递归并没有太大帮助（还需要很多步骤）。所以现在我想先检查一下棋盘上是否有产生无法解决的谜题的模式，如果是这样的话，我会指示脚本一开始就不要遍历它。和以前一样，将发布我的发现。
我以前在c++和c#中都写过这篇文章。我可以告诉您，7x7阵列不是最好的。考虑标准深度优先搜索算法和作为位板的板表示。我可能会在c中发布一个完整的解决方案，但如果你愿意的话，可以换一个板。
此外，考虑到该解决方案需要深度优先搜索，您真的无法绕过递归。我的第一次尝试和你现在做的一样，但很慢。位板实现在几秒钟而不是几分钟内完成。
编辑：
这是我对一块三角形的15钉木板的解决方案。除了三角形的顶部外，起跑板上的所有钉子都已就位，获胜的解决方案被定义为最后一个钉子最终位于顶部位置。除了需要重新定义哪些移动是可用的以及哪些移动是合法的表之外，该算法应该对您起同样的作用。
基本解释：板是这样排列的：
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被清除，则移动是"合法的"。这里有所有移动的查找表，以及合法的移动定义。
为了进行深度优先搜索，我们需要：
- 结束状态（有一点：我把它定义为只有p1，这很琐碎，从而"欺骗"了它）
- 进行和撤消移动（将当前板与候选移动异或，同样微不足道）
- 生成候选的移动集（同样，一些二进制xor/和操作。唯一复杂的部分，如果需要，我可以稍后详细说明…）
代码：
#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;
}
根据您的描述，我怀疑主要的慢点是a）递归b）多次复制板。如果你可以把它放在一个循环中，而不是使用递归，这可能会有所帮助。如果你可以用一个或几个电路板副本（比如说，每个潜在路径一个电路板，通过引用函数传递它），这也可能会有所帮助。
你的运行时间将根据木板的大小和钉子的数量呈指数级增长；你想做的是让它尽可能缓慢地增加。
例如，假设你有一块20x20的木板，除了一个位置外，其他位置都满了。有399个钉子。这些钉子中的每一个都可能在其他398个钉子中迭代以找到解决方案：这意味着你的递归循环迭代20x20x20x20次，每次都制作一个新的400个钉子板。这是很多循环，这是很多板！
根据你链接的代码，我现在看到的唯一优化是让董事会一次只计算出一个动作，尝试这个动作，看看它会去哪里，而不是计算每个阶段的所有动作。不过，这是一个线性优化，而不是指数优化；这可能在一定程度上有所帮助，但不会有多大帮助。（例如，董事会不会进行n^2次计算来计算每一步，而是平均进行（n^2）/2次——仍然是O（n ^2）。
此外，getMoves函数本身非常慢——在我看来，它可以被重写得更快，尤其是当它被调用160000次时。