An Integer Linear Programming Model for the Evolomino Puzzle

이 논문은 니콜리가 발행한 논리 퍼즐 '에볼로미노'의 규칙을 정수 선형 계획법 (ILP) 모델로 공식화하고, 이를 활용한 퍼즐 생성 알고리즘을 제안하여 CP-SAT 솔버가 18x18 크기까지의 퍼즐을 효율적으로 해결할 수 있음을 입증했습니다.

핵심

1. 에볼로미노 퍼즐이란 무엇일까요?

상상해 보세요. 종이 위에 격자가 있고, 그 위에 화살표와 몇 개의 작은 사각형이 그려져 있습니다.

• 목표: 빈칸에 사각형을 채워 넣어서, 화살표가 가리키는 방향으로 **블록들이 '진화'**하도록 만드는 것입니다.
• 진화의 규칙:
  1. 화살표는 최소 2 개 이상의 블록을 지나야 합니다.
  2. 첫 번째 블록은 작은 덩어리 (예: 1 칸) 입니다.
  3. 그다음 블록은 이전 블록의 모양을 그대로 유지한 채, 한 칸만 더 붙여서 커져야 합니다. (회전하거나 뒤집으면 안 됩니다.)
  4. 모든 블록은 서로 연결되어 있어야 합니다.

마치 식물이 자라나는 과정을 생각하시면 됩니다. 작은 싹 (첫 번째 블록) 이 자라서 잎이 하나 더 달린 큰 식물 (두 번째 블록) 이 되고, 다시 잎이 하나 더 달린 더 큰 식물 (세 번째 블록) 이 되는 것처럼요. 하지만 이 식물은 화살표라는 '길'을 따라만 자라야 합니다.

2. 연구자들이 무엇을 했나요? (수학적 모델링)

이 퍼즐은 사람이 풀기엔 재미있지만, 컴퓨터가 풀기엔 매우 까다롭습니다. 컴퓨터는 "어? 여기가 맞나?"라고 추측할 수 없기 때문입니다.

연구자들은 이 퍼즐의 규칙을 **컴퓨터가 이해할 수 있는 '수학의 법칙 (정수 선형 계획법, ILP)'**으로 번역했습니다.

• 비유: 퍼즐의 규칙을 레고 조립 설명서처럼 정밀하게 적어낸 것입니다.
  • "블록 A 는 반드시 블록 B 뒤에 와야 해."
  • "블록 B 는 블록 A 보다 정확히 1 칸 더 커야 해."
  • "이 두 칸은 서로 붙어 있으면 안 돼."
  • "모든 블록은 한 줄로 이어져 있어야 해."

이렇게 수많은 '법칙'을 컴퓨터에게 주면, 컴퓨터는 이 법칙을 모두 만족하는 유일한 답을 찾아냅니다. 마치 수천 개의 자물쇠를 동시에 열어야 하는 금고를 열 때, 각 자물쇠의 열쇠 구멍 모양을 정확히 맞춰주는 것과 같습니다.

3. 새로운 퍼즐을 만드는 방법 (퍼즐 생성기)

연구자들은 단순히 퍼즐을 푸는 것뿐만 아니라, 반드시 '한 가지 답'만 나오는 새로운 퍼즐을 자동으로 만들어내는 알고리즘도 개발했습니다.

• 과정:
  1. 빈 종이에 무작위로 화살표를 그립니다.
  2. 블록을 자라게 해봅니다.
  3. 핵심: "이 퍼즐을 풀었을 때 답이 하나만 나오는가?"를 컴퓨터에게 확인시킵니다.
  4. 만약 답이 두 개 이상 나온다면, 불필요한 단서 (화살표나 블록) 를 지우거나 추가해서 정답이 딱 하나만 남을 때까지 다듬습니다.

이것은 요리사가 새로운 레시피를 개발할 때, "이 요리를 하면 맛이 너무 강해져서 다른 레시피와 구별이 안 되네? 그럼 소금 양을 조금 줄여보자"라고 반복해서 맛을 보는 과정과 비슷합니다.

4. 컴퓨터는 얼마나 잘 풀까요? (실험 결과)

연구자들은 이 방법을 이용해 5x5 크기의 작은 퍼즐부터 18x18 크기의 거대한 퍼즐까지 만들어 테스트했습니다.

