Java - PuzzleManiac - Smart
Smart One
We've already used two ways of generating new combinations of bricks. The
Naive algorithm just throws them all together.
All others are smarter: they put the bricks
down one by one and check if everything is alright up to then. These algorithms
leave many free spaces between the bricks that are already placed. Smart
One will try to fill these free spaces by generating combinations in a
complete other way.
It searches for the first free place in the field starting from a certain
direction. All the places that come before this free place are already
filled. Then the algorithm tries to place one of the remaining bricks on
the board making sure that it covers the free place. Thus a new free place
is filled and the computer can go on searching for the next free place.
If there's none, the puzzle is solved. If there is, it tries to place a
brick on the board the same way as described before. This repeats itself
until the puzzle is solved. There is no need for a test here because it
fills all the gaps.
We will include one though. It starts the same way as the Space Checking
test. We count the free spaces in the free field and look wether or not
it's in a list. What list? The list we're speaking about is found as follows.
We know that we have to fill the free field with one or more bricks. Thus
the size of the free field must be the sum of the sizes of one or more
bricks. So we create a list containing all possible sums of sizes of bricks.
Any size that is not in this list is invalid. This test rejects many wrong
situations and only some slip through.
This algorithm is highly effective (it's about 1000 times faster on
a normal puzzle then the Space Check algorithm).
The time necessary to solve the puzzle is less dependant of the order in
which the bricks are presented. This makes it the ultimate weapon to aim
at a puzzle. Altough there is no need for the test (it even slows the algorithm
down) we left it in ecause otherwise there would be nothing to visualise.
Demonstration
Project verslag
PuzzleManiac page
Home