Problem
Place eight queens on an 8×8 chessboard so that no two queens attack each other
References
total number is 92
Solution - 1
// Lambda.cpp : Defines the entry point for the console application.
//
#include <iostream>
using namespace std;
void init_chess_board(bool chessboard[8][8])
{
int i, j;
for(i = 0; i < 8; i++){
for(j = 0; j < 8; j++){
chessboard[i][j] = true;
}
}
}
bool is_valid_pos(bool chessboard[8][8], int r, int c)
{
int i, j;
for(i = 0; i < 8; i++){
for(j = 0; j < 8; j++){
if(i == r && chessboard[i][j] == false){
return false;
}
if(j == c && chessboard[i][j] == false){
return false;
}
if((j - i == c - r) && chessboard[i][j] == false){
return false;
}
if((r - i == j - c) && chessboard[i][j] == false){
return false;
}
}
}
return true;
}
void mark_pos(bool chessboard[8][8], int r, int c)
{
chessboard[r][c] = false;
}
void copy_chess_board(bool dst[8][8], bool src[8][8])
{
int i, j;
for(i = 0; i < 8; i++){
for(j = 0; j < 8; j++){
dst[i][j] = src[i][j];
}
}
}
void display_chess_board(bool chessboard[8][8])
{
int i, j;
for(i = 0; i < 8; i ++){
for(j = 0; j < 8; j++){
if(chessboard[i][j]){
cout << " * ";
}
else{
cout << " Q ";
}
}
cout << endl;
}
}
void eight_queen(int &total, bool chessboard[8][8], int time)
{
int i, j;
if(time == 7){
for(j = 0; j < 8; j++){
if(is_valid_pos(chessboard, 7, j)){
cout << "No. " << total << endl;
mark_pos(chessboard, time, j);
display_chess_board(chessboard);
total ++;
}
}
return;
}
for(j = 0; j < 8; j++){
if(is_valid_pos(chessboard, time , j)){
bool tmp[8][8];
copy_chess_board(tmp, chessboard);
mark_pos(tmp, time, j);
eight_queen(total, tmp, time + 1);
}
}
}
int main(int argc, char* argv[])
{
bool chessboard[8][8];
int total = 0;
init_chess_board(chessboard);
eight_queen(total, chessboard, 0);
cout << "total number is: " << total << endl;
return 0;
}
Output
Solution - 2
// EightQueens.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
static int sTotalNumber = 0;
bool IsConflicted(vector<int> queensLoc, int nextRow, int expectedCol)
{
// Dectect column conflict
for (int j = 0; j < nextRow; ++j){
if (queensLoc[j] == expectedCol){
return true;
}
}
// Detect dialognal conflict
for (int j = 0; j < nextRow; ++j){
if (abs(j - nextRow) == abs(queensLoc[j] - expectedCol)){
return true;
}
}
return false;
}
void LayNextQueen(vector<int> queensLoc, int row, int boardSize)
{
if (row == boardSize){
sTotalNumber++;
cout << sTotalNumber << " --- ";
copy(queensLoc.begin(), queensLoc.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
for (int i = 0; i < boardSize; ++i){
if (IsConflicted(queensLoc, row, i) == false){
queensLoc.push_back(i);
LayNextQueen(queensLoc, row + 1, boardSize);
queensLoc.pop_back();
}
}
}
void EightQueens()
{
vector<int> queensLoc;
LayNextQueen(queensLoc, 0, 8);
}
int main(int argc, char* argv[])
{
EightQueens();
return 0;
}
Output
1 --- 0 4 7 5 2 6 1 3
2 --- 0 5 7 2 6 3 1 4
3 --- 0 6 3 5 7 1 4 2
4 --- 0 6 4 7 1 3 5 2
5 --- 1 3 5 7 2 0 6 4
6 --- 1 4 6 0 2 7 5 3
7 --- 1 4 6 3 0 7 5 2
8 --- 1 5 0 6 3 7 2 4
9 --- 1 5 7 2 0 3 6 4
10 --- 1 6 2 5 7 4 0 3
11 --- 1 6 4 7 0 3 5 2
12 --- 1 7 5 0 2 4 6 3
13 --- 2 0 6 4 7 1 3 5
14 --- 2 4 1 7 0 6 3 5
15 --- 2 4 1 7 5 3 6 0
16 --- 2 4 6 0 3 1 7 5
17 --- 2 4 7 3 0 6 1 5
18 --- 2 5 1 4 7 0 6 3
19 --- 2 5 1 6 0 3 7 4
20 --- 2 5 1 6 4 0 7 3
21 --- 2 5 3 0 7 4 6 1
22 --- 2 5 3 1 7 4 6 0
23 --- 2 5 7 0 3 6 4 1
24 --- 2 5 7 0 4 6 1 3
25 --- 2 5 7 1 3 0 6 4
26 --- 2 6 1 7 4 0 3 5
27 --- 2 6 1 7 5 3 0 4
28 --- 2 7 3 6 0 5 1 4
29 --- 3 0 4 7 1 6 2 5
30 --- 3 0 4 7 5 2 6 1
31 --- 3 1 4 7 5 0 2 6
32 --- 3 1 6 2 5 7 0 4
33 --- 3 1 6 2 5 7 4 0
34 --- 3 1 6 4 0 7 5 2
35 --- 3 1 7 4 6 0 2 5
36 --- 3 1 7 5 0 2 4 6
37 --- 3 5 0 4 1 7 2 6
38 --- 3 5 7 1 6 0 2 4
39 --- 3 5 7 2 0 6 4 1
40 --- 3 6 0 7 4 1 5 2
41 --- 3 6 2 7 1 4 0 5
42 --- 3 6 4 1 5 0 2 7
43 --- 3 6 4 2 0 5 7 1
44 --- 3 7 0 2 5 1 6 4
45 --- 3 7 0 4 6 1 5 2
46 --- 3 7 4 2 0 6 1 5
47 --- 4 0 3 5 7 1 6 2
48 --- 4 0 7 3 1 6 2 5
49 --- 4 0 7 5 2 6 1 3
50 --- 4 1 3 5 7 2 0 6
51 --- 4 1 3 6 2 7 5 0
52 --- 4 1 5 0 6 3 7 2
53 --- 4 1 7 0 3 6 2 5
54 --- 4 2 0 5 7 1 3 6
55 --- 4 2 0 6 1 7 5 3
56 --- 4 2 7 3 6 0 5 1
57 --- 4 6 0 2 7 5 3 1
58 --- 4 6 0 3 1 7 5 2
59 --- 4 6 1 3 7 0 2 5
60 --- 4 6 1 5 2 0 3 7
61 --- 4 6 1 5 2 0 7 3
62 --- 4 6 3 0 2 7 5 1
63 --- 4 7 3 0 2 5 1 6
64 --- 4 7 3 0 6 1 5 2
65 --- 5 0 4 1 7 2 6 3
66 --- 5 1 6 0 2 4 7 3
67 --- 5 1 6 0 3 7 4 2
68 --- 5 2 0 6 4 7 1 3
69 --- 5 2 0 7 3 1 6 4
70 --- 5 2 0 7 4 1 3 6
71 --- 5 2 4 6 0 3 1 7
72 --- 5 2 4 7 0 3 1 6
73 --- 5 2 6 1 3 7 0 4
74 --- 5 2 6 1 7 4 0 3
75 --- 5 2 6 3 0 7 1 4
76 --- 5 3 0 4 7 1 6 2
77 --- 5 3 1 7 4 6 0 2
78 --- 5 3 6 0 2 4 1 7
79 --- 5 3 6 0 7 1 4 2
80 --- 5 7 1 3 0 6 4 2
81 --- 6 0 2 7 5 3 1 4
82 --- 6 1 3 0 7 4 2 5
83 --- 6 1 5 2 0 3 7 4
84 --- 6 2 0 5 7 4 1 3
85 --- 6 2 7 1 4 0 5 3
86 --- 6 3 1 4 7 0 2 5
87 --- 6 3 1 7 5 0 2 4
88 --- 6 4 2 0 5 7 1 3
89 --- 7 1 3 0 6 4 2 5
90 --- 7 1 4 2 0 6 3 5
91 --- 7 2 0 5 1 4 6 3
92 --- 7 3 0 2 5 1 6 4
Press any key to continue . . .