npuzzle

Overview

• The goal of this project is to solve the N-puzzle using the A* algorithm with admissible heuristics
• Heuristics used: Manhattan distance, Manhattan distance + Linear conflict, Misplaced tiles
• Bonus: visualizer => server + front (reactJS)

Usage

client/
npm install && npm start

assets/
python generator.py -s 3 > map

server/
make
./npuzzle -f ../assets/map -greedy -visualizer

./npuzzle:

• -f string
    File containing the puzzle to solve
  
• -greedy
  Use greedy search (if not true, uniform-cost search is used by default)
  
• -heuristic string
  Heuristics: Manhattan "m", Misplaced Tiles "mt" or Manhattan + Linear Conflict "mlc" (default "mlc")
  
• -visualizer
  Launch a web app to visualize results on your browser
  

Most effective configurations

• 3x3: Manhattan distance + Linear conflict in greedy search
• 4x4 and 5x5: Manhattan distance + Linear conflict in uniform-cost search