2.7 Solving the N-queens problem

Let’s solve the N-queens problem by applying various ZDD operations introduced in the previous sections. N-queens problem is the number of different ways N number of queens can be set up on an NN chessboard so that no two queens may attack each other. The queen is a chess that is capable of moving across and at angular movements in Shogi (Japanese chess). As shown in the figure 2.1, the chess can move in a total of eight directions: right, left, up, down and diagonally.

x   x       x x   x x x o x     x x x   x   x   Table 2.1: The queen indicated as "o" can move to the squares marked as "x". (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) (1,3) (1,4) (2,0) (2,1) (2,2) (2,3) (2,4) (3,0) (3,1) (3,2) (3,3) (3,4) (4,0) (4,1) (4,2) (4,3) (4,4) Table 2.2: Coordinates of the chessboard o             o             o   o             o   Table 2.3: Example of a solution to 5 queens problem

Figure 2.1 shows a Ruby script for 5 queens problem using ZDD.

The assumed coordinates of the chessboard used in this script is shown in figure 2.2. The basic idea of the script is as follows. First, assume an item as a square where the Queen can be placed on the chessboard. The total number of squares on the chessboard is computed by , and all itemset combinations can be enumerated from .

It is sufficient to apply the explanation in section 2.3 for this example. Then select the itemset that meets the two conditions as follows.

1. Remove all itemsets that may attack each other.

2. Delete the itemset with size less than 5.

In this case, among itemsets whose size is larger than 5, remove those which satisfy the first condition. Next, verify the movement of the chess with the details described in the figures. At the end of the script, the number of terms in ZDD object stored during the operation and the number of internal contact points will be returned as output.

#!/usr/bin/env ruby
#encoding: utf-8
require "zdd"

n = 5

# In the nested loop below, the itemset combinations of 25 squares (items) are enumerated, 
and stored in the variable "all".
# Use the characters "i, j" to indicate the coordinates for the item name.
all=ZDD.constant(1)
(0...n).each{|i|
	(0...n).each{|j|
		all *= (1+ZDD::itemset("#{i},#{j}"))
	}
}

# Enumerate all combinations two squares that attack each other and stored in the variable "ng".
ng=ZDD.constant(0)
(0...n).each{|i| # row loop
  (0...n).each{|j| # column loop
     # Item pair which has the same row number (i) with the square i.j
    (j+1...n).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i},#{k}") # Row
    }
     # Item pair which has the same column number (i) with the square i.j
    (i+1...n).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{k},#{j}") # Row
    }
    # item pair with the square i.j. and lower right direction from that square
    (1...[n-i,n-j].min).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i+k},#{j+k}") #
    }
    # item pair with the square i.j. and lower left direction from that square
    (1...[n-i,j+1].min).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i+k},#{j-k}") #
    }
  }
}
st=Time.new # Use for time measurement
selNG=all.restrict(ng)     # 1) Select itemsets that contains the items pair which attacks 
each other from all itemsets "all".
selOK=selNG.iif(0,all)     # 2) Exclude the itemset obtained in 1) from the all itemsets "all".
selLT=selOK.permitsym(n-1) # 3) From the results in 2), select the itemset where the size is 
less than n-1.
ans  =selLT.iif(0,selOK)   # 4) From the results in 2), remove the itemsets obtained in 3).

# Display the number of ZDD itemset (totalweight function) created from the calculation process
 and the number of ZDD nodes (size function).
# totalweight function is a method to aggregate the weight of each term in ZDD.
# Since the weight of all terms is 1, thus the number of itemset in the expression is 
known from the expression. 
puts "all   : #{all.totalweight}\t #{all.size}"
puts "selNG : #{selNG.totalweight}\t #{selNG.size}"
puts "selOK : #{selOK.totalweight}\t #{selOK.size}"
puts "selLT : #{selLT.totalweight}\t #{selLT.size}"
puts "ans   : #{ans.totalweight}\t #{ans.size}"
puts "time: #{Time.new-st}"
ans.show # Display the solution 

The results are shown as follows. There are about 33.55 million (value of ) possible ways to arrange the queens on 25 squares, represented by only 25 ZDD nodes. The number of combinations (selNG) which attack each other selected by the restrict function is about the same, but the number of ZDD nodes rapidly increases to 587, it is also where most time is consumed. Finally, the solution includes 10 enumerated itemsets.

Among them, the placement of "0,0 1,2 2,4 3,1 4,3" in the initial solution (term) is shown in figure 2.3.

all   : 33554432	 25
selNG : 33553970	 587
selOK : 462	 193
selLT : 452	 199
ans   : 10	 40
time: 0.003749
 0,0 1,2 2,4 3,1 4,3 + 0,0 1,3 2,1 3,4 4,2 + 0,1 1,3 2,0 3,2 4,4 + 0,1
  1,4 2,2 3,0 4,3 + 0,2 1,0 2,3 3,1 4,4 + 0,2 1,4 2,1 3,3 4,0 + 0,3 1,0
  2,2 3,4 4,1 + 0,3 1,1 2,4 3,2 4,0 + 0,4 1,1 2,3 3,0 4,2 + 0,4 1,2 2,0
  3,3 4,1

Furthermore, the number of ZDD nodes, solutions and processing time when N is set from 4 to 11 are displayed in Table 2.4.

ZDD objects (all) for all combinations of all squares, and ZDD object with the maximum number of ZDD nodes (selNG) are shown.

The number of nodes of selNG is about 20 million when N=11. It means about 600M bytes memory will be consumed for calculating 30 byte per node.

The workspace during the calculation is limited to N=11 on a PC with 8GB memory. More efficient solution using ZDD is shown in the reference [, users are welcomed to challenge the program by all means.