8 Queens 작동 원리

어떤 서클에서 운영하는지에 따라-예를 들어 가장 친한 친구는 컴퓨터 프로그래머이고 여동생은 체스 신동입니다-당신은 이미 8 Queens 퍼즐에 익숙 할 것입니다. 나머지 우리에게 8 Queens 퍼즐 (또는 문제 또는 단순히 "8 Queens")은 아마도 우리가 생각하는 데 많은 시간을 소비하는 것이 아닐 것입니다.

퍼즐은 충분히 간단합니다. 두 사람이 서로 공격하지 않도록 체스 판에 퀸 8 개를 어떻게 배치 할 수 있습니까? "무슨 체스 판에 배치 할 수 있습니다 왕비의 최대 수는, 그래서 두 개의 서로를 공격 할 수 없음"하지만이 퍼즐은 훨씬 덜 어려워진다으로 또는, 질문은 종종 언급되어있을 때 구글 이, 용어 「8 퀸즈 퍼즐」이 등장.

당신은 왜 지구상에서 당신이 여덟 명의 여왕을 두는 데 관심이 있는지 스스로에게 물을 것입니다. 그리고 예, 표면적으로는 전략적인 퍼즐 일뿐입니다. 그러나 (그리고 이것은 컴퓨터를 코딩하는 가장 친한 친구를 갖는 것이 편리한 곳입니다) 8 Queens 퍼즐은 프로그래머의 정통성과 문해력을 테스트하는 좋은 방법입니다.

이제 겁내지 마세요. 계속 읽기 위해 컴퓨터 프로그래밍의 복잡성을 이해하도록 강요받지 않을 것입니다. 그러나 프로그래밍 코드를 사용하여 퍼즐을 풀 수 있으며 일부는 다른 것보다 더 우아하다는 것을 알아야합니다. 예를 들어, 한 번에 하나씩 제외하고 가능한 모든 배치를 간단히 살펴볼 수있는 "무력"프로그램을 사용하여 솔루션을 확실히 찾을 수 있습니다. 그러나 정교한 코더는보다 정교한 알고리즘 을 사용하여 바로 가기가있는 프로그램을 구성 하여 솔루션을 더 빨리 찾을 수 있습니다. 8 Queens와 같은 광범위한 문제에 대한 솔루션을 코딩하는 비정상적이거나 독창적 인 방법을 생각 해낼 수 있다는 것은 코드 작성자의 정통한 사람을위한 훌륭한 테스트가 될 수 있습니다.

따라서 8 Queens의 작동 방식을 설명하기 위해 1과 0을 묶지 않을 것이지만 퍼즐에 대한 몇 가지 해결책을 제공 할 것입니다.

이제 퍼즐의 기본 전제를 ​​얻었으므로 문제가 왜 그렇게 독특한 지 확인해야합니다. 이를 위해 우리의 체스 기본 사항을 살펴 보겠습니다. 체스 게임에서 여왕은 고려해야 할 힘입니다. 그녀는 원하는만큼 수직, 수평 또는 대각선으로 직선으로 이동할 수 있습니다. 한 가지 문제점은 점프를 할 수 없다는 것입니다. 그러니 폰이 방해가된다면 그녀는 그것을 잡아서 멈춰야합니다.

이것이 8 Queens 퍼즐을 흥미롭게 만드는 이유입니다. 여왕이 위, 아래, 왼쪽, 오른쪽 및 대각선으로 움직일 수 있다면, 같은 행, 열 또는 대각선을 공유하지 않고 얼마나 많은 전쟁 왕족이 보드를 차지할 수 있습니까? 자, 당신은 보드에 여왕을 놓고 그들 모두를 치기 전에 다른 조합을 시도하는 것이 훌륭한 아이디어라고 생각할 수 있습니다. 물론 가능합니다. 그러나 4,426,165,368 개의 잠재적 솔루션이 있으므로 지름길을 찾는 것이 좋습니다.

여왕을 40 억 개의 사각형에 배치하기 전에 먼저 누군가가 실제로 언젠가 앉아서 이것이 오후를 낭비하는 좋은 방법이라고 결정했음을 인정합시다. 예상대로 "My Big Fat Gypsy Wedding"를 재방송 한 사람이 아니라 19 세기 독일 체스 마스터이자 작곡가 인 Max Bezzel이었습니다. ( 체스 작곡가 는 퍼즐이라고도하는 체스 문제를 만들어 해결하는 사람입니다.) 1848 년 독일 체스 잡지 DieSchachzeitung에 처음 등장했습니다.

