12主导骑士拼图（回溯） [英] 12 dominating knights puzzle (backtracking)

查看：186
本文介绍了12主导骑士拼图（回溯）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我一直在寻找几个小时，并没有找到一个完全工作的解决方案，这种拼图还是。所以我跟着类似的问题与主教。



我需要做的是在棋盘上放置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  {
 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  {
 for（int j = 0; j  {
 chessBoard [i] [j] = num; 
} 
} 
} 
 void printChessBoard（int（& chessBoard）[N] [N]）
 {
 for（int i = 0 ; i  {
 for（int j = 0; 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& amp; 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& amp; 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- j-2] = num; 
 
 for（int k = 0; k  {
 for（int x = 0; 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& amp; 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& amp; 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- j-2] = num; 
} 
 bool allSpaceDominated（int（& chessBoard）[N] [N]）
 {
 for（int i = 0; i  {
 for（int j = 0; j  {
 if（chessBoard [i] [j] == 0）return false; 
} 
} 
 return true; 
}

编辑：




  • 修改 placeKnight 和 removeKnight ，j + 2

  • 添加 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  {
 for（int j = 0; j < N; j ++）
 {
 if（chessBoard [i] [j]！= 2）
 {
 placeKnight（chessBoard，i，j）; 
 printChessBoard（chessBoard）; //一步一步
 if（backtracking（chessBoard，knightNum + 1））return true; 
 
 removeKnight（chessBoard，i，j）; 
} 
} 
} 
 return false; // ADDED LINE 
} 
} 
 void fillChessBoard（int（& chessBoard）[N] [N]，int num）
 {
 for = 0; i  {
 for（int j = 0; j  {
 chessBoard [i] [j] 
} 
} 
} 
 void printChessBoard（int（& chessBoard）[N] [N]）
 {
 for（int i = 0 ; i  {
 for（int j = 0; 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<& chessBoard [i + 2] [j + 1]！= 2）chessBoard [i + 2 ] [j + 1] = num; 
 if（i + 2<& j-1> = 0& chessBoard [i + 2] [j-1]！= 2）chessBoard [i + 2] [j -1] = num; 
 
 if（i-2> = 0&& j + 1<& 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<& chessBoard [i + 1] [j + 2]！= 2）chessBoard [i + 1 ] [j + 2] = num; 
 if（i + 1<& j-2> = 0& chessBoard [i + 1] [j-2]！= 2）chessBoard [i + 1] [j -2] = num; 
 
 if（i-1> = 0&& j + 2<& 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- j-2] = num; 
 
 for（int k = 0; k  {
 for（int x = 0; 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<& chessBoard [i + 2] [j + 1]！= 2）chessBoard [i + 2 ] [j + 1] = num; 
 if（i + 2<& j-1> = 0& chessBoard [i + 2] [j-1]！= 2）chessBoard [i + 2] [j -1] = num; 
 
 if（i-2> = 0&& j + 1<& 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<& chessBoard [i + 1] [j + 2]！= 2）chessBoard [i + 1 ] [j + 2] = num; 
 if（i + 1<& j-2> = 0& chessBoard [i + 1] [j-2]！= 2）chessBoard [i + 1] [j -2] = num; 
 
 if（i-1> = 0&& j + 2<& 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- j-2] = num; 
} 
 bool allSpaceDominated（int（& chessBoard）[N] [N]）
 {
 for（int i = 0; i  {
 for（int j = 0; j  {
 if（chessBoard [i] [j] == 0）return false; 
} 
} 
 return true; 
}


解决方案

@ gnasher729指出试图放置所有12个骑士将是非常低效的，所以我们可以尝试放置6骑士在白色块而不是，但使用这种方法，我们只能攻击最大的 32个黑块中的32个

$



因此，从上面我们可以采取两种方法：


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


@ gnasher729说我们可以镜像解决方案，有固定2个地方，然后找到镜子的逻辑，因为只有30块被攻击，如果没有骑士14，那么所有的32块将被攻击，并找到一个镜子也许是可能的。 / p>


2）第二个是暴力强制剩下的6个骑士，每当我们找到一个解决方案的前6个骑士攻击超过26 黑块，我实现，但仍然没有找到一个解决方案。


如@ n.m。说我们可以尝试从中心找到解决方案，以减少搜索空间，所以我试图找到解决方案，骑士在 6 X 6 中心广场，进一步只寻找解决方案，当32个黑块中的30个被攻击而不是26，并且最终能够找到两个对称的问题的解决方案，可能有更多的解决方案可用的问题用更好的方法。 p>

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<& 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&& amp; mark [i + 1] [j + 2] == 0）mark [i + 1 ] [j + 2] = 1; 
 if（j + 2<& 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  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  for（int i = 0; i  for（int j = 0; j } 
 for（int i = 0; i  for（int j = 0; j } 
 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; 
 
 //不要放置当前骑士（currX，currY）
 backtrackBlack（knightNum，newX，newY）; 
 //尝试将当前骑士放在（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  for（int i = 0; i  for（int j = 0; j } 
 for（int i = 0; i  for（int j = 0; j } 
 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; 
 
 //不要放置当前骑士（currX，currY）
 backtrackWhite（knightNum，newX，newY）; 
 //尝试将当前骑士放在（currX，currY）
 if（（currX + currY）％2 == 0& currX> 0&& currX& -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<< endl; 
 return 0; 
}

它在89秒内找到2个解决方案。



输出：

  0 0 0 0 0 0 0 0 
 0 0 K 0 0 0 0 0 
 0 0 KK 0 KK 0 
 0 0 0 0 0 K 0 0 
 0 0 K 0 0 0 0 0 
 0 KK 0 KK 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 KK 0 KK 0 0 
 0 0 K 0 0 0 0 0 
 0 0 0 0 0 K 0 0 
 0 0 KK 0 KK 0 
 0 0 K 0 0 0 0 0 
 0 0 0 0 0 0 0 0 
 
所用时间：89.2418


I've been searching for hours and haven't found a fully working solution for this kind of puzzle yet. So I followed similar problem with bishops.

What I need to do is place 12 knights on the chess board in such a way, that all free squares of the board are attacked by at least one piece.

The final result should look like this:

The problem is that my program only tries different combinations with two last pieces and then somehow crashes. EDITED

What I have done so far:

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

Edit:

  • Fixed array boundaries in placeKnight and removeKnight (like, j+2 < N instead of j+2 <= N)
  • Added return false; in backtracking

Problem: Now it loops forever. Tries tons of combinations, but never finds the one I need (Brute-force?)

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

解决方案

As pointed out by @gnasher729 trying to place all the 12 knights would be very inefficient, so we can try to place 6 knights on white blocks instead, but using this approach we can only attack a maximum of 30 black blocks out of 32.

So from the above we can take 2 approaches :

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 said that we could mirror the solution, but i was not able to come up with the logic of fixing 2 places and then finding the mirror, because only 30 blocks were being attacked, had the no of knights been 14, then all the 32 blocks would have been attacked, and finding a mirror maybe would have been possible.

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.

So as @n.m. said we can try to find solutions from the center to reduce the search space, so i tried to find solution by placing the knights in the 6 X 6 center square, and further only looked for solutions when 30 out of the 32 black blocks were being attacked instead of 26, and finally was able to find 2 solutions to the problem which were both symmetric, there might be more solutions available to the problem with a better approach.

Code in 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;
}

It only finds 2 solution in about 89 seconds.

Output : 

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

这篇关于12主导骑士拼图（回溯）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