표시된 기호의 최소 수

Question

나는 7x7 그리드를 가지고 있는데, 여기서 가장 적은 양의 "표시된 위치"를 찾고자하므로 표시되지 않은 위치 그룹은 4보다 크지 않습니다 (대각선이 아닌 위, 아래, 왼쪽 및 오른쪽으로 만 이동). 아래는 19 개의 표시된 기호를 사용하는 솔루션의 예입니다.

누구든지 18 개 이하 만 사용하는 솔루션을 찾을 수 있습니까?

Answer 1

나는 이것이 최적의 해결책이 될 것으로 기대하지만 아직 그 증거가 없습니다.

표시된 사각형은 17 개뿐입니다.

. X. . . X.
 . . X. X. .
 . X. X. X.
 X. . X. . 엑스
 . X. X. X.
 . . X. X. .
 . X. . . X.

Answer 2

다음과 같이 정수 선형 프로그래밍을 통해이 세트 커버링 문제를 해결할 수 있습니다. 각 펜토미노$p$, 허락하다 $C_p$그것을 구성하는 (5) 그리드 셀의 집합입니다. 각 그리드 셀에 대해$(i,j)$, 이진 결정 변수 $x_{i,j}$해당 셀이 표시되었는지 여부를 나타냅니다. 문제는 최소화하는 것입니다.$\sum_{i,j} x_{i,j}$ 선형 제약 조건 : $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all $피$}$$ 최적의 값 $n\in\{1,\dots,10\}$되고 \ {행렬} 시작 n은 1 2 3 4 5 6 7 8 9 10 \\ \ hline \ 분 및 0 0 3 5 8 13 17 24 31 & 39 \\ \ end {matrix}