%I #51 Mar 01 2026 09:49:07

%S 0,1,1,4,5,9,12,17,21,27,33,41,48,56,65,75,85,96,108,121,133

%N Heyawake numbers: maximum number of painted cells in an n X n grid, such that no two painted cells are orthogonally adjacent and the unpainted cells form a contiguous area.

%C Inspired by the Japanese puzzle of the same name.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Heyawake">Heyawake</a>.

%F For n > 4, a(n) >= A239072(n-4) + 2*n - 2.

%e For n=6, the painted cells could be A1, A3, A6, B5, C1, C3, D4, D6, E2, F1, F4, F6 (a(6)=12 cells in all, equal to the lower bound given in the Formula section):

%e #.#..#

%e ....#.

%e #.#...

%e ...#.#

%e .#....

%e #..#.#

%e For n=7, a(7) is equal to the lower bound 17. The unique solution comes from the A239072(3) = 5 painted cells enclosed into a frame of unpainted cells and then into the outer frame in which every other cell is painted, including the corners:

%e #.#.#.#

%e .......

%e #.#.#.#

%e ...#...

%e #.#.#.#

%e .......

%e #.#.#.#

%Y Cf. A239072, A322125, A354673.

%K nonn,more

%O 0,4

%A _Elliott Line_, Mar 13 2014

%E Some values corrected, incorrect values removed by _Elliott Line_, Aug 21 2014

%E a(16) and a(20) corrected by _Elliott Line_ at the suggestion of Greg Malen, Sep 02 2020

%E Entry edited by _Andrei Zabolotskii_, Feb 28 2026. The terms need independent verification.