Bezzel은 퍼즐을 푸는 데 그다지 관심이 없었습니다. 그는 단순히 질문을 던지는 것에 만족했습니다. 그러나 1850 년에 수학자 Franz Nauck은이 문제를 논의한 또 다른 기사를 썼습니다. (퍼즐에 대한 첫 번째 해결책은 결국 Nauck에 의해 해결되었습니다.) 대수학의 기본 이론을 발견 한 것으로 알려진 19 세기 수학자 칼 가우스의 관심을 끌었습니다. Gauss가 해결책을 찾는 데 관심을 갖자 다른 사람들이 따라 갔고 퍼즐을 풀기위한 다양한 접근법이 등장하기 시작했습니다.

"8"이 서로 공격하지 않고 보드에 얼마나 많은 여왕을 배치 할 수 있는지에 대한 우리의 구체적인 질문에 대한 답이라는 것은 놀라운 일이 아닙니다. 하지만 여덟 명의 여왕을 배치 할 수있는 방법과 그것이 어떻게 설정되는지 살펴 보겠습니다.

우리는 무차별 대입 컴퓨터 프로그램이 퍼즐을 해결하는 한 가지 방법에 대해 이야기했습니다. 4,426,165,368 개의 가능성을 수동으로 테스트하는 것이 확실히 무차별 대입으로 간주되지만 솔루션 범위를 좁히는 더 쉬운 방법이 있습니다. 다른 수학자 인 JWL Glaisher가 1874 년에 해결책을 찾기 위해 결정자를 사용하는 방법을 설명하는 논문을 발표했을 때 단순화 된 방법이 제공되었습니다. "Determinants"는 약간 어렵게 들리지만 Glaisher가 기본적으로 매트릭스를 구성했으며 그 매트릭스에서 파생 된 시스템을 사용하여 가능한 솔루션을 92로 좁힐 수 있다는 사실 만 알아야합니다.

그리고 92 개의 솔루션이 남아 있습니다. 그러나 속지 마십시오. 당신은 92 개의 체스 판을 정렬 할 수 없을 것입니다. 각 체스 판에는 8 개의 퀸이 평화롭게 자리 잡고 있습니다. 왜냐하면 실제로는 12 개의 독특한 솔루션이 있기 때문입니다.

혼란스러워? 12 개의 고유 한 솔루션과 92 개의 기본 솔루션의 차이점은 말 그대로 보는 방식에 달려 있습니다. 여덟 명의 여왕으로 12 개의 서로 다른 보드를 설정할 수 있지만 보드를 단순히 뒤집거나 거울에 반사하여 보드를 기술적으로 다르게 보이게하여 "다르게"만들기 만하면됩니다. 해결책. (이것은 회전 및 반사 대칭 작업 이라고 합니다..) 그래서 당신은 12 개의 독특한 보드를 가지고 90도, 180도, 270도를 돌린 다음 각 회전에서 반사합니다. 하지만 한 가지 더-하나의 고유 한 보드가 대칭이므로 두 각도에서 동일하게 보입니다. 다른 모든 보드에는 8 개의 변형이 있지만 대칭형 보드에는 4 개만 있습니다. 따라서 12 개의 보드 x 8 개의 변형 (96) 대신 대칭형 보드에 존재하지 않는 4 개를 실제로 뺍니다. 우리는 무엇을 얻습니까? 92 가지 기본 솔루션.

이제 수학에 속지 마십시오. 당신은 항상 체스 판을 발견하고 자신을 위해 몇 가지 배치를 시도 할 수 있습니다. (물론 하나의 답을 찾는 것이 12 개를 모두 찾는 것보다 훨씬 쉽습니다.) 그리고 웹 에는 몇 가지 다른 솔루션을 찾을 수 있는 프로그램도 있습니다 . (경고 : 그들은 당신을 어리석게 만들 수 있습니다.)

여왕을 뒤섞기 전에 다음 페이지에서 자세한 정보를 확인하십시오.

알파벳보다 알고리즘에 덜 관심이있는 사람 이었기 때문에 여덟 퀸즈 퍼즐을 이해하는 데 큰 기대가 없었습니다. 실용적인 응용 프로그램이 있다고 확신했지만 볼 수 없었습니다. 아이러니하게도 문제의 방대함을 이해했을 때 그것이 왜 유용 할 수 있는지 알아보기 시작했습니다. 엄청난 가능성에서 솔루션 세트를 찾는 것이 코드가 존재하는 이유 중 하나입니다. 8 Queens 문제는 프로그래머와 수학자 모두에게 검색을 단순화하는 새로운 기술을 발견하도록 도전합니다.

관련된 링크들

출처