2x2 루빅스 큐브를 풀기 위해 Python과 양면 너비 우선 검색을 사용했습니다.
MIT 6.006 프로젝트에서 영감을 얻었습니다. 처음부터 독특하게 만들어졌습니다.
https://youtu.be/ZHxLO6fubaU
큐브 API, 알고리즘, GUI를 처음부터 만들었습니다. 6개의 면 각각에는 4개의 서로 다른 정사각형이 있어 총 24개의 정사각형이 됩니다. 또한 큐브를 구성하는 모서리 조각은 총 8개이며, 각 모서리 조각은 3가지 방향을 가지므로 24개의 정사각형과 조화를 이룹니다.
각 측면의 24개 하위 섹션 각각을 'xyz'가 포함된 문자열로 정의했습니다. 여기서 x는 바로 향하는 색상이고 y와 z는 해당 모서리의 큐브 주위에서 시계 방향으로 이동합니다.
저는 큐브를 돌아다니며 해결된 상태를 나타내는 고정 숫자를 각 면에 할당했습니다. 예를 들어 0, 1, 2, 3은 앞면의 흰색 부분 4개 부분으로, 0은 왼쪽 상단이고 다른 하나는 시계 방향 순서입니다.
큐브에서 수행할 수 있는 동작은 12가지입니다. 오른쪽, 왼쪽, 위, 아래, 앞, 뒤. 이들 각각은 시계 반대 방향으로 움직이므로 6x2 = 12 이동입니다. 이들 12개 각각은 큐브의 절반을 조작하므로 12개의 정사각형이 됩니다. 이러한 움직임을 만들기 위해 하위 사각형이 원래 위치에서 다음 위치로 회전하는 시계 방향으로 6개 각각에 대한 사전을 만들었습니다. 소수를 수행하기 위해 키와 값을 바꿨습니다.
이 문제를 해결하는 것은 큐브의 가능한 순열이 엄청나게 많기 때문에 특히 까다롭습니다. 24개의 하위 사각형이 있으며 이는 24P24 = 24!입니다. 이것은 10^23의 크기입니다. 특정 상황으로 인해 이 금액보다 적지만 그 수는 여전히 엄청납니다.
트리를 만들려면 각 동작을 실행해야 하고 매우 커지는 동작의 모든 동작을 실행해야 합니다. 12^트리 높이. 이전에 방문한 순열에 대한 작업을 다시 실행하지 않도록 방문한 위치의 사전을 생성하여 이 크기를 제한할 수 있었습니다.
나는 1면 BFS를 만드는 것으로 시작했지만 분기 트리가 너무 커지기 때문에 재귀 한계에 도달했습니다. 이 문제를 해결하기 위해 시작 솔루션과 종료 솔루션에서 분기를 번갈아 생성하여 양면 BFS를 사용했습니다. 나무를 생성하고 반대편이 이미 지점을 찾았는지 확인합니다. 그렇다면 연결 지점을 반환합니다.
이 모든 과정에서 각 노드는 상위(전면 분기의 경우) 또는 하위(후면 분기의 경우)를 저장합니다. 소요된 경로를 찾기 위해 연결 노드에서 부모를 재귀적으로 찾은 다음 해당 지점의 모든 자식을 찾았습니다. 이로 인해 스크램블에서 해결까지의 위치가 배열되었습니다.
이 프로젝트에서는 그래프 이론과 너비 우선 검색을 적용했습니다. Python과 재귀 능력이 향상되었습니다. 또한 더 오래 걸리는 솔루션을 찾을 수 없었기 때문에 2x2 큐브를 풀기 위한 최대 이동 수는 11개 라는 것을 실험적으로 발견했습니다.
tkinter 라이브러리를 사용하여 프로젝트용 GUI를 만드는 방법을 배웠습니다.
