Start
Research
Students
Contests
Gallery
Games & projects
Links
Contact
History
|
Cold Basements
(see the problem statement in Polish)
are one of the problems from ONTAK 2013. A 20x15 maze contains
a guard and up to 6 treasures. Bythur and the guard alternately move
in 8 directions. The guard always moves in a way which minimalizes the Euclidean distance
from Bythur (in case of a tie the guard stays in place). An official algorithmic problem
was, given the board in an ASCII format, to determine the number of moves that Bythur has to make in order to gather the
maximum amount of treasures and exit the maze. An extra contest was about creating
a maze where Bythur has to make the greatest number of moves possible.
On this page you can enter your own maze and see Bythur's shortest route through it (among those which collect the greatest amount of treasures). You are encouraged to look at a solution with 1115 moves and try to find one which requires more moves (yes, it is possible to invent a better one by hand). I am planning to look at mazes sent by people from time to time. If I see something interesing, I am going to add it to the "solutions" section below. (You can sign the maze if you want) # - wall, A..Z - guard, $ - treasure, < - entrance, > - exit Solutions: II place on ONTAK: Michał Zieliński (1115 moves) (a board generated with a simple genetic algorithm). I place on ONTAK: Paweł Burzyński (1195 moves). I have managed to improve Paweł's solution (1636 moves). In August 2015, Tomek Czajka has found a much better solution (4888 moves). This solution was found with simulated annealing. Tweet |
Start
Badania
Studenci
Konkursy
Galeria
Gry/projekty
Linki
Kontakt
Historia