2살 아들이 알려준 제약 충족 문제 풀이

My two year old taught me constraint solving

저자의 두 살배기 아들이 Brio 목재 기차 장난감을 좋아해서, 아빠는 기차를 만지지 못하는 대신 트랙 레이아웃을 만드는 데 몰두하게 된다. 이 과정에서 트랙 조각을 모두 닫힌 루프로 배열하는 것이 알고리즘 문제임을 깨닫고, 백트래킹, 제약 충족, SAT 솔버를 사용해 문제를 해결하는 방법을 탐구한다. 아들은 그래프 이론 용어(사이클, 차수, 오일러 회로)를 사용하며 아빠를 놀라게 한다. 이 글은 장난감 트랙을 통해 검색 공간, 지수적 폭발, 제약 조건이 탐색 공간을 줄이는 방법 등 컴퓨터 과학 개념을 설명한다.