login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%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