Hoo-Doo is a puzzle by Tryne Games, which consists of an 8×8 board with a set of pegs. The pegs come in 8 colours with 8 pegs each, as well as two transparent pegs. The aim is to fill all 64 holes by the pegs such that no two pegs of the same colour lie in the same row, column, or diagonal. The transparent pegs have no colour and so may be in the same row, column or diagonal as any other peg. The fewer of the transparent pegs you use, the better. Note that all diagonals count, not just the two main diagonals.
There was a prize of $1000 to the first person to solve the puzzle without the use of the transparent pegs.
There are 64 coloured pegs, 8 of each colour, so they can be arranged on the board in 64!/8!8 = 1.817·1052 ways. This is of course not a good measure of difficulty, since you would never try to fill up the rest of the board if you have already placed two pieces of the same colour in a row or column.
Let's fill the grid without using any transparent pegs, but with as few clashes as possible. You can do so with only two pairs of pegs of the same colour in the same row/column/diagonal. It is not possible to do this with fewer than two clashing peg pairs, so the competition prize was unwinnable.
|
|
|
|
|
In these solutions with two clashing pairs of pegs (shown in bold italic type), you can replace one peg of each pair with a transparent peg to give solutions that use both transparent pegs. Apart from rotations, mirror images, and colour permutations, there are no other solutions with two transparent pegs.
It is easy to prove that no solution exists without the use of transparent pegs. The eight pegs of each colour have to form a solution to the eight queens problem (place eight chess queens on a chess board so that no two attack each other). There are only 12 such patterns (see the Frustr8tor page). We need both main diagonals to contain a piece of each colour, but only six of the 8-queen patterns have queens on both main diagonals. Unfortunately all six of those patterns use up a square diagonally adjacent to a corner. There are only four such squares, but we would need to combine eight of those patterns to form a Hoo-Doo solution.
If the shorter diagonals (of lengths 1-5) are ignored then there are two solutions. So in the following solutions, not only do the rows, columns and main diagonals not have any repeated colours, but neither do the diagonals of length 6 or 7.
|
|
You can also play the game on a 7×7 square using only 7 colours. There is essentially only one solution (without transparent pegs).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 6 | 7 | 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 6 | 7 | 1 | 2 | 3 |
| 2 | 3 | 4 | 5 | 6 | 7 | 1 |
| 7 | 1 | 2 | 3 | 4 | 5 | 6 |
| 5 | 6 | 7 | 1 | 2 | 3 | 4 |
| 3 | 4 | 5 | 6 | 7 | 1 | 2 |
A 6×6 square using only 6 colours is impossible, even with 2 transparent pegs. The 5×5 square with 5 colours and no transparent pegs has an essentially unique solution.
| 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 1 | 2 | 3 |
| 2 | 3 | 4 | 5 | 1 |
| 5 | 1 | 2 | 3 | 4 |
| 3 | 4 | 5 | 1 | 2 |
Smaller squares are also impossible.
You may notice that the 5×5 and 7×7 solutions have the same simple structure. Each row is the same as the one above, except shifted two places to the right. If the board has size n×n with n coprime to 6, then there is always such a solution.
The converse has also been proven: Knut Vik designs do not exist on boards where n is a multiple of 2 or 3. Note however that this does not prove that no Hoo-Doo solution exists for those sizes, because Hoo-Doo does not require that the board's diagonals wrap around. The next board sizes with a Knut Vik design are 11, 13, 17, and 19.