Solving the N-Queens-Problem Part I

This is the source-code to a series i'm going to start here in the coding-articles part.
It implements a genetic algorithm to solve the n-queens problem. The purpose of the algorithm is to be comprehensive not fast. I did not pick the fastest implemention as this would not have been that easy to comprehend. As you'll notice the limiting factor here (beside the selection-operator) is the space-complexity. The bigger the population-size the slower the algorithm performs. But it does find solutions for the 4,5,6,7 and 8-queens problem in acceptable time. This is the start of the series and i'm going to present some more algorithms for solving the n-queens-problem. Most of them will perfom much better.
There will also be one that can solve the problem for huge Ns. More on that in the next parts. Have fun and feel free to comment or criticize.

In will soon present a coding-article that explains in depth the theory behind this algorithm.
The algorithm itself is based on the techniques outlined in the very good book "Artificial Intelligence A Modern Approach" (International Edition)

Most of the code is standard r5rs scheme. But for example (printf) is not standard.
To test this you best grab chicken-scheme.

Please login to post comments.

closure

Posted 68 Days Ago

Hi, first you need to grab a copy of chicken-scheme. Depending on your os you may want to download either prepackaged packets or you go to call-with-current-continuation.org and check out the latest release there. Or you might even want to fetch current trunk from svn. Once you have the program all you need to do is invoke it with csi -s filename.scm. You can even (load) it into the repl and play with it. cheers

rbharatram

Posted 69 Days Ago

I'm new to Scheme How do i try to run this program?

Izzmo

Posted 82 Days Ago

The article is now out Cinjection!

Cinjection

Posted 97 Days Ago

Cool stuff. I can't wait until this article comes out. I've heard of this problem before, but I've never really looked into to. I guess I'll look at it more when the article comes out. Some of this code is still over my head. I guess I have a lot of Scheme to still learn :)

Page 1 of 1

Solving the N-Queens-Problem Part I
Recursive Lambdas with the Y and U Combinator
down the tree
simple constraint problem solver

Splitting a list recursively in Scheme
Genetic Algorithm for solving the N-Queens problem
Converting from infix notation to prefix and postfix notation
Factoring numbers
Path Finding

Splitting a list recursively in Scheme
down the tree
Solving the N-Queens-Problem Part I
Factoring numbers
Filtered Accumulator