## Introduction

Hidato first came to our attention in an article by Alex Bellos where he describes solving a puzzle made of hexagonal cells. In addition to the hexagonal form there are also two versions of the puzzle made of square cells, one of which is known as Numbrix.

For all forms of the puzzle the player is presented with a grid of cells, some containing numbers,
including 1 and N, where N
is the number of active cells in the grid. The aim is to place a chain of
consecutive numbers in **touching cells** so that there is a continuous
path from the cell containing 1 to the cell containing N. Only one such path is possible.

Our game includes all three forms of puzzle. One is the form in which hexagonal cells touch via their edges and hence in **6 directions**. The other two types of puzzle consist of square cells in a square grid and their difference lies in their distinct definitions of touching. The simplest type touch orthogonally through their edges, ie in ** 4 directions**, but the more complex puzzles also touch diagonally through their corners, ie in **8 directions**. All the cells in the square grids are used in the path, but some cells in the hexagonal grids (displayed black) are inactive.

## Hidato Example 1

A screenshot from Hidato showing a partially completed puzzle in which the cells touch in 8 directions. The shading indicates the number of candidates remaining for each cell. The player has clicked on the pink button in a cell to reveal the remaining candidates for that cell.

## Hidato Example 2

A screenshot from Hidato showing the solution for the puzzle from Example 1. The sequence of the colours in the rainbow is used to make it easier to follow the path.

## Hidato Example 3

A screenshot from Hidato showing a partially completed puzzle in which the cells touch in 6 directions. The black cells serve only as obstacles. The program has options for choosing font sizes and for this screenshot the smallest size has been used. The player has clicked on the pink button in a cell to reveal the remaining candidates for that cell.

The easiest way to learn about the game is from the Worked example video. Read the caption then watch the video. It illustrates many of the games features and you won't need to read the rest of this page. Better: download the game and play it.

Note these puzzles differ from all the others we have worked on because of the large number of candidate answers: at the beginning of the game there are nearly N possible answers for each cell. This means that we cannot show all of the candidates all of the time as we can, say for Sudoku and so we are using popup menus which appear when the mouse cursor passes over them. In each cell there is one popup for deleting candidates and another for setting the answer. Nevertheless, with so many candidates to display these menus can be rather unwieldy. However, as explained here a right-click on the wand will apply some simple filters and so reduce the numbers of candidates to more manageable proportions.

Our inability to display all the candidates all of the time also impacts on the game's use of hints. In our other games we see the hints and the way we provide them partly as a learning device: that players can see cause and effect and learn to recognise the corresponding patterns for themselves. Of course they also enable the player to advance in the game and continue playing without asking the program to show the solution. But in Hidato we expect the hints to almost exclusively play the latter role. There are two reasons for this. The first is a result of our inability to simultaneously display all the candidates during game play: for a player to recognise, say a hidden single, she has to be able to see all the remaining candidates, and here she cannot. And the second reason is that while natural for a computer program (that can "see" all the candidates all of the time) most of the offered Sudoku-like algorithms are not the ones that a human player would naturally apply to this type of problem anyway. Apart from the Exclusion Rule, something like Prune on Path seems to us the nearest to a human strategy.

We have attempted to overcome our inability of simultaneously show all candidates by adding a slider to the bottom of the puzzle display. The slider can be moved to show which candidates remain in which cells: when the slider is over position X all cells containing candidate X will be highlighted in red. Though useful it is clearly insufficient, as to reveal, say, a hidden pair, would require two sliders... However, as we have said humans are unlikely to apply such methods to this type of puzzle. Popup menus are also used to display the result of hint requests.

The game includes 3 blocks of 1000 puzzles. The first block are square cells and these 'touch' orthogonally. The second block contains grids of hexagonal cells and each cell touches it 6 neighbours. The last block contains square cells and these touch orthogonally and diagonally.

## Hidato Worked Example

