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
KEYWORD
nonn,more,hard
AUTHOR
Yanzhe Qiu, Nov 27 2018
STATUS
approved