Claude Berge’ puzzles

In our first study “Analysis of the Game of Hex” all the positions analysed result from the initial positions of the Hexboard Hn of order n. Let us be reminded that the general winning strategy and the elements of tactic in this study have made it possible to find the solution of the Hexboard Hn, whatever the order n.

This present study illustrates and completes the previous one. We have , in effect, applied the same method of analysis—analysis of one move only by White each time White has to play, if we consider that white is the winner (or Black in the opposite case), and analysis of all the moves possible of Black each time Black has to play(or White on the contrary)—we also applied the same general winning strategy and used the same elements of tactic in order to analyse Claude Berge’ puzzles, some of which have any number of white cells and black cells. Knowing the general winning strategy, the analyses of these Puzzles, which are not easy to solve, as their name suggests, have not needed a great effort of imagination on our behalf.

In particular, it should be noted that the winner has always played the best move. Moreover, the use of the support cells concept and their name given by us in our previous study, as well as threats and doubles attacks, not forgetting the position-types, have allowed us to carry all our analyses to a successful conclusion.

The result of the aforementioned is that the general theory we created makes it possible for us to analyse all the positions of the Game of Hex, whether or not they result from initial positions of the Hexboard Hn, of order n whatever n may be.

If we remember that Stefan Reisch proved in 1981 that the Game of Hex is a NP-complete Game, it is not out of place to ask the question:

Do we have the relation:

P=NP ?

See the Study: Puzzles du Jeu d’Hex