那些遇到过的问题

12个主宰骑士拼图(回溯)

Ren*_*ack 18 c++ recursion chess backtracking

我一直在寻找几个小时,但还没有为这种拼图找到一个完全可行的解决方案.所以我跟主教跟着类似的问题.

我需要做的是以这样的方式在棋盘上放置12个骑士,使得棋盘的所有自由方格都被至少一件攻击.

最终结果应如下所示:

在此输入图像描述

问题是 我的程序只尝试与最后两个部分的不同组合,然后以某种方式崩溃. EDITED

到目前为止我做了什么:

#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;
}
Run Code Online (Sandbox Code Playgroud)

编辑:

  • 固定数组边界placeKnight和removeKnight(比如,j + 2 <N而不是j + 2 <= N)
  • 新增return false;的backtracking

问题: 现在它永远循环.尝试了大量的组合,但从未找到我需要的组合(暴力？)

#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;
}
Run Code Online (Sandbox Code Playgroud)

gna*_*729 15

您的尝试效率非常低,因此可能只是因为效率低下而无法找到解决方案.

首先,尝试放置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!!!
Run Code Online (Sandbox Code Playgroud)

这不到一百万次检查,所以需要几毫秒.

PS.你的placeKnight/removeKnight的组合不起作用.例如,c3被b1或a2上的骑士所覆盖.如果你将骑士放在a2上,然后放在b1上,然后移除b1上的骑士,你将c3设置为"未覆盖".

PS.如果你有一个更大的棋盘,你会采取捷径来减少可能性.例如,字段a1必须由第一行,第二行上的骑士或第三行上的b3覆盖.因此,如果你试图将骑士放在c3或更高的战场上,并且没有覆盖a1,则根本不需要在该战场或后期战场上设置骑士.

uSe*_*sed 3

正如 @gnasher729 所指出的，尝试放置所有 12 个骑士会非常低效，因此我们可以尝试放置 6 个骑士white blocks，但使用这种方法我们最多只能攻击30 black blocks out of 32.

所以从上面我们可以采取两种方法：

1）我们可以在剩下的2个黑色方块上固定2个骑士，然后尝试将剩下的4个骑士放在剩下的30个黑色方块上，注意现在我们只需要攻击剩下的26个白色方块。

@gnasher729说我们可以镜像解决方案，但我无法想出修复2个地方然后找到镜像的逻辑，因为只有30个街区受到攻击，如果骑士的数量是14，那么所有的32 个街区将受到攻击，找到一面镜子也许是可能的。

2）第二种方法是每当我们为攻击超过 26 的前 6 个骑士找到解决方案时，就暴力破解剩余的 6 个骑士，black blocks我实施了该解决方案，但仍然没有找到解决方案。

所以正如@nm所说，我们可以尝试从中心找到解决方案以减少搜索空间，所以我尝试通过将骑士放置在中心6 X 6广场来找到解决方案，并且进一步仅在32个黑色块中有30个出现时才寻找解决方案被攻击而不是 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;
}
Run Code Online (Sandbox Code Playgroud)

它只在大约 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
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

1432 次

最近记录：

9 年，4 月 前
相关归档
从标准输入中捕获字符,无需等待按下输入 163
使用CMake预编译的头文件 99
C++ Filehandling:ios:app和ios之间的区别:吃了吗？ 56
为什么C++ 11有`make_shared`而不是`make_unique` 50
Clang看不到基本标题 46
为什么std :: fstreams这么慢？ 38
未命名的结构可以继承吗？ 29
如何在编译时生成嵌套循环 28
C++递归模板类型推导 6
在try-catch块中递归调用重试N次 4
难疑归档
如何从JavaScript对象中删除属性？ 5813
grep一个文件,但显示几个周围的行？ 3277
从Git中的分支中删除提交 3035
Git获取远程分支 2088
如何使div 100%的浏览器窗口高度？ 2016
什么是控制倒置？ 1704
什么是 ":-!!" 用C代码？ 1627
如何从GET参数中获取值？ 1255
SOAP与REST(差异) 1206
在Python中将两个列表转换为字典 1101