|
Home
Inroduction:
In this project of we are trying to solve edge matching puzzle by
search algorithms (mostly Genetic Algorithm and Multiobjective
Evolutionary Algorigthm).
This problem is taken from "Eternity II Puzzle".The Eternity II Puzzle
is a particularly hard tiling puzzle comprising 256 squares tiles and 22
colors that was
released in 2007 as part of a competition to win 2M USD.
Edge matching puzzles are hard (NP-compute) Computational problems.
Here puzzle problem is discribed as, the puzzle constists a board with
some 'r' rows and 'c' columns. The board filled with 'n(=rXc)' square
tiles. Each of
these has one colour for each side. Tile can move and can rotate 90, 180
and 270 degree. The aim is to cover the floor with these tiles. A tile
can be
placed adjacent to another if and only if the touching edge of the tiles
match. The challenge is to cover maximum area in minimum time possible.
Motivation:
Considering the popularity of the games over the years, yet it
remains a challenging puzzle. Since it is extremely unlikely to solve
the puzzle, but attempt
to do so provides an opportunity to learn the range of artificial
intelligence and operations research techniques, alongwith.
Due to its huge search space(For the 256 tile puzzle there are: 256! ×
4256 = 1.15 × 10661 possible tile combinations.) and challenges of
dealing them, the
project creates an opportunity to deepen the knowledge of certain areas
of Search Algorithms in Artificial Intelligence.
Objectives:
(a) The first objective is to maximize the number of matching edges in colour,
(b) second objective is to maximize number of square regions of 2 by 2 tiles that match in their adjacent inner sides and
(c) third objective to maximize the number of tiles that have their four sides matched with the adjacent tiles.
The Implementation(back-tracking algorithm) Overview:
-Randomly generate a valid board.
-Jumble the tiles and remove them from the board.
-Place a tile onto the board in a valid position - i.e. the sides match neighbouring tiles or edge-colours.
-If there are no possible tiles left that fit the board then remove the previous tile and try alternatives.
-Repeat from 3. until the board is full.
Related Works:
(a) Marc labers: Marc labers implemented a C++Code
which runs fairly well on low dimensional puzzles. Doc solver works by
first
creating arrays that list the pieces that will have given colors on
certain edges. This means that finding a piece with, say a green left
edge and a red top
edge, requires indexing the 2 dimensional array storing left and top
matching pieces with the code for a green edge and the code for a red
edge. The solver
works by starting at the top left corner and tiling towards the bottom
right corner, so there is no need for an array that would contain
matches for say, only
top and bottom edges. If the solver reaches a dead end, it backtracks
recursively to the last decision point and tries again. Once the solver
reaches the lower
right corner, a solution has been found.
References:
(1) Jorge Munoz, German Gutierrez and Araceli Sanchis, University
Carlos III of Madrid Avda. de la Universidad 30, 28911 Legan ́s, Spain
(2009).
(PDF)
(2) Marijn J.H. Heule, Department of Software Technology, Faculty of
Electrical Engineering, Mathematics and Computer Sciences, Delft
University
of Technology(2008).(PDF)(Pages 69 to 82)
(3) Wim Vancroonenburg , Tony Wauters , and Greet Vanden Berghe, CODeS
research group, KaHo Sint-Lieven, Gebroeders Desmetstraat 1, 9000 Gent,
Belgium.
(PDF)
|