15 퍼즐의 짧은 역사

15 퍼즐은 늘 있었던 것처럼 보이지만, 대략적인 「생일」이 있습니다. 1879년에서 1880년으로 넘어가는 겨울입니다. 숫자가 적힌 나무 조각이 든 작은 상자가 몇 달 만에 뉴욕주 북부의 신기한 물건에서 미국과 유럽을 휩쓴 열풍이 되었습니다.

누가 발명했을까

오랫동안 공은 미국의 유명한 퍼즐 작가 샘 로이드에게 돌아갔습니다. 그가 1890년대부터 자기가 발명했다고 주장했기 때문입니다. 하지만 사실이 아니었습니다. 퍼즐 역사가 제리 슬로컴과 딕 소너벨트가 거슬러 올라가 보니, 뉴욕주 커내스토타의 우체국장 노이스 채프먼이 1870년대 중반에 이미 이 퍼즐의 한 형태를 친구들에게 보여 주고 있었습니다. 퍼즐은 시러큐스로, 다시 보스턴으로 퍼졌고, 1879년 말 그곳 목공들이 만들어 팔기 시작했습니다. 채프먼은 1880년에 특허를 신청했지만 거절당했습니다.

1880년의 열풍

1880년 초, 「젬 퍼즐」 「보스 퍼즐」 같은 이름으로 팔린 이 상자는 어디에나 있었습니다. 신문에는 작은 상자에 매달린 사람들을 그린 만평이 실렸고, 고용주들은 일할 시간을 빼앗긴다고 불평했으며, 아예 금지한 가게도 있었습니다. 몇 주 만에 대서양을 건너 영국, 프랑스, 독일로 퍼졌습니다. 그리고 올 때만큼 빠르게, 여름이 되자 유행은 사그라들었습니다.

「14–15」 퍼즐과 상금

열풍의 한 원인은 짓궂은 장치였습니다. 퍼즐은 14와 15만 서로 바뀐 채로 팔리는 일이 많았고, 그것을 바로잡아 보라는 도전이 붙었습니다. 푸는 사람에게 상금을 준다는 이야기도 있었습니다. 샘 로이드는 나중에 자기도 1,000달러의 상금을 걸었다고 말했지만, 실제로 걸었다는 증거는 없습니다. 그래도 이 이야기는 널리 퍼졌습니다.

상금을 받은 사람은 없었습니다. 아무도 풀 수 없었으니까요. 1879년, 미국 수학자 윌리엄 존슨과 윌리엄 스토리가 『아메리칸 저널 오브 매스매틱스』에 증명을 발표했습니다. 어떤 이동을 해도 어떤 셈의 홀짝은 바뀌지 않으므로, 가능한 배치의 정확히 절반은 완성된 판에서 갈 수 있고 나머지 절반은 갈 수 없다는 것입니다. 「14–15」 배치는 갈 수 없는 쪽이었습니다. 인기 있는 놀이가 수학 증명으로 결론 난 가장 이른 예 가운데 하나입니다.

판은 몇 가지나 될까

타일 15개와 빈칸을 상자에 놓는 방법은 16!(약 20.9조) 가지이고, 그중 약 10.5조 가지가 풀 수 있습니다. 종이와 연필로 하나씩 확인하기엔 너무 많아서, 「가장 어려운 판은 몇 수가 필요한가」라는 질문은 백 년 가까이 풀리지 않았습니다.

이것을 바꾼 것은 컴퓨터였습니다. 1985년 리처드 코프는 15 퍼즐을 예로 IDA*라는 탐색 방법을 발표했습니다. 지금도 쓰이는 방법으로, 이 사이트의 풀이기도 이것을 씁니다. 1990년대에는 취리히의 연구자들이 모든 15 퍼즐을 80수 안에 풀 수 있고, 정말로 80수가 모두 필요한 판도 있다는 것을 보였습니다. 더 작은 8 퍼즐은 최대 31수입니다. 5×5의 24 퍼즐은 정확한 값이 아직 알려지지 않았습니다.

여러 가지 이름

중국에서는 15 퍼즐을 「数字华容道」(숫자 화용도)라고 부릅니다. 더 오래된 중국 슬라이딩 블록 퍼즐 「화용도」에서 온 이름으로, 삼국지의 조조가 화용도의 매복에서 빠져나가도록 블록을 움직이는 퍼즐입니다. 일본에서는 「15パズル」, 프랑스에서는 taquin, 스페인과 중남미에서는 juego del 15라고 합니다. 이 퍼즐은 한 번도 사라진 적이 없습니다. 값싼 플라스틱 버전은 고전적인 주머니 장난감이 되었고, 오늘날 스피드 고수들은 4×4를 몇 초 만에 풉니다.

해 보고 싶다면 15 퍼즐을 플레이하거나 푸는 법을 배워 보세요.