php Peg Puzzle 解算器超时 [英] Timeout on a php Peg Puzzle solver
问题描述
第一次来.
我正在使用递归开发 Peg Puzzle php 求解器.对于小而简单的板，我得到了想要的结果(脚本正确解决了难题)，但对于更大和完整的板(即所有插槽，但一个被占用)，我得到了 php 超时.我需要让它与 7x7 板一起工作，布局如下:
I'm working on a Peg Puzzle php solver, using recursion. For small and simple boards, I get the desired results (the script solves the puzzle correctly), but for larger and full boards (i.e. all slots but one occupied) I get a php timeout. I need to get it to work with a 7x7 board, with the following layout:
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' 是空闲插槽.
Where 'x' is unusable, '1' is a slot with a peg and '0' is a free slot.
棋盘由 7x7 数组(数组的数组)表示.我一次一个键遍历它，进行以下检查:
The board is represented by 7x7 array (an array of arrays). I traverse it one key at a time, doing the following checks:
这个键的值是1"吗?如果是，以下键的值是否也是 '1' 和后面的 '0' ?(这意味着有一个钉子要拿，并且有一个空间可以移动第一个).如果是，那么我会创建一个电路板副本并应用这些更改，然后将其重新发送给函数.如果没有，我检查另一个方向(当前检查顺序是:右、左、上、下).
Is this key's value '1'? If yes, is the following key's value '1' too and the following '0' ? (which means there's a peg to take, and there's a space to move the first one). If yes, then I create a copy of the board and apply these changes, and resend it to the function. If not, I check in another direction (currently checking order is: right, left, up, down).
当脚本无法从该位置找到有效路径时，递归结束.然后，我检查一下是否只剩下一个挂钩(这意味着棋盘已解决)，或者是否还有挂钩(这意味着棋盘未解决).在后者中，应该丢弃整个路径.
Recursion ends when the script can't find a valid path from that position. Then, I do a check to see if there's only one peg left (which would mean that the board is solved), or if there are pegs left (which would mean that the board wasn't solved). In the latter, the whole path should be discarded.
我会复制并粘贴我的代码，但由于它仍然有点混乱，我更愿意解释它.
I would copy&paste my code, but as it's still a little messy I preferred to explain it.
我尝试了 Rodolphe Courtier's 算法(此处)，结果相同.
I tried Rodolphe Courtier's algorithm (here), with the same results.
提前致谢！
好的，到目前为止，使 DFS 非递归并没有太大帮助(仍然涉及很多步骤).所以现在我正在考虑首先检查棋盘上是否有产生无法解决的谜题的模式，如果是这种情况，我会指示脚本首先不要费心遍历它.和以前一样，将发布我的发现.
Ok, so far making the DFS non-recursive didn't quite help (there are still a lot of steps involved). So now I'm thinking about checking the board for patterns that yield a unsolvable puzzle first, and if that's the case I instruct the script not to bother traversing it in the first place. As before, will post my findings.
推荐答案
我以前用 c++ 和 c# 写过这个.我可以告诉你 7x7 阵列不是最好的.考虑标准的深度优先搜索算法和作为位板的板表示.如果你愿意，我可能可以用 c 语言发布一个完整的解决方案，但对于不同的板.
I've written this before in both c++ and c#. I can tell you that the 7x7 array is not best. Consider a standard depth first search algorithm and a board representation as a bitboard. I can probably post a full solution in c but for a different board if you like.
另外，考虑到解决方案需要深度优先搜索，您确实无法绕过递归.我的第一次尝试做了一些类似于你正在做的事情，而且速度很慢.位板实现在几秒钟内完成，而不是几分钟.
Also given that the solution requires depth first search you really can't get around the recursion. My first try did something like what you're doing and it was slow. The bitboard implementation completed in seconds not minutes.
这是我对三角形形状的 15 个钉板的解决方案.除了三角形的顶部之外，起始板上的所有钉都已就位，获胜解决方案被定义为最后一个钉在顶部位置.除了您需要重新定义哪些移动可用以及哪些移动是合法的表格之外，该算法应该对您同样有效.
This was my solution for a 15 peg board that was in the shape of a triangle. The start board had all pegs in place except for the top of the triangle, and the winning solution is defined as last peg ending up in the top position. The algorithm should work identically for you except that you need to redefine the tables for what moves are available and what moves are legal.
基本解释:板子是这样排列的:
Basic explanation: The board is arranged like this:
p1
p2 p3
p4 p5 p6
p7 p8 p9 pa
pb pc pd pe pf
每个位置都映射到 16 位整数上的一位.该板从除 p1 之外的所有位开始.移动"是三位的三元组.例如，(p1, p2, p4) 是一个可能的移动.如果设置了 p1,p2 位且 p4 清零，或 p2,p4 设置且 p1 清零，则移动是合法的".有所有移动的查找表，以及合法的移动定义.
The each location is mapped to one bit on a 16-bit int. The board starts with all bits on except p1. A "move" is a triplet of three bits. For example, (p1, p2, p4) is a possible move. The move is "legal" if p1,p2 bit is set and p4 is clear, OR p2,p4 is set and p1 is clear. There's lookup tables for all moves, and the legal move definitions.
为了进行深度优先搜索，我们需要:
In order to do a depth first search, we need:
- 结束状态(一点点:我通过将其定义为仅 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;
}
这篇关于php Peg Puzzle 解算器超时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
