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

001./**
002. * N queens problem
003. * @author Pavel Micka
004. */
005.public class QueensProblem {
006.    private int solutionsCount = 0;
007.    /**
008.     * Solves and prints out solution of the n queens problem
009.     * @param size size of the problem
010.     */
011.    public void solve(int size) {
012.        boolean[][] array = new boolean[size][size];
013.        solveQueensProblem(array, 0, 0, true, 0);
014.        solveQueensProblem(array, 0, 0, false, 0);
015.    }
016.    /**
017.     * Solves the n queens problem
018.     * @param array chessboard
019.     * @param x x coordinate where to place the current queen
020.     * @param y y coordinate where to place the current queen
021.     * @param set true if the queen should be placed, false otherwise
022.     * @param queensCount how many queens are already placed
023.     */
024.    private void solveQueensProblem(boolean[][] array, int x, int y, boolean set, int queensCount) {
025.        array[y][x] = set;
026.        if (set && !checkConsistency(array, x, y)) {
027.            return;
028.        }
029.        if (set) {
030.            queensCount++;
031.        }
032. 
033.        if (queensCount == array.length) {
034.            solutionsCount++;
035.            printArray(array);
036.            return; //solution found
037.        }
038.        x = x + 1; //increment x
039.        int overflow = x == array[y].length ? 1 : 0;
040.        if (overflow == 1) {//if x overflowed
041.            x = 0; //set to 0
042.            y += 1; //increment y
043.        }
044. 
045.        if (y >= array.length) {
046.            return; //end of the problem, all decisions have been made
047.        }
048.        //lets make both decisions
049.        solveQueensProblem(array, x, y, true, queensCount);
050.        solveQueensProblem(array, x, y, false, queensCount);
051. 
052.    }
053.    /**
054.     * Check that no queen can attack another
055.     * @param array chessboard
056.     * @param x x coordinate where the new queen will be placed
057.     * @param y y coordinate where the new queen will be placed
058.     * @return true if the the model after queen placement is consistent, false otherwise
059.     */
060.    private boolean checkConsistency(boolean[][] array, int x, int y) {
061.        //horizontally
062.        for (int i = 0; i < array[y].length; i++) {
063.            if (i != x && array[y][i] == true) {
064.                return false;
065.            }
066.        }
067.        //vertically
068.        for (int i = 0; i < array.length; i++) {
069.            if (i != y && array[i][x] == true) {
070.                return false;
071.            }
072.        }
073.        //diagonally left bottom to right top
074.        int i = 1;
075.        while (x + i < array[y].length && y - i >= 0) {
076.            if (array[y - i][x + i]) {
077.                return false;
078.            }
079.            i++;
080.        }
081.        i = 1;
082.        while (x - i >= 0 && y + i < array.length) {
083.            if (array[y + i][x - i]) {
084.                return false;
085.            }
086.            i++;
087.        }
088.        //diagonally left top, right bottom
089.        i = 1;
090.        while (x - i >= 0 && y - i >= 0) {
091.            if (array[y - i][x - i]) {
092.                return false;
093.            }
094.            i++;
095.        }
096.        i = 1;
097.        while (x + i < array[y].length && y + i < array.length) {
098.            if (array[y + i][x + i]) {
099.                return false;
100.            }
101.            i++;
102.        }
103.        return true;
104.    }
105.    /**
106.     * Print out the chessboard
107.     * @param array chessboard
108.     */
109.    private void printArray(boolean[][] array) {
110.        System.out.println("Reseni #" + solutionsCount);
111.        for (int i = 0; i < array.length; i++) {
112.            System.out.print("\\n|");
113.            for (int j = 0; j < array[i].length; j++) {
114.                if (array[i][j]) {
115.                    System.out.print("Q|");
116.                } else {
117.                    System.out.print(" |");
118.                }
119.            }
120.        }
121.        System.out.println("\\n---------------------");
122.    }
123. 
124.    /**
125.     * @return the solutionsCount
126.     */
127.    public int getSolutionsCount() {
128.        return solutionsCount;
129.    }
130.}
001./**
002. * N queens problem
003. * @author Michal Orsel
004. * @author Pavel Micka
005. * Rewriten to C by Michal Orsel
006. *
008. */
009. 
010.#include <stdio.h>
011. 
012. 
013./**
014. * Solves n queens problem
015. * @param a checkerboard
016. * @param x coordinate x, where the next (this) queen should be placed
017. * @param y coordinate y, where the next (this) queen should be placed
018. * @param set if the queen should be placed 1 - yes, 0 - no
019. * @param queensCount how many queens are already placed
020. * @param solutionsCount number of solutions
021. * @return
022. */
023.int solveQueensProblem(char * a, int x, int y, int set, int queensCount, int size, int * solutionsCount)
024.{
025.  a[y*size+x] = set;
026.  if(set && !checkConsistency(a, x, y, size))
027.    return 0;
028.   
029.  if(set)
030.    queensCount++;
031.   
032.  if(queensCount == size)
033.  {
034.    (*solutionsCount)++;
035.    return 1; //solution found
036.  }
037.   
038.  x++;
039.  if(x >= size) //if x overflowed
040.  {
041.    x = 0; //set it to 0
042.    y++; //increment y
043.  }
044. 
045.  if(y >= size)
046.    return 1; //end of the tast, the checkerboard was fully traversed
047. 
048.  //make both decisions
049.  solveQueensProblem(a, x, y, 1, queensCount, size, solutionsCount);
050.  solveQueensProblem(a, x, y, 0, queensCount, size, solutionsCount);
051.   
052.  return 1;
053.}
054. 
055. 
056./**
057. * Check that no queen can attack another
058. * @param a checkerboard
059. * @param x kam bude nova dama vlozena na ose x
060. * @param y kam bude nova dama vlozena na ose y
061. * @return
062. */
063.int checkConsistency(char * a, int x, int y, int size)
064.{
065.  //horizontally x
066.  int i;
067.  for(i = 0; i < size; i++) // mozno otocit na for(i = size-1; i >= 0; i--)
068.  {
069.    if(i != x && a[y*size+i] == 1)
070.      return 0;
071.  }
072.  //vertically
073.  for(i = 0; i < size; i++)
074.  {
075.    if(i != y && a[i*size+x] == 1)
076.      return 0;
077.  }
078.   
079.  //diagonal left-bottom, right-upper
080.  i = 1;
081.  //vpravo nahoru
082.  while(x + i < size && y - i >= 0)
083.  {
084.    if(a[(y - i)*size+(x + i)])
085.      return 0;
086.    i++;
087.  }
088.   
089.  i = 1;
090.  //left and down
091.  while(x - i >= 0 && y + i < size)
092.  {
093.    if(a[(y + i)*size+(x - i)])
094.      return 0;
095.    i++;
096.  }
097.   
098.  //diagonal left-upper, right-bottom
099.  i = 1;
100.  //vlevo nahoru
101.  while(x - i >= 0 && y - i >= 0)
102.  {
103.    if(a[(y - i)*size+(x - i)])
104.      return 0;
105.    i++;
106.  }
107.   
108.  i = 1;
109.  //right and down
110.  while(x + i < size && y + i < size)
111.  {
112.    if(a[(y + i)*size+(x + i)])
113.      return 0;     
114.    i++;
115.  }
116.   
117.  return 1;
118.}
119. 
120.int main()
121.{
122.  #define SIZE 8
123.  int solutionsCount = 0;
124.  char a[SIZE*SIZE] = {0};
125.   
126.  solveQueensProblem(a, 0, 0, 1, 0, SIZE, &solutionsCount);
127.  solveQueensProblem(a, 0, 0, 0, 0, SIZE, &solutionsCount);
128.   
129.  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);       
130.  system("pause");
131.    return 0;
132.}
001./**
002. * N queens problem
003. * @author Pavel Micka
004. */
005.class QueensProblem {
006.private:
007.    int solutionsCount;
008.    /**
009.     * Solves the n queens problem
010.     * @param array chessboard
011.     * @param x x coordinate where to place the current queen
012.     * @param y y coordinate where to place the current queen
013.     * @param set true if the queen should be placed, false otherwise
014.     * @param queensCount how many queens are already placed
015.     */
016.    void solveQueensProblem(bool ** a, int x, int y, bool set, int queensCount, int size) {
017.        a[y][x] = set;
018.        if (set && !checkConsistency(a, x, y, size)) {
019.            return;
020.        }
021.        if (set) {
022.            queensCount++;
023.        }
024. 
025.        if (queensCount == size) {
026.            solutionsCount++;
027.            printArray(a, size);
028.            return; //reseni nalezeno
029.        }
030.        x = x + 1; //increment x
031.        int overflow = x == size ? 1 : 0;
032.        if (overflow == 1) {//if x overflowed
033.            x = 0; //set x to 0
034.            y += 1; //increment y
035.        }
036. 
037.        if (y >= size) {
038.            return; //end of the problem, all decisions have been made
039.        }
040.        //lets make both decisions
041.        solveQueensProblem(a, x, y, true, queensCount, size);
042.        solveQueensProblem(a, x, y, false, queensCount, size);
043. 
044.    }
045.    /**
046.     * Check that no queen can attack another
047.     * @param array chessboard
048.     * @param x x coordinate where the new queen will be placed
049.     * @param y y coordinate where the new queen will be placed
050.     * @param size size of the chessboard
051.     * @return true if the the model after queen placement is consistent, false otherwise
052.     */
053.    bool checkConsistency(bool ** a, int x, int y, int size) {
054.        //horizontally
055.        for (int i = 0; i < size; i++) {
056.            if (i != x && a[y][i] == true) {
057.                return false;
058.            }
059.        }
060.        //vertically
061.        for (int i = 0; i < size; i++) {
062.            if (i != y && a[i][x] == true) {
063.                return false;
064.            }
065.        }
066.        //diagonally left bottom to right top
067.        int j = 1;
068.        while (x + j < size && y - j >= 0) {
069.            if (a[y - j][x + j]) {
070.                return false;
071.            }
072.            j++;
073.        }
074.        j = 1;
075.        while (x - j >= 0 && y + j < size) {
076.            if (a[y + j][x - j]) {
077.                return false;
078.            }
079.            j++;
080.        }
081.        //diagonally left top, right bottom
082.        j = 1;
083.        while (x - j >= 0 && y - j >= 0) {
084.            if (a[y - j][x - j]) {
085.                return false;
086.            }
087.            j++;
088.        }
089.        j = 1;
090.        while (x + j < size && y + j < size) {
091.            if (a[y + j][x + j]) {
092.                return false;
093.            }
094.            j++;
095.        }
096.        return true;
097.         
098.    }
099.    /**
100.     * Print out the chessboard
101.     * @param array chessboard
102.     * @param size size of the chessboard
103.     */
104.    void printArray(bool ** a, int size) {
105.        cout << "Reseni #" << this->solutionsCount;
106.        for (int i = 0; i < size; i++) {
107.            cout << "\\n" << "|";
108. 
109.            for (int j = 0; j < size; j++) {
110.                if (a[i][j]) {
111.                    cout << "Q|";
112.                } else {
113.                    cout << " |";
114.                }
115.            }
116.        }
117.        cout << "\\n" << "---------------------\\n";
118.    }
119.public:
120.    QueensProblem(){
121.        this->solutionsCount = 0;
122.    }
123.    /**
124.     * Solves and prints out solution of the n queens problem
125.     * @param size size of the problem
126.     */
127.    void solve(int size) {
128.        bool ** a = new bool*[size];
129.        for(int j = 0; j < size; j++){
130.            a[j] = new bool[size];
131.            for(int k = 0;  k < size; k++){
132.                a[j][k] = false;
133.            }
134.        }
135.        solveQueensProblem(a, 0, 0, true, 0, size);
136.        solveQueensProblem(a, 0, 0, false, 0, size);
137.        for(int i = 0; i < size; i ++) delete[] a[i];
138.        delete[] a;
139.    }
140. 
141.    /**
142.     * @return the solutionsCount
143.     */
144.    int getSolutionsCount() {
145.        return solutionsCount;
146.    }
147.};
001.; Autor: Michal Orsel
003.bits 32
004. 
005.section .data
006. 
007.section .text
008. 
009.global solveQueensProblem
010.global checkConsistency
011. 
012.; int solveQueensProblem(char * a, int x, int y, int set, int queensCount, int size, int * solutionsCount)
013.solveQueensProblem:
014.    enter 0, 0
015.     
016.    push esi
017.    push edi
018.    push ebx
019.    push ecx
020. 
021.  ; parameters
022.  ;[ ebp + 8 ]  ; char * a
023.  ;[ ebp + 12 ] ; int x,
024.  ;[ ebp + 16 ] ; int y,
025.  ;[ ebp + 20 ] ; int set,
026.  ;[ ebp + 24 ] ; int queensCount,
027.  ;[ ebp + 28 ] ; int size,
028.  ;[ ebp + 32 ] ; int * solutionsCount
029. 
030.  ; a[y * size + x] = set
031.  mov edx, 0                           
032.  mov eax, [ ebp + 16 ]                 ; y
033.  mul dword [ ebp + 28 ]                ; y * size
034.  add eax, [ ebp + 12 ]                 ; (y * size) + x
035.  mov esi, [ ebp + 8 ]                  ; a 
036.  mov edx, [ ebp + 20 ]                 ; set
037.  mov byte [ esi + eax ], dl             ; a[y * size + x] = set
038.   
039.  ; if(set && !checkConsistency(a, x, y, size)) return 0
040.  cmp dword [ ebp + 20 ], 0
041.  je .n_if_1
042.  ; call checkConsistency(a, x, y, size)
043.    push dword [ ebp + 28 ]               ; size
044.    push dword [ ebp + 16 ]               ; y
045.    push dword [ ebp + 12 ]               ; x
046.    push dword [ ebp + 8 ]                ; a
047.    call checkConsistency
048.    add esp, 16
049.    cmp eax, 0
050.    jne .n_if_1    
051.    ; return 0
052.    mov eax, 0
053.    jmp .return
054.  .n_if_1:
055.   
056.  ; if(set) queensCount++;
057.  cmp dword [ ebp + 20 ], 0
058.  je .n_if_2
059.    inc dword [ ebp + 24 ]
060.  .n_if_2:
061.   
062.  ; if(queensCount == size)
063.  mov esi, [ ebp + 28 ]                 ; size
064.  cmp dword [ ebp + 24 ], esi
065.  jne .n_if_3
066.    mov esi, [ ebp + 32 ]               ; *solutionsCount
067.    inc dword [ esi ]                   ; (*solutionsCount)++;
068.    ; return 1
069.    mov eax, 1
070.    jmp .return
071.  .n_if_3:
072.     
073.  inc dword [ ebp + 12 ]                ; x++
074.   
075.  ; if(x >= size)
076.  mov esi, [ ebp + 28 ]                 ; size
077.  cmp dword [ ebp + 12 ], esi
078.  jl .n_if_4
079.    mov dword [ ebp + 12 ], 0           ; x = 0
080.    inc dword [ ebp + 16 ]              ; y++  
081.  .n_if_4:
082.   
083.  ; if(y >= size)
084.  mov esi, [ ebp + 28 ]                 ; size
085.  cmp dword [ ebp + 16 ], esi
086.  jl .n_if_5
087.    ; return 1
088.    mov eax, 1 
089.    jmp .return
090.  .n_if_5:
091.   
092.  ; call solveQueensProblem(a, x, y, 1, queensCount, size, solutionsCount)
093.  push dword [ ebp + 32 ]               ; solutionsCount
094.  push dword [ ebp + 28 ]               ; size
095.  push dword [ ebp + 24 ]               ; queensCount
096.  push dword 1                          ; 1
097.    push dword [ ebp + 16 ]               ; y
098.    push dword [ ebp + 12 ]               ; x
099.    push dword [ ebp + 8 ]                ; a
100.    call solveQueensProblem
101.    add esp, 28
102.     
103.  ; call solveQueensProblem(a, x, y, 0, queensCount, size, solutionsCount)
104.  push dword [ ebp + 32 ]               ; solutionsCount
105.  push dword [ ebp + 28 ]               ; size
106.  push dword [ ebp + 24 ]               ; queensCount
107.  push dword 0                          ; 0
108.    push dword [ ebp + 16 ]               ; y
109.    push dword [ ebp + 12 ]               ; x
110.    push dword [ ebp + 8 ]                ; a
111.    call solveQueensProblem
112.    add esp, 28
113.   
114.  ; return 1
115.  mov eax, 1
116.   
117..return:
118. 
119.  pop ecx
120.    pop ebx
121.    pop edi
122.    pop esi
123.     
124.    leave
125.    ret
126. 
127.; ------------------------------------------------------------------------------
128. 
129.; int checkConsistency(char * a, int x, int y, int size)
130.checkConsistency:
131.    enter 0, 0
132.     
133.  push ecx
134.  push esi
135.  push edx
136. 
137.  ; parametry
138.  ;[ ebp + 8 ]  ; char * a
139.  ;[ ebp + 12 ] ; int x,
140.  ;[ ebp + 16 ] ; int y,
141.  ;[ ebp + 20 ] ; int size
142.   
143.  ; for(i = 0; i < size; i++)
144.  mov ecx, 0
145.  .for_1:
146.    cmp ecx, dword [ ebp + 20 ]        
147.    jge .n_for_1
148.      
149.    ; if(i != x && a[y * size + i] == 1) return 0 
150.    cmp ecx, dword [ ebp + 12 ]
151.    je .n_if_1
152.    mov edx, 0                         
153.    mov eax, [ ebp + 16 ]               ; y
154.    mul dword [ ebp + 20 ]              ; y * size
155.    add eax, ecx                        ; (y * size) + i
156.    mov esi, [ ebp + 8 ]                ; a 
157.    cmp byte [esi + eax ], byte 1    
158.    jne .n_if_1
159.      mov eax, 0                        ; return 0
160.      jmp .return  
161.    .n_if_1:
162.     
163.    inc ecx                             ; i++ 
164.    jmp .for_1
165.  .n_for_1:
166.   
167.  ; for(i = 0; i < size; i++)
168.  mov ecx, 0
169.  .for_2:
170.    cmp ecx, dword [ ebp + 20 ]
171.    jge .n_for_2
172.         
173.    ; if(i != y && a[i * size + x] == 1) return 0
174.    cmp ecx, dword [ ebp + 16 ]
175.    je .n_if_2
176.    mov edx, 0                         
177.    mov eax, ecx                        ; i
178.    mul dword [ ebp + 20 ]              ; i * size
179.    add eax, [ ebp + 12 ]               ; (i * size) + x
180.    mov esi, [ ebp + 8 ]                ; a 
181.    cmp byte [esi + eax ], byte 1    
182.    jne .n_if_2
183.      ; return 0
184.      mov eax, 0
185.      jmp .return  
186.    .n_if_2:
187.   
188.    inc ecx                             ; i++
189.    jmp .for_2 
190.  .n_for_2:
191.   
192.  mov ecx, 1                            ; i = 1
193. 
194.  ; while(x + i < size && y - i >= 0)
195.  .while_1:
196.  mov eax, dword [ ebp + 12 ]           ; x
197.  add eax, ecx                          ; x + i
198.  cmp eax, [ ebp + 20 ]
199.  jge .n_while_1
200.  mov eax, [ ebp + 16 ]                 ; y
201.  sub eax, ecx                          ; y - i
202.  cmp eax, 0
203.  jl .n_while_1
204.    ; if(a[(y - i) * size + (x + i)])
205.    mov eax, dword [ ebp + 16 ]         ; y
206.    sub eax, ecx                        ; y - i
207.    mul dword [ ebp + 20 ]              ; (y - i) * size
208.    add eax, dword [ ebp + 12 ]         ; (y - i) * size + x
209.    add eax, ecx                        ; (y - i) * size + x + i
210.    mov esi, [ ebp + 8 ]                ; a
211.    cmp byte [esi + eax ], byte 0
212.    je .n_if_3
213.      ; return 0
214.      mov eax, 0
215.      jmp .return
216.    .n_if_3:   
217.    inc ecx                             ; i++
218.    jmp .while_1
219.  .n_while_1:    
220.         
221.  mov ecx, 1                            ; i = 1
222.   
223.  ; while(x - i >= 0 && y + i < size)
224.  .while_2:
225.  mov eax, dword [ ebp + 12 ]           ; x
226.  sub eax, ecx                          ; x - i
227.  cmp eax, 0
228.  jl .n_while_2
229.  mov eax, dword [ ebp + 16 ]           ; y
230.  add eax, ecx                          ; y + i
231.  cmp eax, dword [ ebp + 20 ]          
232.  jge .n_while_2
233.    ; if(a[(y + i) * size + (x - i)])
234.    mov eax, dword [ ebp + 16 ]         ; y
235.    add eax, ecx                        ; y + i
236.    mul dword [ ebp + 20 ]              ; (y + i) * size
237.    add eax, dword [ ebp + 12 ]         ; (y + i) * size + x
238.    sub eax, ecx                        ; (y + i) * size + x - i
239.    mov esi, [ ebp + 8 ]                ; a 
240.    cmp byte [esi + eax ], byte 0
241.    je .n_if_4
242.      ; return 0
243.      mov eax, 0
244.      jmp .return
245.    .n_if_4:   
246.    inc ecx                             ; i++
247.    jmp .while_2
248.  .n_while_2:    
249.         
250.  mov ecx, 1                            ; i = 1
251.   
252.  ; while(x - i >= 0 && y - i >= 0)
253.  .while_3:
254.  mov eax, dword [ ebp + 12 ]           ; x
255.  sub eax, ecx                          ; x - i
256.  cmp eax, 0
257.  jl .n_while_3
258.  mov eax, dword [ ebp + 16 ]           ; y
259.  sub eax, ecx                          ; y - i
260.  cmp eax, 0
261.  jl .n_while_3
262.    ; if(a[(y - i) * size + (x - i)])
263.    mov eax, dword [ ebp + 16 ]         ; y
264.    sub eax, ecx                        ; y - i
265.    mul dword [ ebp + 20 ]              ; (y - i) * size
266.    add eax, dword [ ebp + 12 ]         ; (y - i) * size + x
267.    sub eax, ecx                        ; (y - i) * size + x - i
268.    mov esi, [ ebp + 8 ]                ; a 
269.    cmp byte [esi + eax ], byte 0
270.    je .n_if_5
271.      ; return 0
272.      mov eax, 0
273.      jmp .return
274.    .n_if_5:   
275.    inc ecx                             ; i++
276.    jmp .while_3
277.  .n_while_3:          
278.         
279.  mov ecx, 1                            ; i = 1
280.   
281.  ; while(x + i < size && y + i < size)
282.  .while_4:
283.  mov eax, dword [ ebp + 12 ]           ; x
284.  add eax, ecx;                         ; x + i
285.  cmp eax, [ ebp + 20 ]                
286.  jge .n_while_4
287.  mov eax, dword [ ebp + 16 ]           ; y
288.  add eax, ecx                          ; y + i
289.  cmp eax, [ ebp + 20 ]                
290.  jge .n_while_4
291.    ; if(a[(y + i) * size + (x + i)])
292.    mov eax, dword [ ebp + 16 ]         ; y
293.    add eax, ecx                        ; y + i
294.    mul dword [ ebp + 20 ]              ; (y + i) * size
295.    add eax, dword [ ebp + 12 ]         ; (y + i) * size + x
296.    add eax, ecx                        ; (y + i) * size + x + i
297.    mov esi, [ ebp + 8 ]                ; a
298.    cmp byte [esi + eax ], byte 0    
299.    je .n_if_6
300.      ; return 0
301.      mov eax, 0
302.      jmp .return
303.    .n_if_6:   
304.    inc ecx                             ; i++
305.    jmp .while_4
306.  .n_while_4:    
307.           
308.  ; return 1       
309.  mov eax, 1 
310.   
311..return:
312. 
313.  pop edx
314.  pop esi
315.  pop ecx
316. 
317.    leave
318.    ret







       
 

Place for your banner

Here is the position ready for our customer's banners.