N-PUZZLE, Oct-Nov 2015

A* pathfinder. (group project)

Grade (tbd/100) (tbd/125)*

---

Team: jaguillo / ngoguey.

Goals:

• Implement an A* algorithm.
• Implement 3 admissibles heuristics.
• Reach the 'snail solution' as 'goal solution' (see below)
• Handle any puzzle size without crashing.
• Grid loader (from file) and generator.
• Ouput some data from the solving phase.
• Solve an 8-puzzle in less than 5 seconds.

Recommended bonuses:

• Use approriate containers for A*.
• Provide an uniform-cost search.
• Provide a greedy search.

Our work:

• Opportunity to write our libftui(TODO: LINK!) (80% of our project), providing an high-level UI for this project and the next ones.
• Opportunity to use OCaml in a real project, for the first time.
• Disjoint Pattern Databases Heuristic(see below), allowing us to solve any 15-puzzles in less than 5 seconds.
• Careful study of graph traversal algorithms.
• IDA* implementation. (as extra)
• Database for linear conflict results

---

Install

curl -O http://www.lua.org/ftp/lua-5.3.1.tar.gz &&
tar -zxf lua-5.3.1.tar.gz &&
cd lua-5.3.1 &&
make linux &&
make test &&
sudo make install &&
cd .. &&
rm -rf lua-5.3.1.tar.gz lua-5.3.1

---

Useful links:

Pattern databases:

• https://www.jair.org/media/1480/live-1480-2332-jair.pdf

N-puzzle solvability:

• https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
• https://youtu.be/NuGDkmwEObM?list=PLB7540DEDD482705B&t=861

Misc:

• https://heuristicswiki.wikispaces.com/N+-+Puzzle

Snail solutions:

Disjoint Pattern Databases:

Linear conflict database:

Sample: Manhattan < Linear Conflict < Database 555 ~= Database 663

*
- A grade of 85 was required to validate the project.
- A maximum grade of 125 was reachable.
- Second sessions are organised for failed projects.

---