N-Queens Problem

Author: James Walker
©2017 under the MIT license

Overview

The N-queens problem is a generalization of the 8-queens puzzle involving how to place eight non-attacking queens on a regular chess board. The N-queens problem asks, given a positive integer N, how many ways are there to place N chess queens on an N × N chess board such that none of the queens can attack each other.

The programs in this repository implement an algorithm that performs a constrained depth-first search (DFS) of the chess board to find solutions to the N-queens problem. The programs are outlined below, with further descriptions about their execution provided in their respective folders. Following this, general results are presented and explained. Lastly, an outline of the constrained DFS algorithm is provided along with a source link.

C Programs in the src_C folder:

• 8-Queens Solver (eight_queens_solver.c)
• N-Queens Solver (n_queens_solver.c)
• N-Queens Counter (n_queens_counter.c)

Go Programs in the src_Go folder:

• N-Queens Solver (n_queens_solver.go)
• N-Queens Counter (n_queens_counter.go)

Python Scripts in the src_Python folder:

• N-Queens Counter (n_queens_counter.py, n_queens_multicore_counter.py)

R Scripts in the src_R folder:

• N-Queens Solver (n_queens_solver.R)
• N-Queens Counter (n_queens_counter.R, n_queens_counter_optimized.R)

Shell Script Programs in the src_Shell folder:

• N-Queens Solver (n_queens_solver.sh)
• N-Queens Counter (n_queens_counter.sh)

Results from the solver program are output as a series of N integers corresponding to the columns on the chess board, with each integer represents the row of the queen in the given column from A to H. In the example shown below, the numbers in the 8-queens solution 1 5 8 6 3 7 2 4 are sequentially ordered by column from A to H. Thus, queens are positioned on the chess board at A1, B5, C8, D6, E3, F7, G2, and H4.

Number Solutions for N-Queens Problems

The N-Queens Counter programs have been used to find the number of queen placements and the number of N-queens solutions for values of N between 1 and 15 with the Go, Python, and R implementations, and values of N between 1 and 19 with the C implementation. As can be seen from the results in the table below, the constrained DFS algorithm significantly reduces the search-space of the problem compared to the (N²)!/(N² − N)! placements that would be made by most naïve combinatorial algorithm.

For the N-Queens Counter implementations in C and Python, the algorithm was improved to take the symmetry of the chess board into account. This modification enables the programs to count all of the possible N-queens solutions using half the number of queen placements required by the original algorithm.

Number of Queens Placed using Different N-Queens Solver Algorithms

N	Naïve Combinitorial	Constrained DFS	Symmetry Constrained DFS	Number of Solutions
1	1	1	1	1
2	12	2	1	0
3	504	5	3	0
4	43,680	16	8	2
5	6,375,600	53	27	10
6	1.402 × 109	152	76	4
7	4.329 × 1011	551	276	40
8	1.785 × 1014	2,056	1,028	92
9	9.467 × 1016	8,393	4,197	352
10	6.282 × 1019	35,538	17,769	724
11	5.096 × 1022	166,925	83,463	2,680
12	4.963 × 1025	856,188	428,094	14,200
13	5.714 × 1028	4,674,889	2,337,445	73,712
14	7.676 × 1031	27,358,552	13,679,276	365,596
15	1.190 × 1035	171,129,071	85,564,536	2,279,184
16	2.109 × 1038	1,141,190,302	570,595,151	14,772,512
17	4.235 × 1041	8,017,021,931	4,008,510,966	95,815,104
18	9.570 × 1044	59,365,844,490	29,682,922,245	666,090,624
19	2.417 × 1048	461,939,618,823	230,969,809,412	4,968,057,848
20	6.784 × 1051	???	???	39,029,188,884

According to the On-Line Encyclopedia of Integer Sequences (OEIS sequence: A000170), the total number of solutions for the N-queens problem has been determined for every value of N up to 27.

Constrained DFS Algorithm Details

The algorithm implemented to solve the 8-queens problem was obtained online from the bottom of the webpage for A Short Introduction to the Art of Programming by Dr. Edsger W. Dijkstra. The 8-queens solver algorithm, shown below, has been adapted and reformatted from the one provided in the link above.

begin ALGORITHM  
  integer n  
  integer h  
  integer k  
  integer array x[0:7]  
  boolean array col[0:7]  
  boolean array up[-7:+7]  
  boolean array down[0:14]  
  
  procedure INITIALIZE EMPTY BOARD:  
    n := 0  
    k := 0  
    repeat until k = 8:  
      col[k] := true  
      k := k + 1  
    end repeat  
    k := 0  
    repeat until k = 15:  
      up[k-7] := true  
      down[k] := true  
      k := k + 1  
    end repeat  
  end procedure INITIALIZE EMPTY BOARD

  procedure PLACE NEXT QUEEN:  
    h := 0  
    repeat until h = 8:  
      if SQUARE H FREE (col[h] = true AND up[n-h] = true AND down[n+h] = true):  
        begin SET QUEEN ON SQUARE H:  
          x[n] := h  
          col[h] := false  
          up[n-h] := false  
          down[n+h] := false  
          n := n + 1  
        end SET QUEEN ON SQUARE H  
        if BOARD FULL (n = 8):  
          begin PRINT QUEEN POSITIONS:  
            k := 0  
            repeat until k = 8:  
              print(x[k])  
              k := k + 1  
            end repeat  
            print(newline)  
          end PRINT QUEEN POSITIONS  
        else:  
          call PLACE NEXT QUEEN  
        end if BOARD FULL  
        begin REMOVE QUEEN FROM SQUARE H:  
          n := n - 1  
          down[n+h] := true  
          up[n-h] := true  
          col[h] := true  
        end REMOVE QUEEN FROM SQUARE H  
      end if SQUARE H FREE  
      h := h + 1  
    end repeat  
  end procedure PLACE NEXT QUEEN  
  
  call INITIALIZE EMPTY BOARD
  call PLACE NEXT QUEEN  
  
end ALGORITHM