Eight queens problem

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 n queens on an n \\times n 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

N1 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



www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?