Problém osmi dam je šachový kombinatorický problém (uveřejněn 1848), jehož cílem je umístit 8 dam na šachovnici takovým způsobem, aby se navzájem neohrožovaly. Zobecněním tohoto problému je problém dam (uveřejněn 1850), jehož cílem je rozmístit
dam na šachovnici velikosti
.
Řešení za pomoci backtrackingu
Problém osmi je klasickou algoritmickou úlohou, na níž se ukazuje technika backtrackingu. V backtrackingu se prochází stavový prostor do hloubky takovým způsobem, že si algoritmus pamatuje všechna dosud učiněná rozhodnutí a v případě, že se ukáže, že daná cesta nevede k výsledku, tak se program vrátí na místo posledního rozhodnutí a změní ho. Tímto způsobem se vyloučí značné množství potenciálních řešení, které by musel projít algoritmus řešící problém hrubou silou.
Počet řešení problému
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Počet | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 | 73712 | 365596 |
Kód
/**
* Problem n dam
* @author Pavel Micka
*/
public class QueensProblem {
private int solutionsCount = 0;
/**
* Vyresi a vypise na konzoli reseni problemu n dam
* @param size velikost problemu
*/
public void solve(int size) {
boolean[][] array = new boolean[size][size];
solveQueensProblem(array, 0, 0, true, 0);
solveQueensProblem(array, 0, 0, false, 0);
}
/**
* Resi problem n dam
* @param array pole
* @param x souradnice x, kam se ma vlozit dalsi (tato) dama
* @param y souradnice y, kam se ma vlozit dalsi (tato) dama
* @param set zda-li se ma dama vlozit @true - ano, @false - ne
* @param queensCount kolik dam je jiz v poli vlozeno
*/
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; //reseni nalezeno
}
x = x + 1;//zvysime x
int overflow = x == array[y].length ? 1 : 0;
if (overflow == 1) {//pokud x preteklo
x = 0; //snizime ho na 0
y += 1; //zvysime y
}
if (y >= array.length) {
return; //konec ulohy, prosli jsme stavovy prostor
}
//ucinime obe rozhodnuti
solveQueensProblem(array, x, y, true, queensCount);
solveQueensProblem(array, x, y, false, queensCount);
}
/**
* Provede kontrolu ohrozeni damy na diagonalach, vodorovne a svisle ose
* @param array pole dam
* @param x kam bude nova dama vlozena na ose x
* @param y kam bude nova dama vlozena na ose y
* @return
*/
private boolean checkConsistency(boolean[][] array, int x, int y) {
//vodorovne
for (int i = 0; i < array[y].length; i++) {
if (i != x && array[y][i] == true) {
return false;
}
}
//svisle
for (int i = 0; i < array.length; i++) {
if (i != y && array[i][x] == true) {
return false;
}
}
//diagonala leva dolni, prava horni
int i = 1;
//vpravo nahoru
while (x + i < array[y].length && y - i >= 0) {
if (array[y - i][x + i]) {
return false;
}
i++;
}
i = 1;
//vlevo dolu
while (x - i >= 0 && y + i < array.length) {
if (array[y + i][x - i]) {
return false;
}
i++;
}
//diagonala leva horni, prava dolni
i = 1;
//vlevo nahoru
while (x - i >= 0 && y - i >= 0) {
if (array[y - i][x - i]) {
return false;
}
i++;
}
i = 1;
//vpravo dolu
while (x + i < array[y].length && y + i < array.length) {
if (array[y + i][x + i]) {
return false;
}
i++;
}
return true;
}
/**
* Vypise pole dam
* @param array pole
*/
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;
}
}
/**
* Problem n dam
* @author Michal Orsel
* @author Pavel Micka
* Upravil a prepsal do C Michal Orsel
*
* Under BSD license (http://opensource.org/licenses/BSD-3-Clause)
*/
#include <stdio.h>
/**
* Resi problem n dam
* @param a sachovnice
* @param x souradnice x, kam se ma vlozit dalsi (tato) dama
* @param y souradnice y, kam se ma vlozit dalsi (tato) dama
* @param set zda-li se ma dama vlozit 1 - ano, 0 - ne
* @param queensCount kolik dam je jiz v poli vlozeno
* @param solutionsCount pocet reseni
* @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; //reseni nalezeno
}
x++;
if(x >= size) //pokud x preteklo
{
x = 0; //snizime ho na 0
y++; //zvysime y
}
if(y >= size)
return 1; //konec ulohy, prosli jsme sachovnici
//ucinime obe rozhodnuti
solveQueensProblem(a, x, y, 1, queensCount, size, solutionsCount);
solveQueensProblem(a, x, y, 0, queensCount, size, solutionsCount);
return 1;
}
/**
* Provede kontrolu ohrozeni damy na diagonalach, vodorovne a svisle ose
* @param a sachovnice
* @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)
{
//vodorovne 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;
}
//svisle
for(i = 0; i < size; i++)
{
if(i != y && a[i*size+x] == 1)
return 0;
}
//diagonala leva dolni, prava horni
i = 1;
//vpravo nahoru
while(x + i < size && y - i >= 0)
{
if(a[(y - i)*size+(x + i)])
return 0;
i++;
}
i = 1;
//vlevo dolu
while(x - i >= 0 && y + i < size)
{
if(a[(y + i)*size+(x - i)])
return 0;
i++;
}
//diagonala leva horni, prava dolni
i = 1;
//vlevo nahoru
while(x - i >= 0 && y - i >= 0)
{
if(a[(y - i)*size+(x - i)])
return 0;
i++;
}
i = 1;
//vpravo dolu
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("Existuje %d variant umisteni %d dam na sachovnici %dx%d takovym zpusobem, aby se navzajem neohrozovaly.\\n", solutionsCount, SIZE, SIZE, SIZE);
system("pause");
return 0;
}
/**
* Problem n dam
* @author Pavel Micka
*/
class QueensProblem {
private:
int solutionsCount;
/**
* Resi problem n dam
* @param array pole
* @param x souradnice x, kam se ma vlozit dalsi (tato) dama
* @param y souradnice y, kam se ma vlozit dalsi (tato) dama
* @param set zda-li se ma dama vlozit @true - ano, @false - ne
* @param queensCount kolik dam je jiz v poli vlozeno
*/
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;//zvysime x
int overflow = x == size ? 1 : 0;
if (overflow == 1) {//pokud x preteklo
x = 0; //snizime ho na 0
y += 1; //zvysime y
}
if (y >= size) {
return; //konec ulohy, prosli jsme stavovy prostor
}
//ucinime obe rozhodnuti
solveQueensProblem(a, x, y, true, queensCount, size);
solveQueensProblem(a, x, y, false, queensCount, size);
}
/**
* Provede kontrolu ohrozeni damy na diagonalach, vodorovne a svisle ose
* @param array pole dam
* @param x kam bude nova dama vlozena na ose x
* @param y kam bude nova dama vlozena na ose y
* @return
*/
bool checkConsistency(bool ** a, int x, int y, int size) {
//vodorovne
for (int i = 0; i < size; i++) {
if (i != x && a[y][i] == true) {
return false;
}
}
//svisle
for (int i = 0; i < size; i++) {
if (i != y && a[i][x] == true) {
return false;
}
}
//diagonala leva dolni, prava horni
int j = 1;
//vpravo nahoru
while (x + j < size && y - j >= 0) {
if (a[y - j][x + j]) {
return false;
}
j++;
}
j = 1;
//vlevo dolu
while (x - j >= 0 && y + j < size) {
if (a[y + j][x - j]) {
return false;
}
j++;
}
//diagonala leva horni, prava dolni
j = 1;
//vlevo nahoru
while (x - j >= 0 && y - j >= 0) {
if (a[y - j][x - j]) {
return false;
}
j++;
}
j = 1;
//vpravo dolu
while (x + j < size && y + j < size) {
if (a[y + j][x + j]) {
return false;
}
j++;
}
return true;
}
/**
* Vypise pole dam
* @param array pole
*/
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;
}
/**
* Vyresi a vypise na konzoli reseni problemu n dam
* @param size velikost problemu
*/
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
; parametry
;[ 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 ; priprava
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
; volani 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:
; volani 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
; volani 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 ; priprava
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 ; priprava
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