🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

이 논문은 스도쿠를 그래프 채색 문제로 재구성하여 기존의 HNN 및 ONN 방식보다 $4 \times 4$ 및 $9 \times 9$ 퍼즐 모두에서 현저히 높은 정확도를 달성한 최적화된 진동 신경망(ONN) 솔버를 소개한다.

원저자: Filip Sabo, Aida Todri-Sanial

게시일 2026-07-20

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Filip Sabo, Aida Todri-Sanial

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터가 단순히 초고속 계산기처럼 숫자를 crunching(처리)하는 것이 아니라, 리듬에 맞춰 춤을 추는 세상을 상상해 보십시오. 이것이 바로 **진동 신경망(Oscillatory Neural Networks, ONNs)**의 영역이며, 일종의 "물리 기반" 컴퓨팅입니다. 이 네트워크는 표준적인 전자 스위치를 사용하는 대신, **진동자(oscillators)**라고 불리는 작게 떨리는 단위들을 사용합니다. 이것은 마치 메트로놈이 가득 찬 방이나 합창단과 같습니다. 이 시스템에서 정보는 단순한 "켜짐(on)" 또는 "꺼짐(off)" 비트로 저장되는 것이 아니라, **위상(phases)**이라고 알려진 진동의 타이밍에 저장됩니다. 두 진동자가 완벽하게 동기화되어 진동하면 "동위상(in phase)" 상태이고, 서로 반대 시간에 진동하면 "역위상(out of phase)" 상태입니다.

이 네트워크의 목표는 모든 진동자가 안정적인 패턴으로 자리 잡는 완벽한 조화, 즉 가장 낮은 에너지 상태를 찾는 것입니다. 이러한 접근 방식은 **조합 최적화 문제(combinatorial optimization problems)**를 해결하는 데 특히 유용합니다. 이는 규칙에 어긋나지 않도록 여러 조각을 배치해야 하는 퍼즐 같은 문제입니다. 여러분은 아마도 인접한 국가들이 서로 같은 색을 공유하지 않도록 지도를 색칠하는 문제인 그래프 채색(Graph Coloring) 문제를 들어본 적이 있을 것입니다. 만약 진동자 네트워크가 자연스럽게 "이웃"들이 같은 시간에 진동하지 않는 패턴으로 자리 잡게 할 수 있다면, 여러분은 단순한 무차별 대입 수학이 아닌 물리학의 법칙을 사용하여 복잡한 퍼즐을 해결한 것입니다. 이것이 중요한 이유는 전통적인 컴퓨터가 이러한 유형의 퍼즐을 다룰 때 엄청난 양의 전력과 시간을 소모하며 고전하는 반면, 이 춤추는 진동자들은 더 빠르고 에너지 효율적인 사고 방식을 제공할 수 있기 때문입니다.

위대한 스도쿠 댄스 배틀

이제 **스도쿠(Sudoku)**에 대해 이야기해 봅시다. 규칙은 알고 계실 겁니다. 격자 안에 숫자를 채워 넣되, 모든 행, 열, 그리고 작은 박스 안에 1부터 9까지(또는 작은 버전의 경우 1부터 4까지)의 숫자가 중복 없이 포함되도록 해야 합니다. 이것은 고전적인 논리 퍼즐이지만, 컴퓨터에게는 엄청난 시행착오를 요구하는 골칫거리입니다.

이 논문의 연구자들인 에인트호번 공과대학교의 필립 사보(Filip Sabo)와 아이다 토드리-사니알(Aida Todri-Sanial)은 이 "춤추는 진동자" 네트워크를 사용하여 스도쿠를 해결하기로 했습니다. 그들은 스도쿠 격을 하나의 그래프 채색 문제로 취급했습니다. 스도쿠 격의 각 빈 셀을 한 명의 무용수라고 상상해 보십시오. 규칙은 간단합니다: 같은 행, 열, 또는 박스에 있는 두 무용수는 같은 "색상"(이 경우 특정 숫자, 예를 들어 1, 2, 또는 3을 나타냄)을 입을 수 없습니다.

진동자의 세계에서 "색상을 입는다"는 것은 특정 리듬으로 진동하는 것을 의미합니다. 9x9 스도쿠의 경우, 진동자가 선택할 수 있는 9가지 가능한 리듬(위상)이 있습니다. 네트워크의 임무는 어떤 두 이웃도 같은 춤 동작을 하지 않도록 모든 무용수가 리듬을 선택하게 만드는 것입니다.

기존 댄스 동작의 문제점

