Student research opportunities

EternityII: Solving Edge Matching Puzzles

Project Code: CECS_689

This project is available at the following levels:
CS single semester, Honours, Summer Scholar
Please note that this project is only for undergraduate students.

Keywords:

Tiling puzzles, artificial intelligence, constraint propagation, search, heuristics

Supervisor:

Professor Sylvie Thiebaux

Outline:

Edge matching puzzles are hard (NP-complete) computational problems which involve tiling an area with regular polygons in such a way that the colors of the edges of adjacent tiles match.

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. Details about the puzzle can be found below. The final date for discovering a complete solution and claiming the prize has elapsed with no winner.

Goals of this project

It is extremely unlikely that you will solve the puzzle, but attempting to do so will give you an opportunity to learn a range of artificial intelligence and operations research techniques whilst having fun. And who knows, you might break the record of the highest number of matching edges.

Requirements/Prerequisites

Enrolled in Computer Science or Mathematics degree. Decent programming skills.

Student Gain

The project will give the student an opportunity to deepen the knowledge of certain areas of Artificial Intelligence acquired during a basic AI course (such as ANU COMP 3620). It is also possible to do this project without any background in AI.