Problém osmi dam

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 n dam (uveřejněn 1850), jehož cílem je rozmístit n dam na šachovnici velikosti n \\times n.

Ř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

N1 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









Doporučujeme