The eight queens problem is a combinatorial chess puzzle (published in 1848), whose goal is to place eight queen pieces on a chessboard in such a way that no queen can attack another. In the generalized version – n queens problem (published in 1850) – is the goal to place queens on an
chessboard so that no queen can attack another.
Finding a solution
The n queens problem is typically solved by a backtracking algorithm. The backtracking algorithm is an exhaustive depth first search technique, in which every decision is remembered. If a partial solution is determined to be invalid, the previous decision is reevaluated and changed. This way all possible solutions can be found or it might be asserted that no solution exists.
Number of solutions
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Count | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 | 73712 | 365596 |
Code
/**
* N queens problem
* @author Pavel Micka
*/
public class QueensProblem {
private int solutionsCount = 0;
/**
* Solves and prints out solution of the n queens problem
* @param size size of the problem
*/
public void solve(int size) {
boolean[][] array = new boolean[size][size];
solveQueensProblem(array, 0, 0, true, 0);
solveQueensProblem(array, 0, 0, false, 0);
}
/**
* Solves the n queens problem
* @param array chessboard
* @param x x coordinate where to place the current queen
* @param y y coordinate where to place the current queen
* @param set true if the queen should be placed, false otherwise
* @param queensCount how many queens are already placed
*/
private void solveQueensProblem(boolean[][] array, int x, int y, boolean set, int queensCount) {
array[y][x] = set;
if (set && !checkConsistency(array, x, y)) {
return;
}
if (set) {
queensCount++;
}
if (queensCount == array.length) {
solutionsCount++;
printArray(array);
return; //solution found
}
x = x + 1; //increment x
int overflow = x == array[y].length ? 1 : 0;
if (overflow == 1) {//if x overflowed
x = 0; //set to 0
y += 1; //increment y
}
if (y >= array.length) {
return; //end of the problem, all decisions have been made
}
//lets make both decisions
solveQueensProblem(array, x, y, true, queensCount);
solveQueensProblem(array, x, y, false, queensCount);
}
/**
* Check that no queen can attack another
* @param array chessboard
* @param x x coordinate where the new queen will be placed
* @param y y coordinate where the new queen will be placed
* @return true if the the model after queen placement is consistent, false otherwise
*/
private boolean checkConsistency(boolean[][] array, int x, int y) {
//horizontally
for (int i = 0; i < array[y].length; i++) {
if (i != x && array[y][i] == true) {
return false;
}
}
//vertically
for (int i = 0; i < array.length; i++) {
if (i != y && array[i][x] == true) {
return false;
}
}
//diagonally left bottom to right top
int i = 1;
while (x + i < array[y].length && y - i >= 0) {
if (array[y - i][x + i]) {
return false;
}
i++;
}
i = 1;
while (x - i >= 0 && y + i < array.length) {
if (array[y + i][x - i]) {
return false;
}
i++;
}
//diagonally left top, right bottom
i = 1;
while (x - i >= 0 && y - i >= 0) {
if (array[y - i][x - i]) {
return false;
}
i++;
}
i = 1;
while (x + i < array[y].length && y + i < array.length) {
if (array[y + i][x + i]) {
return false;
}
i++;
}
return true;
}
/**
* Print out the chessboard
* @param array chessboard
*/
private void printArray(boolean[][] array) {
System.out.println("Reseni #" + solutionsCount);
for (int i = 0; i < array.length; i++) {
System.out.print("\\n|");
for (int j = 0; j < array[i].length; j++) {
if (array[i][j]) {
System.out.print("Q|");
} else {
System.out.print(" |");
}
}
}
System.out.println("\\n---------------------");
}
/**
* @return the solutionsCount
*/
public int getSolutionsCount() {
return solutionsCount;
}
}
/**
* N queens problem
* @author Michal Orsel
* @author Pavel Micka
* Rewriten to C by Michal Orsel
*
* Under BSD license (http://opensource.org/licenses/BSD-3-Clause)
*/
#include <stdio.h>
/**
* Solves n queens problem
* @param a checkerboard
* @param x coordinate x, where the next (this) queen should be placed
* @param y coordinate y, where the next (this) queen should be placed
* @param set if the queen should be placed 1 - yes, 0 - no
* @param queensCount how many queens are already placed
* @param solutionsCount number of solutions
* @return
*/
int solveQueensProblem(char * a, int x, int y, int set, int queensCount, int size, int * solutionsCount)
{
a[y*size+x] = set;
if(set && !checkConsistency(a, x, y, size))
return 0;
if(set)
queensCount++;
if(queensCount == size)
{
(*solutionsCount)++;
return 1; //solution found
}
x++;
if(x >= size) //if x overflowed
{
x = 0; //set it to 0
y++; //increment y
}
if(y >= size)
return 1; //end of the tast, the checkerboard was fully traversed
//make both decisions
solveQueensProblem(a, x, y, 1, queensCount, size, solutionsCount);
solveQueensProblem(a, x, y, 0, queensCount, size, solutionsCount);
return 1;
}
/**
* Check that no queen can attack another
* @param a checkerboard
* @param x kam bude nova dama vlozena na ose x
* @param y kam bude nova dama vlozena na ose y
* @return
*/
int checkConsistency(char * a, int x, int y, int size)
{
//horizontally x
int i;
for(i = 0; i < size; i++) // mozno otocit na for(i = size-1; i >= 0; i--)
{
if(i != x && a[y*size+i] == 1)
return 0;
}
//vertically
for(i = 0; i < size; i++)
{
if(i != y && a[i*size+x] == 1)
return 0;
}
//diagonal left-bottom, right-upper
i = 1;
//vpravo nahoru
while(x + i < size && y - i >= 0)
{
if(a[(y - i)*size+(x + i)])
return 0;
i++;
}
i = 1;
//left and down
while(x - i >= 0 && y + i < size)
{
if(a[(y + i)*size+(x - i)])
return 0;
i++;
}
//diagonal left-upper, right-bottom
i = 1;
//vlevo nahoru
while(x - i >= 0 && y - i >= 0)
{
if(a[(y - i)*size+(x - i)])
return 0;
i++;
}
i = 1;
//right and down
while(x + i < size && y + i < size)
{
if(a[(y + i)*size+(x + i)])
return 0;
i++;
}
return 1;
}
int main()
{
#define SIZE 8
int solutionsCount = 0;
char a[SIZE*SIZE] = {0};
solveQueensProblem(a, 0, 0, 1, 0, SIZE, &solutionsCount);
solveQueensProblem(a, 0, 0, 0, 0, SIZE, &solutionsCount);
printf("There are %d variants of placement %d queens on the checkerboard %dx%d in such a way that no queen endangers another.\\n", solutionsCount, SIZE, SIZE, SIZE);
system("pause");
return 0;
}
/**
* N queens problem
* @author Pavel Micka
*/
class QueensProblem {
private:
int solutionsCount;
/**
* Solves the n queens problem
* @param array chessboard
* @param x x coordinate where to place the current queen
* @param y y coordinate where to place the current queen
* @param set true if the queen should be placed, false otherwise
* @param queensCount how many queens are already placed
*/
void solveQueensProblem(bool ** a, int x, int y, bool set, int queensCount, int size) {
a[y][x] = set;
if (set && !checkConsistency(a, x, y, size)) {
return;
}
if (set) {
queensCount++;
}
if (queensCount == size) {
solutionsCount++;
printArray(a, size);
return; //reseni nalezeno
}
x = x + 1; //increment x
int overflow = x == size ? 1 : 0;
if (overflow == 1) {//if x overflowed
x = 0; //set x to 0
y += 1; //increment y
}
if (y >= size) {
return; //end of the problem, all decisions have been made
}
//lets make both decisions
solveQueensProblem(a, x, y, true, queensCount, size);
solveQueensProblem(a, x, y, false, queensCount, size);
}
/**
* Check that no queen can attack another
* @param array chessboard
* @param x x coordinate where the new queen will be placed
* @param y y coordinate where the new queen will be placed
* @param size size of the chessboard
* @return true if the the model after queen placement is consistent, false otherwise
*/
bool checkConsistency(bool ** a, int x, int y, int size) {
//horizontally
for (int i = 0; i < size; i++) {
if (i != x && a[y][i] == true) {
return false;
}
}
//vertically
for (int i = 0; i < size; i++) {
if (i != y && a[i][x] == true) {
return false;
}
}
//diagonally left bottom to right top
int j = 1;
while (x + j < size && y - j >= 0) {
if (a[y - j][x + j]) {
return false;
}
j++;
}
j = 1;
while (x - j >= 0 && y + j < size) {
if (a[y + j][x - j]) {
return false;
}
j++;
}
//diagonally left top, right bottom
j = 1;
while (x - j >= 0 && y - j >= 0) {
if (a[y - j][x - j]) {
return false;
}
j++;
}
j = 1;
while (x + j < size && y + j < size) {
if (a[y + j][x + j]) {
return false;
}
j++;
}
return true;
}
/**
* Print out the chessboard
* @param array chessboard
* @param size size of the chessboard
*/
void printArray(bool ** a, int size) {
cout << "Reseni #" << this->solutionsCount;
for (int i = 0; i < size; i++) {
cout << "\\n" << "|";
for (int j = 0; j < size; j++) {
if (a[i][j]) {
cout << "Q|";
} else {
cout << " |";
}
}
}
cout << "\\n" << "---------------------\\n";
}
public:
QueensProblem(){
this->solutionsCount = 0;
}
/**
* Solves and prints out solution of the n queens problem
* @param size size of the problem
*/
void solve(int size) {
bool ** a = new bool*[size];
for(int j = 0; j < size; j++){
a[j] = new bool[size];
for(int k = 0; k < size; k++){
a[j][k] = false;
}
}
solveQueensProblem(a, 0, 0, true, 0, size);
solveQueensProblem(a, 0, 0, false, 0, size);
for(int i = 0; i < size; i ++) delete[] a[i];
delete[] a;
}
/**
* @return the solutionsCount
*/
int getSolutionsCount() {
return solutionsCount;
}
};
; Autor: Michal Orsel
; Under BSD license (http://opensource.org/licenses/BSD-3-Clause)
bits 32
section .data
section .text
global solveQueensProblem
global checkConsistency
; int solveQueensProblem(char * a, int x, int y, int set, int queensCount, int size, int * solutionsCount)
solveQueensProblem:
enter 0, 0
push esi
push edi
push ebx
push ecx
; parameters
;[ ebp + 8 ] ; char * a
;[ ebp + 12 ] ; int x,
;[ ebp + 16 ] ; int y,
;[ ebp + 20 ] ; int set,
;[ ebp + 24 ] ; int queensCount,
;[ ebp + 28 ] ; int size,
;[ ebp + 32 ] ; int * solutionsCount
; a[y * size + x] = set
mov edx, 0
mov eax, [ ebp + 16 ] ; y
mul dword [ ebp + 28 ] ; y * size
add eax, [ ebp + 12 ] ; (y * size) + x
mov esi, [ ebp + 8 ] ; a
mov edx, [ ebp + 20 ] ; set
mov byte [ esi + eax ], dl ; a[y * size + x] = set
; if(set && !checkConsistency(a, x, y, size)) return 0
cmp dword [ ebp + 20 ], 0
je .n_if_1
; call checkConsistency(a, x, y, size)
push dword [ ebp + 28 ] ; size
push dword [ ebp + 16 ] ; y
push dword [ ebp + 12 ] ; x
push dword [ ebp + 8 ] ; a
call checkConsistency
add esp, 16
cmp eax, 0
jne .n_if_1
; return 0
mov eax, 0
jmp .return
.n_if_1:
; if(set) queensCount++;
cmp dword [ ebp + 20 ], 0
je .n_if_2
inc dword [ ebp + 24 ]
.n_if_2:
; if(queensCount == size)
mov esi, [ ebp + 28 ] ; size
cmp dword [ ebp + 24 ], esi
jne .n_if_3
mov esi, [ ebp + 32 ] ; *solutionsCount
inc dword [ esi ] ; (*solutionsCount)++;
; return 1
mov eax, 1
jmp .return
.n_if_3:
inc dword [ ebp + 12 ] ; x++
; if(x >= size)
mov esi, [ ebp + 28 ] ; size
cmp dword [ ebp + 12 ], esi
jl .n_if_4
mov dword [ ebp + 12 ], 0 ; x = 0
inc dword [ ebp + 16 ] ; y++
.n_if_4:
; if(y >= size)
mov esi, [ ebp + 28 ] ; size
cmp dword [ ebp + 16 ], esi
jl .n_if_5
; return 1
mov eax, 1
jmp .return
.n_if_5:
; call solveQueensProblem(a, x, y, 1, queensCount, size, solutionsCount)
push dword [ ebp + 32 ] ; solutionsCount
push dword [ ebp + 28 ] ; size
push dword [ ebp + 24 ] ; queensCount
push dword 1 ; 1
push dword [ ebp + 16 ] ; y
push dword [ ebp + 12 ] ; x
push dword [ ebp + 8 ] ; a
call solveQueensProblem
add esp, 28
; call solveQueensProblem(a, x, y, 0, queensCount, size, solutionsCount)
push dword [ ebp + 32 ] ; solutionsCount
push dword [ ebp + 28 ] ; size
push dword [ ebp + 24 ] ; queensCount
push dword 0 ; 0
push dword [ ebp + 16 ] ; y
push dword [ ebp + 12 ] ; x
push dword [ ebp + 8 ] ; a
call solveQueensProblem
add esp, 28
; return 1
mov eax, 1
.return:
pop ecx
pop ebx
pop edi
pop esi
leave
ret
; ------------------------------------------------------------------------------
; int checkConsistency(char * a, int x, int y, int size)
checkConsistency:
enter 0, 0
push ecx
push esi
push edx
; parametry
;[ ebp + 8 ] ; char * a
;[ ebp + 12 ] ; int x,
;[ ebp + 16 ] ; int y,
;[ ebp + 20 ] ; int size
; for(i = 0; i < size; i++)
mov ecx, 0
.for_1:
cmp ecx, dword [ ebp + 20 ]
jge .n_for_1
; if(i != x && a[y * size + i] == 1) return 0
cmp ecx, dword [ ebp + 12 ]
je .n_if_1
mov edx, 0
mov eax, [ ebp + 16 ] ; y
mul dword [ ebp + 20 ] ; y * size
add eax, ecx ; (y * size) + i
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 1
jne .n_if_1
mov eax, 0 ; return 0
jmp .return
.n_if_1:
inc ecx ; i++
jmp .for_1
.n_for_1:
; for(i = 0; i < size; i++)
mov ecx, 0
.for_2:
cmp ecx, dword [ ebp + 20 ]
jge .n_for_2
; if(i != y && a[i * size + x] == 1) return 0
cmp ecx, dword [ ebp + 16 ]
je .n_if_2
mov edx, 0
mov eax, ecx ; i
mul dword [ ebp + 20 ] ; i * size
add eax, [ ebp + 12 ] ; (i * size) + x
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 1
jne .n_if_2
; return 0
mov eax, 0
jmp .return
.n_if_2:
inc ecx ; i++
jmp .for_2
.n_for_2:
mov ecx, 1 ; i = 1
; while(x + i < size && y - i >= 0)
.while_1:
mov eax, dword [ ebp + 12 ] ; x
add eax, ecx ; x + i
cmp eax, [ ebp + 20 ]
jge .n_while_1
mov eax, [ ebp + 16 ] ; y
sub eax, ecx ; y - i
cmp eax, 0
jl .n_while_1
; if(a[(y - i) * size + (x + i)])
mov eax, dword [ ebp + 16 ] ; y
sub eax, ecx ; y - i
mul dword [ ebp + 20 ] ; (y - i) * size
add eax, dword [ ebp + 12 ] ; (y - i) * size + x
add eax, ecx ; (y - i) * size + x + i
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 0
je .n_if_3
; return 0
mov eax, 0
jmp .return
.n_if_3:
inc ecx ; i++
jmp .while_1
.n_while_1:
mov ecx, 1 ; i = 1
; while(x - i >= 0 && y + i < size)
.while_2:
mov eax, dword [ ebp + 12 ] ; x
sub eax, ecx ; x - i
cmp eax, 0
jl .n_while_2
mov eax, dword [ ebp + 16 ] ; y
add eax, ecx ; y + i
cmp eax, dword [ ebp + 20 ]
jge .n_while_2
; if(a[(y + i) * size + (x - i)])
mov eax, dword [ ebp + 16 ] ; y
add eax, ecx ; y + i
mul dword [ ebp + 20 ] ; (y + i) * size
add eax, dword [ ebp + 12 ] ; (y + i) * size + x
sub eax, ecx ; (y + i) * size + x - i
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 0
je .n_if_4
; return 0
mov eax, 0
jmp .return
.n_if_4:
inc ecx ; i++
jmp .while_2
.n_while_2:
mov ecx, 1 ; i = 1
; while(x - i >= 0 && y - i >= 0)
.while_3:
mov eax, dword [ ebp + 12 ] ; x
sub eax, ecx ; x - i
cmp eax, 0
jl .n_while_3
mov eax, dword [ ebp + 16 ] ; y
sub eax, ecx ; y - i
cmp eax, 0
jl .n_while_3
; if(a[(y - i) * size + (x - i)])
mov eax, dword [ ebp + 16 ] ; y
sub eax, ecx ; y - i
mul dword [ ebp + 20 ] ; (y - i) * size
add eax, dword [ ebp + 12 ] ; (y - i) * size + x
sub eax, ecx ; (y - i) * size + x - i
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 0
je .n_if_5
; return 0
mov eax, 0
jmp .return
.n_if_5:
inc ecx ; i++
jmp .while_3
.n_while_3:
mov ecx, 1 ; i = 1
; while(x + i < size && y + i < size)
.while_4:
mov eax, dword [ ebp + 12 ] ; x
add eax, ecx; ; x + i
cmp eax, [ ebp + 20 ]
jge .n_while_4
mov eax, dword [ ebp + 16 ] ; y
add eax, ecx ; y + i
cmp eax, [ ebp + 20 ]
jge .n_while_4
; if(a[(y + i) * size + (x + i)])
mov eax, dword [ ebp + 16 ] ; y
add eax, ecx ; y + i
mul dword [ ebp + 20 ] ; (y + i) * size
add eax, dword [ ebp + 12 ] ; (y + i) * size + x
add eax, ecx ; (y + i) * size + x + i
mov esi, [ ebp + 8 ] ; a
cmp byte [esi + eax ], byte 0
je .n_if_6
; return 0
mov eax, 0
jmp .return
.n_if_6:
inc ecx ; i++
jmp .while_4
.n_while_4:
; return 1
mov eax, 1
.return:
pop edx
pop esi
pop ecx
leave
ret