The Search for a Perfect Square

Most of the puzzles on this site have black squares: cells where no number can go. A perfect board would have none. Every cell would hold a number, so every row and every column would be a complete line of pairs. Apart from the trivial 2×2 board, which is just four 1s, nobody has ever found one. I don't yet know whether any exist, and finding out is the question at the centre of this project.

The best 18×18 board so far

This is the fullest 18×18 board my search has found. It holds 296 numbers in its 324 cells, about 91%, and leaves 28 black squares.

17139101131137292101311717 133101239118272101391287 910134121145921025131211 101241113349321021211913 113121338610511681251310 3938410649862102 11114610549651121029 11491064357369510272 38539587112927 7292478459113583 27210596375346109411 92102115694510641111 2102689116108393 10135128611511106831312311 139111221023943131141210 111213521029541112413109 781291310272811931210313 17711131029273113111091317

18×18 is the smallest size that's undecided. Every smaller size is settled — apart from 2×2, none of them have a perfect board.

On a perfect n×n board the middle rows and columns are completely filled, and each one must hold every number from 1 to n/2, each appearing exactly twice. In other words, each is a Skolem sequence of order n/2. The proof on the previous page shows that a Skolem sequence of order m exists only when m has a remainder of 0 or 1 when divided by 4. A Skolem sequence of order m is 2m long, since every number comes as a pair, so doubling that result means a perfect n×n board needs n to have a remainder of 0 or 2 when divided by 8. That limits the search to sizes such as 8×8, 10×10, 16×16, 18×18, 24×24 and so on.