저자들은 다른 과학자들이 이전에 이를 어떻게 시도했는지 살펴보았습니다. 한 방법은 매우 복잡한 수학 공식을 사용하는 것이었는데, 이는 마치 춤을 추기 전에 모든 근육의 움직임을 미리 계산하여 안무를 짜는 것과 같이 비용이 많이 드는 작업이었습니다. 또 다른 방법은 더 단순한 접근 방식을 사용했지만, 치명적인 결함이 있었습니다. 바로 무용수들이 "속임수"를 쓸 수 있게 허용한다는 점이었습니다.

두 무용수가 같은 행에서 둘 다 "숫자 1" 댄스를 하기로 결정한 시나리오를 상상해 보십시오. 기존의 더 단순한 모델에서는 네트워크가 "헤이, 그들은 둘 다 '숫자 1' 리듬을 하고 있네, 둘 다 유효한 리듬이니까 괜찮아!"라고 생각할 수도 있습니다. 하지만 스도쿠에서 이것은 재앙입니다. 규칙에 따르면 같은 행에 두 개의 1이 있어서는 안 됩니다. 기존 모델에는 무용수들이 실수로 잘못된 숫자에 동기화되었을 때 그들을 그 나쁜 상태에서 쫓아낼 방법이 없었습니다.

새로운 "킥(Kick)" 항

이를 해결하기 위해, 저자들은 진동자를 춤추게 하는 더 단순한 새로운 방법을 발명했고, 특별한 "킥(kick)" 메커니즘을 추가했습니다.

더 단순한 리듬: 복잡하고 비용이 많이 드는 수학 공식 대신, 그들은 더 깔끔하고 직접적인 방정식을 사용했습니다. 이를 통해 컴퓨터 시뮬레이션이 훨씬 더 빠르고 저렴하게 실행되었습니다.
"킥" (비법 소스): 이것이 가장 중요한 부분입니다. 그들은 방정식에 심판 역할을 하는 특별한 항을 추가했습니다. 만약 같은 행, 열, 또는 박스에 있는 두 무용수가 실수로 정확히 같은 주파수로 진동하기 시작하면(즉, 같은 숫자를 선택하면), 이 심판은 그들에게 날카로운 "킥"을 줍니다. 이 킥은 그들을 그 안정적이고 편안한 상태에서 밀어내어 다른 리듬을 시도하도록 강제합니다.

이 "킥"은 네트워크가 실제로 올바르게 풀렸을 때만 안착하도록 보장합니다. 이것은 마치 교실을 돌아다니는 선생님과 같습니다. 만약 두 학생이 똑같이 틀린 답을 속삭이고 있다면, 선생님은 그들의 어깨를 톡톡 쳐서 멈추고 다시 생각하게 만드는 것과 같습니다.

결과: 결점 없는 퍼 प्रदर्शन (Performance)

연구팀은 자신들의 새로운 "킥이 있는(kick-ass)" 진동자 솔버를 4x4 격부터 표준 9x9 격에 이르는 수천 개의 스도쿠 퍼즐에 테스트했습니다. 그들은 자신들의 결과를 홉필드 신경망(HNN)에 기반한 솔버와 또 다른 표준 진동 신경망을 포함한 두 가지 유명한 솔버와 비교했습니다.

결과는 다음과 같았습니다:

4x4 퍼즐의 경우: 그들의 새로운 솔버는 거의 완벽했습니다. 퍼즐에 숫자가 얼마나 많이 비어 있든 상관없이 거의 100%의 퍼즐을 정확하게 해결했습니다. 다른 솔버들은 어려워질수록(비어 있는 숫자가 많아질수록) 정확도가 급격히 떨어지며 고전했습니다.
9x9 퍼즐의 경우: 결과는 여전히 인상적이었지만, 완전히 완벽하지는 않았습니다. 퍼즐에 비어 있는 숫자가 적을 때(약 25% 미만)는 그들의 솔버는 결점이 없었습니다. 퍼즐이 더 어려워졌을 때도(최대 37.5%까지) 80% 이상의 퍼즐을 해결했습니다. 그러나 퍼즐이 매우 어려워졌을 때(50% 이상의 빈 숫자)는 솔버가 흔들리기 시작하여 약 50% 정도만 맞혔습니다. 다른 솔버들은 훨씬 더 빨리 실패했으며, 종종 비어 있는 숫자가 40~50%를 넘어서면 제대로 된 퍼즐을 하나도 풀지 못했습니다.

연구진은 또한 "질서 매개변수(order parameter)"를 살펴보았는데, 이는 기본적으로 진동자들이 최종적인 올바른 리듬으로 얼마나 잘 안착했는지를 나타내는 점수입니다. 그들은 솔버가 퍼즐을 맞혔을 때마다 진동자들이 매우 잘 조직되어 있었다는 것(높은 질서 매개변수)을 발견했습니다. 퍼즐을 틀렸을 때는 진동자들이 혼란스럽고 안정적인 패턴에 합의하지 못했습니다.

향arian (Next Steps)

