Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Eight queens problem checking
// t12e13.queens.cpp
// juanfc 2022-01-19
//
#include <iostream>
#include <array>
using namespace std;
const int N = 8;
const int NQUEENS = 8;
typedef array<array<char,N>,N> TChessboard;
void test(TChessboard m);
bool noThreaten(TChessboard m);
int main()
{
test((TChessboard) {{
{{'*', ' ', ' ', ' ', ' ', ' ', ' ', ' '}}, // 0
{{' ', ' ', ' ', ' ', ' ', ' ', '*', ' '}}, // 1
{{' ', ' ', ' ', ' ', '*', ' ', ' ', ' '}}, // 2
{{' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'}}, // 3
{{' ', '*', ' ', ' ', ' ', ' ', ' ', ' '}}, // 4
{{' ', ' ', ' ', '*', ' ', ' ', ' ', ' '}}, // 5
{{' ', ' ', ' ', ' ', ' ', '*', ' ', ' '}}, // 6
{{' ', ' ', '*', ' ', ' ', ' ', ' ', ' '}}, // 7
// 0 1 2 3 4 5 6 7
}});
test((TChessboard) {{
{{' ', ' ', '*', ' ', ' ', ' ', ' ', ' '}}, // 0
{{' ', ' ', ' ', ' ', ' ', '*', ' ', ' '}}, // 1
{{' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'}}, // 2
{{'*', ' ', ' ', ' ', ' ', ' ', ' ', ' '}}, // 3
{{' ', ' ', ' ', '*', ' ', ' ', ' ', ' '}}, // 4
{{' ', ' ', ' ', ' ', ' ', ' ', '*', ' '}}, // 5
{{' ', ' ', ' ', ' ', '*', ' ', ' ', ' '}}, // 6
{{' ', '*', ' ', ' ', ' ', ' ', ' ', ' '}}, // 7
// 0 1 2 3 4 5 6 7
}});
return 0;
}
bool noThreaten(TChessboard m);
void test(TChessboard m)
{
cout << " ";
for (int i = 0; i < N; ++i)
cout << i;
cout << endl;
for (int i = 0; i < N; ++i) {
cout << i;
for (int j = 0; j < N; ++j)
cout << m[i][j];
cout << endl;
}
if (noThreaten(m)) cout << "\t\tCORRECT" << endl;
else cout << "\t\tINCORRECT" << endl;
}
bool check(TChessboard m, int row, int col);
bool noThreaten(TChessboard m)
{
int cnt = 0;
bool ok = true;
int i = 0;
while (i < N and cnt <= NQUEENS and ok) {
int j = 0;
while (j < N and cnt <= NQUEENS and ok) {
if (m[i][j] == '*') {
ok = check(m, i, j);
}
++j;
}
++i;
}
return ok;
}
bool check(TChessboard m, int row, int col)
{
bool ok = true;
// check column
int x = 0;
while (x < N and (x == row or m[x][col] != '*'))
++x;
ok = x == N;
// check row
x = 0;
while (ok and x < N and (x == col or m[row][x] != '*'))
++x;
ok = x == N;
// cout << row << ", " << col << endl;
if (ok) {
// \ diag zone right
if (row<=col) {
x = 0;
while (col-row+x < N and (x == row or m[x][col-row+x] != '*')) {
// cout << x << ", " << col-row+x << endl;
++x;
}
ok = col-row+x == N;
} else{
// \ diag zone left
x = 0;
while (row-col+x < N and (x == col or m[row-col+x][x] != '*')) {
// cout << row-col+x << ", " << x << endl;
++x;
}
ok = row-col+x == N;
}
}
if (ok) {
// / upper
if (row+col<N) {
x = 0;
while (col+row-x >= 0 and (x == col or m[col+row-x][x] != '*')) {
// cout << col+row-x << ", " << x << endl;
++x;
}
ok = col+row-x < 0;
} else{
// / lower
x = 0;
while (col-(N-1-row)+x < N and (N-1-x == row or m[N-1-x][col-(N-1-row)+x] != '*')) {
// cout << N-1-x << ", " << col-(N-1-row)+x << endl;
++x;
}
ok = col-(N-1-row)+x == N;
}
}
return ok;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment