N Queen's Puzzle Solver

[Cervantes]

Anyone remember those puzzles I made a while back? Today I made a program that will determine and output the winning combinations for the 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.
This page says theres 92 solutions. Wierd. Well, good enough, right?

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

[Delos]

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]

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.

code:

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 <= N and y + k <= N and grid (x + k, y + k) then             result false         elsif x - k > 0 and y - k > 0 and grid (x - k, y - k) then             result false         elsif x + k <= N and y - k > 0 and grid (x + k, y - k) then             result false         elsif x - k > 0 and y + k <= N and grid (x - k, y + k) then             result false         end if     end for     result true end clearSpot proc drawGrid     drawfillbox (0, 0, maxx, maxy, grey)     for x : 1 .. N         for y : 1 .. N             if grid (x, y) then                 drawfillbox (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, black)             else                 drawfillbox (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, white)             end if             drawbox (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, black)         end for     end for end drawGrid proc Solve (col : int)     if col > N then         return     end if     for y : 1 .. N         if clearSpot (col, y) then             grid (col, y) := true             if col = N then                 solutions += 1                 %/* <- take out '%' to comment this block (may need to hit F2)                 drawGrid                 put "SOLUTION!!! (", solutions, ")"                 View.Update                 cls                 Input.Pause                 %*/             end if             %/* <- take out '%' to comment this block (may need to hit F2)             cls             drawGrid             View.Update             delay (250)             %*/             Solve (col + 1)             grid (col, y) := false         end if     end for end Solve for x : 1 .. N     for y : 1 .. N         grid (x, y) := false     end for end for Solve (1) put "Solutions: ", solutions, " Time: ", Time.Elapsed / 1000 View.Update

[edit] solved 12x12 in just over 500 seconds... 14200 solutions.

[Cervantes]

Wow. Very nice program, zylum. I wish I was better with recursion, myself.

Your computer can't be that crappy, however, because I found all 92 solutions with your program in 0.48 seconds (without drawing anything, of course). With drawing and no delay and no Input.Pause, it took 5.6 seconds. I'm on a P4 1.6 ghz.

Also, is it just me, or did you forget to check the rows in your clearSpot function? Shouldn't there be a:

code:

elsif grid (i, k) then             result false

after the code to check columns? Or is that not necessary, for some funky reason?
Finally, it sure would be nicer if i was x and j was y! 8)
Great job.

[zylum]

im glad you like my program

the reason i dont check if the column is valid is because i already know its valid. in the recursive function i place queens on empty columns (the functions parameter tells it what column its on).. once a queen is placed on the Nth column on a valid square then we know we have a solution..

btw to solve 8x8 *with* drawing, it took my computer 13.3 seconds lol.. im on a p3 733mHz