N-Puzzle (version: javascript)

stack view

try live demo here 

The goal of this project is to solve the N-puzzle ("taquin" in French) game using the A*
search algorithm or one of its variants.

You start with a square board made up of N*N cells. One of these cells will be empty,
the others will contain numbers, starting from 1, that will be unique in this instance of
the puzzle.

Your search algorithm will have to find a valid sequence of moves in order to reach the
final state, a.k.a the "snail solution", which depends on the size of the puzzle (Example
below). While there will be no direct evaluation of its performance in this instance of the
project, it has to have at least a vaguely reasonable perfomance : Taking a few second to
solve a 3-puzzle is pushing it, ten seconds is unacceptable.

The only move one can do in the N-puzzle is to swap the empty cell with one of its
neighbors (No diagonals, of course. Imagine you’re sliding a block with a number on it
towards an empty space).

Todo list

  • add bloomFilter for the visited set for faster filtering than normal new set
  • comment all code in all files.
  • fix the greedy/uniform implementation
  • simplify the implemention of greedy condition in lib/node.js
  • add more heuristics (> 4)
    • manhattan
    • linear conflicts = (manhattan * 1.5 + conflicts)
    • hamming (missplaced)
    • gaschnig (details )
    • euclidean
    • diagonal
    • read more about heuristics here (click me )
  • support using one or multiple heuristic
  • update the puzzle parser for more accuracy and error handling
  • add solvability checker
  • config the solver to add type of target puzzle option (zero last, zero first, snail)
  • create seprate method functions for the heuristics
  • pack all the Puzzle solver into one package
  • add support of BFS + DFS search algorithms alongside with A*
  • write unit tests for the engine
    • ASTAR
    • BFS
    • DFS
    • file parser
    • puzzle generator
    • solvability checker
    • heuristics score
  • add folder to contain different puzzle inputs file for testing
  • create an UI for n-puzzle using the package created in previous task (99%)

Documentation

incomming…