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' ？ (这意味着有一个钉子要拿，并且有一个空间来移动第一个)。
如果是，那么我会创建一个电路板副本并应用这些更改，然后将其重新发送给函数。
如果没有，我检查另一个方向(当前检查顺序是:右、左、上、下)。

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

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

我试过 Rodolphe Courtier's 算法( here )，结果相同。

提前致谢!

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

Answer 1

我以前用 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 来“欺骗”，这是微不足道的)

进行和撤消移动(将当前棋盘与候选移动进行异或，同样是微不足道的)

生成候选移动集(同样，一些二进制异或/和运算。唯一复杂的部分，如果需要，我可以稍后详细说明......)

编码:

#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;
}