12 独霸骑士谜题（回溯）
12 dominating knights puzzle (backtracking)
我已经搜索了几个小时，但还没有找到解决此类难题的完整解决方案。所以我跟主教有类似的问题。
我需要做的是将 12 个马放在棋盘上，使棋盘上的所有自由方格至少被一个棋子攻击。
最终结果应该是这样的：
问题是 我的程序只尝试对最后两个部分进行不同的组合，然后不知何故崩溃。 已编辑
到目前为止我做了什么：
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard); //step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++) //correct overlapping dominations
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}
编辑：
- 修复了
placeKnight 和 removeKnight 中的数组边界（例如，j+2
< N 而不是 j+2 <= N)
- 在
backtracking 中添加了 return false;
问题：
现在它永远循环。尝试了大量组合，但从未找到我需要的组合（蛮力？）
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
printChessBoard(chessBoard);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard);// step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
return false; //ADDED LINE
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
//cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++)
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}
你的尝试效率很低，所以可能只是因为效率低下你找不到解决方案。
首先，尝试放置12个骑士是没有意义的。将 6 个骑士放在白色区域上。找到所有的解决方案。然后可以镜像任何在白色区域有 6 个马的解决方案，并在黑色区域给出 6 个马，然后将其组合。
其次，您试图以任意顺序放置骑士。但是顺序是任意的。因此，将它们按某种排序顺序排列，例如 a1、c1、e1、g1、b2、d2、f2、h2、a3 等。这样可以将选择的数量减少 6 倍！或 720（在您的原始情况下为 12！= 十亿）。
为了提高效率：从0到31对白色区域进行编号。从0到31对黑色区域进行编号。对于每个黑色区域，找到该区域的骑士可以到达的白色区域的索引，并创建代表这些字段的 32 位位图。
然后：
for (int k1 = 0; k1 < 27; ++k1)
for (int k2 = k1+1, k2 < 28; ++k2)
for (int k3 = k2+1; k3 < 29; ++k3)
for (int k4 = k3+1; k4 < 30; ++k4)
for (int k5 = k4+1; k5 < 31; ++k5)
for (int k6 = k5+1; k6 < 32; ++k6)
if ((bits [k1] | bits [k2] | bits [k3] | bits [k4] | bits [k5] | bits [k6]) == 0xffffffff)
// got a solution!!!
不到一百万张支票，所以需要几毫秒。
PS。您的 placeKnight / removeKnight 组合不起作用。例如，c3 被 b1 或 a2 上的马覆盖。如果你在 a2 上放置马，然后在 b1 上，然后移除 b1 上的马，你将 c3 设置为 "not covered"。
PS。如果你有一个更大的棋盘，你会走捷径来减少可能性的数量。例如，字段 a1 必须由第一行、第二行或第三行的 b3 的马覆盖。因此，如果您尝试将马放在 c3 或更晚的字段上，而 a1 未被覆盖，则根本没有必要尝试将马放在该字段或更晚的字段上。
正如@gnasher729 所指出的那样，尝试放置所有 12 个骑士效率非常低，因此我们可以尝试在 white blocks 上放置 6 个骑士，但使用这种方法我们最多只能攻击30 black blocks out of 32.
所以从上面我们可以采取两种方法:
1) We can fix 2 knights on the remaining 2 black blocks, and then try to place the remaining 4 knights on the remaining 30 black blocks, notice now we only need to attack the remaining 26 white blocks.
@gnasher729 说我们可以镜像解决方案，但是我无法想出固定 2 个地方然后找到镜像的逻辑，因为只有 30 个街区被攻击，没有骑士14，那么32个区块都被攻击了，找个镜像说不定就可以了
2) The second would be to brute force the remaining 6 knights whenever we find a solution for the first 6 knights that attacked more than 26 black blocks, which i implemented but that was still not finding a solution.
所以@n.m。说我们可以尝试从中心寻找解决方案以减少搜索 space，所以我尝试通过将骑士放在 6 X 6 中心广场来寻找解决方案，并且进一步只在 30 个时寻找解决方案32 个黑块被攻击而不是 26 个，最终能够找到 2 个对称的问题解决方案，可能会有更多的解决方案可以用更好的方法解决问题。
C++ 代码：
#include <iostream>
#include <ctime>
using namespace std;
#define N 8
int board[N][N], mark[N][N];
void placeOnBoard(int i, int j){
int count = 0;
if(mark[i][j] == 0) mark[i][j] = 1;
if(i+2 < N && j+1 < N && mark[i+2][j+1] == 0) mark[i+2][j+1] = 1;
if(i+2 < N && j-1 >= 0 && mark[i+2][j-1] == 0) mark[i+2][j-1] = 1;
if(i-2 >= 0 && j+1 < N && mark[i-2][j+1] == 0) mark[i-2][j+1] = 1;
if(i-2 >= 0 && j-1 >= 0 && mark[i-2][j-1] == 0) mark[i-2][j-1] = 1;
if(j+2 < N && i+1 < N && mark[i+1][j+2] == 0) mark[i+1][j+2] = 1;
if(j+2 < N && i-1 >= 0 && mark[i-1][j+2] == 0) mark[i-1][j+2] = 1;
if(j-2 >= 0 && i+1 < N && mark[i+1][j-2] == 0) mark[i+1][j-2] = 1;
if(j-2 >= 0 && i-1 >= 0 && mark[i-1][j-2] == 0) mark[i-1][j-2] = 1;
}
void printBoard(){
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(board[i][j] != 0) cout << "K ";
else cout << board[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void backtrackBlack(int knightNum, int currX, int currY){
if(knightNum == 7){
int count = 0;
for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
}
if(count == 64) printBoard();
return;
}
if(currX == N-1 && currY == N) return;
int newX, newY; //new place in the board to move to
if(currY == N) newY = 0,newX = currX + 1;
else newY = currY + 1,newX = currX;
//do not place the current knight at (currX, currY)
backtrackBlack(knightNum, newX, newY);
//try to place the current knight at (currX, currY)
if((currX + currY) % 2 == 1 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
board[currX][currY] = knightNum;
backtrackBlack(knightNum+1, newX, newY);
board[currX][currY] = 0;
}
}
void backtrackWhite(int knightNum, int currX, int currY){
if(knightNum == 7){
int count = 0;
for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
}
if(count >= 32){
backtrackBlack(1, 0, 0);
//printBoard();
}
return;
}
if(currX == N-1 && currY == N) return;
int newX, newY; //new place in the board to move to
if(currY == N) newY = 0,newX = currX + 1;
else newY = currY + 1,newX = currX;
//do not place the current knight at (currX, currY)
backtrackWhite(knightNum, newX, newY);
//try to place the current knight at (currX, currY)
if((currX + currY) % 2 == 0 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
board[currX][currY] = knightNum;
backtrackWhite(knightNum+1, newX, newY);
board[currX][currY] = 0;
}
}
int main(){
time_t t = clock();
backtrackWhite(1, 0, 0);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC;
cout << "Time Taken : " << time_taken<< endl;
return 0;
}
它在大约 89 秒内只找到 2 个解决方案。
输出：
0 0 0 0 0 0 0 0
0 0 K 0 0 0 0 0
0 0 K K 0 K K 0
0 0 0 0 0 K 0 0
0 0 K 0 0 0 0 0
0 K K 0 K K 0 0
0 0 0 0 0 K 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 K 0 0
0 K K 0 K K 0 0
0 0 K 0 0 0 0 0
0 0 0 0 0 K 0 0
0 0 K K 0 K K 0
0 0 K 0 0 0 0 0
0 0 0 0 0 0 0 0
Time Taken : 89.2418
这是一个相当有效的方法；您的棋盘是 [8][8] 的数组或 [64] 的单个数组。您有 12 块棋子要放置。在我们开始编写任何代码来实现解决此问题的程序之前，让我们首先评估情况并设计一个算法。
我们首先可以做两件事，我们可以省略或消除我们已经知道是骑士不能去的地方的单元格来满足 solution/s 这个问题。这些是棋盘的外部单元格或边框、四个对角相邻的内角，以及构成棋盘死点的 4 个单元格或拼贴块。如果任何一个马被放置在这些方块中的任何一个上，那么解决方案将不起作用。我们还可以查看最小公分母，即 4，这样我们就可以将棋盘分成 4 个象限，并在该象限中仅使用 3 个棋子。
这有两件事；一个它使算法更容易定义和更有效，并且它还满足另一个条件。其他条件是这样的，我们必须在每个象限中有 3 个骑士才能使解决方案有效。如果任何一个象限中有 4 个或更多，并且任何一个象限中的数量少于 3，解决方案将再次失败。
如果我们查看每个象限，我们可以看到：
- 左上象限 - 右下象限单元格是中心单元格之一。
- 右上象限 - 左下象限单元格是中心单元格之一。
- 左下象限 - 右上象限是中心单元格之一。
- 右下象限 - 左上角单元格是中心单元格之一。
是什么让它如此重要？我们知道，当在棋盘上放置一个马以让任何开放单元被设置为攻击时，棋盘正中心连接这 4 个象限的这 4 个方块不能在它们的位置有一个马，并且至少有一个在它的水平或垂直方向上向外相邻的单元格必须有一个骑士。知道了这一点，我们可以在 1 个象限上放置 3 个骑士，立即排除我们刚刚标记的单元格和与同一中心单元格相邻的另一个单元格。
如果你解决了这些象限中的一个，那么其他三个只是它们的翻译。因此，使用这种方法，只需要这么多的计算就可以解决一个 4x4 网格，其内角被列为起点，其水平或垂直邻居将放置一个骑士，并且无论哪个放置了骑士，另一个相邻的都会留空。这是一个图表，可以直观地看到这个消除过程，以便您知道如何正确构建或实施您的检查、搜索和放置算法。
所以一旦能够看到这个并知道问题是怎么回事。这些是您的算法中要采取的步骤。
- 划分 - 4 个象限 - 每个象限 3 个骑士
- 消除或跳过无效单元格（边框、内角和中心单元格）
- 在垂直或水平位置放置与中心单元格相邻的位置。
- 有 7 个可能的单元格可供选择放置，但由于一个被选中而另一个相邻的单元格没有放置位置，我们现在还有 5 个单元格可以放置另外 2 个骑士。
- 解决该象限的其余棋盘。
- 对上述解进行对称。如果这是象限 1 那么我们不需要解决象限 4，我们可以采用所有解决方案并执行+对角线对称。如果这是象限 2 那么我们不需要求解象限 3，我们可以执行 - 对角线对称。
- 现在将所有解决方案的所有 4 个象限拼接在一起并发送
将每个解决方案提交给您的检查器，以验证它是否满足可攻击条件。这应该是对 [64] 的数组进行线性搜索并进行一些比较，相当快。
- 删除任何不符合要求的解决方案。
- 打印结果。
编辑
这里有一个示例程序演示了如何设置一个预定义板，该板在您开始解决问题之前准备好并验证解决方案是否正确。
#include <conio.h>
#include <iostream>
#include <iomanip>
// These Enums Are Only A Visual Reference And Are Not Used
enum CellPlacement {
EMPTY_CELL = 0,
BLOCKED_BORDER = 1,
BLOCKED_CENTER = 2,
KNIGHT_PLACED = 3,
};
enum CellColor {
WHITE = 0,
WHITE = 1,
};
enum IsAttacked {
NO = 0,
YES = 1,
};
struct Cell {
unsigned char row : 3; // [0x00, 0x07]
unsigned char col : 3; // [0x00, 0x07]
unsigned char color : 1; // [0x00, 0x01] - Refer to CellColor
unsigned char attacked : 1; // [0x00, 0x01] - Refer to IsAttacked
unsigned char quad : 3; // [0x01, 0x04]
unsigned char state : 3; // [0x00, 0x03] - Refer to CellPlacement
};
struct Board {
Cell cell[8][8];
};
struct Quad {
Cell cell[4][4];
};
struct DividedBoard {
Quad quad[4];
};
int main() {
Board board;
DividedBoard divBoard;
// Temporary
unsigned char state = 0x00;
unsigned char quad = 0x00;
for ( unsigned char row = 0; row < 8; row++ ) {
for ( unsigned char col = 0; col < 8; col++ ) {
// Place Coords
board.cell[row][col].row = row;
board.cell[row][col].col = col;
// Mark Borders, Inner Corners & Center
if ( row == 0x00 || row == 0x07 || col == 0x00 || col == 0x07 ) { // Outer Boarders
state = 0x01;
board.cell[row][col].state = state;
} else if ( (row == 0x01 && col == 0x01) || (row == 0x01 && col == 0x06) || // Top Left & Right Inner Adjacent Corners
(row == 0x06 && col == 0x01) || (row == 0x06 && col == 0x06) ) { // Bottom Left & Right Inner Adjacent Corners
state = 0x01;
board.cell[row][col].state = state;
} else if ( (row == 0x03 && col == 0x03) || (row == 0x03 && col == 0x04) || // Top Left & Right Centers
(row == 0x04 && col == 0x03) || (row == 0x04 && col == 0x04) ) { // Bottom Left & Right Centers
state = 0x02;
board.cell[row][col].state = state;
} else {
state = 0x00;
board.cell[row][col].state = state; // Empty Cells
}
// Mark Wich Quadrant They Belong To And Populate Our Divided Board
if ( (row >= 0x00 && row < 0x04) && (col >= 0x00 && col < 0x04) ) {
quad = 0x01;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[0].cell[row][col].row = row;
divBoard.quad[0].cell[row][col].col = col;
divBoard.quad[0].cell[row][col].state = state;
divBoard.quad[0].cell[row][col].quad = quad;
}
if ( (row >= 0x00 && row < 0x04) && (col >= 0x04) ) {
quad = 0x02;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[1].cell[row][col-4].row = row;
divBoard.quad[1].cell[row][col-4].col = col;
divBoard.quad[1].cell[row][col-4].state = state;
divBoard.quad[1].cell[row][col-4].quad = quad;
}
if ( (row >= 0x04) && (col >= 0x00 && col < 0x04) ) {
quad = 0x03;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[2].cell[row-4][col].row = row;
divBoard.quad[2].cell[row-4][col].col = col;
divBoard.quad[2].cell[row-4][col].state = state;
divBoard.quad[2].cell[row-4][col].quad = quad;
}
if ( row >= 0x04 && col >= 0x04 ) {
quad = 0x04;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[3].cell[row-4][col-4].row = row;
divBoard.quad[3].cell[row-4][col-4].col = col;
divBoard.quad[3].cell[row-4][col-4].state = state;
divBoard.quad[3].cell[row-4][col-4].quad = quad;
}
}
}
// Display Board With Blocked & Empty Squares
std::cout << std::setw(19) << std::setfill('[=10=]') << "Full Board:\n";
std::cout << std::setw(20) << std::setfill('[=10=]') << "-----------\n\n";
for ( unsigned char row = 0x00; row < 0x08; row++ ) {
for ( unsigned char col = 0x00; col < 0x08; col++ ) {
std::cout << std::setw(2) << +board.cell[row][col].state << " ";
}
std::cout << "\n\n";
}
std::cout << "\n";
// Now Print Our Divided Board By Each Quadrant
for ( unsigned quad = 0; quad < 4; quad++ ) {
std::cout << std::setw(6) << "Quad" << quad << ":\n\n";
for ( unsigned row = 0; row < 4; row++ ) {
for ( unsigned col = 0; col < 4; col++ ) {
std::cout << std::setw(2) << +divBoard.quad[quad].cell[row][col].state << " ";
}
std::cout << "\n\n";
}
std::cout << "\n";
}
std::cout << "\nPress any key to quit.\n" << std::endl;
_getch();
return 0;
} // main
如果您通过控制台 运行 这个程序，它基本上会打印出我之前显示的图像图表。如您所见，此处的结构已经创建。在代码中，我将外板标记为 1，将 4 个内部单元格标记为 2，将空单元格标记为 0。从现在开始，这是获取第一个四边形并从选择两个点之一开始的问题与中心相邻，这是值为 2 的单元格。我们 [8][8] 中的此网格位置是 [3][3]，因此您可以使用任一位置 2[3] or location 3 开始，如果您将一个 Knight 的值设置为 3，那么对于这个可能的解决方案，另一个将保持为 0。如您所见，只有 7 个空单元格，做出第一个选择后，只剩下 5 个单元格可供选择放置您的第二个骑士，然后还有 4 个位置可以放置您的第三个也是最后一个骑士。
完成此步骤后，您可以进行 + 对称性的反射，使四边形 4 具有相同的解决方案模式。一旦为四边形 1 生成所有这些解决方案，四边形 4 也已完成。然后你必须对 Quad 2 & 3 做同样的事情。
因此，如果我们计算放置 1 个马，留下 2 个马放置和 5 个位置，这意味着第一个马放置有 10 种可能的解决方案。如果我们考虑到第一个 nice 被放置在另一个位置，那么对于一个象限我们总共有 20 种可能的解决方案。我们知道有 4 个象限，所以当您拥有容纳所有四边形的容器时，总共有 20^4 种不同的可能解决方案可供选择。总共有 160,000 个排列，用于计算所有不同的可能位置。
我实际上已经提到，Quad1 的解决方案是 Qaud4 的反映，而 Qaud2 的解决方案是 Quad3 的反映。由于正方形被标记为黑色或白色，因此在测试所有解决方案时都是如此。然而，当涉及到放置马来寻找可能的解决方案时，none 是相关的，所以我们可以只找到 1 个象限的所有排列，并将它们从其标记的中心单元格旋转到能够将这些解决方案映射到其他 3 个象限。因此，一旦我们找到象限 1 的 20 种可能的布局，只需对所有 20 种布局执行 3 次旋转即可得到 80 种不同的布局。
接下来就是混合和匹配这些布局中的每一个并根据我们的规则板进行测试的问题。
现在这并没有解决问题；但这是解决这个问题的有效方法，可以最大限度地减少在棋盘上设置字符的排列数量。你可以使用这种方法来设计你的算法来测试所有可能的答案以找到所有正确的解决方案。现在我展示的这些结构是一个好的开始，但您也可以添加到单元格结构中。您可以为方块的颜色添加一个标识符，如果它的位置受到攻击，则可以添加另一个标识符。我使用 unsigned char 是因为与 int 或 short 相比，使用字节时内存占用要小得多，而且由于所需值的范围仅为 0-7，我还决定使用我的 Cell 结构中的位字段。因此，1 个单元不再是 6 个字节，单个单元现在只有 2 个字节，还剩下几个位。由于字节顺序，您在使用位字段时需要小心，但是，由于所有值都是无符号字符，所以这应该不是问题。当我们开始对可能的解决方案进行所有排列以找到可行的解决方案时，这有助于在四元结果中构建这些单元格的数组时节省内存 space。此外，通过使用数字而不是实际字母设置单元格值可以使数学计算更容易。
我没有提到的一件事是：我不是 100% 确定这一点，但是因为我是一名国际象棋选手，所以我看棋盘的时间足够长，当你去做所有的生成过程时可能的解决方案，您甚至可以在将它们发送到函数以验证它们是否满足最终条件之前消除其中的大多数，也就是说，我认为他们安排的一个象限中的 3 个骑士也必须在他们攻击的形状相同。换句话说，他们将在棋盘上形成一个 L 形。这意味着如果这三个马中的一个没有另一个马在水平和垂直位置都相邻，我们可以得出结论，这个布局将不是一个有效的布局。当你在一个象限中放置你的骑士时，你可以合并这一步，然后这样当你为其他 3 个象限进行旋转时，你将需要解决排列总数的一小部分。
并且由于将相邻规则应用于中心单元格以及我认为放置的三个骑士必须形成其攻击方式的附加条件，这是一张显示所有有效位置的图像骑士可以在。
由于靠近中心的放置规则，如果您选择垂直单元格，那么中心的水平单元格将被清空，这让我相信至少有 8 种可能的解决方案，可能只有 2 种或其中4个有效。因此，我们甚至进一步缩小了搜索范围和排列范围。由于先前的规则，我们还可以得出缩小搜索范围的一件事，即我们也可以在此处应用 "Bingo" 规则。就像在 Bingo 中一样，中心单元是 "Free"，对我们来说每个象限都没有中心单元，但是从所有可能位置的十字图案我们现在知道这个十字的中心将总是有一个骑士。使用我使用的坐标并在整个板上按行列排列，这些将是 [2,2]、[2,5]、[5,2] 和 [5,5]。所以在放置阶段，这些可以首先自动添加，然后你可以选择与中心相邻的，最后你有两个选择，你的最后一块不会是另一个也与你的中心单元格相邻的单元格那个象限。
对于这个额外的案例，我们将总排列从 160,000 个减少到每个象限 4 个，整个棋盘的总排列为 4^4。因此，如果您预先查找了所有这些可能的解决方案 table，那么检查有效性的函数只需调用 256 次，而不是 160,000 次或数十亿次，如果您 运行所有董事会安置。预排除是许多人在解决复杂问题之前没有考虑到的步骤之一。这样做的好处在于，如果总共有 256 种可能的排列可以生成要测试的有效答案（如果它通过了要求），那么这些排列中的每一个都可以是 0-255 的索引。所有这些解决方案的索引首先使用十六进制值中的 unsigned char 到 1 个字节的内存中。
现在，关于检查可能解决方案的这 256 种排列的函数，这可以在线性过程中的一个简单的 for & while 循环中完成，只需检查每个单元格以查看它是否受到基本碰撞检测过程的攻击如果其中任何一个失败，我们就可以跳出那个 while 循环的迭代并放弃这个解决方案，然后转到我们的 for 循环的下一个迭代并继续该过程。如果解决方案的容器确实满足它，那么您想要标记该解决方案的出现并将其保存到另一个容器中，该容器包含循环的每次迭代的所有有效解决方案。这也可以消除递归的需要或使用。
我知道这很长，但要详细解释它需要那么多时间，我花了几个小时来检查问题、绘制图形、编写小程序并解释我所做的事情以及我为什么这样做，所以请随时发表评论，让我知道您对这种方法的看法。
首先我定义我的基本概念攻击能力。
攻击能力是多少骑士可以攻击给定的单元格。
例如：
角落单元只能由两个马攻击，因此攻击能力为二。中格攻击力为8.
细胞攻击能力
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
计算攻击力
AttackingNodes::AttackingNodes(int x, int y)
{
target = new Element(x, y);
CreateAtackList();
}
void AttackingNodes::CreateAtackList()
{
for(int diffx = -2; diffx <=2; ++diffx)
{
for(int diffy = -2; diffy <=2; ++diffy)
{
if((diffx*diffx + diffy* diffy) == 5)
{
AddAttack(target->_X + diffx, target->_Y + diffy);
}
}
}
}
void AttackingNodes::AddAttack( int x, int y )
{
if(x >= 0 && y >= 0 && x < BOARD_SIZE && y < BOARD_SIZE)
{
Element* element = new Element(x, y);
attackers.push_back(element);
}
}
攻击节点中攻击者的规模等于可攻击性。
然后创建 multimap 针对攻击节点的可攻击性
for(int x = 0; x < BOARD_SIZE; ++x)
{
for(int y = 0; y < BOARD_SIZE; ++y)
{
AttackingNodes* nodes = new AttackingNodes(x, y);
attackNodes[x][y] = nodes;
mapAttackPriority.insert(std::make_pair(nodes->attackers.size(), nodes));
}
}
如果可攻击性较低，则攻击给定单元格的选项较少。
因此选择多图中的第一个节点，它具有较少的攻击选项。
第一个单元格将为 0, 0。
攻击0有两个选项，0
1, 2 or 2, 1
让我们选择 1、2 并攻击单元格（如果它们是空的）。可以攻击6个细胞
attack(..) 将骑士放置在给定的单元格中。攻击者和目标以相同的方式相关。所以这里使用了计算攻击能力时产生的数据。
bool Solution::attack( Element* nodes )
{
++knightCount;
AttackingNodes* attackList = PriorityTargets::inst->attackNodes[nodes->_X][nodes->_Y];
std::list<Element*>::iterator itr;
board[nodes->_X][nodes->_Y] = CC_KNIGHT;
for(itr = attackList->attackers.begin(); itr != attackList->attackers.end(); ++itr)
{
Element* attackNode = *itr;
if(board[attackNode->_X][attackNode->_Y] == CC_EMPTY)
{
board[attackNode->_X][attackNode->_Y] = CC_ATTACKED;
}
}
return false;
}
|一个| 0 |一个| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 |一个 | 0 | 0 | 0 | 0 |
| 0 | K | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 |一个 | 0 | 0 | 0 | 0 |
|一个| 0 |一个 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
然后算法搜索下一个空单元格（没有 Knight，没有 Attacked），攻击性最低，用可用选项攻击它。
AttackingNodes* PriorityTargets::GetNextNode( Solution* solution )
{
std::multimap<size_t, AttackingNodes*>::iterator priorityItr;
for(priorityItr = mapAttackPriority.begin(); priorityItr != mapAttackPriority.end(); ++priorityItr)
{
AttackingNodes* attackNodes = priorityItr->second;
if(solution->board[attackNodes->target->_X][attackNodes->target->_Y] == CC_EMPTY)
{
return attackNodes;
}
}
return NULL;
}
这将是第二个选项的另一个角节点，它会一直持续到骑士数大于 12 或没有空单元格。
骑士数大于 12，这是一次失败的尝试并被跟踪。
如果没有空单元格就是一个解决方案。
Solution::Solution()
{
Clear();
}
void Solution::Print()
{
std::cout << std::endl ;
for(int x = 0; x < BOARD_SIZE; ++x)
{
for(int y = 0; y < BOARD_SIZE; ++y)
{
std::cout << (int)board[x][y] << " ";
}
std::cout << std::endl ;
}
std::cout << std::endl ;
}
bool Solution::Solve( Solution* solution )
{
AttackingNodes* nextAttackingNode = PriorityTargets::inst->GetNextNode(solution);
if(nextAttackingNode != NULL)
{
Solution* newSolutioon = new Solution();
std::list<Element*>::iterator itr;
for(itr = nextAttackingNode->attackers.begin(); itr != nextAttackingNode->attackers.end(); ++itr)
{
Element* attack = *itr;
*newSolutioon = *solution;
newSolutioon->attack(attack);
if(newSolutioon->knightCount < 13)
{
Solve(newSolutioon);
}
else
{
//Fail
newSolutioon->Clear();
}
}
delete newSolutioon;
}
else
{
std::cout << "Solved" << std::endl;
solution->Print();
}
return false;
}
void Solution::Clear()
{
memset(board, 0, BOARD_SIZE*BOARD_SIZE);
knightCount = 0;
}
我在 visual studio 2008 发布模式下不到 500 毫秒就得到了答案。
我用了2个骑士，1个攻击。
在限制各种棋盘大小的骑士统治问题方面已经做了大量工作。 Here is an article that seems to summarize all the previous work and adds a few new twists. And here is an article that claims to demonstrate a linear-time algorithm for knights domination. I've even found references to a constant-time knights domination algorithm，但我没看到有人不厌其烦地写出来。先动脑再写代码
我已经搜索了几个小时，但还没有找到解决此类难题的完整解决方案。所以我跟主教有类似的问题。
我需要做的是将 12 个马放在棋盘上，使棋盘上的所有自由方格至少被一个棋子攻击。
最终结果应该是这样的：
问题是 我的程序只尝试对最后两个部分进行不同的组合，然后不知何故崩溃。 已编辑
到目前为止我做了什么：
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard); //step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++) //correct overlapping dominations
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}
编辑：
- 修复了
placeKnight和removeKnight中的数组边界（例如，j+2 < N 而不是 j+2 <= N) - 在
backtracking 中添加了
return false;
问题： 现在它永远循环。尝试了大量组合，但从未找到我需要的组合（蛮力？）
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
printChessBoard(chessBoard);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard);// step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
return false; //ADDED LINE
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
//cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++)
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}
你的尝试效率很低，所以可能只是因为效率低下你找不到解决方案。
首先，尝试放置12个骑士是没有意义的。将 6 个骑士放在白色区域上。找到所有的解决方案。然后可以镜像任何在白色区域有 6 个马的解决方案，并在黑色区域给出 6 个马，然后将其组合。
其次，您试图以任意顺序放置骑士。但是顺序是任意的。因此，将它们按某种排序顺序排列，例如 a1、c1、e1、g1、b2、d2、f2、h2、a3 等。这样可以将选择的数量减少 6 倍！或 720（在您的原始情况下为 12！= 十亿）。
为了提高效率：从0到31对白色区域进行编号。从0到31对黑色区域进行编号。对于每个黑色区域，找到该区域的骑士可以到达的白色区域的索引，并创建代表这些字段的 32 位位图。
然后：
for (int k1 = 0; k1 < 27; ++k1)
for (int k2 = k1+1, k2 < 28; ++k2)
for (int k3 = k2+1; k3 < 29; ++k3)
for (int k4 = k3+1; k4 < 30; ++k4)
for (int k5 = k4+1; k5 < 31; ++k5)
for (int k6 = k5+1; k6 < 32; ++k6)
if ((bits [k1] | bits [k2] | bits [k3] | bits [k4] | bits [k5] | bits [k6]) == 0xffffffff)
// got a solution!!!
不到一百万张支票，所以需要几毫秒。
PS。您的 placeKnight / removeKnight 组合不起作用。例如，c3 被 b1 或 a2 上的马覆盖。如果你在 a2 上放置马，然后在 b1 上，然后移除 b1 上的马，你将 c3 设置为 "not covered"。
PS。如果你有一个更大的棋盘，你会走捷径来减少可能性的数量。例如，字段 a1 必须由第一行、第二行或第三行的 b3 的马覆盖。因此，如果您尝试将马放在 c3 或更晚的字段上，而 a1 未被覆盖，则根本没有必要尝试将马放在该字段或更晚的字段上。
正如@gnasher729 所指出的那样，尝试放置所有 12 个骑士效率非常低，因此我们可以尝试在 white blocks 上放置 6 个骑士，但使用这种方法我们最多只能攻击30 black blocks out of 32.
所以从上面我们可以采取两种方法:
1) We can fix 2 knights on the remaining 2 black blocks, and then try to place the remaining 4 knights on the remaining 30 black blocks, notice now we only need to attack the remaining 26 white blocks.
@gnasher729 说我们可以镜像解决方案，但是我无法想出固定 2 个地方然后找到镜像的逻辑，因为只有 30 个街区被攻击，没有骑士14，那么32个区块都被攻击了，找个镜像说不定就可以了
2) The second would be to brute force the remaining 6 knights whenever we find a solution for the first 6 knights that attacked more than 26
black blocks, which i implemented but that was still not finding a solution.
所以@n.m。说我们可以尝试从中心寻找解决方案以减少搜索 space，所以我尝试通过将骑士放在 6 X 6 中心广场来寻找解决方案，并且进一步只在 30 个时寻找解决方案32 个黑块被攻击而不是 26 个，最终能够找到 2 个对称的问题解决方案，可能会有更多的解决方案可以用更好的方法解决问题。
C++ 代码：
#include <iostream>
#include <ctime>
using namespace std;
#define N 8
int board[N][N], mark[N][N];
void placeOnBoard(int i, int j){
int count = 0;
if(mark[i][j] == 0) mark[i][j] = 1;
if(i+2 < N && j+1 < N && mark[i+2][j+1] == 0) mark[i+2][j+1] = 1;
if(i+2 < N && j-1 >= 0 && mark[i+2][j-1] == 0) mark[i+2][j-1] = 1;
if(i-2 >= 0 && j+1 < N && mark[i-2][j+1] == 0) mark[i-2][j+1] = 1;
if(i-2 >= 0 && j-1 >= 0 && mark[i-2][j-1] == 0) mark[i-2][j-1] = 1;
if(j+2 < N && i+1 < N && mark[i+1][j+2] == 0) mark[i+1][j+2] = 1;
if(j+2 < N && i-1 >= 0 && mark[i-1][j+2] == 0) mark[i-1][j+2] = 1;
if(j-2 >= 0 && i+1 < N && mark[i+1][j-2] == 0) mark[i+1][j-2] = 1;
if(j-2 >= 0 && i-1 >= 0 && mark[i-1][j-2] == 0) mark[i-1][j-2] = 1;
}
void printBoard(){
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(board[i][j] != 0) cout << "K ";
else cout << board[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void backtrackBlack(int knightNum, int currX, int currY){
if(knightNum == 7){
int count = 0;
for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
}
if(count == 64) printBoard();
return;
}
if(currX == N-1 && currY == N) return;
int newX, newY; //new place in the board to move to
if(currY == N) newY = 0,newX = currX + 1;
else newY = currY + 1,newX = currX;
//do not place the current knight at (currX, currY)
backtrackBlack(knightNum, newX, newY);
//try to place the current knight at (currX, currY)
if((currX + currY) % 2 == 1 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
board[currX][currY] = knightNum;
backtrackBlack(knightNum+1, newX, newY);
board[currX][currY] = 0;
}
}
void backtrackWhite(int knightNum, int currX, int currY){
if(knightNum == 7){
int count = 0;
for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
}
if(count >= 32){
backtrackBlack(1, 0, 0);
//printBoard();
}
return;
}
if(currX == N-1 && currY == N) return;
int newX, newY; //new place in the board to move to
if(currY == N) newY = 0,newX = currX + 1;
else newY = currY + 1,newX = currX;
//do not place the current knight at (currX, currY)
backtrackWhite(knightNum, newX, newY);
//try to place the current knight at (currX, currY)
if((currX + currY) % 2 == 0 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
board[currX][currY] = knightNum;
backtrackWhite(knightNum+1, newX, newY);
board[currX][currY] = 0;
}
}
int main(){
time_t t = clock();
backtrackWhite(1, 0, 0);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC;
cout << "Time Taken : " << time_taken<< endl;
return 0;
}
它在大约 89 秒内只找到 2 个解决方案。
输出：
0 0 0 0 0 0 0 0
0 0 K 0 0 0 0 0
0 0 K K 0 K K 0
0 0 0 0 0 K 0 0
0 0 K 0 0 0 0 0
0 K K 0 K K 0 0
0 0 0 0 0 K 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 K 0 0
0 K K 0 K K 0 0
0 0 K 0 0 0 0 0
0 0 0 0 0 K 0 0
0 0 K K 0 K K 0
0 0 K 0 0 0 0 0
0 0 0 0 0 0 0 0
Time Taken : 89.2418
这是一个相当有效的方法；您的棋盘是 [8][8] 的数组或 [64] 的单个数组。您有 12 块棋子要放置。在我们开始编写任何代码来实现解决此问题的程序之前，让我们首先评估情况并设计一个算法。
我们首先可以做两件事，我们可以省略或消除我们已经知道是骑士不能去的地方的单元格来满足 solution/s 这个问题。这些是棋盘的外部单元格或边框、四个对角相邻的内角，以及构成棋盘死点的 4 个单元格或拼贴块。如果任何一个马被放置在这些方块中的任何一个上，那么解决方案将不起作用。我们还可以查看最小公分母，即 4，这样我们就可以将棋盘分成 4 个象限，并在该象限中仅使用 3 个棋子。
这有两件事；一个它使算法更容易定义和更有效，并且它还满足另一个条件。其他条件是这样的，我们必须在每个象限中有 3 个骑士才能使解决方案有效。如果任何一个象限中有 4 个或更多，并且任何一个象限中的数量少于 3，解决方案将再次失败。
如果我们查看每个象限，我们可以看到：
- 左上象限 - 右下象限单元格是中心单元格之一。
- 右上象限 - 左下象限单元格是中心单元格之一。
- 左下象限 - 右上象限是中心单元格之一。
- 右下象限 - 左上角单元格是中心单元格之一。
是什么让它如此重要？我们知道，当在棋盘上放置一个马以让任何开放单元被设置为攻击时，棋盘正中心连接这 4 个象限的这 4 个方块不能在它们的位置有一个马，并且至少有一个在它的水平或垂直方向上向外相邻的单元格必须有一个骑士。知道了这一点，我们可以在 1 个象限上放置 3 个骑士，立即排除我们刚刚标记的单元格和与同一中心单元格相邻的另一个单元格。
如果你解决了这些象限中的一个，那么其他三个只是它们的翻译。因此，使用这种方法，只需要这么多的计算就可以解决一个 4x4 网格，其内角被列为起点，其水平或垂直邻居将放置一个骑士，并且无论哪个放置了骑士，另一个相邻的都会留空。这是一个图表，可以直观地看到这个消除过程，以便您知道如何正确构建或实施您的检查、搜索和放置算法。
所以一旦能够看到这个并知道问题是怎么回事。这些是您的算法中要采取的步骤。
- 划分 - 4 个象限 - 每个象限 3 个骑士
- 消除或跳过无效单元格（边框、内角和中心单元格）
- 在垂直或水平位置放置与中心单元格相邻的位置。
- 有 7 个可能的单元格可供选择放置，但由于一个被选中而另一个相邻的单元格没有放置位置，我们现在还有 5 个单元格可以放置另外 2 个骑士。
- 解决该象限的其余棋盘。
- 对上述解进行对称。如果这是象限 1 那么我们不需要解决象限 4，我们可以采用所有解决方案并执行+对角线对称。如果这是象限 2 那么我们不需要求解象限 3，我们可以执行 - 对角线对称。
- 现在将所有解决方案的所有 4 个象限拼接在一起并发送 将每个解决方案提交给您的检查器，以验证它是否满足可攻击条件。这应该是对 [64] 的数组进行线性搜索并进行一些比较，相当快。
- 删除任何不符合要求的解决方案。
- 打印结果。
编辑
这里有一个示例程序演示了如何设置一个预定义板，该板在您开始解决问题之前准备好并验证解决方案是否正确。
#include <conio.h>
#include <iostream>
#include <iomanip>
// These Enums Are Only A Visual Reference And Are Not Used
enum CellPlacement {
EMPTY_CELL = 0,
BLOCKED_BORDER = 1,
BLOCKED_CENTER = 2,
KNIGHT_PLACED = 3,
};
enum CellColor {
WHITE = 0,
WHITE = 1,
};
enum IsAttacked {
NO = 0,
YES = 1,
};
struct Cell {
unsigned char row : 3; // [0x00, 0x07]
unsigned char col : 3; // [0x00, 0x07]
unsigned char color : 1; // [0x00, 0x01] - Refer to CellColor
unsigned char attacked : 1; // [0x00, 0x01] - Refer to IsAttacked
unsigned char quad : 3; // [0x01, 0x04]
unsigned char state : 3; // [0x00, 0x03] - Refer to CellPlacement
};
struct Board {
Cell cell[8][8];
};
struct Quad {
Cell cell[4][4];
};
struct DividedBoard {
Quad quad[4];
};
int main() {
Board board;
DividedBoard divBoard;
// Temporary
unsigned char state = 0x00;
unsigned char quad = 0x00;
for ( unsigned char row = 0; row < 8; row++ ) {
for ( unsigned char col = 0; col < 8; col++ ) {
// Place Coords
board.cell[row][col].row = row;
board.cell[row][col].col = col;
// Mark Borders, Inner Corners & Center
if ( row == 0x00 || row == 0x07 || col == 0x00 || col == 0x07 ) { // Outer Boarders
state = 0x01;
board.cell[row][col].state = state;
} else if ( (row == 0x01 && col == 0x01) || (row == 0x01 && col == 0x06) || // Top Left & Right Inner Adjacent Corners
(row == 0x06 && col == 0x01) || (row == 0x06 && col == 0x06) ) { // Bottom Left & Right Inner Adjacent Corners
state = 0x01;
board.cell[row][col].state = state;
} else if ( (row == 0x03 && col == 0x03) || (row == 0x03 && col == 0x04) || // Top Left & Right Centers
(row == 0x04 && col == 0x03) || (row == 0x04 && col == 0x04) ) { // Bottom Left & Right Centers
state = 0x02;
board.cell[row][col].state = state;
} else {
state = 0x00;
board.cell[row][col].state = state; // Empty Cells
}
// Mark Wich Quadrant They Belong To And Populate Our Divided Board
if ( (row >= 0x00 && row < 0x04) && (col >= 0x00 && col < 0x04) ) {
quad = 0x01;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[0].cell[row][col].row = row;
divBoard.quad[0].cell[row][col].col = col;
divBoard.quad[0].cell[row][col].state = state;
divBoard.quad[0].cell[row][col].quad = quad;
}
if ( (row >= 0x00 && row < 0x04) && (col >= 0x04) ) {
quad = 0x02;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[1].cell[row][col-4].row = row;
divBoard.quad[1].cell[row][col-4].col = col;
divBoard.quad[1].cell[row][col-4].state = state;
divBoard.quad[1].cell[row][col-4].quad = quad;
}
if ( (row >= 0x04) && (col >= 0x00 && col < 0x04) ) {
quad = 0x03;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[2].cell[row-4][col].row = row;
divBoard.quad[2].cell[row-4][col].col = col;
divBoard.quad[2].cell[row-4][col].state = state;
divBoard.quad[2].cell[row-4][col].quad = quad;
}
if ( row >= 0x04 && col >= 0x04 ) {
quad = 0x04;
board.cell[row][col].quad = quad;
// Set Divided Board To This Quads State
divBoard.quad[3].cell[row-4][col-4].row = row;
divBoard.quad[3].cell[row-4][col-4].col = col;
divBoard.quad[3].cell[row-4][col-4].state = state;
divBoard.quad[3].cell[row-4][col-4].quad = quad;
}
}
}
// Display Board With Blocked & Empty Squares
std::cout << std::setw(19) << std::setfill('[=10=]') << "Full Board:\n";
std::cout << std::setw(20) << std::setfill('[=10=]') << "-----------\n\n";
for ( unsigned char row = 0x00; row < 0x08; row++ ) {
for ( unsigned char col = 0x00; col < 0x08; col++ ) {
std::cout << std::setw(2) << +board.cell[row][col].state << " ";
}
std::cout << "\n\n";
}
std::cout << "\n";
// Now Print Our Divided Board By Each Quadrant
for ( unsigned quad = 0; quad < 4; quad++ ) {
std::cout << std::setw(6) << "Quad" << quad << ":\n\n";
for ( unsigned row = 0; row < 4; row++ ) {
for ( unsigned col = 0; col < 4; col++ ) {
std::cout << std::setw(2) << +divBoard.quad[quad].cell[row][col].state << " ";
}
std::cout << "\n\n";
}
std::cout << "\n";
}
std::cout << "\nPress any key to quit.\n" << std::endl;
_getch();
return 0;
} // main
如果您通过控制台 运行 这个程序，它基本上会打印出我之前显示的图像图表。如您所见，此处的结构已经创建。在代码中，我将外板标记为 1，将 4 个内部单元格标记为 2，将空单元格标记为 0。从现在开始，这是获取第一个四边形并从选择两个点之一开始的问题与中心相邻，这是值为 2 的单元格。我们 [8][8] 中的此网格位置是 [3][3]，因此您可以使用任一位置 2[3] or location 3 开始，如果您将一个 Knight 的值设置为 3，那么对于这个可能的解决方案，另一个将保持为 0。如您所见，只有 7 个空单元格，做出第一个选择后，只剩下 5 个单元格可供选择放置您的第二个骑士，然后还有 4 个位置可以放置您的第三个也是最后一个骑士。
完成此步骤后，您可以进行 + 对称性的反射，使四边形 4 具有相同的解决方案模式。一旦为四边形 1 生成所有这些解决方案，四边形 4 也已完成。然后你必须对 Quad 2 & 3 做同样的事情。
因此，如果我们计算放置 1 个马，留下 2 个马放置和 5 个位置，这意味着第一个马放置有 10 种可能的解决方案。如果我们考虑到第一个 nice 被放置在另一个位置，那么对于一个象限我们总共有 20 种可能的解决方案。我们知道有 4 个象限，所以当您拥有容纳所有四边形的容器时，总共有 20^4 种不同的可能解决方案可供选择。总共有 160,000 个排列，用于计算所有不同的可能位置。
我实际上已经提到，Quad1 的解决方案是 Qaud4 的反映，而 Qaud2 的解决方案是 Quad3 的反映。由于正方形被标记为黑色或白色，因此在测试所有解决方案时都是如此。然而，当涉及到放置马来寻找可能的解决方案时，none 是相关的，所以我们可以只找到 1 个象限的所有排列，并将它们从其标记的中心单元格旋转到能够将这些解决方案映射到其他 3 个象限。因此，一旦我们找到象限 1 的 20 种可能的布局，只需对所有 20 种布局执行 3 次旋转即可得到 80 种不同的布局。
接下来就是混合和匹配这些布局中的每一个并根据我们的规则板进行测试的问题。
现在这并没有解决问题；但这是解决这个问题的有效方法，可以最大限度地减少在棋盘上设置字符的排列数量。你可以使用这种方法来设计你的算法来测试所有可能的答案以找到所有正确的解决方案。现在我展示的这些结构是一个好的开始，但您也可以添加到单元格结构中。您可以为方块的颜色添加一个标识符，如果它的位置受到攻击，则可以添加另一个标识符。我使用 unsigned char 是因为与 int 或 short 相比，使用字节时内存占用要小得多，而且由于所需值的范围仅为 0-7，我还决定使用我的 Cell 结构中的位字段。因此，1 个单元不再是 6 个字节，单个单元现在只有 2 个字节，还剩下几个位。由于字节顺序，您在使用位字段时需要小心，但是，由于所有值都是无符号字符，所以这应该不是问题。当我们开始对可能的解决方案进行所有排列以找到可行的解决方案时，这有助于在四元结果中构建这些单元格的数组时节省内存 space。此外，通过使用数字而不是实际字母设置单元格值可以使数学计算更容易。
我没有提到的一件事是：我不是 100% 确定这一点，但是因为我是一名国际象棋选手，所以我看棋盘的时间足够长，当你去做所有的生成过程时可能的解决方案，您甚至可以在将它们发送到函数以验证它们是否满足最终条件之前消除其中的大多数，也就是说，我认为他们安排的一个象限中的 3 个骑士也必须在他们攻击的形状相同。换句话说，他们将在棋盘上形成一个 L 形。这意味着如果这三个马中的一个没有另一个马在水平和垂直位置都相邻，我们可以得出结论，这个布局将不是一个有效的布局。当你在一个象限中放置你的骑士时，你可以合并这一步，然后这样当你为其他 3 个象限进行旋转时，你将需要解决排列总数的一小部分。
并且由于将相邻规则应用于中心单元格以及我认为放置的三个骑士必须形成其攻击方式的附加条件，这是一张显示所有有效位置的图像骑士可以在。
由于靠近中心的放置规则，如果您选择垂直单元格，那么中心的水平单元格将被清空，这让我相信至少有 8 种可能的解决方案，可能只有 2 种或其中4个有效。因此，我们甚至进一步缩小了搜索范围和排列范围。由于先前的规则，我们还可以得出缩小搜索范围的一件事，即我们也可以在此处应用 "Bingo" 规则。就像在 Bingo 中一样，中心单元是 "Free"，对我们来说每个象限都没有中心单元，但是从所有可能位置的十字图案我们现在知道这个十字的中心将总是有一个骑士。使用我使用的坐标并在整个板上按行列排列，这些将是 [2,2]、[2,5]、[5,2] 和 [5,5]。所以在放置阶段，这些可以首先自动添加，然后你可以选择与中心相邻的，最后你有两个选择，你的最后一块不会是另一个也与你的中心单元格相邻的单元格那个象限。
对于这个额外的案例，我们将总排列从 160,000 个减少到每个象限 4 个，整个棋盘的总排列为 4^4。因此，如果您预先查找了所有这些可能的解决方案 table，那么检查有效性的函数只需调用 256 次，而不是 160,000 次或数十亿次，如果您 运行所有董事会安置。预排除是许多人在解决复杂问题之前没有考虑到的步骤之一。这样做的好处在于，如果总共有 256 种可能的排列可以生成要测试的有效答案（如果它通过了要求），那么这些排列中的每一个都可以是 0-255 的索引。所有这些解决方案的索引首先使用十六进制值中的 unsigned char 到 1 个字节的内存中。
现在，关于检查可能解决方案的这 256 种排列的函数，这可以在线性过程中的一个简单的 for & while 循环中完成，只需检查每个单元格以查看它是否受到基本碰撞检测过程的攻击如果其中任何一个失败，我们就可以跳出那个 while 循环的迭代并放弃这个解决方案，然后转到我们的 for 循环的下一个迭代并继续该过程。如果解决方案的容器确实满足它，那么您想要标记该解决方案的出现并将其保存到另一个容器中，该容器包含循环的每次迭代的所有有效解决方案。这也可以消除递归的需要或使用。
我知道这很长，但要详细解释它需要那么多时间，我花了几个小时来检查问题、绘制图形、编写小程序并解释我所做的事情以及我为什么这样做，所以请随时发表评论，让我知道您对这种方法的看法。
首先我定义我的基本概念攻击能力。 攻击能力是多少骑士可以攻击给定的单元格。
例如： 角落单元只能由两个马攻击，因此攻击能力为二。中格攻击力为8.
细胞攻击能力
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
计算攻击力
AttackingNodes::AttackingNodes(int x, int y)
{
target = new Element(x, y);
CreateAtackList();
}
void AttackingNodes::CreateAtackList()
{
for(int diffx = -2; diffx <=2; ++diffx)
{
for(int diffy = -2; diffy <=2; ++diffy)
{
if((diffx*diffx + diffy* diffy) == 5)
{
AddAttack(target->_X + diffx, target->_Y + diffy);
}
}
}
}
void AttackingNodes::AddAttack( int x, int y )
{
if(x >= 0 && y >= 0 && x < BOARD_SIZE && y < BOARD_SIZE)
{
Element* element = new Element(x, y);
attackers.push_back(element);
}
}
攻击节点中攻击者的规模等于可攻击性。
然后创建 multimap 针对攻击节点的可攻击性
for(int x = 0; x < BOARD_SIZE; ++x)
{
for(int y = 0; y < BOARD_SIZE; ++y)
{
AttackingNodes* nodes = new AttackingNodes(x, y);
attackNodes[x][y] = nodes;
mapAttackPriority.insert(std::make_pair(nodes->attackers.size(), nodes));
}
}
如果可攻击性较低，则攻击给定单元格的选项较少。
因此选择多图中的第一个节点，它具有较少的攻击选项。
第一个单元格将为 0, 0。 攻击0有两个选项，0
1, 2 or 2, 1
让我们选择 1、2 并攻击单元格（如果它们是空的）。可以攻击6个细胞
attack(..) 将骑士放置在给定的单元格中。攻击者和目标以相同的方式相关。所以这里使用了计算攻击能力时产生的数据。
bool Solution::attack( Element* nodes )
{
++knightCount;
AttackingNodes* attackList = PriorityTargets::inst->attackNodes[nodes->_X][nodes->_Y];
std::list<Element*>::iterator itr;
board[nodes->_X][nodes->_Y] = CC_KNIGHT;
for(itr = attackList->attackers.begin(); itr != attackList->attackers.end(); ++itr)
{
Element* attackNode = *itr;
if(board[attackNode->_X][attackNode->_Y] == CC_EMPTY)
{
board[attackNode->_X][attackNode->_Y] = CC_ATTACKED;
}
}
return false;
}
|一个| 0 |一个| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 |一个 | 0 | 0 | 0 | 0 |
| 0 | K | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 |一个 | 0 | 0 | 0 | 0 |
|一个| 0 |一个 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
然后算法搜索下一个空单元格（没有 Knight，没有 Attacked），攻击性最低，用可用选项攻击它。
AttackingNodes* PriorityTargets::GetNextNode( Solution* solution )
{
std::multimap<size_t, AttackingNodes*>::iterator priorityItr;
for(priorityItr = mapAttackPriority.begin(); priorityItr != mapAttackPriority.end(); ++priorityItr)
{
AttackingNodes* attackNodes = priorityItr->second;
if(solution->board[attackNodes->target->_X][attackNodes->target->_Y] == CC_EMPTY)
{
return attackNodes;
}
}
return NULL;
}
这将是第二个选项的另一个角节点，它会一直持续到骑士数大于 12 或没有空单元格。
骑士数大于 12，这是一次失败的尝试并被跟踪。 如果没有空单元格就是一个解决方案。
Solution::Solution()
{
Clear();
}
void Solution::Print()
{
std::cout << std::endl ;
for(int x = 0; x < BOARD_SIZE; ++x)
{
for(int y = 0; y < BOARD_SIZE; ++y)
{
std::cout << (int)board[x][y] << " ";
}
std::cout << std::endl ;
}
std::cout << std::endl ;
}
bool Solution::Solve( Solution* solution )
{
AttackingNodes* nextAttackingNode = PriorityTargets::inst->GetNextNode(solution);
if(nextAttackingNode != NULL)
{
Solution* newSolutioon = new Solution();
std::list<Element*>::iterator itr;
for(itr = nextAttackingNode->attackers.begin(); itr != nextAttackingNode->attackers.end(); ++itr)
{
Element* attack = *itr;
*newSolutioon = *solution;
newSolutioon->attack(attack);
if(newSolutioon->knightCount < 13)
{
Solve(newSolutioon);
}
else
{
//Fail
newSolutioon->Clear();
}
}
delete newSolutioon;
}
else
{
std::cout << "Solved" << std::endl;
solution->Print();
}
return false;
}
void Solution::Clear()
{
memset(board, 0, BOARD_SIZE*BOARD_SIZE);
knightCount = 0;
}
我在 visual studio 2008 发布模式下不到 500 毫秒就得到了答案。 我用了2个骑士，1个攻击。
在限制各种棋盘大小的骑士统治问题方面已经做了大量工作。 Here is an article that seems to summarize all the previous work and adds a few new twists. And here is an article that claims to demonstrate a linear-time algorithm for knights domination. I've even found references to a constant-time knights domination algorithm，但我没看到有人不厌其烦地写出来。先动脑再写代码