-----------------------------------

Cervantes

Wed Jul 27, 2005 5:25 pm


N Queen's Puzzle Solver

-----------------------------------

Anyone remember those N Queens puzzle.

For those who are unfamiliar with the puzzle, it goes like this: You've got a chess board (or any square board) and eight queens (or as many queens as the board is wide).  You must position all the queens on the board so that each queen is safe from the others.  That is, no two queens can be in the same row, column, or diagonal.

Attached are two files.  The first is the program that will go ahead and solve the puzzle.  This second is a program to try to solve the puzzle yourself.  (I know I've got one like this in my puzzles thread [link above], but I had to redo most of it anyways, so I figured I'd make it look nice[r].)  

In the solver: If you want to speed things up, comment out the delay on line 266.  You may also want to comment out the Input.Pause on line 273.  The only reason you would want to keep the delay is to see how the program works.  If you're looking for solutions, ditch the delay, because the first solution on an 8 by 8 grid is 876 moves in.

With no delay and no Input.Pause, it takes my computer 121 seconds to find 86 winning combinations, in 13186 moves on an 8x8 grid.
[url=http://www.durangobill.com/N_Queens.html]This page says theres 92 solutions.  Wierd.  Well, good enough, right? :lol:

The program will crash on anything under a 3x3 grid.


-----------------------------------

Delos

Wed Jul 27, 2005 5:53 pm



-----------------------------------

Not bad.  Your method is very straightforward and blunt.  Naturally, this works.  I've heard of a lot more complex algorithms that foresee problems with certain sets of moves, thus cutting down on runtime significantly.  Couldn't say how they work...


-----------------------------------

zylum

Wed Jul 27, 2005 11:23 pm



-----------------------------------

i think straight forward recursion is the simplest solution to this problem... although it takes a while for larger values of N...

my proggy finds 92 solutions for 8x8 grid in 0.5 seconds on my crappy computer and 724 solutions for a 10x10 grid in 15 seconds.

setscreen ("offscreenonly,graphics:500;500,nobuttonbar")

const N := 5
const gridSize := maxx div (N + 2)
var grid : array 1 .. N, 1 .. N of boolean
var solutions : int := 0
colorback (grey)

fcn clearSpot (x, y : int) : boolean
    for k : 1 .. N
        if grid (k, y) then
            result false
        elsif x + k  0 and grid (x - k, y - k) then
            result false
        elsif x + k  0 and grid (x + k, y - k) then
            result false
        elsif x - k > 0 and y + k  N then
        return
    end if
    for y : 1 .. N
        if clearSpot (col, y) then
            grid (col, y) := true
            if col = N then
                solutions += 1
                %/*