This mission is an adaptation of the "Cube" game (from Simon Tatham's Portable Puzzle Collection ). If you are lost or just want to play, the game is available here .

There is an uncolored cube on a rectangular grid with six colored cells. You must roll the cube to color it entirely, and return the way you roll the cube to do so.
If the cube rolls on a colored cell and the corresponding face is uncolored, then the face is colored instead of the cell.
If the cube rolls on an uncolored cell and the corresponding face is colored, then the cell is colored instead of the face.

Note: There are many ways to color the cube. Fortunately, you do not have to return the shortest way to do it because it would be too difficult on large grids (up to 50 rows and 50 columns).

The first argument gives the grid dimensions (number of rows, number of columns).
The second argument is the position of the cube (row, column).
The last argument is the set of the positions of the colored cells.
Directions are represented by "N" (north), "S" (south), "W" (west) and "E" (east).

Input: Two tuples of two integers and a set of tuples of two integers.

Output: A string with "NSWE" directions.

Example:

Move   Cube position  Colored cells                              Colored faces
       (2, 1)         (0, 0) (0, 1) (1, 0) (2, 0) (3, 0) (3, 1)  no colored face
West   (2, 0)         (0, 0) (0, 1) (1, 0) (3, 0) (3, 1)         Down
South  (3, 0)         (0, 0) (0, 1) (1, 0) (3, 1)                Down North
East   (3, 1)         (0, 0) (0, 1) (1, 0)                       Down North West
North  (2, 1)         (0, 0) (0, 1) (1, 0) (2, 1)                South West
West   (2, 0)         (0, 0) (0, 1) (1, 0) (2, 0) (2, 1)         South
East   (2, 1)         (0, 0) (0, 1) (1, 0) (2, 0)                Down South
North  (1, 1)         (0, 0) (0, 1) (1, 0) (2, 0)                South Up
North  (0, 1)         (0, 0) (1, 0) (2, 0)                       Down North Up
West   (0, 0)         (1, 0) (2, 0)                              Down East North West
South  (1, 0)         (2, 0)                                     Down East North Up West
South  (2, 0)         no colored cell anymore                    all faces are colored
Hence on that grid, one way to color the cube entirely is "WSENWENNWSS".

roll_cube((4, 2), (2, 1), {(0, 0), (0, 1), (1, 0), (2, 0), (3, 0), (3, 1)})
# "WSENWENNWSS" or "WNNESSNSSWNEWESWE" or ...

To play the puzzles / tests yourself: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Preconditions:

• All puzzles are solvable.
• 2 ≤ dimensions[0] ≤ 50 and 2 ≤ dimensions[1] ≤ 50.
• all(0 ≤ row < dimensions[0] and 0 ≤ col < dimensions[1] for row, col in colored | {start})