N Queens Puzzle

Wed, 22 Jul 2009 18:05:09 GMT

I've been reading this great book, Structure and Interpretation of Computer Programs for the last few days. The examples are full of really cool math, algorithms, techniques and stuff. Here is an exercise that i managed to solve in scheme, The Eight queens puzzle.

The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves.

And here is the source.

(define (range a b)
  (if (= a b)
      null
      (cons a (range (+ a 1) b))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append null (map proc seq)))

(define (enumerate sequence)
  (define (iter counter sequence)
    (if (null? sequence)
        null
        (append (list (cons counter (car sequence))) (iter (+ counter 1) (cdr sequence)))))
  (iter 0 sequence))

(define (rook-attack-safe? possibilities)
  (accumulate (lambda (a b) (and a b))
              true
              (map (lambda (possibility)
                     (not (= possibility (last possibilities))))
                   (cdr (reverse possibilities)))))

(define (bishop-attack-safe? possibilities)
  (accumulate (lambda (a b) (and a b))
              true
              (map (lambda (pair)
                     (not (= (abs (- (last possibilities) (cdr pair)))
                             (abs (- (- (length possibilities) 1) (car pair))))))
                   (enumerate (reverse (cdr (reverse possibilities)))))))

(define (safe? possibilities)
  (and (rook-attack-safe? possibilities)
       (bishop-attack-safe? possibilities)))

(define (n-queens-puzzle k)
  (define (solve n k)
    (if (= n 0)
        '(())
        (filter safe?
               (flatmap (lambda (last)
                          (map (lambda (item)
                                 (append item (list last)))
                               (solve (- n 1) k)))
                        (range 0 k)))))
  (solve k k))

Please excuse the crappy code. Im a total noob schemer, infact this is probably my first real scheme program. The solution is based on the recursive method described in the book. It works like this: only one queen can be placed in any one column, the problem of placing queens in all columns without any check can be reduced, using recursion, to that of placing a queen in the last column of a board in which all the other columns already have queens in positions that do not check each other.

It took quite some time to solve an 8x8 board. Im not even sure if the results are correct. But a few random checks on paper turned out correct and i got 92 results, which according to wikipedia is the total number of solutions. However, there are only 12 unique solutions, many of the 92 solutions are repetitions since one solution can be horizontally or vertically flipped to create different solutions. Each solution here is a list whose indices correspond to the board column number and the values represent the row in which the queen is placed in the corresponding column.

