In today's project you are going to implement this game, but we will generalize it to grids of arbitrary size. Here is an example run:
> scala sliding.scala 3 4
o----o o----o o----o o----o
| | | | | | | |
| 7 | | 6 | | 3 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 8 | | 1 | | 10 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o
| | | | | |
| 9 | | 2 | | 5 |
| | | | | |
o----o o----o o----o
What is your move> d
o----o o----o o----o o----o
| | | | | | | |
| 7 | | 6 | | 3 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o
| | | | | |
| 8 | | 1 | | 10 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move> left
o----o o----o o----o o----o
| | | | | | | |
| 7 | | 6 | | 3 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o
| | | | | |
| 8 | | 1 | | 10 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move> l
o----o o----o o----o o----o
| | | | | | | |
| 7 | | 6 | | 3 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o
| | | | | |
| 8 | | 1 | | 10 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move> D
o----o o----o o----o
| | | | | |
| 7 | | 6 | | 11 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 8 | | 1 | | 3 | | 10 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move> R
o----o o----o o----o
| | | | | |
| 7 | | 6 | | 11 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 8 | | 1 | | 3 | | 10 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move> u
o----o o----o o----o o----o
| | | | | | | |
| 7 | | 1 | | 6 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o
| | | | | |
| 8 | | 3 | | 10 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 4 | | 9 | | 2 | | 5 |
| | | | | | | |
o----o o----o o----o o----o
What is your move>
We will build up the game one function at a time. Write one function, and test each function using Scala's interactive mode before you go on to the next function.
This function will create the playing field for us. It takes two arguments, and returns a two-dimensional array of integers:
def makeField(rows: Int, cols: Int): Array[Array[Int]] = {
Here are some tests:
scala> :load sliding.scala Loading sliding.scala... makeField: (rows: Int, cols: Int)Array[Array[Int]] scala> makeField(2, 2) res1: Array[Array[Int]] = Array(Array(1, 2), Array(3, 0)) scala> makeField(3, 4) res2: Array[Array[Int]] = Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 0))
Note that field is a two-dimensional array, or, more precisely, an array of arrays. Two create such an array, you first need to create the outer array:
field = new Array[Array[Int]](rows)At this point, every slot of field is null. You have to fill them in one by one:
for (row <- 0 until rows) field(row) = new Array[Int](cols)Once this is done, you can use field as a two-dimensional grid. The cell at position row, col can be accessed as field(row)(col).
This function displays the grid of tiles. The number zero corresponds to the empty tile—you have to leave its spot empty. Here are some tests:
scala> :load sliding.scala Loading sliding.scala... makeField: (rows: Int, cols: Int)Array[Array[Int]] displayField: (field: Array[Array[Int]])Unit scala> val f1 = makeField(2, 3) f1: Array[Array[Int]] = Array(Array(1, 2, 3), Array(4, 5, 0)) scala> val f2 = makeField(4, 4) f2: Array[Array[Int]] = Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12), Array(13, 14, 15, 0)) scala> val f3 = makeField(3, 9) f3: Array[Array[Int]] = Array(Array(1, 2, 3, 4, 5, 6, 7, 8, 9), Array(10, 11, 12, 13, 14, 15, 16, 17, 18), Array(19, 20, 21, 22, 23, 24, 25, 26, 0)) scala> displayField(f1) o----o o----o o----o | | | | | | | 1 | | 2 | | 3 | | | | | | | o----o o----o o----o o----o o----o | | | | | 4 | | 5 | | | | | o----o o----o scala> displayField(f2) o----o o----o o----o o----o | | | | | | | | | 1 | | 2 | | 3 | | 4 | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o o----o | | | | | | | | | 5 | | 6 | | 7 | | 8 | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o o----o | | | | | | | | | 9 | | 10 | | 11 | | 12 | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o | | | | | | | 13 | | 14 | | 15 | | | | | | | o----o o----o o----o scala> displayField(f3) o----o o----o o----o o----o o----o o----o o----o o----o o----o | | | | | | | | | | | | | | | | | | | 1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 | | 8 | | 9 | | | | | | | | | | | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o | | | | | | | | | | | | | | | | | | | 10 | | 11 | | 12 | | 13 | | 14 | | 15 | | 16 | | 17 | | 18 | | | | | | | | | | | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o o----o | | | | | | | | | | | | | | | | | 19 | | 20 | | 21 | | 22 | | 23 | | 24 | | 25 | | 26 | | | | | | | | | | | | | | | | | o----o o----o o----o o----o o----o o----o o----o o----o
Since we want to practice case classes, let's define a class Pos to represent a position on the field:
case class Pos(row: Int, col: Int)
Now write a function findEmpty that takes a field and finds the position of the empty tile:
def findEmpty(field: Array[Array[Int]]): Pos = {
Here are some example tests (using the definitions above):
scala> findEmpty(f1) res6: Pos = Pos(1,2) scala> findEmpty(f2) res7: Pos = Pos(3,3) scala> findEmpty(f3) res8: Pos = Pos(2,8)
The most important function performs a move on the board. It takes a Pos argument which indicates the direction of the move, namely:
scala> val left = Pos(0, 1) left: Pos = Pos(0,1) scala> val right = Pos(0, -1) right: Pos = Pos(0,-1) scala> val up = Pos(1, 0) up: Pos = Pos(1,0) scala> val down = Pos(-1, 0) down: Pos = Pos(-1,0) scala> displayField(f1) o----o o----o o----o | | | | | | | 1 | | 2 | | 3 | | | | | | | o----o o----o o----o o----o o----o | | | | | 4 | | 5 | | | | | o----o o----o scala> makeMove(f1, down) scala> displayField(f1) o----o o----o | | | | | 1 | | 2 | | | | | o----o o----o o----o o----o o----o | | | | | | | 4 | | 5 | | 3 | | | | | | | o----o o----o o----o scala> makeMove(f1, right) scala> displayField(f1) o----o o----o | | | | | 1 | | 2 | | | | | o----o o----o o----o o----o o----o | | | | | | | 4 | | 5 | | 3 | | | | | | | o----o o----o o----o
So makeMove uses findEmpty to find the empty spot, and then moves the tile from the neighboring spot:
def makeMove(field: Array[Array[Int]], delta: Pos) {
val now = findEmpty(field)
val upd = Pos(now.row + delta.row, now.col + delta.col)
field(now.row)(now.col) = field(upd.row)(upd.col)
field(upd.row)(upd.col) = 0
}
Of course you also have to check that position upd is really on
the field.
Now we need a function that creates a random starting configuration. We cannot simply use a random permutation of the tiles, since then we wouldn't know if the puzzle can be solved. So we start with a solved puzzle, and then perform a sequence of, say, 1000 random moves to shuffle it. To make your life easier, here is a function that does this:
def shuffle(field: Array[Array[Int]], iter: Int) {
val moves = Array(Pos(1,0), Pos(-1,0), Pos(0,1), Pos(0,-1))
for (i <- 1 to iter) {
val mov = moves((math.random * 4).toInt)
makeMove(field, mov)
}
}
Here is a test:
scala> val f = makeField(4, 4)
f: Array[Array[Int]] = Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12), Array(13, 14, 15, 0))
scala> shuffle(f, 1000)
scala> displayField(f)
o----o o----o o----o
| | | | | |
| 3 | | 8 | | 10 |
| | | | | |
o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 9 | | 5 | | 15 | | 11 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 1 | | 12 | | 4 | | 14 |
| | | | | | | |
o----o o----o o----o o----o
o----o o----o o----o o----o
| | | | | | | |
| 13 | | 7 | | 6 | | 2 |
| | | | | | | |
o----o o----o o----o o----o
Now we need a function strToMove that takes the user's input and converts it to a Pos object:
def strToMove(s: String): Pos = {
The function should look at the first non-white letter, and both
uppercase and lowercase letters should work:
scala> strToMove(" left ")
res2: Pos = Pos(0,1)
scala> strToMove(" Left ")
res3: Pos = Pos(0,1)
scala> strToMove("r")
res4: Pos = Pos(0,-1)
scala> strToMove(" UP")
res5: Pos = Pos(1,0)
scala> strToMove(" DN ")
res6: Pos = Pos(-1,0)
scala> strToMove(" XYZ ")
res7: Pos = Pos(0,0)
scala> strToMove("")
res8: Pos = Pos(0,0)
Any unrecognized string (including the empty string) results in
Pos(0,0).
Here is a function to run the game based on the functions we already have:
def playGame(rows: Int, cols: Int) {
val f = makeField(rows, cols)
shuffle(f, 1000)
while (true) {
displayField(f)
val s = readLine("What is your move> ")
println()
if (s == "quit")
return
val move = strToMove(s)
makeMove(f, move)
}
}
Test this function from Scala's interactive mode.
Finally, use the command line arguments so that you can start the script sliding.scala with arguments for the number of rows and columns. If the script is called without arguments, then the number of rows and columns is four.
You can now improve your program by adding two more features: First, keep a counter of the number of moves, and display it in every round. Second, the game should recognized when the puzzle has been solved, and terminate automatically, printing a congratulation message to the user with the number of moves that the player used.