A video from hidato showing an example of the simplest form of puzzle being solved. In these puzzles cells only touch orthogonally: left and right and up and down. In this example all answers are set using the left popup menu in the cells and no use is made of the righthand candidate deletion menu. Apologies that some of the popup menus disappear off the bottom of the video recording. The video starts when the player selects puzzle number 998 and clicks the right mouse button on the wand to reduce the numbers of candidates to manageable size. Note the shading of the cells changing to reflect their numbers of remaining candidates. For demonstration purposes only we use the slider so that the cells containing each candidate are lit up in turn. At first the puzzle looks impossible, but then we see that 1 must connect leftwards to 2, otherwise the corner cell would be isolated. Three follows and then we are stuck until we see that 26 can only be connected on its left side to 32 because the right side is too far away. So we fill in 25, then 24 and 23 follow easily. Then 22 must touch 21 and 23. A quick right click on the wand to reduce the candidates. Now we return to 26 and fill in 27 and 20, followed by 28. Then 29, 30 and 31 are easy, and so are 4, 5, 6. A quick click on the hand icon to make sure we've made no mistakes. Then we see that 19 is now obvious, then 35, 33, 7, 8, 9. Nervous click on the hand to make sure we are OK so far, and the rest fall into place. As an encore we reload the puzzle by putting the cursor in the Entry box and hitting Enter, then click on the sad smiley to demonstrate how the program shows the solution as a rainbow coloured animation.

## Playing

The program starts with a randomly selected puzzle displayed. It shows a grid of cells, some containing numbers, including 1 and N, where N is the number of cells in the grid. The aim is to place a chain of consecutive numbers in touching cells so that there is a continuous path between the cell containing 1 to the cell containing N.

Each empty cell contains two menu buttons which will appear when the mouse cursor crosses them. Both menus show the remaining candidate answers for the cell. A selection made using the left menu will set the answer for the cell. The right menu can be used to delete candidates. At the bottom of the grid is slider which can be moved to show which candidates remain in which cells: when the slider is over position X all cells containing candidate X will be highlighted in red.

At the top of the display is a Toolbar. The jigsaw piece button at the left is a menu which has options for configuring the program and saving the current settings. Options include "Set Prune Distance" which allows a minimum distance value to be set for the Prune on Distance component of Simple Filter; "Shade Cells" which toggles the function which shades cells according to the number of candidates they still contain; "Set Animation Delay" which sets the number of milliseconds between steps for the show solution function; and "Font Size" which allows font sizes to be selected.

Next to the jigsaw button is an cube icon (chosen by our admiration for the redblobgames site and its information about cube distances) which is used for selecting a random puzzle from the program's built-in puzzles; a wand for selecting and executing hints; a thumb for checking and correcting errors, and a sad smiley for showing the solution. To the right of this are 3 numbers. The first is the puzzle number, the next the puzzle difficulty and the next a clock which ticks every 5 seconds. The puzzle number display is also an input box: players can position the cursor over this area and type in a number between 0 and 2999 followed by 'Enter' to load the corresponding puzzle.

## Hint Example

The green buttons mark the "causes" and red the "effects". Here the nearest numerical neighbour above 25 is 30 and the cell with the red popup containing 29 cannot lie on any path between them and so its 29 can be deleted.

When a hint is requested the clock display is used to show a 2-letter abbreviation for the name of the hint found. The hint options available by left-clicking on the wand are searched for in the following order: Exclusion Rule(ER), Prune on Distance(PD), Prune on Path(PP), Hidden Single(HS), Naked Pairs(NP), Naked Triples(NT), Hidden Pairs(HP), Hidden Triples(HT). The first hint found will be shown. Hints are shown by displaying green and red menu buttons in the affected cells. Green buttons indicate the 'reasons' for a hint and red buttons where candidates can be deleted. Clicking on the buttons will reveal list of the candidates involved. While the hint is active (shown by the wand icon leaning backwards) clicking on the wand with the middle mouse button will cause a pop-up to appear containing a short explanation of the hint. A further left click on the wand icon will delete the candidates shown in the red menus. Right-clicking on the wand will apply Simple Filter using the current "Prune Distance" value.

The program will not report errors until the player clicks on the thumb or requests a hint. Errors are reported by the thumb turning down and the incorrect cells being highlighted. A further click on the thumb will correct the error(s) and undo all changes made since the first error. At any time, typing 'Enter' will restart the current puzzle.

