Introduction
Shakashaka is an unusual puzzle game we discovered in a Guardian article by Alex Bellos. As originally conceived the game is played using a pencil and a grid printed on paper. The pencil is used to shade selected white cells diagonally, ie just one side of a line stretching from corner to diagonally opposite corner. The aim is that collectively, this should leave behind un-shaded areas, all of which are rectangular. Some of the puzzle cells are black and contain the numbers 0 - 4 which define how many shaded cells they must abut in the finished puzzle. For example a black cell containing a 3 must have a shaded edge from each of 3 cells sharing three of its sides. A black cell containing 0 must be surrounded by white or black cells. These numbered cells are clues to finding the solution, but the player will also need to add shading to areas of the grid devoid of clues. At the end of the game all the clues must be satisfied and all the un-shaded areas must be rectangles or squares.
Perfect shading of a white cell is equivalent to placing a black triangle in one of its corners. In our version of the game, instead of shading, black triangles are placed by clicking in the corresponding cell corner. As the player works out where to place the triangles, and fills them in, the rectangular shapes slowly emerge in the grid.
Shakashaka Example
A screenshot from shakashaka. It shows a 10 x 10 grid near the beginning of a game where the player has started to fill in cells. As usual those on the edge are initially the only ones for which the solution can be worked out. Some cells, where it is clear that no triangle could be the solution, have been marked as empty using yellow squares. One rectangular shape is already completely finished and others are emerging.
Playing
The game starts by drawing a grid of cells, most of which are white but some are black. Of the black cells, a few may be plain, but the majority will contain one of the numbers 0 - 4. These are the clue cells and the numbers show the number of triangles which need to be placed next to the four sides of the clue cells to complete the puzzle. The player places a triangle in a cell by left-clicking in the corresponding quadrant. A right-click will remove it. If the player thinks a cell is an internal part of a rectangle a middle-click will set it as empty, which is denoted by colouring it yellow. Using yellow distinguishes it from the default white of cells and hence shows the player that it has been set.
Triangles
In the descriptions of the algorithms, in order to identify the triangles, we number the four triangle orientations as shown here..
The program starts with a randomly selected puzzle displayed. In the toolbar the jigsaw symbol contains a menu, the next symbol starts a new game; the wand requests a hint, a second click on the wand will perform the hint operation; the thumb checks if the puzzle contains any errors and a second click will clear the errors; the sad smiley shows the solution; the entrybox shows the current puzzle number and can be used to select a new puzzle number; the number next to the puzzle number is the puzzle difficulty score. The clock ticks every 5 seconds but will be replaced by the algorithm code if a hint is requested. A left click on the hint button will request a hint. While the hint is active (shown by the wand icon leaning leftwards) clicking on the wand with the middle mouse button will cause a pop-up to appear containing a short explanation of the hint. Hints are shown by an orange coloured question mark. A further left click will reveal the solution for the cell. The program contains 500 puzzles roughly sorted in order of difficulty.
Shakashaka Worked Example
A video from shakashaka. The player starts by using the puzzle number box to enter a new puzzle number. An experienced player, she quickly fills in triangles and empty cells around the edge, and those next to the diagonal 3 and 4 clues. Next she matches the side of an emerging rectangle before asking for a hint. This is rather obvious, but does enable her to make further progress. Notice her occasional use of the thumb button to check for mistakes. Eventually this reveals she has placed two incorrect triangles which she clears with a further click on the thumb. Another error is found later when she requests a hint, but as the boxes appear she can make progress by matching sides, so finally she adds the last triangle and the clock flashes to signal the end of the game.
Algorithms
The algorithms used by Shakashaka are explained using examples. When the player requests a hint the program displays an orange coloured "?" in a cell whose answer can be deduced from the current state of the puzzle. Below we show one hint example for each algorithm, and to its right the solution for the highlighted cell. The algorithms are named Alg_0 to Alg_17.
Alg_0
Alg_0, The environment of some clues forces particular triangles to be the only possible answer. Here the hint cell must contain a triangle because the 2 clue has only two available faces. Only triangles of type 3 or 4 have a horizontal face compatible with the clue and the 4 triangle would create an inextensible shape. So the solution must be a type 3 triangle, as shown in the result figure.
Alg_1
Each edge of the grid is restricted to two particular triangle types: top: types 1 and 2; bottom: types 3 and 4; left: types 2 and 3; right: types 1 and 4. If an edge cell has a triangle it determines which of the two possibilities must be occupied by its neighbouring edge cell. Here it must be of type 4, as shown in the result figure.
Alg_2
If a clue is satisfied all of its remaining exposed faces must touch empty cells. Here the 2 clue has triangles above and below, so the right hand face must be empty. As shown in the Results figure.
Alg_3
Find pairs of cells forming a 135 degree angle. Add the appropriate triangle to change the angle to 90 degrees.
Alg_4
Find pairs of cells on the edge of the grid which form a 135 degree angle. Add the appropriate triangle to change the angle to 90 degrees.
Alg_5
Find an unsatisfied clue which is touching exactly the number of blank cells it requires. If only one triangle type is compatible with one of the blank cells, it must be its solution.
Alg_9
A clue on the edge of the grid which requires only one more triangle to be satisfied and which has only one adjacent blank cell must have a particulat triangle type.
Alg_11
Find unsatisfied clues requiring one more triangle and having two adjacent blank cells. One of those must be set empty. If an empty cell is incompatible with either blank cell, the other one must be empty.
Alg_17
This algorithm uses the data contained in Possible Patterns and finds unsolved cells for which either only one triangle type or an empty cell is compatible with the surrounding cells. Easy for a computer, but not impossible for an experienced Shakashaka player. Here the only possible solution is an empty cell.
Patterns
The adjacent figure contains every pairwise arrangement of the component shapes used in a Shakashaka puzzle.
Shakashaka Patterns
This diagram shows all the possible pairwise arrangements of shapes in a Shakashaka puzzle. Those ringed in red are the arrangements which cannot occur.
It includes all four triangle orientations plus a black square to represent clue cells, empty cells and black cells. Each interior cell in a Shakashaka puzzle has eight neighbours. The diagram shows each of the five shapes surrounded (ie in all 8 positions), in turn, by all of the shapes. Those circled in red will never occur in a Shakashaka puzzle and so can be discounted when trying to figure out which shape is the solution for a cell.