저자들은 자신들의 "킥" 항이 성공의 이유라고 확신하고 있지만, 아직 할 일이 남아 있다고 인정합니다. 그들의 모델에는 작동시키기 위해 수동으로 돌려야 했던 몇 가지 "조절 가능한 매개 변수(tuneable parameters)"가 있었으며, 이를 알아내는 데 많은 시간이 걸렸습니다. 또한 가장 어려운 9x9 퍼즐의 경우, 진동자들이 가라앉기 위해 더 많은 시간 동안 "춤을" 추어야 했거나, 혹은 "킥"이 충분히 강력하지 않았을 수도 있다는 점을 발견했습니다.

그들은 미래 버전의 솔버가 더 복-잡한 "비선형(nonlinear)" 진동자(더 복잡한 동작을 가진 무용수들)를 사용하거나, 규칙 위반자를 더 잘 잡아내도록 "킥" 함수를 미세 조정할 수 있다고 제안합니다. 하지만 현재로서, 그들은 이러한 춤추는 네트워크의 물리학에 단순하고 영리한 규칙을 추가함으로써 이전보다 훨씬 더 잘 스도쿠 퍼즐을 해결할 수 있음을 보여주었습니다. 이것은 작은 발걸음이지만, 때로는 망가진 시스템을 고치기 위해 필요한 것이 단지 올바른 방향으로의 작은 밀침(push)일 수 있다는 것을 증명합니다.

기술 요약: 진동 신경망을 이용한 그래프 채색 접근 방식의 스도쿠 해결

문제 정의
본 논문은 물리 기반 컴퓨팅 패러다임을 사용하여 제약 조건이 있는 조합 최적화 문제(COP), 구체적으로 스도쿠 퍼즐을 해결하는 과제를 다룹니다. 전통적인 컴퓨팅 아키텍처는 문제의 크기가 커짐에 따라 해결 시간이 기하급수적으로 증가하는 NP-어려운(NP-hard) 문제를 다룰 때 메모리-연산 병목 현상과 높은 전력 소비 문제에 직면합니다. 저자들은 기존의 인공 신경망(ANN) 및 호프필드 신경망(HNN)의 대안으로, 결합된 진동자들의 역학을 통해 기저 에너지 함수를 최소화하는 진동 신경망(ONN)을 활용할 것을 제안합니다. 구체적인 과제는 스도카 규칙(즉, 어떤 행, 열, 박스에서도 숫자가 중복되지 않아야 함)을 진동자의 위상 역학에 매핑할 때, 규칙 위반(예: 동일한 행에 있는 두 진동자가 동일한 "숫자" 위상으로 수렴하는 경우)을 허용하지 않도록 하는 것입니다.

방법론
저자들은 스도쿠를 그래프 채색 문제로 정식화하며, 여기서 각 셀은 노드가 되고 엣지는 행, 열 또는 박스를 공유하는 셀들을 연결합니다. 목표는 각 노드에 고유한 "색상"(위상)을 할당하는 것입니다.

위상 매핑: $N \times N$ 크기의 스도쿠(여기서 $K=N$ )에 대해, 이상적인 위상은 다음과 같이 이산 값으로 매핑됩니다: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ (단, $k \in \{1, ..., K\}$ ).
수정된 상미분방정식(ODE): 저자들은 기존의 ONN 그래프 채색 모델(특히 Max-K-Cut 정식화)이 조절 가능한 파라미터로 인해 계산 비용이 높고, 연결된 노드들이 동일한 위상으로 수렴하여 규칙을 위반할 가능성이 있다는 점을 비판합니다. 이에 따라 저자들은 더 단순하고 계산 비용이 저렴한 진동 역학을 위한 상미분방정식(ODE)을 제안합니다:
$\dot{\phi}_i = -f_{unknown}(\phi_i) \left[ \frac{1}{N} \sum_{j} W_{ij} \sin\left(\frac{K}{2}(\phi_i - \phi_j)\right) + K_S \sin(K\phi_i) \right] + f_{unknown}(\phi_i) K_G \sum_{j} W'_{ij} g(\phi_i, \phi_j)$
- 첫 번째 항: 진동자들이 $\frac{2\pi}{K}$ 만큼 떨어지도록 유도합니다 (Max-K-Cut 로직).
- 두 번째 항 ( $K_S$ ): 진동자들이 특정 이상적인 위상 값에 안착하도록 강제합니다.
- 세 번째 항 (새로운 기여): 연결된 두 진동자가 동일한 위상에 도달했는지(규칙 위반)를 감지하는 함수 $g(\phi_i, \phi_j)$ 를 포함하는 추가 항입니다. 만약 위반이 감지되면, 이 항은 진동자를 해당 안정 상태에서 "밀어내는(kick)" 그래디언트를 주입합니다.
가중치 행렬 ( $W_{ij}$ ): 가중치는 알려진 숫자가 미지의 숫자보다 더 강한 영향력을 행사하도록 설계되었습니다. 알려진 숫자는 고정되어 있으며(그래디언트 0), 미지의 숫자는 이웃과 상호작용합니다. 동일한 행/열/박스 내의 두 미지 숫자 사이의 가중치는 음수이지만, 알려진 숫자와 관련된 가중치보다는 절댓값이 작습니다.
질서 매개변수 ( $\kappa$ ): 수렴을 추적하기 위한 지표가 정의되며, 값이 1에 가까울수록 사전에 설정된 이상적인 위상으로 성공적으로 수렴했음을 나타냅니다.

