CSCI 341 Theory of Computation

Fall 2025, with Schmid

There is an assignment that starts with these notes. Click here for the LaTeX used to typeset the assignment.

Puzzle games, solutions, and state diagrams

If you haven't noticed this yet in your math-based courses, one of the quirks of an abstract mathematical definition is that it can apply to really unexpected examples. Part of the fun of theoretical computer science is that those abstract mathematical definitions are often not too hard to reverse engineer from the unexpected examples. Case in point, let's play some puzzle games, shall we?

Some 2-D Puzzle Games

Directional Mazes

(Directional Maze) A directional maze \(M\) consists the following components:
  • An \(n\times m\) grid \(G\) of positions, where \(n\) and \(m\) are whole numbers
  • A set of legal positions \(L \subseteq G\)
  • Two postions called \(S\)tart and \(E\)nd
  • A set of legal moves \(A \subseteq \{\Uparrow, \Downarrow, \Rightarrow, \Leftarrow\}\)
  • A spelunker, \(C\)oby, that inhabits any legal position
You play a directional maze by applying legal moves to change the position of \(C\) from any legal position to any other legal position. A solution to a directional maze is a sequence of legal moves that takes \(C\) from \(S\) to \(E\).
The Smiley Maze

The directional maze above consists of a \(10\times 10\) grid of positions. The set of legal positions \(L\) is the set of white or beige positions, and in this case the only legal moves are \(A = \{\Rightarrow, \Uparrow\}\).

Note. We assume throughout this section that attempting a move from a legal position to a non-legal position ends the game.

(Smiley Maze)
  1. Does the sequence \(\Uparrow\Uparrow\Uparrow\Rightarrow\Uparrow\) solve the Smiley Maze?
  2. Find a solution to the Smiley Maze, in the form of a sequence of legal moves from \(A\).
  3. How many solutions are there?
  4. Change one position on the grid from illegal to legal such that there is exactly one additional solution after the change.
If you're not feeling over it yet, repeat this exercise a second time for the Spotted Maze below.
The Spotted Maze. The \(S\)tart is in the bottom-left corner and the \(E\)nd is in the top right.

So, we have already seen that a solution is a sequence of legal moves that brings \(C\)oby from the \(S\)tart to the \(E\)nd of the maze. We have already seen that more than one solution can exist for a particular maze.

(Solution to a Directional Maze) Given a directional maze \(M = (G, L, S, E, A, C)\), the solution space of \(M\) is set of all sequences of legal moves from \(A\) that bring \(C\) from \(S\) to \(E\). The solution space is written \(\mathcal S(M)\).
(Sunshine) Find a directional maze \(M\) whose solution space is exactly \[ \mathcal S(M) = \{\Uparrow\Uparrow\Uparrow\Rightarrow\Rightarrow\Uparrow, \Uparrow\Rightarrow\Rightarrow\Uparrow\Uparrow\Uparrow\} \] In other words, there are exactly two solutions in \(\mathcal S(M)\). If you haven't already, try to find the smallest one, and convince yourself that it is indeed the smallest.
How tall must the game board be?
(No Upper Bounds) Find a directional maze that has an infinite solution space (again, try to find the smallest one).
You are allowed to change \(A\). See the definition of directional maze above.
(Always an Upper Bound) Let \(M = (G, L, S, E, A, C)\) be a directional maze with the set of legal moves \(A = \{\Uparrow, \Rightarrow\}\). Prove that \(\mathcal S(M)\) is finite (there are only finitely many elements) by calculating an upper bound on the number of all possible legal paths through an \(n\times m\) directional maze.

Sokoban games

Sokoban is a puzzle videogame developed by Thinking Rabbit in the 1980s. The format of the game is very similar to a directional maze: you control a character by instructing them to perform one of four legal moves \(\{\Uparrow, \Rightarrow, \Leftarrow, \Downarrow\}\) to move from one legal position to another. The difference is an added element: there are boxes you have to push into certain finishing positions. It's a little easier to understand the game once you've played it a bit.

A Sokoban game from Math Is Fun. Use the arrow keys to move the character around (go to the actual page for a better gaming experience on levels other than 1).

