login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A322125
Minimum number of shaded cells in an n X n Hitori solution grid.
1
0, 1, 2, 4, 5, 8, 11
OFFSET
1,3
COMMENTS
Cells are shaded in an n*n grid, such that
- Unshaded cells are orthogonally connected.
- Shaded cells cannot touch orthogonally.
- Shading any unshaded cells will break one (or both) of the rules above.
In the original Hitori puzzle, the last rule is not required.
Subsequent terms a(8), a(9), a(10) are at most 15, 19, 24.
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.
FORMULA
a(n) <= A321684(n). - Andrey Zabolotskiy, Jan 14 2019
EXAMPLE
Case n=4: A solution with the minimum number of shaded cells is:
X . X .
. . . .
X . . X
. . . .
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.
.
Example solutions for each n are given below. Positions of shaded cells are given.
n a(n) example
1 0
2 1 1/
3 2 1/2/
4 4 1.3//1.4/
5 5 2.4///2.4/3
6 8 2/3.5/4/1/2.6/4
7 11 2.6/3/4/1.5.7/2/5/2.6
*8 15 2.6/3.7/4/1.5/2.6.8/4/3.5/2.7
*9 19 4.8/1.3.5/8/3.6.9/2/1.5.7/4.8/3.9/2.6
*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
*=not confirmed to be minimal.
CROSSREFS
Cf. A322150 (number of minimum solutions), A321684 (same sequence without the connectivity of the unshaded cells required).
Sequence in context: A018257 A103075 A294940 * A174803 A282434 A105659
KEYWORD
nonn,more,hard
AUTHOR
Yanzhe Qiu, Nov 27 2018
STATUS
approved