Yanzhe Qiu - cp's OEIS frontend

User: Yanzhe Qiu

Yanzhe Qiu has authored 1 sequences.

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

0, 1, 2, 4, 5, 8, 11

Offset: 1

Yanzhe Qiu, Nov 27 2018

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.

			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.

Cf. A322150 (number of minimum solutions), A321684 (same sequence without the connectivity of the unshaded cells required).

a(n) <= A321684(n). - Andrey Zabolotskiy, Jan 14 2019

cp's OEIS Frontend

User: Yanzhe Qiu

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula