A sliding puzzle

You probably know the 15-puzzle, where you start with 15 tiles in a 4x4 square, initially in a random permutation, and the goal is to arrange them in the correct order. The only allowed move is to slide a tile into the empty spot, so there are at most four legal moves: up, down, left, and right.

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:

$ kts sliding.kts 3 4
o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 10 | |  5 | |  7 | | 11 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  1 | |  2 | |  6 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
       o----o o----o o----o 
       |    | |    | |    | 
       |  3 | |  8 | |  4 | 
       |    | |    | |    | 
       o----o o----o o----o 
What is your move> d

o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 10 | |  5 | |  7 | | 11 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
       o----o o----o o----o 
       |    | |    | |    | 
       |  1 | |  2 | |  6 | 
       |    | |    | |    | 
       o----o o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
What is your move> left

o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 10 | |  5 | |  7 | | 11 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o        o----o o----o 
|    |        |    | |    | 
|  1 |        |  2 | |  6 | 
|    |        |    | |    | 
o----o        o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
What is your move> l

o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 10 | |  5 | |  7 | | 11 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o        o----o 
|    | |    |        |    | 
|  1 | |  2 |        |  6 | 
|    | |    |        |    | 
o----o o----o        o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
What is your move> D

o----o o----o        o----o 
|    | |    |        |    | 
| 10 | |  5 |        | 11 | 
|    | |    |        |    | 
o----o o----o        o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  1 | |  2 | |  7 | |  6 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
What is your move> R

o----o        o----o o----o 
|    |        |    | |    | 
| 10 |        |  5 | | 11 | 
|    |        |    | |    | 
o----o        o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  1 | |  2 | |  7 | |  6 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
What is your move> u

o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 10 | |  2 | |  5 | | 11 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o        o----o o----o 
|    |        |    | |    | 
|  1 |        |  7 | |  6 | 
|    |        |    | |    | 
o----o        o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  3 | |  8 | |  4 | 
|    | |    | |    | |    | 
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 the interactive mode before you go on to the next function.

makeField

This function will create the playing field for us. It takes two arguments, and returns a two-dimensional array of integers:

fun makeField(rows: Int, cols: Int): Array<Array<Int>> {
  // ...
}

Here are some tests:

>>> :load sliding.kts
>>> val r1 = makeField(2, 2)
>>> r1.joinToString(separator="\n", transform={ it.joinToString() } )
1, 2
3, 0
>>> val r2 = makeField(4, 7)
>>> r2.joinToString(separator="\n", transform={ it.joinToString() } )
1, 2, 3, 4, 5, 6, 7
8, 9, 10, 11, 12, 13, 14
15, 16, 17, 18, 19, 20, 21
22, 23, 24, 25, 26, 27, 0

Note that field is a two-dimensional array, or, more precisely, an array of arrays. You can create such an array with the following syntax:

  field = Array(rows) { Array(columns) { 0 } }

The cell at position row, col can now be accessed as field[row][col].

displayField

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:

>>> val f1 = makeField(2, 3)
>>> val f2 = makeField(4, 4)
>>> val f3 = makeField(3, 9)
>>> 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        
>>> 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        
>>> 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        

findEmpty

Since we want to practice data classes, let's define a class Pos to represent a position on the field:

  data class Pos(val row: Int, val col: Int)

Now write a function findEmpty that takes a field and finds the position of the empty tile:

fun findEmpty(field: Array<Array<Int>>): Pos {
  // ...
}

Here are some example tests (using the definitions above):

>>> findEmpty(f1)
Pos(row=1, col=2)
>>> findEmpty(f2)
Pos(row=3, col=3)
>>> findEmpty(f3)
Pos(row=2, col=8)

makeMove

The most important function performs a move on the board. It takes a Pos argument which indicates the direction of the move, namely:

>>> val left = Pos(0, 1)
>>> val right = Pos(0, -1)
>>> val up = Pos(1, 0)
>>> val down = Pos(-1, 0)
>>> 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        
>>> makeMove(f1, down)
>>> 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 
>>> makeMove(f1, right)
>>> 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:

fun makeMove(field: Array<Array<Int>>, delta: Pos) {
  val rows = field.size
  val cols = field[0].size
  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 need to add a check that position upd is really on the field.

shuffle

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:

val random = java.util.Random()

fun shuffle(field: Array<Array<Int>>, iter: Int) {
  val moves = arrayOf(Pos(1,0), Pos(-1,0), Pos(0,1), Pos(0,-1))
  for (i in 1 .. iter) {
    val mov = moves[random.nextInt(4)]
    makeMove(field, mov)
  }
}

Here is a test:

>>> val f = makeField(4, 4)
>>> shuffle(f, 1000)
>>> displayField(f)
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  9 | |  5 | | 13 | | 14 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o o----o        
|    | |    | |    |        
|  6 | |  4 | |  3 |        
|    | |    | |    |        
o----o o----o o----o        
o----o o----o o----o o----o 
|    | |    | |    | |    | 
| 12 | |  8 | | 11 | |  1 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 
o----o o----o o----o o----o 
|    | |    | |    | |    | 
|  7 | | 10 | |  2 | | 15 | 
|    | |    | |    | |    | 
o----o o----o o----o o----o 

strToMove

Now we need a function strToMove that takes the user's input and converts it to a Pos object:

fun strToMove(s: String): Pos {
  // ...
}

The function should look at the first non-white letter, and both uppercase and lowercase letters should work:

>>> strToMove(" left ")
Pos(row=0, col=1)
>>> strToMove("  Left ")
Pos(row=0, col=1)
>>> strToMove("r")
Pos(row=0, col=-1)
>>> strToMove("  UP")
Pos(row=1, col=0)
>>> strToMove("  DN  ")
Pos(row=-1, col=0)
>>> strToMove("  XYZ ")
Pos(row=0, col=0)
>>> strToMove("")
Pos(row=0, col=0)

Any unrecognized string (including the empty string) results in Pos(0,0).

The main game

Here is a function to run the game based on the functions we already have:

import org.otfried.cs109.readString

fun playGame(rows: Int, cols: Int) {
  val f = makeField(rows, cols)
  shuffle(f, 1000)
  while (true) {
    displayField(f)
    val s = readString("What is your move> ")
    println()
    if (s == "quit")
      return
    val move = strToMove(s)
    makeMove(f, move)
  }
}

Test this function from the interactive mode.

Command line arguments

Finally, use the command line arguments so that you can start the script sliding.kts 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.

Bonus: Finishing touches

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 recognize 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.