오늘 저녁 나는 우드 퍼즐을 풀려고했는데, 이런 종류의 문제에 대한 해결책을 찾을 수있는 가장 좋은 방법은 무엇인지 궁금해했습니다.이 게임을 해결하는 가장 좋은 방법은 무엇입니까?
목표는 단단한 물체 (예 : 3 차원의 테트리스 조각)를 결합하여 피스가 적합 할 경우에만 조각을 구조물에 부착하거나 미끄러질 수 있다는 사실을 고려한 적절한 방법으로 모양을 형성하는 것입니다 운동의 종류 (회전 무시, 단지 90 ° 회전).
this 사진을 확인하여 무슨 뜻인지 이해하십시오.
내 최신 CS 클래스에서 상태를 C++로 개체로 표현하여 작동하는 일반적인 퍼즐 솔버를 만들었습니다. 각 객체에는 표현 된 상태를 다른 상태와 비교하는 메소드가 있습니다. 이것은 국가가 이미 보았는지 확인하기 위해 메모 작성에 사용되었습니다. 또한 각 주에는 해당 상태에서 직접 도달 할 수있는 상태를 생성하는 방법 (예 : 블록 회전, 블록 배치, 블록 이동)이 있습니다. 해결사는 상태 대기열을 유지하고 대기열 앞쪽에서 상태를 팝핑하여 원하는 상태 (즉, 해결 된 퍼즐)인지 확인합니다. 그렇지 않은 경우, 메모 작성 (해시 세트 사용) 상태가 이미 확인되었는지 확인했습니다. 그렇지 않은 경우 현재 상태에서 도달 할 수있는 상태가 생성되어 대기열의 후면에 추가됩니다. 빈 큐가 풀리지 않는 퍼즐을 알렸다.
3D와 비슷한 것을 개념화하는 것은 어렵 겠지만, 컴퓨터화 된 퍼즐 해결에 대한 기본 접근법입니다.
컴퓨터의 경우 조합 수가 적기 때문에 간단한 검색 알고리즘을 시도하기 때문에 다소 문제가 많습니다. 모든 가능한 구성을 확인한 후이 구성의 결과에서 끝 구성 (예 : 큐브)으로 끝날 때까지 계속 진행하는 algorithm입니다.
모든 상태 검사 및 변환을 한 상태에서 다른 상태로 수행 할 수있는 프로그램을 작성하는 데 문제가 있습니다. 물리적으로 구성이 가능한지 확인해야하기 때문입니다.
3 차원 polyomino 패킹 문제의 하위 집합과 같습니다. 해당 주제에는 다양한 scholarly papers 명이 있습니다.
당신이 처리하고자하는 퍼즐이 당신이 링크 한 사진이라면, 바닥에있는 길을 찾을 때까지 가능한 해결책 트리를 검색하는 것이 아마도 가능할 것입니다.
각 퍼즐 조각이 얼굴에 부착 된 여러 큐브 인 경우 각 큐브에 각 조각을 맞추어서 퍼즐을 해결하려면 각 큐브에 4 번씩 구성 큐브를 넣은 다음 다음과 같습니다.
각 조각의 임의의 큐브를 원점으로 선언하십시오. 각 퍼즐 조각에 대해 가능한 24 개의 회전이 있음을 관찰하십시오. 원점 큐브의 가능한 각면에 대한 방향 중 하나가 위쪽을 향하게하고, 그 위치에서 수직 축을 중심으로 4 번 회전 할 수 있습니다.
같은 회전을하고 원본 큐브를 조각의 다른 큐브로 변환 한 후 동일한 최종 조각을 생성 할 수있는 방향을 찾아 검색 공간을 제거하려고 시도하면 완전히 동일한 점유 공간이됩니다 이전에 고려한 회전으로 볼륨, 미래 고려에서 회전 회전합니다.
가방에서 물건을 꺼냅니다. 가방에 조각이 없으면 해결책입니다. 용액 부피의 각 셀과 각 셀의 당긴 조각의 각 회전을 반복합니다.조각이 검색 량 안에 완전히 들어 있고 다른 조각과 겹치지 않으면이 단락을 반복하십시오. 그렇지 않으면 다음 회전으로 진행하거나 더 이상 회전이 없으면 다음 셀로 이동하거나 더 이상 셀이 없으면 해결 방법없이 돌아옵니다.
마지막 단락이 솔루션없이 반환되면 퍼즐을 풀 수 없습니다.
질문의 이미지보다 큰 문제의 경우, 분기 생성을 위해 더 나은 (그리고 명시적인) 가지 치기 전략이 필요합니다. 서술 된 바와 같이, 상태 공간은 sum_ {i = 1}^조각 (i * 목표의 양 * 6 [회전])이고, "직접 도달 할 수있는"상태를 생성하는 데 소비되는 시간은 적어도 다른 크기의 순서가 될 것이다. 볼륨 충돌 탐지 등을 수행 할 수 있습니다. 또한 BFS 대신 DFS가 도움이 될 수 있습니다. – p00ya
BFS의 포인트는 주에 "최단 경로"를 제공한다는 것입니다. DFS는 해당 상태에 도달 한 첫 번째 분기를 선택합니다. 반드시 가장 짧은 분기는 아닙니다. – Edward