See https://en.wikipedia.org/wiki/Eight_queens_puzzle
For a non recursive non-back-tracking algorithm.
It is a loop that (when using a vector) can easily be unrolled in parallelly
executed loops.
I implemented it as follows running on 2 processors:
#lang racket
#|
The following text is copied from article n queens of wikipedia:
This heuristic solves N queens for any N ≥ 4. It forms the list of numbers
for vertical positions (rows) of queens with horizontal position (column)
simply increasing. N is 8 for eight queens puzzle.
1. If the remainder from dividing N by 6 is not 2 or 3 then the list is
simply all even numbers followed by all odd numbers ≤ N
2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 -
1,3,5,7)
3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i.
e. 3,1,7,5)
4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end
of odd list (i.e. 4,6,8,2 - 5,7,9,1,3)
5. Append odd list to the even list and place queens in the rows given by
these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5)
In the following procedure I use a vector with as many elements as the chess
board has rows. Every element is assigned exactly once. Rows and columns are
counted from 0 (in the wikipedia article they are counted from 1)
Futures allow two or more loops to run simulanuously on two or more
processors. If you don't have futures, replace (define f (future odd)) by
(odd) and remove the touch.
|#
(require racket/future)
(define (queens n)
(define v (make-vector n))
(define n-odd (quotient n 2))
(define r (remainder n 6))
(define (odd)
(case r
((3)
(for ((k (in-range 0 (sub1 n-odd)))) (vector-set! v k (+ 3 (* 2 k))))
(vector-set! v (sub1 n-odd) 1))
(else
(for ((k (in-range 0 n-odd))) (vector-set! v k (add1 (* 2 k)))))))
(define (even)
(case r
((2)
(vector-set! v n-odd 2)
(vector-set! v (add1 n-odd) 0)
(for ((k (in-range (+ 2 n-odd) n)))
(vector-set! v k (+ 6 (* 2 (- k n-odd 2)))))
(vector-set! v (sub1 n) 4))
((3)
(for ((k (in-range n-odd (- n 2))))
(vector-set! v k (+ 4 (* 2 (- k n-odd)))))
(vector-set! v (- n 2) 0)
(vector-set! v (- n 1) 2))
(else
(for ((k (in-range n-odd n)))
(vector-set! v k (* 2 (- k n-odd)))))))
(define f (future odd))
(even)
(touch f)
v)
(define (check v)
(let ((n (vector-length v)))
(for/and ((x1 (in-range 0 n)))
(let ((y1 (vector-ref v x1)))
(for/and ((x2 (in-range (add1 x1) n)))
(let ((y2 (vector-ref v x2)))
(not
(or
(= y1 y2)
(= (abs (- x1 x2)) (abs (- y1 y2)))))))))))
(for/and ((n (in-range 4 100))) (check (queens n)))
(for ((k (in-range 2 9)))
(printf "(expt 10 ~s) : " k)
(let ((n (expt 10 k)))
(time (queens n))))
Runs fast:
(expt 10 2) : cpu time: 0 real time: 0 gc time: 0
(expt 10 3) : cpu time: 0 real time: 0 gc time: 0
(expt 10 4) : cpu time: 0 real time: 0 gc time: 0
(expt 10 5) : cpu time: 0 real time: 0 gc time: 0
(expt 10 6) : cpu time: 63 real time: 47 gc time: 32
(expt 10 7) : cpu time: 203 real time: 140 gc time: 15
(expt 10 8) : cpu time: 3183 real time: 2543 gc time: 1123
Times measured with DrRacket
Jos
-----Original Message-----
From: racket-users@googlegroups.com [mailto:racket-users@googlegroups.com]
On Behalf Of Brian Adkins
Sent: sábado, 12 de marzo de 2016 1:42
To: Racket Users
Subject: [racket-users] Sequential vs. Parallel 13-Queens program
I coded up a sequential and parallel version of N-Queens, then did a ton of
benchmark runs of 13-Queens to compare the time. For each configuration
(sequential or parallel w/ M workers), I ran the programs 6 times, threw out
the high two & low two and averaged the middle two numbers.
The spreadsheet with timings is here:
https://docs.google.com/spreadsheets/d/1LFwdZbBveaARY_AquGXY9jgaSJlOA03NQCV9
TeYQ-l8/edit?usp=sharing
The code is here:
https://gist.github.com/lojic/aef0aec491d3dc9cb40b
I didn't spend any time refining/optimizing, so it's fairly crude, but
informative nonetheless.
The executive summary of timings for the parallel version:
# Places Time
1 34.9
2 19.7
3 13.8
4 12.3
5 11.9
6 12.9
7 12.1
8 12.2
The sequential version took 31.3 seconds.
The basic idea for the parallel version is to place the first 13 starting
positions in a queue that the place workers will pull from and produce a set
of solutions with that starting position. Both the parallel and sequential
versions collect all 73,712 solutions in a list and compute the length of
it. I hardcoded the number of solutions as a quick & dirty way of
determining completion in the parallel version just to allow me to get the
timings easily.
It was great to finally write some Racket code that got all my cores heated
up :)
Brian
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