주요 기여

새로운 ONN 정식화: 본 논문은 스도쿠를 그래프 채색 문제로 재정의하면서 ODE에 특정 제약 조건 강제 항을 추가한 수정된 ONN 솔버를 도입합니다. 이 항은 시스템이 모든 스도쿠 제약 조건을 충족할 때만 소멸하는 그래디언트(안정 상태)에 도달하도록 보장하여, 연결된 노드들이 동일한 위상으로 수렴하는 "거짓 양성(false positives)" 문제를 방지합니다.
계산 효율성: 저자들은 복잡하고 파라미터가 많은 Max-K-Cut ODE를 상호작용 함수의 피크 폭(peak-width) 파라미터를 조정할 필요가 없는 더 단순하고 계산 비용이 저렴한 모델로 대체했습니다.
벤치마킹: 본 연구는 $4 \times 4$ 및 $9 \times 9$ 퍼즐에 대해 미지 숫자의 비율이 다양하게 변하는 조건에서 기존 HNN 솔버 및 일반적인 ONN 솔버와의 종합적인 정확도 비교를 제공합니다.

결과

$4 \times 4$ 퍼즐: 제안된 솔버는 테스트된 모든 미지 숫자 비율(최대 87.5%까지)에서 거의 완벽한 정확도를 달enc혔으며, HNN 및 기존 ONN 솔버를 크게 압도했습니다. HNN 솔버는 미지 비율이 60%를 초과할 때 완전히 실패했으며, 기존 ONN 솔버는 미지 비율이 50%일 때 약 80%의 정확도로 떨어졌습니다.
$9 \times 9$ 퍼즐: 제안된 솔버는 다른 방법들에 비해 우수한 성능을 입증했습니다. 미지 비율이 25%까지는 완벽한 정확도를 달성했으며, 37.5%의 미지 비율에서도 80% 이상의 정확도를 유지했습니다. 그러나 미지 숫자가 증가함에 따라 성능이 저하되어, 미지 비율이 50%일 때 약 50%로 떨어졌고, 미지 비율이 70%를 초과하면 퍼즐을 올바르게 해결하는 데 실패했습니다.
질서 매개변수: 정확도와 질서 매개변수 사이에 강한 상관관계가 있었습니다. 높은 정확도는 이상적인 위상으로의 수렴(질서 매개변수 1 근처)과 일치했으며, 낮은 정확도는 낮은 질서 매개변수와 상관관계가 있었는데, 이는 시스템이 유효한 안정 상태에 도달하지 못했음을 시사합니다.

의의 및 주장
본 논문은 제안된 접근 방식이 특히 작은 그리드( $4 \times 4$ ) 및 중간 정도의 제약이 있는 $9 \times 9$ 그리드에서 기존 HNN 및 ONN 스도카 솔버보다 정확도 측면에서 크게 우수하다고 주장합니다. 저자들은 이러한 성공의 원인을 에너지 최소화는 만족하지만 스도카 규칙을 위반하는 무효한 안정 상태를 효과적으로 제거하는 ODE의 추가 항 덕분이라고 설명합니다.

저자들은 모델이 네 개의 조절 가능한 파라미터에 의존하여 파라미터 탐색 비용이 많이 든다는 점을 언급하며 한계를 겸허히 인정했습니다. 그들은 $9 \times 9$ 퍼즐에서 미지 비율이 매우 높을 경우, 추가된 항이 충분히 강력하게 스케일링되지 않았거나 시스템이 안정화되는 데 더 많은 진동 주기가 필요할 수 있다고 제안합니다. 본 논문은 제약 조건 강제 항을 포함하는 확장된 ODE가 ONN을 이용한 COP 해결을 위한 유효한 전략임을 결론지으며, 향-후 연구에서 고도의 비선형 진동자와 대안적인 제약 조건 강제 함수 정식화를 탐구해야 한다고 제안합니다.

위대한 스도쿠 댄스 배틀

기존 댄스 동작의 문제점

새로운 "킥(Kick)" 항

결과: 결점 없는 퍼 प्रदर्शन (Performance)

향arian (Next Steps)

유사한 논문