Solution #1: This is a classic problem to implement using backtracking. We will start from the first row and move down to the last row placing a queen at each row and checking that each queen satisfies the following two conditions:
- The column number must be different from the already placed queens.
- It should not share a diagonal with already placed queens.
Here is the code,
- The column number must be different from the already placed queens.
- It should not share a diagonal with already placed queens.
Here is the code,
#define BOARD_SIZE 8 int col[BOARD_SIZE]={0,}; void printQueens() { int i; for(i=0; i < BOARD_SIZE; i++) { printf("%d\n", col[i]); } printf("\n"); } int checkRow(int row) { int i; for(i=0; i < row; i++) { int diff = abs(col[i] - col[row]); if((diff == 0) || (diff == (row-i))) return 0; } return 1; } void putQueen(int row) { if(row == BOARD_SIZE) { printQueens(); return; } int i=0; for(i=0; i < BOARD_SIZE; i++) { col[row] = i; if(checkRow(row)) putQueen(row+1); } } void main() { putQueen(0); }
No comments:
Post a Comment