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
placeKnightandremoveKnight(like, j+2 < N instead of j+2 <= N) - Added
return false;inbacktracking
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; } 5 Answers
Answers 1
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 Answers 2
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.
Answers 3
Here is a fairly efficient approach; your board is an array of [8][8] or a single array of [64]. You have 12 pieces to place. Before we begin to write any code to implement a program to solve this problem, let's first assess the situation and design an algorithm.
There are 2 things we can do first, we can omit or eliminate cells that we already know are places that a knight can not be to satisfy the solution/s to this problem. These are the outer cells or boarder of the board, the four diagonally adjacent inner corners, and the 4 cells or tiles that make up the dead center of the board. If any one knight is placed on any one of these squares then the solution will not work. We can also look at the lowest common denominator which is 4 and with this we can divide the board into 4 quadrants and work with only 3 pieces in that quadrant.
This does two things; one it makes the algorithm easier to define and more efficient, and it also satisfies another condition. The other conditions is this, we must have 3 knights in each quadrant for the solution to be valid. If there are 4 or more in any one quadrant and there are less than 3 in anyone quadrant, the solution again will fail.
If we look at each Quadrant we can see this:
- Top Left Quadrant - Bottom Right Cell is one of the center cells.
- Top Right Quadrant - Bottom Left Cell is one of the center cells.
- Bottom Left Quadrant - Top Right Cell is one of the center cells.
- Bottom Right Quadrant - Top Left Cell is one of the center cells.
What makes this vital? We know that when placing a knight on the board for any open cell to be set to attack that these 4 squares at the very center of the board that joins these 4 quadrants can not have a Knight in their locations and that at least one of the outward adjacent cells either in the horizontal or vertical direction of it must have a Knight. Knowing this we can work on 1 Quadrant to place 3 Knights with the immediate exclusion of the cell that we just marked and the other cell that is adjacent to the same center cell.
If you solve one of these quadrants then the other three are just translations of them. So with this approach it would only take so many computations to solve a 4x4 grid with its inner corner listed as a starting point and either its horizontal or vertical neighbor will have a knight placed, and which ever one has a knight placed the other adjacent will be left empty. Here is a diagram to visually see this elimination process before hand so that you know how to properly construct or implement your checking, searching and placement algorithms.
So once being able to see this and know what is happening with the problem. These are the steps to take in your algorithm.
- Divide - 4 Quadrants - 3 Knights per quadrant
- Eliminate or skip over invalid cells (Border, inner corners and center cells)
- Place adjacent from center cell either at the vertical or horizontal position.
- There was 7 possible cells to choose for placement, but since one is selected and the other adjacent won't have a placement we now have 5 cells left to place 2 more knights.
- Solve the rest of board for this quadrant.
- Perform Symmetry On The Above solution. If this is quadrant 1 then we don't need to solve quadrant 4, we can take all of the solutions and perform a +diagonal symmetry. If this is quadrant 2 then we don't need to solve for quadrant 3, we can perform the -diagonal symmetry.
- Now stitch all 4 quadrants back together for all of the solutions and send each solution to your checker to verify if it satisfy the attackable condition. This should be a linear search through an array of [64] with a few comparisons, fairly quick.
- Remove any solution that doesn't fit the requirements.
- Print the results.
Edit
Here is a sample program demonstrating how to set up a predefined board that is prepared before you begin to start solving the problem and to verify if the solutions are correct.
#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('\0') << "Full Board:\n"; std::cout << std::setw(20) << std::setfill('\0') << "-----------\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 If you run this program through the console it will basically print out the image diagram that I had previously displayed. As you can see the structure here is already created. In the code I marked the outer board with a value of 1, the 4 inner cells with 2 and empty cells with 0. From This point now on it is a matter of taking your first quad and start by choosing one of two points that are adjacent to the center which is the cell that has a value of 2. This grid location in our [8][8] is [3][3] so you can use either location 2[3] or location 3 to start with and if you set a Knight there a value of 3, then the other will remain a 0 for this possible solution. As you can see there are only 7 empty cells and after making your first choice there are only 5 cells left to chose to place your 2nd Knight, then there are 4 locations left to place your third and final knight.
Once this step is done, you can do the reflection of the +symmetry to have to same solution pattern for Quad 4. Once you generate all these solutions for Quad 1 Quad 4 is also completed. Then you have to do the same for Quad 2 & 3.
So if we do the math where 1 Knight is placed leaving 2 knights to place and 5 locations That means there are 10 possible solutions to the first knights placement. If we take into the account that the first nice was placed in the other location then that gives us a total of 20 possible solutions for 1 quadrant. We know that there are 4 quadrants so when you have your container that holds all the quads there is a total of 20^4 different possible solutions to choose from. Which is 160,000 total permutations that count for all the different possible placement.
I had actually mentioned that the solutions of Quad1 are the reflection of Qaud4 and that the solutions of Qaud2 are the reflection of Quad3. This is true when testing all of the solutions because of the square being marked as black or white. However when it comes to placing the knights to find possible solutions, none of that is relevant so instead of doing symmetry at this stage, we can just find all permutations for 1 quadrant and just rotate them from its marked center cell to be able to map those solutions to the other 3 quadrants. So once we find the 20 possible layouts for Quadrant 1, it is just a matter of performing 3 rotations on all 20 layouts to give us our 80 different layouts.
Then it is a matter of mixing and matching each of these layouts and testing it against our rule board.
Now this doesn't solve the problem; but this is an efficient way to break down this problem to minimize the amount of permutations of setting the characters on the board. And you can use this approach to design your algorithm to test all the possible answers to find all the correct solutions. Now these structures that I have shown is a good start, but you can also add to the cell structure. You can add an identifier for what color the square is, and another identifier that if it it's position is under attack. I used unsigned char's because the memory foot print is much smaller when working with a byte as opposed to an int, or even a short, and since the range of values for what is needed only goes from 0-7 I also decided to use a bit field within my Cell structure. So stead of 1 cell being 6 bytes a single cell is now only 2 bytes with a couple of bits left over. You need to take caution when using bit fields due to endianess, however, since all values are of unsigned char, this shouldn't be an issue. This helps to conserve and save on memory space when building the arrays of these cells in the quad results when we begin to do all the permutations of the possible solutions to find a working solution. Also by setting the cells values with numbers as opposed to an actual letter allows the math calculations to be much easier.
One thing that I did not mention is this: I'm not 100% sure about this, but from looking at the board long enough because I am a Chess Player, When you go to do the process of generating all the possible solutions, you can eliminate a majority of them before you even send them to the function to verify if they satisfy the final condition, and that is, I think that the 3 Knights in one quadrant within their arrangement would also have to be in the same shape in which they attack. Another words they will form an L shape on the board. Which means that if one of these three knights does not have another knight that is adjacent both in the horizontal and vertical position, the we could conclude that this layout is not going to be a valid layout. You could incorporate this step when you are doing the placement of your knights with in a single quadrant and then this way when you do the rotations for the other 3 quadrants you will have a fraction of the total amount of permutations to solve for.
And because of applying that adjacent rule to a center cell and the additional condition that I believe that the three knights that are placed have to make the shape of how it attacks, here is an image showing all the valid locations a knight can be in.
Due to the adjacent to the center rule of placement where if you choose the cell vertical then the center's horizontal cell will be emptied, then that leaves me to believe that are at least 8 possible solutions, which only maybe 2 or 4 of them are valid. So we even narrowed down our search and permutations even more. One thing we can also conclude to narrowing down our search because of the previous rule is we can apply the "Bingo" Rule here as well. Just like in Bingo the center cell is "Free", well for us here with in each quadrant there is no center cell, however from the patter of the cross from all the possible placements we now know that the center of this cross will always have a knight. Using the coordinates that I used and going by row col on the full board, these would be [2,2], [2,5], [5,2] & [5,5]. So during the placement phase these can automatically be added first, then you have the choice of the adjacent to center, then finally you have two choices left with your last piece that will not be the other cell that is also adjacent to your center cell of that Quadrant.
And with this additional case we have reduced our total permutations from 160,000 down to 4 per quadrant for 4^4 total permutations across the entire board. So if you have a pre-populated look up table of all these possible solutions then the function to check for validity will only have to be called 256 times as opposed to 160,000 or billions if you run it for all board placements. Pre-elimination is one of the steps that many people do not take into account before solving a complex problem. What is so nice about this, is that if there are 256 total possible permutations that can generate a valid answer to be tested if it passes the requirements is that each of these can be index from 0-255. The indexing for all these solutions using an unsigned char in hex values first into 1 byte of memory.
Now as for your function to check these 256 permutations of possible solutions this can be done in a simple for & while loop in a linear process just checking each cell to see if it is attacked by doing a basic collision detection process and if anyone one of these fails, we can break out of the iteration of that while loop and discard this solution, then go to the next iteration of our for loop and continue that process. If a container of a solution does satisfy it then you want to mark the occurrence of that solution and save it into another container that holds all valid solutions for each iteration of the loops. This can also eliminate the need or use for recursion.
I know that this is quite long, but it takes that much to explain it in detail and it took me several few hours to examine the problem, draw up the graphics, write the small program and to explain what I did and why I did it, so please feel free to leave a comment and let me know what you think of this approach.
Answers 4
First I define my basic concept attack-ability. Attack-ability is how many knights can attack given cell.
Ex: Corner cells can be attacked by only two knights so attack-ability is two. Attack-ability of middle cell is 8.
Attack-ability of cells
| 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 |
Calculating attackability
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); } } size of the attackers in attacking nodes is equal to attackability.
Then multimap is created attackability against attackingNodes
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)); } } If attackability is low then there is lesser options for attacking given cell.
So first node from multimap is chosen which has lesser attacking options.
First cell will be 0, 0. There is two options to attack 0, 0
1, 2 or 2, 1 Lets choose 1, 2 and attack cells if they are empty. It can attack 6 cells.
attack(..) is placing knight in given cell. Atackers and targets are same way related. So data generated while calculating attack-ability is used here.
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; } | A | 0 | A | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | A | 0 | 0 | 0 | 0 |
| 0 | K | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | A | 0 | 0 | 0 | 0 |
| A | 0 | A | 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 |
Then algorithm search for next empty cell (no Knight, no Attacked) with lowest attackability attack it with available options.
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; } It will be an another corner node for second options and it will go on until knight count is larger than 12 or no empty cells.
knight count is larger than 12 it is a fail attempt and backed tracked. If there is no empty cell then it is a solution.
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; } And I got the answer in lesser than 500 ms in visual studio 2008 release mode. I have used 2 for Knight and 1 for attacked.
Answers 5
A lot of work has been done on bounding the knights domination problem for various board sizes. Here is an article that seems to summarize all the previous work and adds a few new twists.
0 comments:
Post a Comment