Eight Queens Algorithm

As Part of my final project in Visual c++ course i had to write a program that implement the Eight Queens problem visually.

In this tutorial I will show what algorithm I have developed and I will give the source code.

But first, lets take a look at the Eight Queens problem.

Eight Queens Problem

This problem is probably as old as the check game itself.

The principal is to place 8 queens on board, and none of the queen shouldn't threat on the other 7.

Sounds easy, isn't it?

Well, there are 92 solution for this problem but if we reduce duplicates we left with only 12 solutions.

Lets take a look in one solution. For example:

As we can see from the board above, none of the queen threats on any other queen.

There are many algorithms that give all the possible solutions.

But what if we want to place a queen on any place on the board and check if it is a valid place?

My algorithm does it.

First, lets see the source code in C

Explenation

I see the board as a 8X8 matrices. The matrices is initialize to 1 on first run. Every time there is a valid place then this place turned into -1. I.e. turn off its validity existence.

When i place a queen on board, all I have to do is to move all directions including diagonals and check that I don't stand in a "-1" place.

Now, lets talk positions.

We can watch the matrices in that form:

Or, we can watch the matrices in that form:

See the difference?

That's how I move across the matrices. I simply convert between regular position and regular numbers and vise versa.

Functions

There are 3 major functions:

1.  VarUnion - union row,col into one number.

2. DissAssembly - dissassembly the number into row and col.

3. Check - check place validity.

VarUnion and DissAssembly are service functions to Check function.

In Check function I move across the matrices and check if the place is valid and that I didn't reached to the matrices border.

If you have any comments, suggestions or questions please email me to eran@4utv.co.il