## Simple Filter

This filter consists of two algorithms. The first is the Exclusion Rule and the second Prune on Distance(. It is selected by clicking the wand with the right mouse button and both algorithms are applied exhaustively. This means that the program keeps applying them in turn until it can remove no more candidates. For the "Prune on Distance" component it uses the "Prune Distance" set in the game menu. Simple Filter has two purposes: to save the player from trivial candidate removal, and secondly to shrink the content of the popup candidate menus. If shading is switched on the resulting lightening of the grey scales will help show cells with fewer possibilities.

Please be aware that, particularly towards the end of a puzzle, the exhaustive nature of the function means that it can completely finish the puzzle!

## Checking for Errors

Clicking on the hand button causes the program to check the puzzle for errors (which can occur due to the player removing incorrect candidates). If errors are detected the hand will flip to the thumbs down position. A further click on the hand will reverse all moves made by the player, back to the last time the puzzle was error free. 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, the hand will flip to thumbs down and the cells with errors will be highlighted.

## Algorithms

The algorithms used by Hidato are explained using examples. Cells containing green popup menus are the "reasons" that candidates in the cells with red popup menus can be removed.

## Exclusion Rule

Exclusion rule: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. When an answer is set all other occurrences of that digit can be deleted. Here, the digit 15 has already been set and so any other digit 15s in the can be deleted.

## Prune on Distance

Prune on distance: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. Once an answer, say X, is set, we know that the cells containing X-1 and X+1 must touch the cell containing X, and hence that they cannot occur further away. X-1 and X+1 can be deleted as candidates from all cells not touching the one containing X. Similarly X-2, X+2 can be deleted as candidates from all cells at least one cell futher away, and so on. The distances between cells are calculated without taking into account obstructions posed by any solved cells. Here the target cell shown with a green popup is too far from the cell with the red popup to contain 27.

## Hidden Single

Hidden single: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. If a cell contains the only remining copy of a digit, that digit must be the answer for the cell, and any other candidates in that cell can be deleted. Here 30 and 33 can be deleted as the hidden single is clearly 34!

## Prune on Path

Prune on path: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. Once an answer, say X, is set, we know that the cells containing X-1 and X+1 must touch the cell containing X, and hence that they cannot occur further away. X-1 and X+1 can be deleted as candidates from all cells not touching the one containing X. Similarly X-2, X+2 can be deleted as candidates from all cells at least one cell futher away, and so on. The distances between cells are calculated by finding the shortest path between cells taking into account obstructions posed by any solved cells or other obstacles. This procedure can only be applied between a cell and its numerically nearest neighbours. Here the nearest numerical neighbour above 25 is 30 and the cell with the red popup containing 29 cannot lie on any path between them and so its 29 can be deleted.

## Naked Pairs

Naked pair: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. If two cells each contain only the same two digits, those digits must be the answers for the two cells, and any other occurrences of those digits can be deleted. Here one of the "naked" candidates must be 16 and so all 16s outside the two cells with the green popup can be deleted.

## Hidden Pairs

Hidden pair: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. If two cells each contain the only remining copies of two digits, those digits must be the answers for the two cells, and any other candidates in those cells can be deleted. Here seven candidates can be deleted because they are not either of the pair of hidden candidates (only one popup menu can be shown at a time).

## Naked Triples

Naked triple: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. If three cells each contain only the same three digits, those digits must be the answers for the three cells, and any other occurrences of those digits can be deleted. Here the player could see what the 3 naked candidates are by clicking on the green buttons. What the screenshot shows is the result of clicking on one of the red buttons and that for the corresponding cell the candidates 29, 28 and 27 can be deleted.

## Hidden Triples

Hidden triple: a solved grid of N cells contains the digits 1 to N ordered consecutively as a continuous chain of touching cells. This means that the digits 1 to N each occur exactly once. If three cells each contain the only remining copies of three digits, those digits must be the answers for the three cells, and any other candidates in those cells can be deleted. Here the player could see what the 3 hidden candidates are by clicking on the green buttons. What the screenshot shows is the player clicking on one of the red buttons which reveals that candidates 29, 28, 27, 23, 34 and 33 can be deleted.