如何解决 3×3 网格中的黑白骑士问题
How to solve black & white knights problem in 3×3 grid
这里是对人工智能知情和不知情搜索算法的测试。
We have a 3×3 grid where B means BLACK KNIGHT and W is WHITE KNIGHT of chess.
+---+---+---+ +---+---+---+
| W | | W | | B | | B |
+---+---+---+ +---+---+---+
| | | | ----> | | | |
+---+---+---+ +---+---+---+
| B | | B | | W | | W |
+---+---+---+ +---+---+---+
B and W can "L" move exactly like knights chess pieces.
What is the best search algorithm to put black ones into current white ones squares and white ones into current black ones square?
- A STAR
- BFS
- DFS
- HILL CLIMBING
我真的很迷茫，不知道正确的选择。
A* 应该是解决这个问题的合适算法。作为目标启发式，您可以使用编号。假设棋盘是空的，到达目标目的地所需的移动次数总是 <= 所需的实际移动次数。
一个重要的方面是可能的职位数量相当少：
420 = Binomial(8,2) * Binomial(6, 2)
一个后果是无论select采用哪种算法，都要注意不要多次通过同一个节点，即通过同一个位置。传统上，国际象棋程序在分析棋子数量较少的位置时使用哈希表。在这里，考虑到可能的位置数量较少，可以 select 完美 散列，即没有串通
关于算法：
- 爬山 方法提供局部最小值，而不是绝对值。它不应该回答这里的问题
- DFS（例如通过回溯实现）在这里似乎不是最好的，因为你冒着在错误路线上深入的风险
- A*算法通常非常高效。但是，它依赖于给定节点的良好启发式估计。在这里，经过手工寻找解决方案后，显然骑士要在短表面上长时间转身（疯马).在这种情况下很难找到好的启发式
- BFS 通常有一个缺点，它会产生非常大量的内存，因此需要花费大量时间来访问这些节点。在这里，由于可能的节点（位置）数量有限并且由于散列，情况并非如此。而且，有了 BFS，一旦我们得到一个解决方案，我们就确定它是最短的
因此我用 C++ 实现了 BFS。结果几乎是瞬间提供的。
16个半步如下：
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | W | | | | W | | | | W | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | B | | B | W | B | | | W | B | | | W | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | | | B | | W | | B | B | W | | B | B | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | | | W | | | | W | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | B | | | | B | | | | | | | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | W | W | | B | W | W | | B | W | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | | | | W | | | | W | B | | | | B | | B | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | B | | | | B | | | | B | | | | B | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | B | | | | B | W | | | | W | | W | | W | | W | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
和节目：
#include <iostream>
#include <array>
#include <vector>
#include <tuple>
#include <algorithm>
int depl[9][2] = {
{5,7}, {6,8}, {3,7}, {2,8}, {-1,-1},
{0,6}, {1,5}, {0,2}, {1,3}};
struct position {
std::array<int, 2> B;
std::array<int, 2> W;
int hash;
position *up = nullptr;
position (int w0, int w1, int b0, int b1) {
if (w0 > w1) std::swap (w0, w1);
if (b0 > b1) std::swap (b0, b1);
B[0] = b0;
B[1] = b1;
W[0] = w0;
W[1] = w1;
cal_hash();
}
position() {};
void cal_hash () {
hash = 1000*B[0] + 100*B[1] + 10*W[0] + W[1];
}
std::vector<position> gene_mov (int white_black) {
std::vector<position> res;
if (!white_black) { // White
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[W[i]][j];
bool test = (pos == W[1-i]) || (pos == B[0]) || (pos == B[1]);
if (!test) {
res.push_back (position(pos, W[1-i], B[0], B[1]));
}
}
}
} else { // Black
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[B[i]][j];
bool test = (pos == B[1-i]) || (pos == W[0]) || (pos == W[1]);
if (!test) {
res.push_back (position(W[0], W[1], pos, B[1-i]));
}
}
}
}
return res;
}
void print (int shift = 0) {
char displ[3][3] = {{' ',' ',' '},
{' ',' ',' '},
{' ',' ',' '}};
displ[1][1] = ' ';
displ[2 - W[0]/3][W[0]%3] = 'W';
displ[2 - W[1]/3][W[1]%3] = 'W';
displ[2 - B[0]/3][B[0]%3] = 'B';
displ[2 - B[1]/3][B[1]%3] = 'B';
Wshift(shift);
std::cout << "+---+---+---+\n";
for (int i = 0; i < 3; ++i) {
Wshift(shift);
for (int j = 0; j < 3; j++) {
std::cout << "| " << displ[i][j] << " ";
}
std::cout << "|\n";
Wshift(shift);
std::cout << "+---+---+---+\n";
}
std::cout << "\n";
}
void Wshift (int shift) {
for (int i = 0; i < shift; ++i)
std::cout << " ";
}
};
std::tuple<bool, int, std::vector<position>> find_moves (position &first, position &end) {
std::vector<position> moves;
std::array<bool, 10000> pos_found = {false};
std::vector<std::vector<position>> dfs;
using pvector = std::vector<position>;
dfs.push_back(pvector(1, first));
int iter = 1;
int white_black = 0;
while (true) {
int n = dfs[iter-1].size();
if (n == 0) return std::make_tuple(false, 0, moves);
dfs.push_back(pvector(0));
for (int i = 0; i < n; ++i) {
auto candidates = dfs[iter-1][i].gene_mov(white_black);
for (auto &c: candidates) {
if (pos_found[c.hash]) continue;
c.up = &dfs[iter-1][i];
if (c.hash == end.hash) { // Last position attained: get the previous moves
moves.resize(iter+1);
moves[iter] = c;
for (int i = iter - 1; i >= 0; i--) {
moves[i] = *(moves[i+1].up);
}
return std::make_tuple(true, iter, moves);
}
pos_found[c.hash] = true;
dfs[iter].push_back (c);
}
}
iter++;
white_black = 1 - white_black;
}
return std::make_tuple(false, -1, moves);
}
int main () {
position first(6, 8, 0, 2);
position end(0, 2, 6, 8);
bool success;
int n_iter;
std::vector<position> moves;
std::tie (success, n_iter, moves) = find_moves (first, end);
std::cout << "success = " << success << "\n";
std::cout << "n_iter = " << n_iter << "\n";
for (auto &m: moves) {
m.print();
std::cout << "\n";
}
return 0;
}
这里是对人工智能知情和不知情搜索算法的测试。
We have a 3×3 grid where B means BLACK KNIGHT and W is WHITE KNIGHT of chess.
+---+---+---+ +---+---+---+ | W | | W | | B | | B | +---+---+---+ +---+---+---+ | | | | ----> | | | | +---+---+---+ +---+---+---+ | B | | B | | W | | W | +---+---+---+ +---+---+---+B and W can "L" move exactly like knights chess pieces.
What is the best search algorithm to put black ones into current white ones squares and white ones into current black ones square?
- A STAR
- BFS
- DFS
- HILL CLIMBING
我真的很迷茫，不知道正确的选择。
A* 应该是解决这个问题的合适算法。作为目标启发式，您可以使用编号。假设棋盘是空的，到达目标目的地所需的移动次数总是 <= 所需的实际移动次数。
一个重要的方面是可能的职位数量相当少：
420 = Binomial(8,2) * Binomial(6, 2)
一个后果是无论select采用哪种算法，都要注意不要多次通过同一个节点，即通过同一个位置。传统上，国际象棋程序在分析棋子数量较少的位置时使用哈希表。在这里，考虑到可能的位置数量较少，可以 select 完美 散列，即没有串通
关于算法：
- 爬山 方法提供局部最小值，而不是绝对值。它不应该回答这里的问题
- DFS（例如通过回溯实现）在这里似乎不是最好的，因为你冒着在错误路线上深入的风险
- A*算法通常非常高效。但是，它依赖于给定节点的良好启发式估计。在这里，经过手工寻找解决方案后，显然骑士要在短表面上长时间转身（疯马).在这种情况下很难找到好的启发式
- BFS 通常有一个缺点，它会产生非常大量的内存，因此需要花费大量时间来访问这些节点。在这里，由于可能的节点（位置）数量有限并且由于散列，情况并非如此。而且，有了 BFS，一旦我们得到一个解决方案，我们就确定它是最短的
因此我用 C++ 实现了 BFS。结果几乎是瞬间提供的。
16个半步如下：
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | W | | | | W | | | | W | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | B | | B | W | B | | | W | B | | | W | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | | | B | | W | | B | B | W | | B | B | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | | | W | | | | W | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | B | | | | B | | | | | | | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | W | W | | B | W | W | | B | W | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | | | | W | | | | W | B | | | | B | | B | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | B | | | | B | | | | B | | | | B | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | B | | | | B | W | | | | W | | W | | W | | W | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
和节目：
#include <iostream>
#include <array>
#include <vector>
#include <tuple>
#include <algorithm>
int depl[9][2] = {
{5,7}, {6,8}, {3,7}, {2,8}, {-1,-1},
{0,6}, {1,5}, {0,2}, {1,3}};
struct position {
std::array<int, 2> B;
std::array<int, 2> W;
int hash;
position *up = nullptr;
position (int w0, int w1, int b0, int b1) {
if (w0 > w1) std::swap (w0, w1);
if (b0 > b1) std::swap (b0, b1);
B[0] = b0;
B[1] = b1;
W[0] = w0;
W[1] = w1;
cal_hash();
}
position() {};
void cal_hash () {
hash = 1000*B[0] + 100*B[1] + 10*W[0] + W[1];
}
std::vector<position> gene_mov (int white_black) {
std::vector<position> res;
if (!white_black) { // White
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[W[i]][j];
bool test = (pos == W[1-i]) || (pos == B[0]) || (pos == B[1]);
if (!test) {
res.push_back (position(pos, W[1-i], B[0], B[1]));
}
}
}
} else { // Black
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[B[i]][j];
bool test = (pos == B[1-i]) || (pos == W[0]) || (pos == W[1]);
if (!test) {
res.push_back (position(W[0], W[1], pos, B[1-i]));
}
}
}
}
return res;
}
void print (int shift = 0) {
char displ[3][3] = {{' ',' ',' '},
{' ',' ',' '},
{' ',' ',' '}};
displ[1][1] = ' ';
displ[2 - W[0]/3][W[0]%3] = 'W';
displ[2 - W[1]/3][W[1]%3] = 'W';
displ[2 - B[0]/3][B[0]%3] = 'B';
displ[2 - B[1]/3][B[1]%3] = 'B';
Wshift(shift);
std::cout << "+---+---+---+\n";
for (int i = 0; i < 3; ++i) {
Wshift(shift);
for (int j = 0; j < 3; j++) {
std::cout << "| " << displ[i][j] << " ";
}
std::cout << "|\n";
Wshift(shift);
std::cout << "+---+---+---+\n";
}
std::cout << "\n";
}
void Wshift (int shift) {
for (int i = 0; i < shift; ++i)
std::cout << " ";
}
};
std::tuple<bool, int, std::vector<position>> find_moves (position &first, position &end) {
std::vector<position> moves;
std::array<bool, 10000> pos_found = {false};
std::vector<std::vector<position>> dfs;
using pvector = std::vector<position>;
dfs.push_back(pvector(1, first));
int iter = 1;
int white_black = 0;
while (true) {
int n = dfs[iter-1].size();
if (n == 0) return std::make_tuple(false, 0, moves);
dfs.push_back(pvector(0));
for (int i = 0; i < n; ++i) {
auto candidates = dfs[iter-1][i].gene_mov(white_black);
for (auto &c: candidates) {
if (pos_found[c.hash]) continue;
c.up = &dfs[iter-1][i];
if (c.hash == end.hash) { // Last position attained: get the previous moves
moves.resize(iter+1);
moves[iter] = c;
for (int i = iter - 1; i >= 0; i--) {
moves[i] = *(moves[i+1].up);
}
return std::make_tuple(true, iter, moves);
}
pos_found[c.hash] = true;
dfs[iter].push_back (c);
}
}
iter++;
white_black = 1 - white_black;
}
return std::make_tuple(false, -1, moves);
}
int main () {
position first(6, 8, 0, 2);
position end(0, 2, 6, 8);
bool success;
int n_iter;
std::vector<position> moves;
std::tie (success, n_iter, moves) = find_moves (first, end);
std::cout << "success = " << success << "\n";
std::cout << "n_iter = " << n_iter << "\n";
for (auto &m: moves) {
m.print();
std::cout << "\n";
}
return 0;
}