((3 1 6 2 5 7 4 0)
 (4 1 3 6 2 7 5 0)
 (2 4 1 7 5 3 6 0)
 (2 5 3 1 7 4 6 0)
 (4 6 0 2 7 5 3 1)
 (3 5 7 2 0 6 4 1)
 (2 5 7 0 3 6 4 1)
 (4 2 7 3 6 0 5 1)
 (4 6 3 0 2 7 5 1)
 (3 0 4 7 5 2 6 1)
 (2 5 3 0 7 4 6 1)
 (3 6 4 2 0 5 7 1)
 (5 3 1 7 4 6 0 2)
 (5 3 6 0 7 1 4 2)
 (0 6 3 5 7 1 4 2)
 (5 7 1 3 0 6 4 2)
 (5 1 6 0 3 7 4 2)
 (3 6 0 7 4 1 5 2)
 (4 7 3 0 6 1 5 2)
 (3 7 0 4 6 1 5 2)
 (1 6 4 7 0 3 5 2)
 (0 6 4 7 1 3 5 2)
 (1 4 6 3 0 7 5 2)
 (3 1 6 4 0 7 5 2)
 (4 6 0 3 1 7 5 2)
 (5 3 0 4 7 1 6 2)
 (4 0 3 5 7 1 6 2)
 (4 1 5 0 6 3 7 2)
 (5 2 6 1 7 4 0 3)
 (1 6 2 5 7 4 0 3)
 (6 2 0 5 7 4 1 3)
 (4 0 7 5 2 6 1 3)
 (0 4 7 5 2 6 1 3)
 (2 5 7 0 4 6 1 3)
 (5 2 0 6 4 7 1 3)
 (6 4 2 0 5 7 1 3)
 (6 2 7 1 4 0 5 3)
 (4 2 0 6 1 7 5 3)
 (1 4 6 0 2 7 5 3)
 (2 5 1 4 7 0 6 3)
 (5 0 4 1 7 2 6 3)
 (7 2 0 5 1 4 6 3)
 (1 7 5 0 2 4 6 3)
 (4 6 1 5 2 0 7 3)
 (2 5 1 6 4 0 7 3)
 (5 1 6 0 2 4 7 3)
 (2 6 1 7 5 3 0 4)
 (5 2 6 1 3 7 0 4)
 (3 1 6 2 5 7 0 4)
 (6 0 2 7 5 3 1 4)
 (0 5 7 2 6 3 1 4)
 (2 7 3 6 0 5 1 4)
 (5 2 6 3 0 7 1 4)
 (6 3 1 7 5 0 2 4)
 (3 5 7 1 6 0 2 4)
 (1 5 0 6 3 7 2 4)
 (1 3 5 7 2 0 6 4)
 (2 5 7 1 3 0 6 4)
 (5 2 0 7 3 1 6 4)
 (7 3 0 2 5 1 6 4)
 (3 7 0 2 5 1 6 4)
 (1 5 7 2 0 3 6 4)
 (6 1 5 2 0 3 7 4)
 (2 5 1 6 0 3 7 4)
 (3 6 2 7 1 4 0 5)
 (3 7 4 2 0 6 1 5)
 (2 4 7 3 0 6 1 5)
 (3 1 7 4 6 0 2 5)
 (4 6 1 3 7 0 2 5)
 (6 3 1 4 7 0 2 5)
 (7 1 3 0 6 4 2 5)
 (6 1 3 0 7 4 2 5)
 (4 0 7 3 1 6 2 5)
 (3 0 4 7 1 6 2 5)
 (4 1 7 0 3 6 2 5)
 (2 6 1 7 4 0 3 5)
 (2 0 6 4 7 1 3 5)
 (7 1 4 2 0 6 3 5)
 (2 4 1 7 0 6 3 5)
 (2 4 6 0 3 1 7 5)
 (4 1 3 5 7 2 0 6)
 (5 2 4 7 0 3 1 6)
 (4 7 3 0 2 5 1 6)
 (3 1 4 7 5 0 2 6)
 (3 5 0 4 1 7 2 6)
 (5 2 0 7 4 1 3 6)
 (4 2 0 5 7 1 3 6)
 (3 1 7 5 0 2 4 6)
 (5 2 4 6 0 3 1 7)
 (5 3 6 0 2 4 1 7)
 (3 6 4 1 5 0 2 7)
 (4 6 1 5 2 0 3 7))

Better solutions

azeemblog v2

Tue, 30 Jun 2009 10:22:28 GMT

This is my first post in 6 months and the 2nd in this entire blog. Not surprising, if you consider that all of my previous attempts at starting a blog were either dumped right from the start or left to rot in oblivion. Ironically, 'start blogging again' was in the top of my new years resolution this year. To be honest, im really not a blogging type of guy. I dont have or can't find the time either.

I wasnt really satisfied with the blog script when i first wrote it in January. It felt like big pile of goo. So i re-wrote it. And here it is, azeemblog v2. I hope this inspires me to write more. More on this later.

Hello World

Wed, 07 Jan 2009 06:26:59 GMT

This blog is my little vacation project. ~~Its partially based Benjamin Golub's blog script.~~ The script is written entirely in python and hosted on Google's App Engine framework. Articles are written in markdown and converted to html using the markdown2 python library.

The system is pretty bare bones now, but im still working on stuff. I will upload the source sometime later.

Azeem's Blog

N Queens Puzzle

azeemblog v2

Hello World