cp's OEIS Frontend

A322125 Minimum number of shaded cells in an n X n Hitori solution grid.

%I A322125 #14 Jan 14 2019 13:49:49
%S A322125 0,1,2,4,5,8,11
%N A322125 Minimum number of shaded cells in an n X n Hitori solution grid.
%C A322125 Cells are shaded in an n*n grid, such that
%C A322125   - Unshaded cells are orthogonally connected.
%C A322125   - Shaded cells cannot touch orthogonally.
%C A322125   - Shading any unshaded cells will break one (or both) of the rules above.
%C A322125 In the original Hitori puzzle, the last rule is not required.
%C A322125 Subsequent terms a(8), a(9), a(10) are at most 15, 19, 24.
%C A322125 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 A322125 a(n) <= A321684(n). - _Andrey Zabolotskiy_, Jan 14 2019
%e A322125 Case n=4: A solution with the minimum number of shaded cells is:
%e A322125    X . X .
%e A322125    . . . .
%e A322125    X . . X
%e A322125    . . . .
%e A322125 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 A322125 .
%e A322125 Example solutions for each n are given below. Positions of shaded cells are given.
%e A322125 n a(n) example
%e A322125 1 0
%e A322125 2 1  1/
%e A322125 3 2  1/2/
%e A322125 4 4  1.3//1.4/
%e A322125 5 5  2.4///2.4/3
%e A322125 6 8  2/3.5/4/1/2.6/4
%e A322125 7 11  2.6/3/4/1.5.7/2/5/2.6
%e A322125 *8 15 2.6/3.7/4/1.5/2.6.8/4/3.5/2.7
%e A322125 *9 19 4.8/1.3.5/8/3.6.9/2/1.5.7/4.8/3.9/2.6
%e A322125 *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 A322125 *=not confirmed to be minimal.
%Y A322125 Cf. A322150 (number of minimum solutions), A321684 (same sequence without the connectivity of the unshaded cells required).
%K A322125 nonn,more,hard
%O A322125 1,3
%A A322125 _Yanzhe Qiu_, Nov 27 2018