Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 7 8 9 |

Game | Cells | States | Solved |

Havannah size 3 | 19 | 2.10^{7} | Yes |

Havannah size 4 | 37 | 6.10^{15} | Yes |

Havannah size 5 | 61 | 1.10^{27} | |

Hex 8x8 | 64 | 10^{29} | Yes |

Havannah size 6 | 91 | 2.10^{41} | |

Hex 11x11 | 121 | 10^{56} | |

Havannah size 7 | 127 | 3.10^{58} | |

Havannah size 8 | 169 | 3.10^{78} | |

Havannah size 9 | 217 | 2.10^{101} | |

Havannah size 10 | 271 | 1.10^{127} | |

It appears that the size of the state space is strongly related to the number
of cells, and thus also with the complexity of the game.
Ewalds also writes: *By comparison with the games that have previously been
solved, size 3 Havannah should be trivial to solve, size 4 should be hard but
possible with brute force, and size 5 may be possible but only if strong
mathematical properties can be found to dramatically reduce the search space
as is done in Hex.* It seems that Havannah is slightly more difficult to
solve, but that does not necessarily make it harder to play.

*Rijksmuseum Twenthe*by Josien Beltman, ISBN:9789055448272, for € 2.95, which on page 92 has a work by Peter Strucken.*aki akademie voor beeldende kunst 1996*, ISBN:9789075522051, for € 2.50.*You should be here! A book about Helsinki, second edition*by Tom Bulgaria (editor) for € 1.50 EUR.

I wondered how these are generated and thought about a JavaScript program to produce them. There are different strategies that can be used. First of all one could randomly generate place nine points, connect all the connections between them, see if there are eleven or more. In case there are eleven, remove some at random. Of course, this would lead to many disconnected drawings. One could use a random walk to generate the points, where locations already visited do not change. Either one could draw the connections of the walk and stop when there would be accidently more than eleven, and in case there are less when nine points are placed, see if some additional connections can be added to add up to eleven. This procedure could fail. Another method would be to generate random points, but take care that they have a neighbour in common with one of the already placed points and draw a connecting connection with this point. And after all points are placed add some additional connections

I wondered how many different PARR's there exist. I wrote the program PARR.cpp for counting them. This
program generates the PARR page. I first decided
to count the number of PARR's in which each pair of points that are neighbours,
have a connection, and allowing crossing diagonals. The total of this is
equal to 2^{20}. From this I calculated the number of PARR's with
possible missing connections. This resulted in a total of 84,024,935,266,353,181 different PARR's. Next, I counted all PARR's where
crossing diagonal connections are not allowed. I did this again in two steps.
This resulted in a total of 4,147,603,839,035,069, which is a lot less, but still a huge number. Note
that these include many PARR's that are not fully connected, meaning that it
is not possible to find a path of connection connecting each pair of points.
Of course, the numbers of PARR's calculated here contain many similar PARR's
with respect to rotation, mirroring, and translation. This property could be
used to reduce the number of cases that have to be studied. But that still
would leave a large number of solutions. I guess that it is only possible to
calculate the number of a relatively low number of points.

- 2: David Mumford: Archive for Reprints, Notes, Talks, and Blog
- 23: Consciousness as a State of Matter

Home | July 2015 | September 2015