• 결과: 최신 컴퓨터 프로그램 (CP-SAT 솔버) 을 사용하면, 11x11 크기의 퍼즐은 1 초도 안 되어 해결합니다.
• 한계: 18x18 같은 거대한 퍼즐은 약 1 분 정도 걸리지만, 여전히 매우 빠르게 해결됩니다.
• 의미: 20 년 전에는 상상도 못 하던 복잡한 퍼즐을, 이제는 컴퓨터가 순식간에 풀어낸다는 뜻입니다. 마치 수백 년 걸릴 법한 미로를, 드론이 순식간에 통과하는 것과 같습니다.

5. 결론: 왜 이 연구가 중요할까요?

이 논문은 단순히 퍼즐을 푸는 방법을 알려주는 것을 넘어, 복잡한 논리 문제를 컴퓨터가 어떻게 해결할 수 있는지 보여주는 사례입니다.

• 실용성: 이 기술은 퍼즐뿐만 아니라, 물류 경로 최적화, 스케줄링, 암호 해독 등 우리 생활의 복잡한 문제들을 해결하는 데에도 적용될 수 있습니다.
• 미래: 연구자들은 앞으로 이 퍼즐을 더 빠르게 풀기 위해 다른 알고리즘 (예: '댄싱 링크' 같은 특수한 방법) 을 시도해 볼 계획이라고 합니다.

한 줄 요약:

"컴퓨터에게 '에볼로미노' 퍼즐의 규칙을 레고 설명서처럼 정밀하게 적어주니, 컴퓨터가 1 초 만에 정답을 찾아냈고, 심지어 새로운 퍼즐까지 자동으로 만들어냈습니다!"

기술 요약

제시된 논문 "An Integer Linear Programming Model for the Evolomino Puzzle (Evolomino 퍼즐을 위한 정수 선형 계획법 모델)"에 대한 상세한 기술적 요약은 다음과 같습니다.

1. 문제 정의: Evolomino 퍼즐

• 배경: Evolomino 는 일본의 퍼즐 출판사 Nikoli 에서 2023 년 3 월에 처음 소개된 새로운 펜 - 종이 논리 퍼즐입니다. 스도쿠, 카쿠로, 슬리더링크 등으로 유명한 Nikoli 의 문화 중립적 퍼즐 시리즈의 일원입니다.
• 규칙:
  • 직사각형 보드 위의 흰색 셀에 정사각형 (□) 을 그려 블록을 형성해야 합니다.
  • 블록은 수직/수평으로 연결된 정사각형들의 집합 (폴리오미노) 으로, 각 블록은 반드시 화살표 위에 놓인 정사각형 하나를 포함해야 합니다.
  • 각 화살표는 최소 2 개 이상의 블록을 통과해야 합니다.
  • 진화 (Evolution) 메커니즘: 화살표 경로 상의 두 번째 및 이후 블록은 이전 블록에 정사각형 하나를 추가하여 크기가 커져야 하며, 회전이나 반전은 허용되지 않습니다. 즉, 블록의 모양이 유지된 채로 확장되어야 합니다.
• 복잡도: 기존 연구 [22] 에 따르면, Evolomino 퍼즐의 해가 존재하는지 판단하는 문제는 **NP-완전 (NP-complete)**이며, 해의 수를 세는 문제는 **#P-완전 (#P-complete)**임이 증명되었습니다.

2. 방법론: 정수 선형 계획법 (ILP) 모델

저자들은 Evolomino 의 규칙을 정수 선형 계획법 (ILP) 모델로 공식화하여 해결책을 도출했습니다. 주요 구성 요소는 다음과 같습니다.

• 변수 정의:

  • $x_i$: 셀 $i$에 정사각형이 있는지 여부 (0 또는 1).
  • $y_{a,i}^k$: 화살표 $a$의 $k$번째 블록이 셀 $i$에 포함되는지 여부.
  • $b_{a}^k$: 화살표 $a$의 $k$번째 블록이 활성화되었는지 여부.
  • $N_{a}^k$: 블록의 크기 (정사각형 개수).
  • 연결성 (Connectivity): 블록이 하나의 연결된 폴리오미노인지 확인하기 위해 Gavish 와 Graves 의 유량 기반 모델을 적용했습니다. 각 블록 내에서 '소스 (화살표 위의 셀)'에서 '소비자 (나머지 셀)'로 유량이 흐르도록 제약합니다.
  • 진화 (Evolution): 블록 $k$가 블록 $k-1$에 대해 이동 (translation) 만 수행하고 회전/반전은 하지 않도록 하는 제약 조건을 도입했습니다.

