Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #14 Jan 14 2019 13:49:49
%S 0,1,2,4,5,8,11
%N Minimum number of shaded cells in an n X n Hitori solution grid.
%C Cells are shaded in an n*n grid, such that
%C - Unshaded cells are orthogonally connected.
%C - Shaded cells cannot touch orthogonally.
%C - Shading any unshaded cells will break one (or both) of the rules above.
%C In the original Hitori puzzle, the last rule is not required.
%C Subsequent terms a(8), a(9), a(10) are at most 15, 19, 24.
%C a(n) is at most n^2/5 + o(n^2). This bound can be obtained by shading (x,y) where x+2y is divisible by 5 followed by adjustments on the edges.
%F a(n) <= A321684(n). - _Andrey Zabolotskiy_, Jan 14 2019
%e Case n=4: A solution with the minimum number of shaded cells is:
%e X . X .
%e . . . .
%e X . . X
%e . . . .
%e In the above, no additional cell can be shaded without either placing it adjacent to another shaded cell or causing the unshaded cells to become disconnected.
%e .
%e Example solutions for each n are given below. Positions of shaded cells are given.
%e n a(n) example
%e 1 0
%e 2 1 1/
%e 3 2 1/2/
%e 4 4 1.3//1.4/
%e 5 5 2.4///2.4/3
%e 6 8 2/3.5/4/1/2.6/4
%e 7 11 2.6/3/4/1.5.7/2/5/2.6
%e *8 15 2.6/3.7/4/1.5/2.6.8/4/3.5/2.7
%e *9 19 4.8/1.3.5/8/3.6.9/2/1.5.7/4.8/3.9/2.6
%e *10 24 5.9/2.4.8/1.6/4.8.10/3.7/2.6/1.5.9/4.8/3.7.10/2.6
%e *=not confirmed to be minimal.
%Y Cf. A322150 (number of minimum solutions), A321684 (same sequence without the connectivity of the unshaded cells required).
%K nonn,more,hard
%O 1,3
%A _Yanzhe Qiu_, Nov 27 2018