페그 솔리테어(Peg Solitaire)는 구멍이 뚫린 보드 위에 여러 개의 말(peg, 구슬)을 놓고, 말을 다른 말 위로 점프시켜 건너뛴 말을 제거하는 1인용 보드 게임이다. 영국에서는 단순히 '솔리테어(Solitaire)'로 불리며, 미국에서는 카드 게임 솔리테어와 구분하기 위해 '페그 솔리테어'라는 명칭을 사용한다. '마블 솔리테어(marble solitaire)', '솔로 노블(solo noble)' 등으로도 불린다.
역사
페그 솔리테어의 가장 오래된 기록은 1697년 프랑스 루이 14세의 궁정으로 거슬러 올라간다. 1697년 8월자 프랑스 문학 잡지 《메르퀴르 갈랑(Mercure galant)》에 보드의 형태, 규칙 및 예시 문제에 대한 설명이 실려 있는데, 이는 인쇄물로 확인되는 최초의 기록이다. 10년 후인 1707년, 클로드 오귀스트 베레(Claude Auguste Berey)가 수비즈 공주 안 드 로앙-샤보(Anne de Rohan-Chabot)가 페그 솔리테어를 즐기는 모습을 새긴 판화를 제작한 바 있다.
보드의 종류
전통적으로 두 가지 형태의 보드가 널리 사용된다.
- 영국식(English) 보드: 십자가 모양으로 총 33개의 구멍이 있다. 게임 시작 시 중앙의 구멍 하나만 비워 두고 나머지 32개 구멍에 말을 채운다.
- 유럽식(European) 보드: 37개의 구멍으로 구성되어 있으며, 영국식보다 팔 부분이 한 줄씩 더 길다.
이 외에도 한 변의 길이가 5인 삼각형 보드(15개 구멍), 다이아몬드형 보드(41개 구멍) 등 다양한 변형이 존재한다.
게임 규칙
게임의 목표는 유효한 이동을 반복하여 보드 위에 단 하나의 말만 남기는 것이다. 이상적으로는 마지막 말이 중앙 구멍에 위치하는 것이 가장 완벽한 클리어로 간주된다.
유효한 이동은 다음과 같다. 말은 상하좌우 직교 방향으로만 이동할 수 있으며, 인접한 구멍에 있는 다른 말을 뛰어넘어 그 너머의 빈 구멍으로 이동한다. 이때 뛰어넘긴 말은 보드에서 제거된다. 대각선 방향으로는 점프할 수 없다.
수학적 분석
페그 솔리테어는 조합론과 추상대수학의 관점에서 깊이 연구되었다. 1990년에는 일반화된 Hi-Q 문제(페그 솔리테어와 동등한 문제)가 NP-완전(NP-complete)임이 증명되었다. 1999년에는 컴퓨터를 이용한 전수 탐색을 통해 영국식 보드의 모든 가능한 게임 변형이 완전히 해결되었다.
영국식 보드에서 추상대수학을 통해 증명된 바에 따르면, 게임이 하나의 말만 남기고 성공적으로 끝날 수 있는 보드상의 위치는 단 5곳(중앙 및 네 변의 중앙)뿐이다. 또한 영국식 표준 게임의 최단 해법은 18수이며, 이는 1912년 어니스트 버골트(Ernest Bergholt)가 발견하고 1964년 존 비즐리(John Beasley)가 최단임을 증명하였다.
유럽식 보드의 경우, 중앙 구멍을 처음에 비운 상태에서는 직교 이동만으로는 하나의 말만 남기는 것이 불가능함이 한스 잔테마(Hans Zantema)의 논증을 통해 증명되었다. 이는 보드의 위치를 세 가지 유형(A, B, C)으로 분류하여 패리티(parity) 분석을 통해 설명된다.
대중문화 속의 페그 솔리테어
미국의 레스토랑 체인 크래커 배럴(Cracker Barrel)은 모든 테이블에 15개 구멍의 삼각형 페그 솔리테어를 비치해 놓은 것으로 유명하다. 애니메이션 영화 《카우보이 비밥: 천국의 문》에서는 주인공의 적대자 빈센트 볼라주가 여가 시간에 페그 솔리테어를 즐기는 모습이 등장한다. 1992년에는 게임보이용 비디오 게임으로도 출시되었으며, 《레이튼 교수와 악마의 상자》에도 퍼즐의 일부로 포함되어 있다.
