Introduction to Data Structures and Algorithms
Assignment 1 Part B: Stacks

  • Due 19 April , 7pm

What To Hand In

  • (and any additional files you change or create for Sokoban)

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

Undo for Sokoban (Weight: 1/3)

Sokoban is a computer game of the puzzle variety that was created in 1980, and is available on many computer platforms. The game involves controlling a worker in a warehouse who has to push boxes around the warehouse to get them onto their destination spots. The worker can only push one box at a time, and cannot pull boxes. It is easy for the player to get stuck in a deadlock where it is no longer possible to move some of the boxes. Some of the levels are extremely difficult to solve.

You can find out more about the Sokoban game from the web.

We have provided a simple implementation of the Sokoban game with four levels. You can control the worker with buttons or keys.

Our implementation of Sokoban is frustrating because if you make a mistake, you have to restart the game from the beginning. The game desperately needs an undo facility, so that you can undo actions if you discover you have made a mistake. It should be possible to undo all actions, all the way back to the beginning of a level.

For this assignment, you need to add an undo button to Sokoban. It should use a Stack that contains the history of actions since the beginning of the current level. Every time the player performs a (successful) action, the action should be recorded on the stack. Every time the player clicks the undo button, the program should pop the top action from the history and "undo" it: if it was a move, the worker should be moved back (in the opposite direction of the recorded direction); if it was a push, the worker should be moved back, along with the box that was pushed.

The amount of code you have to write is quite small, but to work out what is needed and where to put it, you will have to read and understand a lot (if not all) of the Sokoban program. This will not be trivial and you should expect to spend time reading the program carefully.

To help you with implementing the undo functionality, we have provided an ActionRecord class for recording information about actions.

To implement the undo facility, you need
  • a history field that contains a Stack of ActionRecord
  • extra lines of code in the methods that perform the actions to create an ActionRecord object and push it on the history stack.
  • extra lines of code in the load method to reset the history stack when the level is reset.
  • an "Undo" button (plus optionally a key mapping from "u" to the undo method).
  • an undo method that is called when the "Undo" button is clicked, which pops the top ActionRecord off the stack, and reverses the action.


Implement "Undo" for Sokoban.


Implement a "Redo" function. When the user presses "undo", the program should not only pop the ActionRecord that was on the history stack and reverse it, it should also put the ActionRecord onto a redo stack. If the player pressed the "redo" button, it should pop the ActionRecord off the redo stack, redo the action, and put it on the history stack again.

The player could use this to undo all the actions from the end of a game, and then replay all the moves.


One of the more frustrating parts of Sokoban is moving the worker from one side of the puzzle to the other in order to get to the next box to push. An old Macintosh version of Sokoban allowed the user to click the mouse on any free cell. If there was a free path from the worker's current position to the new cell, the program would find the path and move the worker automatically along the path.

Add this facility to Sokoban; it involves searching for a route through the empty cells of the warehouse and then making the worker step along the route.

A starting point is just to find straight paths; the full version should find any free path.