• 주요 제약 조건:

  1. 할당: 각 정사각형은 정확히 하나의 블록에 속해야 함.
  2. 간격: 같은 화살표 상에서 인접한 셀에 정사각형이 놓일 수 없음 (블록이 분리됨).
  3. 블록 활성화: 블록이 활성화되지 않으면 비어 있어야 함.
  4. 크기 증가: 후속 블록은 이전 블록보다 정사각형이 정확히 1 개 더 많아야 함.
  5. 기하학적 일관성: 블록 진화 시 모양이 보존되도록 (회전/반전 없음) 정사각형 간의 대응 관계를 선형 제약으로 표현.
  6. 연결성: 유량 보존 법칙을 통해 각 블록이 연결된 단일 컴포넌트임을 보장.

• 모델 규모: 변수와 제약 조건의 수는 보드 크기 $|C|$와 블록 수 $K$에 따라 $O(K \cdot |C|^2)$로 증가하며, 기하학적 일관성을 유지하는 제약이 가장 비용이 많이 듭니다.

3. 주요 기여: 퍼즐 생성 알고리즘

논문은 ILP 프레임워크를 활용하여 **유일한 해 (Unique Solution)**를 가진 무작위 Evolomino 퍼즐을 생성하는 알고리즘을 제안했습니다.

• 생성 과정:
  1. 빈 보드에서 편향된 무작위 보행 (Biased Random Walk) 을 통해 화살표를 그립니다.
  2. 블록을 배치하고 진화 시킵니다.
  3. CarveToUnique (조각내기): 모든 단서와 블록을 배치한 후, 해의 유일성을 보장하기 위해 불필요한 단서 (화살표, 정사각형, 그림자 셀) 를 제거합니다.
  4. 유일성 검증: 각 단서 제거 시 ILP 솔버를 호출하여 현재 해와 다른 해가 존재하는지 확인합니다. 다른 해가 존재하면 제거를 취소하고 되돌립니다.
• 의의: 이 과정을 통해 생성된 퍼즐은 항상 정답이 하나뿐이며, 이를 통해 벤치마크 데이터셋을 구축할 수 있었습니다.

4. 실험 결과 및 성능

• 데이터셋: 5x5 부터 18x18 까지 다양한 크기의 700 개 이상의 퍼즐 (500 개는 유일 해 보장, 200 개는 해 보장) 로 구성된 커스텀 벤치마크를 구축했습니다.
• 솔버 비교: Google OR-Tools 의 네 가지 솔버 (CP-SAT, SCIP, CBC, BOP) 를 10x10 크기의 50 개 인스턴스로 비교했습니다.
  • 결과: CP-SAT가 압도적으로 우수하여 180 초 시간 제한 내 모든 50 개 인스턴스를 해결했습니다. (BOP 와 SCIP 는 47 개, CBC 는 46 개 해결). 1 초 이내에 48 개를 해결했습니다.
• 규모별 성능 (CP-SAT):
  • 11x11 이하: 중앙값 실행 시간 1 초 미만.
  • 14x14 이하: 중앙값 실행 시간 5 초 이내.
  • 18x18: 중앙값 실행 시간 약 48 초 (1 분 이내).
  • 18x18 인스턴스의 경우 모델에 약 40,000 개의 변수와 100 만 개의 선형 제약 조건이 포함되었음에도 현대적 솔버가 효율적으로 처리함을 보였습니다.

5. 의의 및 결론

• 이론적 기여: NP-완전 문제로 알려진 Evolomino 퍼즐을 ILP 로 공식화하여 체계적인 해결 방법을 제시했습니다.
• 실용적 가치: 최신 CP-SAT 솔버를 사용하면 18x18 크기의 복잡한 퍼즐도 1 분 이내에 해결 가능함을 입증했습니다. 이는 퍼즐 생성 및 해결을 위한 강력한 도구임을 보여줍니다.
• 향후 연구: 백트래킹, SAT 기반 모델, DLX (Dancing Links) 알고리즘 등을 활용한 대안적 접근법 연구의 필요성을 제기했습니다.

요약하자면, 이 논문은 새로운 논리 퍼즐 'Evolomino'의 규칙을 수학적으로 정립하고, 이를 기반으로 효율적인 생성 알고리즘과 고성능 솔버를 통해 대규모 퍼즐을 해결할 수 있음을 입증한 중요한 연구입니다.