### 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
*h*_{2}=9 and *h*_{3}=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 *h*_{4}=67. Although it
uses but a brute-force approach, its soundness seems good fun to
prove.