Friday, July 18, 2008

Eight Queen Code

[Updated for Silverlight 2]

I blogged previously about the N-Queen problem. Here I am going to explain how I did it.

The Board and the Queen
I used a StackPanel to hold the Board and the button. The board is a 8x 8 Grid. And empty at design time. Also have a event handler for the button Click.
The Queen is a user control having just a Image with a white Background.
Now adding one Canvas for each square and painting it with blackish or whitish gradient brush already created as a resource

Repeating this for 64 squares.


Canvas c = new Canvas();

if ((row + col) % 2 == 0)

{

c.Background = (LinearGradientBrush)Resources["BlackBrush"];

}

else

{

c.Background = (LinearGradientBrush)Resources["WhiteBrush"];

}

Also having a blue hidden rectangle in each square that shows up when that square is being traversed and creates a nice animation. Also having a global variable for storing the squares and blue rectangles as we need them later.

For adding and removing the Queen I am using this code.

Sqare[row, col].Children.Add(new Queen());

Sqare[row, col].Children.RemoveAt(0);

The Animation

The animation for the blue rectangle is like the following.


<Storyboard x:Name="AnimSquare" Storyboard.TargetProperty="Opacity" Duration="0:0:0.2">

<DoubleAnimationUsingKeyFrames BeginTime="00:00:00">

<SplineDoubleKeyFrame KeyTime="00:00:00" Value="0"/>

<SplineDoubleKeyFrame KeyTime="00:00:00.1" Value="1"/>

<SplineDoubleKeyFrame KeyTime="00:00:00.13" Value="0"/>

</DoubleAnimationUsingKeyFrames>

</Storyboard>


See there is no target name defined for the storyboard as we will be applying different square (The blue rectangle over the square exactly) as target.


AnimSquare.Stop();

Storyboard.SetTarget(AnimSquare, SquareMask[Grow, Gcol]);

AnimSquare.Begin();

The Algorithm

The algorithm is as follows.

As there will be 8 Queens for 8 rows there will be one at each row.

Start from the left top square.

Put a Queen if that does not captured by other queens.

Jump to the next row and try it for 8 squares in that row.

If unsuccessful then go to previous row and remove the previous Queen placed there and try another square that have not been tried for that row.

If that also unsuccessful go to lower rows until you find a new square to put the queen in that row.

This can be achieved with a recursion.


private void PlaceQueen(int row, int col)

{

if (row == NoOFQueen) return; //Get out of recursion

CheckedCol[row] = col;

if (IsSafe(row, col))

{

if (!flag)

{

PutQueen(row, col);

row++;

col = 0;

}

else

{

CheckedCol[row] = 0;

row--;

RemoveQueen(row, CheckedCol[row]);

col = CheckedCol[row] + 1;

}

}

else

{

if (col == (NoOFQueen - 1)) // No where to place queen in the row

{

CheckedCol[row] = 0;

row--;

RemoveQueen(row, CheckedCol[row]);

}

else

{

col++;

}

}

//Grow = row; Gcol = col;

PlaceQueen(row, col);

}

Now the methods used here are self explanatory and simple. There is only one tricky part in this recursion. That is the boolean flag. It keeps the track if the queen from the last column has been removed. So next there wont be any queen placed on that column even if the square is safe. It will go farther one level down and so. The flag is set false whenever a new queen is placed on the board.

There I did a little change in this method. Instead of calling the same method from PlaceQueen it has been called from a Tick event of a timer to enable animation. (see the commented Grow and Gcol. G for global ).

This version of my program is still yet needs optimization and some code cleanup. It does not check if something unexpected happens. It doesnt even have a safecounter for getting out of recursion in case 8 Queens can not be placed at all.

Here is the demo.

And you can download the complete source from here.

for any clarification or modification please leave a comment.

2 comments:

Anonymous said...

Can you re-upload the 8-queen source code? It appears to have been taken down.

Thanks,

Tanmoy Rajguru said...

Please check it now. I have uploaded it again. :)