Course:CPSC312-2016-Project2-N-Puzzle

Slide Puzzle Game

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 allowing players actually play the game and still have the solver solve it for them if they need it. Additionally we can try adding a hint system where a player can ask for a hint which gives them the next best move.

What did we learn from doing this?

Functional programming is suitable for our game because were easily able to define the parameters and rules of the game. We represented our board as a list of positions, which allowed to define legal moves given the current board. After each move the game would be able to check if the game has been won. As this project was a continuation of our last one, we wanted to solve the problem of an unsolvable puzzles looping in the Prolog program. We learned how to determine if a puzzle is unsolvable and implemented it into our program. This formula for determining solvability is based on the number of inversions a puzzle has. If total inversions was odd the puzzle is unsolvable.

Including in the game was a system to ask the program for hints. To do this, the game would have to use a puzzle solver to create a workable solution and return the first move from the set of moves. 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. On this iteration we tried to implement the Manhattan distance of mismatched tiles. However, having the Manhattan distance alone is not sufficient to solve the puzzle. This due to the fact that some inversions may lead to the same Manhattan distance and the program will continuously loop between the inversion. A more sophisticated heuristic would be required to properly solve the puzzle optimally and felt that it was once again beyond the scope of our technical ability. We decided to allow the user to use the manhattan distance heuristic (which will work on simple boards), or to use the exhaustive search method which will attempt to solve the puzzle within N steps.

Unsolvable Puzzles

play [1,0,3,2,4,5,6,7,8] play [7,0,2,8,5,3,6,4,1]