Suppose you are implementing the 15 puzzle game:

This is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to rearrange the tiles and place them in increasing numerical order.

Here’s an example configuration:

You decide to record the game state as a list of length 16, with elements between 0-15 (0 denotes the empty cell), using the following convention:

the first four elements contain the numbers in the first row of the board,

the fifth-eighth elements contain the numbers in the second row of the board,

the ninth-twelfth elements contain the numbers in the third row of the board, and

the thirteenth-sixteenth element csontain the numbers in the fourth row of the board.

Suppose you generalise this to a game involving a N \times N board, using a list of size N^2. The user indicates how they want to move at every step. Assume you can directly access and update any element in your list.

How much time do you need to update the configuration?

- proportional to N
- proportional to N^2
- constant