To place N tokens on an NxN grid so that no two tokens are on the same row, column, or diagonal. In terms of chess, it is to place N queens on a chess board with NxN squares so that none of them attack each other
To do this we must use a recursive depth first search, which is
also known as a backtrack search. The concept behind this algorithm is to
successively place the tokens in columns. When it is impossible to place a
token in a column (it is on the same diagonal, row, or column as another
token), the algorithm backtracks and adjusts a preceeding token.
I implemented my N Queens algorithm using the simplest, most primitive routines
possible. I have no pointers, or recursive calls. I make no use of any
conio.h or math.h functions. I use loops within loops to make my
algorithm work, and my procedure to see if a node is promising uses
incrementation of the row and column values to check to see if a queen
has been placed. It may not be pretty but it works.
The concept behind my algorithm is simple:
As the version I came up with is NON-recursive, the space requirements
are simple. The space taken up is dependent on the size of the board,
all other variables are constant in size. Therefore space requirement is
N^2, the size of the board.
I inserted a timer into my c++ code, in order to find the actual time it
took to run the program. I discovered that for n,1 where n is the number
of queens and 1 means that the search starts in the top left corner,
even n's were significantly slower, almost by a factor of 10! (All this
was done by using n=4 as a benchmark, and computing up to n=22).
Furthermore, plotting the graph suggested that time complexity was of
the order of 2^n.
The applications of backtracking (the general n-queens algorithm)
are varied: transportation: This algorithm could be used to compute the
most efficient bus/train/plane schedules and routes, so that two routes do
not overlap in coverage.
Placement of ANYTHING on a grid: Instead of row/column/diagonal
intersection the algorithm, the algorithm could check for distance, to
make sure that say, coverage of sprinklers on a farm are at there most
efficient, and no plot is covered by two sprinklers.
Wiring: Backtracking could be used to make sure that the wiring in a
building is most efficient, in reaching all the various things that use it.
More examples to come if I can think of any
My first attempts at attmepting to make it using a recursive algorithm
and dynamic storage allocation showed me that both methods were overly
complicated for a simple algorithm. So I tried solving it using while and
repeat until loops. Unfortunately they were transformed into a myriad of
goto statements, which I eventually cut down to two as I tightened up my
code. The first version was VERY long, and I spent a long time trying to
tighten up the loops, and the checking statements. At one point I even
considered using assembly to quicken up some problem areas.
The storage of the array is annoying. It took me a good hour until I
remembered that array sizes had to be constant in C++. So I set them up
as a hundered. An impossibly high number for this algorithm as after 29
even the odd numbered arrays take minutes to create, and at a time
complexity of 2^n, it probably blossoms into days by the mid 40's. I'd
hate to wait for the algorithm to solve n=100.
The time complexity was annoying. I tried solving it using standard math
techiniques, but discovered that my easy to program goto loops made it
very difficult to solve. So I resorted to the direct approach, I timed
how long it took to operate. I came up with 2^n. I think this is right,
and looking at other peoples pages it seemed a lot quicker than the n^n
and n! results (which if one thing, my approach showed to be WAY to high).
Doing this project I learned how to create graphics using neopaint, and
how to program using the html script.
If diagrams background is not matched perfectly by the projects
background, it is because your not using the standard sized netscape
screen. if you put it back to normal, you won't be able to tell where th
diagram begins, and the page does. Cool huh?
The n-queens problem was very fascinating. Now if I only was done
making the diagrams for it I could put more of them up here. I love making
cool diagrams. Like the one I have up there now? I made it using
neopaint, an excellent shareware program. Thought it was cool that the
background was the same as the rest of the page.
This project was good forsomething. Learned how to make menu's,
internal links, and colors in html.
Look for new advancements, and other stuff on my home page Like the wallpaper on this page? Want to send me a huge amount of money in appreciation of all my hard work? please tell me:
dtolman@yahoo.com
The following diagram shows the tree that the algorithm generates when n=4.
The numbering indicates the order in which the vertices are generated.
The solution is at the vertex 8
Thought Process Behind Code
1st: see if any spaces in a row is promising. Once one is found, place a
queen there.
2nd: Have we come to a solution. If we're on the nth row, and n
queens have been placed, the answer is yes. If we're still on the 1st
row, and no queen can be placed, there is no solution.If neither go to
then next row, and return to step one.
3rd:If we can't place any queens, but there is no positive or negative
solution backtrack. Go back to the last queen placed, erase it, goto the
next column, and return to step one. If we can't erase any more
queens, the problem is unsolvable, return negative result.
begin:
board=NxN array
top:
board(1,1):=1 // a queen is placed in top left
Call promising //see if any promising nodes
if promising=TRUE, board(x,y):=1 //if promising place a queen
if promising=TRUE x=x+1 // goto next row
if n queens placed return true //problem is solved
if row=1 and no queens placed,return false
//problem can't be solved
if no queens placed, begin:
backtrack to previous row, erase queen
have we tried all combo's?
If True, return false //problem can't be solved
column:=0
goto top //continue to loop until problem solved
// or all combos tried
Experience Report:
Author's
note:
And finally a word of thank to all the little people who gave me a hand
whether they knew about it or not.