Course:CPSC312-2016-Project1-SlidePuzzleSolver

Slide Puzzle Solver

Authors: Ha Nguyen, Vincent Chan, Hoi Ting Tai

What is the problem?

A sliding puzzle is a game where you get a grid of square pieces of a picture that is scrambled where one space is left empty. This is a space that the player uses to slide around the square pieces until the puzzle picture is unscrambled.

Our Slide Puzzle Solver will take in a 3x3 puzzle (a list of numbers) and solve the puzzle for you. It will return a list of which pieces you should move in the order that they should be moved. For example, the given starting puzzle board may be:

  1   2   3
  6   4   
  7   5   8

This would be represented in our solver by a list, from left to right and top to bottom and with s representing the space: [1,2,3,6,4,s,7,5,8]. For our solver, we declared the solution for all the puzzles to be [1,2,3,4,s,5,6,7,8] where the space is in the center piece. We called this the end board.

What is the something extra?

Our something extra will be in the way we solve the sliding puzzle through prolog. If the original puzzle isn't difficult enough, we will attempt to add a new aspect to the puzzle (e.g. add more empty spaces) that makes it harder to solve (for our prolog problem) or solve it such that we use the least number of moves possible.

What did we learn from doing this?

(This should be written after you have done the work.) What is the bottom-line? Is logic programming suitable for (part-of) the task? Make sure you include the evidence for your claims.

Yes, logic programming is suitable for this problem because we can logically define the rules for solving the the puzzle. The rules can be given as facts that define legal moves given the current board. With the board and rules defined, we can recursively look for our solution. The resulting program is relatively short, easy to read, and easy to understand.

We found that depending on the ordering of the move predicates (left, up, down, right), a solution path can be many orders larger than the optimal solution. For example, if the left predicate is the first one listed (meaning the program will go left first) and a board that is solved by moving the space exactly one to the right, the solution will try to go left first and find an unoptimal solution from there.

  Goal       Input            Possible Solution when program moves up first
  1 2          1 2               s 2    2 s    2 3    2 3    s 3    3 s    3 1    3 1    s 1    1 s    1 2      
  3 s          s 3               1 3    1 3    1 s    s 1    2 1    2 1    2 s    s 2    3 2    3 2    3 s

To solve the problem of generating longer than necessary answers, we modified the solution to take in an additional parameter, N, which limits the search to N or less possible moves. Now, if the board can be solved within 1 move, prolog will not continue any answers that are longer than N moves. This helps solve the problem with running out of local stack space due to the huge number of branches and solutions at each recursive step. Moreover, we know that the 8-puzzle can always be solved within 31 moves (https://en.wikipedia.org/wiki/15_puzzle).

A possible solution to generating the most optimal path would be using a heuristic function that predicts the next best move to make. This could be achieved by looking at how many tiles are mismatched at each branch or the sum of the distance to travel of the mismatched tiles. If moving up generates a higher mismatch tile distance than going down, then the program should go down instead. While there are many studied heuristic algorithms available, we believe this went beyond the scope of our project as the algorithms themselves tended to be more mathematical and difficult to understand.