This site requires JavaScript, please enable it in your browser!
Greenfoot back

Report as inappropriate.

GershiBelshi
GershiBelshi presents ...

2011/3/18

Eight Queen Problem

http://en.wikipedia.org/wiki/Eight_queens_puzzle

The Eight Queen Problem is a classical
problem that concerns the question
"how can we place eight queen on a
chess board so that non of the queens
are threatened by any of the other
queens?"

This program solves it automatically
for you.

There is also additional functionality
in this program. It allows you to
place a queen in a place of your
own choice and to resize the board.

Here a brief instruction for using
each of the functions:

Solve:
Press the solve button to make the
program solve the problem for the
given conditions.

Place Q:
This function lets you place a queen.
Move the green square up, down, left,
and right and press enter when it
is on the spot in which you want
your queen to be placed. A queen
cannot be placed on a flower. If
you want to cancel placing a queen
press the space button.

Resize:
The resize function lets you resize the board in the range 1-11.
Press the resize button, then type
the number that you want the board
to be resized to and press enter.
The resize function also clears the
board.

Clear:
This function simply clears the
board of any flowers and queens.

Flowers:
The flowers indicate threatened positions. Queens cannot be placed
on flowers.


This project was inspired by the GridWorld case-study.


All rights reserved to GershiBelshi (C) 2011.

3917 views / 616 in the last 7 days

3 votes | 0 in the last 7 days

Tags: simulation with-source

open in greenfoot
Your browser is ignoring the <APPLET> tag.
HTML5 version not available | Scenario not running?
A new version of this scenario was uploaded on Fri Mar 18 00:42:41 UTC 2011 http://en.wikipedia.org/wiki/Eight_queens_puzzle The Eight Queen Problem is a classical problem that concerns the question "how can we place eight queens on a chess board so that non of the queens are threatened by any of the other queens?" This program solves it automatically for you. There is also additional functionality in this program. It allows you to place a queen in a place of your own choice and to resize the board. Here a brief instruction for using each of the functions: Solve: Press the solve button to make the program solve the problem for the given conditions. If you want to get the solution without going through the animation, press the pause button while the animation is running. Place Q: This function lets you place a queen. Move the green square up, down, left, and right and press enter when it is on the spot in which you want your queen to be placed. A queen cannot be placed on a flower. If you want to cancel placing a queen press the space button. Resize: The resize function lets you resize the board in the range 1-11. Press the resize button, then type the number that you want the board to be resized to and press enter. The resize function also clears the board. Clear: This function simply clears the board of any flowers and queens. Flowers: The flowers indicate threatened positions. Queens cannot be placed on flowers. This project was inspired by the GridWorld case-study. All rights reserved to GershiBelshi (C) 2011.
A new version of this scenario was uploaded on Fri Mar 18 00:43:42 UTC 2011
GershiBelshiGershiBelshi

2011/3/18

Please give me feedback!
TimTim

2011/3/20

Excellent job! Looping through the possible moves is essentially doing a depth first search of the possible positions. Have you considered trying to solve using bit boards? It might be fun for you. If you don't know, a bit board is simply a 64-bit integer that has a 1 or 0 for each square on the board. For this problem you could have a bit board representing the location of all queens currently on the board (1s for squares with queens and 0s for empty squares). You could then have a bit board representing all positions that would be under attack by a queen if placed in a certain square. Performing a bitwise AND between those two bit boards will result in a 0 if no queen would be under attack in that position or a number >0 if at least one queen would be under attack. The advantage of this is that it doesn't require looping and bitwise operations take a single clock cycle on a 64bit processor. Bit boards are very common for game theory in games played on 8x8 grids.
kongxingakongxinga

2011/3/20

Impressive!

Want to leave a comment? You must first log in.

Who likes this?

nachocab jogit666 kongxinga