Technical Report: DCC-2004-04

Educated brute-force to get h(4)

Rogério Reis, Nelma Moreira and João Pedro Pedroso

DCC-FC & LIACC, Universidade do Porto
R. do Campo Alegre 823, 4150-180 Porto, Portugal
Phone: 351 226.078.830, Fax: 351 226.003.654
E-mail: {rvr, nam, jpp} at ncc.up.pt

June 2004


Abstract

In one of his numerous conferences, Frank Harary, talked about one of his many games, that, as usual, had a very difficult problem associated to it. In this case, a family of games for two players in which the selected number of columns in the game has a vital importance. He has proved that for 2 and 3 columns the longest match has 9 and 24 moves respectively, that is to say that h2=9 and h3=24. At the same time it was announced that he knew a solution of length 67 for the problem with 4 columns, but he didn't know if it was the maximum. We present here a program that proves that h4=67. Although it uses but a brute-force approach, its soundness seems good fun to prove.