We are always going to assume that the set of legal moves in a Sokoban game is \(A = \{\Uparrow, \Rightarrow, \Leftarrow, \Downarrow\}\). Similar to the situation in a directional maze, a solution is a sequence of legal moves that put boxes over all of the finishing positions (the red dots). In this case, the starting configuration of the game really matters!

Three more (smaller) Sokoban games, (A), (B), and (C).
(First Push) Describe the solution spaces of each of the Sokoban games (A), (B), and (C) above.
Two out of the three of them have infinite solution spaces.

State Diagrams

In directional mazes and Sokoban games, hitting the arrow keys is what allows us to transform one configuration of the game board into another. The computer science words for configuration and transform are state and transition respectively.

(State and Transition) A state of a system (including games like directional mazes and Sokoban) consists of all of the data of the system that can be determined at a fixed point in time. In games, a state consists of all of the positions of the tokens (like the spelunker, the boxes, and the box pusher). A state transition is a transformation of one state into another mediated by a legal move. If \(s_0\) and \(s_1\) are states and there is a legal move \(a \in A\) that takes \(s_0\) to \(s_1\), then we write \(s_0 \xrightarrow{a} s_1\).
Two state transitions between three states \(s_0,s_1,s_2\), respectively, of of Sokoban game (A). Written using the labelled-arrow notation \(s_0 \xrightarrow{\Leftarrow} s_1 \xrightarrow{\Uparrow} s_2\).
(More States) Draw three more states of Sokoban game (A), including a state in winning position, and draw all of the transitions that are possible between the six resulting states. Further indicate that a state is in winning position by drawing a circle around it.
(Reachable) A state \(s\) is reachable from a state \(s_0\) if there is a sequence of state transitions \(s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} \cdots \xrightarrow{a_n} s\) that begins for some legal moves \(a_0,a_1,\dots,a_n \in A\).
(Even More States!) How many states are reachable from Sokoban game (A) in total?

The picture above and your solution to the State and Transition exercise that came after it is what's called a state diagram. The state diagram with six states that you drew is not a complete state diagram, because not every state (and state transition) appears in it. These can be a bit difficult to draw usually, because even simple games can have very complex state diagrams.

Sokoban game (D).
(A Complete State Diagram) Draw the complete state diagram of all seven states reachable from Sokoban game (D) above. Indicate that a state is in a winning position by drawing an extra circle around it.

As you might have discovered already, state diagrams don't always need have the full configuration of the game drawn into every state. Forgetting about all of that extra information and just drawing little labelled circles for states (maybe the label describes the state a little bit) is a lot more convenient. A state diagram that doesn't have any description at all written into each state is called an abstract state diagram, because the precise nature of every state has been abstracted away.

(Abstracting Away) Draw abstract state diagrams for Sokoban games (D) and (B).
Abstract state diagram (A).
(Reverse Engineering) Find a Sokoban game that represents state \(s_1\) in abstract state diagram (A). Replace the states in the state diagram with drawings of each state of the Sokoban game.
(Impossibility) Prove that there does not exist a directional maze that represents state \(s_1\) in abstract state diagram (A).
Determine the set of legal moves \(A\). Is there a way that legal moves interact in a directional maze that you won't always see in a Sokoban game?

Transition Tables

A more formal way of writing down a state diagram is a transition table. We will leave the formal definition for next time, when we start to treat state diagrams as formal entities called automata, but the basic idea should be intuitive. A transition table records all the state transitions in one big table. For example, the state diagram for abstract state diagram (A) is the table below:

\(\textcolor{gray}{\rightarrow}\) \(\Uparrow\) \(\Rightarrow\) \(\Downarrow\) \(\Leftarrow\)
\(s_1\) \(s_2\)
\(s_2\) \(s_3\) \(s_4\)
\(s_3\) \(s_2\)
\(s_4\) \(s_2\)
The transition table for abstract state diagram (A).

In the left-most column of the table, you can see the states of the state diagram, and at the top (in the first row) you can see all the legal moves. If \(s\) is a state and \(a\) is a legal move, then if the \((s, a)\)-indexed item in the table is the state \(t\), then you should read: \(s \xrightarrow{a} t\). For example, in the transition table for abstract state diagram (A), you can see that the \((s_3,\Uparrow)\)-indexed item is \(s_2\), because \(s_3 \xrightarrow{\Uparrow} s_2\).

(Transition Tables) Write out the transition tables for Sokoban Games (D) and (B).
Top