2009-11-10 - SOLVING THE SLIDER PUZZLE part 1 - Introduction
This series of articles is based on the Sliding Around article on the Daily WTF. In this first part I will tell you more about the modelling of the slider puzzle and how the model discussed here could be extended even further.
1 | 2 | 3 ---+---+--- 4 | 5 | 6 ---+---+--- 7 | 8 | _
Used files:
PuzzleState.java: State of a n*n sliderpuzzle.
Position.java: small class to keep track of 2 integers that define a position in the grid.
Main.java: contains main function and the actual solvers.
There are several ways you can keep track of where all the pieces in the puzzle are. One way would be to just have 9 integers keeping track of each piece, 0 being the empty square. Another way would be to have a single or multidimensional array or vector. I chose for a one-dimensional array because it allowed me to work not with only puzzles of 3*3 but also 4*4 or any other number of pieces on the side.
That vector however, is on the inside. What is important in a class are the public funtions and what they do. There 1 constructor. It will create a correctly solved puzzle with a edge-size of n. There is also a static method called createRandom. This function will return a puzzlestate with size n that has had x random moves. Thus this function always creates a solvable puzzle.
isCorrect will return true when the puzzle is correctly solved.
getSquare will return the value at the given position. Should the position be out of bounds an assert will trigger. getEmptySquare will return the position of the empty square.
makeMove returns the puzzlestate following at the moving the piece at the specified direction into the empty space. If a move should not be possible, (being at the edge) the function will return null.
example of the result of a moving the piece to the left of the empty square:
1 | 2 | 3 ---+---+--- 4 | _ | 6 ---+---+--- 7 | 8 | 5 1 | 2 | 3 ---+---+--- _ | 4 | 6 ---+---+--- 7 | 8 | 5
As last function there is getPossibleMoves which will return all possible puzzlestates following a move from this puzzlestate. toString and equals have no special prequisites and do what you expect them to do.
This was an overview of puzzlestate. In the next part I will discuss how I made 2 solvers for this state and what else I would need for other solution methods.
