Introduction

Shikaku or Divide by Box is a logic game published by Nikoli. It is also known as Cell Block in the Guardian. In the pencil and paper version of the game the player is presented with a rectangular grid of cells; most are empty but some contain numbers, typically with values in the range 2 - 20. For our purposes we'll term these numbered cells "clue cells". The object of the game is to draw non-overlapping rectangles around the clue cells so that, when complete, the grid is completely covered by rectangles, each of exactly the size of the value in the enclosed clue cell (so for example a clue cell of value 4 would be in a rectangle of 4 cells).

Contents

Instead of drawing lines to denote the rectangles around clue cells the PZL version randomly assigns a different colour to each clue cell. When the player guesses that a cell is part of the rectangle for a clue it will be given the same colour as the clue cell. So when the rectangle is finished all its cells will be the same colour, hence, the rectangles are defined by colour. This can be seen in accompanying figure which shows a partially completed puzzle.

As a solving aid PZL Shikaku can optionally colour code the unsolved cells using grey scales to denote the number of possible rectangles that could cover them. The lighter the shading the fewer possible rectangles. This can be seen in the Worked Example shown below.

Shikaku Example

Shikaku Example

A partially completed Shikaku puzzle with the shading switched off.

The game includes 2000 built-in puzzles of sizes between 7x7 and 20x15. All the puzzles of a given size occur in a block and within the block they are sorted so that the easiest puzzles are at the start and the hardest at the end. No guessing is required to solve any of these puzzles. If players get stuck a hint button will suggest a cell whose solution can be deduced given the current state of the puzzle. It is also possible to read in and solve external puzzles stored in the format shown here.

Summary

The game starts by showing a randomly selected puzzle. Players try to find cells that can only be covered by one rectangle (there will always be at least one), and set its solution accordingly. To set a guess for a rectangle, first left-click on the numbered cell, then left-click on the distal cell. All the intervening cells will change colour to that of the clue cell. Depending on the position of the clue cell relative to its enclosing rectangle, more than one such operation may be required to completely colour a rectangle. This can be seen in the following Worked Example video. To unset a guess use a right mouse click. Only one cell can be unset at a time. And please note, correct answers cannot be unset!

Clicking the hand icon will cause the program to check for errors and to colour black any found. A further click on the hand will remove all errors. If you get stuck, clicking on the wand icon will request a hint and the program will place a question mark on a cell whose solution can be deduced from the current state of the grid. If you cannot work out which clue covers the cell, another click on the wand will cause the correct colour to be set. If a hint is requested when the grid is incorrect no hint will be shown, instead all the incorrect cells will be coloured black and the thumb will turn down. A click on the hand will correct all the errors. Clicking the sad smiley icon requests that the solution is shown.

The jigsaw icon contains a menu for configuring the game and for loading external puzzles. Clicking the icon to its right will load a randomly selected puzzle. The box to the right of the sad smiley contains the current puzzle number and can be used to select a puzzle by number or to reload the current puzzle (just hit "Enter"). The number to the right of the number box is the current puzzle's difficulty score. To its right is a clock. This clock display will be overwritten by the algorithm number if the hint option is selected. The game uses only 3 algorithms, numbered 0, 1 and 2.

Shikaku Worked Example

A video from Shikaku showing the easiest 10x10 puzzle being solved with the grey scale shading switched on. The player selects puzzle number 300 and spots immediately that the 2 clue in the top right is the only one which can reach the corner cell and that a 6 clue can only have a single rectangle. Notice the operations required. Later the player fills in a complete solution for an 8 clue and then uses the thumb icon to check if it is correct. It isn't, and the program colours two incorrect cells black. A further click on the thumb corrects the errors. Further on the player uses the hint button to request a clue. Note throughout how the shading changes as the number of possible solutions diminishes.

Checking for Errors

Clicking on the hand button causes the program to check the puzzle for errors. If errors are detected the hand will flip to the thumbs down position. A further click on the hand will undo all errors. Note that when a hint is requested the program always checks the puzzle for errors first. If errors are detected no hint search will be performed and the hand will flip to thumbs down. A click on the hand and the errors will be removed.

Difficulty Score

The Difficulty Score is the number to the right of the puzzle number. Though it can only provide a rough indication of how hard a player will find any particular puzzle, it does give a useful indication of the relative difficulty of puzzles. For this game the difficulty depends on the number of different rectangles that might apparently satisfy each clue and then on choosing between them to find the subset that can fit together without overlapping. For any individual clue it is relatively easy to reject rectangles which overlap other clue cells, but it is much harder to find the one rectangle for each clue which is compatible with all those around it. The more potential rectangles the harder the puzzle. So, our difficulty measure is the sum of the number of rectangles for each clue which do not contain other clue cells. That is, for each clue cell we find all rectangles and then we delete those which go off the edge of the grid and those which contain other clue cells. The remaining number of rectangles for a clue cell is the difficulty for that clue, and the total for all clue cells is the difficulty for the puzzle. Obviously, bigger puzzles are expected to have higher difficulty scores. These scores were used to sort the built-in puzzles into order: easiest first.

Algorithms

The program uses 3 hint algorithms. They focus more on the potential rectangles for each clue cell than on the individual unsolved cells. Algorithm 0 looks to see if the remaining rectangles for a clue all share any cells. If these are the only possible rectangles and each of them contains a particular cell, which ever is the correct rectangle that cell must be part of the solution. Algorithm 1 looks to see if there are any cells which can only be covered by the rectangles for one clue. If only one clue can reach a cell that clue must be its solution. Algorithm 2 monitors each unsolved clue to see, as the solving process proceeds, if that clue has only one remaining rectangle. If so, that rectangle is obviously the solution for the cells it contains. The hint option applies these algorithms in the above order. If any of them finds a new cell that can be solved it reports its finding and the search stops.

When necessary a guessing algorithm with backtracking is used in combination with the logical algorithms to solve external puzzles. It is possible that external puzzles may have more than one solution or may be entered incorrectly. If either of these cases occur the solving algorithm could have problems and get stuck in a loop. To deal with this possibility the program has a time limit, after which it will give up and load a randomly selected built-in puzzle. The game menu has an option for setting this time limit (in seconds). If an external puzzle does requires guessing (rare in our experience) the difficulty score will be set to -1. If a hint is requested when a guess is required the program will simply provide the solution for a cell (which it worked out when solving the puzzle)!

The logical algorithms are quite fast. They can solve all 2000 built-in puzzles in a total time of under 7 seconds using a 5 year old desktop machine. Indeed, to help keep the size of the program to a minimum, the program does not store the solutions for the built-in puzzles, only their clues, and then solves them each time they are chosen. The time taken, at an average of 7/2000 seconds, is obviously imperceptible.