12 dominating knights puzzle (backtracking)

Question

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

Answer 1

Your attempt is very inefficient, so it might be just because of the inefficiency that you can't find a solution.

First, it's pointless to try to place 12 knights. Place 6 knights onto white fields. Find all solutions. Then any solution with 6 knights on white fields can be mirrored and gives 6 knights on black fields, and you combine that.

Second, you are trying to place the knights in any order. But the order is arbitrary. So place them in some sorted order, like a1, c1, e1, g1, b2, d2, f2, h2, a3... etc. That reduces the number of choices by a factor 6! or 720 (in your original case 12! = billions).

To be efficient: Number the white fields from 0 to 31. Number the black fields from 0 to 31. For each black field, find the indices of the white fields that can be reached by a knight on that field, and create a 32 bit bitmap representing those fields.

Then:

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!!!

That's less than a million checks, so it would take a few milliseconds.

PS. Your combination of placeKnight / removeKnight doesn't work. For example, c3 is covered both by a knight on b1 or on a2. If you place a knight on a2, then on b1, then remove the knight on b1, you set c3 to "not covered".

PS. If you had a bigger chessboard, you would take shortcuts to reduce the number of possibilities. For example, field a1 must be covered by a knight on the first row, second row, or b3 on the third row. So if you try to put a knight on a field c3 or later, and a1 isn't covered, there is no need to try putting a knight on that field or a later field at all.

Answer 2

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