A 15 puzzle consists of a rectangular board with $$m$$ rows and $$n$$ columns, where one of the fields stays empty. Puzzle pieces on horizontally or vertically adjacent fields can be moved to this empty field. Because of this, the whole field moves. The first 15 puzzle was invented by Noyes Chapman and started a real puzzle mania in 1880.

In various variants of the puzzle, the pieces are marked with numbers, letters or parts of an image. The purpose is to first move the pieces a large number of times, so that they are positioned in a random order on the board. After that, the pieces must be moved in a way that they end up in the original order on the board.

Assignment

Define a class fifteenpuzzle to represent 15 puzzles, of which the pieces are marked with ASCII characters. This class must implement the following methods:

• An initializing method __init__ to which three arguments must be given: i) the number of rows $$m$$, ii) the number of columns $$n$$ and iii) a string. The pieces of the puzzle must be marked from left to right and from top to bottom with the consecutive characters of the given string. This string must have an equal amount of characters as the number of fields in the 15 puzzle, and must have exactly one space that indicates the position of the empty field. The initializing method must raise an AssertionError with the text invalid configuration if the condition is not met. The board must also have at least three rows and three columns, if not, the initializing method must raise an AssertionError with the text puzzle must contain at least three rows and columns.

• A method __str__ with which a string representation of the current state of the 15 puzzle can be printed. The string representation consists of $$m$$ lines, which $$n$$ characters are written out that mark the puzzle pieces. The string representation itself does not end in a newline.

• A method __repr__ with which a string representation of the current state of the 15 puzzle can be printed. This string representation reads as a Python expression that makes a new object of the class fifteenpuzzle that has the same condition.

• A method move with which the empty field of the 15 puzzle is moved successively over a number of given positions. The possible directions are left (L), right (R), up (U) and down (D) and indicate in which direction the empty field must be moved, not the direction in which an adjacent puzzle piece is moved towards the empty field. To this method, a string must be given that solely consists of the L, R, U and D. Based on these directions, the method must execute the corresponding movement of the empty field. As soon as an invalid movement must be executed, the method must raise an AssertionError with the text invalid direction. Previous (correct) movements, however, must still be executed.

Example

The example below shows how a $$4 \times 4$$ 15 puzzle of which the letters initially read pikante loketten, can be converted over a number of movements to a puzzle of which the letters spell the word platentektoniek.

>>> puzzle = Slidingpuzzle(4, 4, 'o draconiandevil'); print(puzzle)
o dr
acon
iand
evil
>>> puzzle.slide('L'); print(puzzle)
 odr
acon
iand
evil
>>> puzzle.slide('RRR'); print(puzzle)
odr 
acon
iand
evil
>>> puzzle.slide('R')
Traceback (most recent call last):
AssertionError: invalid direction: R
>>> puzzle.slide('LLLDRURULLDRLDRRLURLDRULRRUDDLRULURDU'); print(puzzle)
leon
ardo
davi
nci 
>>> puzzle
Slidingpuzzle(4, 4, 'leonardodavinci ')

>>> puzzle = Slidingpuzzle(2, 2, "AOJN")
Traceback (most recent call last):
AssertionError: puzzle must have at least 3 rows and columns
>>> puzzle = Slidingpuzzle(4, 4, "AOJNDH")
Traceback (most recent call last):
AssertionError: invalid configuration
>>> puzzle = Slidingpuzzle(4, 4, "OEKBFJOZKSOLDFKE")
Traceback (most recent call last):
AssertionError: invalid configuration

Below you will find a graphical display of this 15 puzzle.

Omdat we het niet kunnen laten, staan hieronder nog enkele voorbeelden van schuifpuzzels die in een aantal schuifbeurten wartaal (of toch niet?) omzetten in een herkenbaar woord.

>>> puzzle = Slidingpuzzle(3, 6, 'risereems npationt')
>>> puzzle.slide('DUDURRRDLRDLRUDUDULLRDRLR')
>>> print(puzzle)
misrep
resent
ation 

>>> puzzle = Slidingpuzzle(7, 3, 'pigheneo iolnrpilceps')
>>> puzzle.slide('DLRDLLUDUUURRLDUDDRDLRDDULLRRLDR')
>>> print(puzzle)
pig
eon
hol
epr
inc
ipl
es 

>>> puzzle = Slidingpuzzle(4, 4, 'penitential moms')
>>> puzzle.slide('LLLUURDDLDRRUULLDRDRUURDLUURDLLURDLLURDDDRR')
>>> puzzle
Slidingpuzzle(4, 4, 'implementations ')

>>> puzzle = Slidingpuzzle(4, 4, 'mythical gorilla')
>>> puzzle.slide('DRRUURDDLUURDLLURULDRURDDLUURDDDLUULLURRRDDLLLUURRRDDD')
>>> puzzle
Slidingpuzzle(4, 4, 'algorithmically ')