8 queens solution via the hill climbing algorithm

Question

1.00/5 (1 vote)

See more:

, +

Hello all,

I'm looking for a C/C++/C#/Perl implementation of the solution to the "8 queens" problem via a "Hill Climbing" algorithm.

I found tons of theoretical explanations on that specific issue on the web but not a single code example.

A moment before I sit down to code this piece of AI myself, I wanted to ask if any of you good people can point me to what I'm looking for.

Thanks in advance,
Matthew.S.

Posted 17-Nov-10 21:32pm

sigurko

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Manfred Rudolf Bihy · Accepted Answer · 2010-11-17T22:58:00

Hi Matthew,

this kind of smells like homework, but I'll give you a couple of hints anyhow.
I hope you understand the 8 queens problem so I wont go into that.

"Hill Climbing" algorithms start at a randomly selected start point, and
try to do small gradual optimizations trying to obtain a solution (which
may not even exist).

So I'd start this by placing the first queen on a randomly selected position
on the board.

Place the next queen on the board (randomly of course). Two things can happen now:
1. No collision of queens -> proceed with next queen
2. Queens collide -> move queen to next available position and re-check until either there are no more available positions or the collision is resolved.
(Remember to wrap around to top left corner when leaving bottom right corner of board until starting position of queen is reached)

If a queen was moved all over the board without finding a collision free position. The previously placed queen needs to be repositioned (randomly of course).

This should give you a pretty good idea to start implementing a straight forward algorithm.

Best Regards,

Manfred