주사위 문제에 대한 알고리즘

이 퍼즐의 모든 솔루션을 찾는 데 가장 좋은 알고리즘이 무엇인지 생각하고있었습니다. 주사위 문제에 대한 알고리즘

는이를 해결하거나 다른 방법을 제안 할 수 있습니다에 대한 접근 방식이 될 되돌아 수 있을까요?

감사합니다.

2010-05-06 excray

흥미 롭습니다. Armor Games도 퍼즐 게임을 만드는 것을 몰랐습니다. 나는 지금 그것을하고있다. (그런데, 나는 가장 작은 주사위 번호를 먼저하는 것이 좋은 경험이 될 것이라고 생각합니다.) 편집 : 오, 주사위는 주사위를 밀 수 있습니까? 복잡한 방법을 추가하는 좋은 방법 .. –

다른 의견 : 레벨 15-19보다 훨씬 쉬운 "어려운 레벨"(레벨 20-30)을 발견했습니다. 왜냐하면 그들이 주사위를 우리에게 줄 수 있기 때문에 때때로 허용됩니다. 약간의 6 도트 다이. 나는 이것을 해결하는 알고리즘이 단순한 A * 검색 일 수 있다고 생각합니다. 당신의 발견 적 방법은 거푸집 동작의 패리티와 합쳐진 전체 동작을 특정 방식으로 조합 한 것입니다. –

링크를 통해 신뢰할 수있는 보안 인증서가없는 사이트로 연결됩니다. Grr. –

모든 솔루션을 원할 경우 역 추적이 반드시 필요합니다. BFS/A */Dijkstra와 나머지는 작동 할 수도 있지만 (어느 것이 든 그것을 증명할 필요가 있음), 어느 쪽의 방법을 사용하든 모든 해결책을주지는 못할 것입니다.

재생할 수있는 영역이 실제로 작고 조각 수와 움직임 수가 비교적 적기 때문에 역 추적은 너무 오래 걸리지 않아야합니다. 이는 좋은 발견 적 방법을 허용합니다.

출처

2010-05-06 13:42:27 IVlad

모든 도달 가능한 위치를 검색하지 않으려면 위치를 해결할 수 없는지 신속하게 결정할 방법이 필요합니다. 당신은 모든 해결 불가능한 직책을 신속하게 배제 할 수 없지만, 많은 부분을 배제 할 수 있습니다.

확인해야 할 것은 다이 D와 홀 H 각각에 대해 다이 D가 홀 H에 도달 할 수 있는지 여부입니다.이 경우에도 정확히 알아 내기 란 쉽지 않습니다. 보수적 인 경계로서, 모든 주사위에 남아있는 숫자를 더할 수 있습니다. D가 많은 운동을 남겼다고 가정합니다 (각각의 운동이 이론적으로 D를 밀 수 있기 때문에). D가 H에 도달 할 수 있는지 확인하십시오. 바운드 된 경우, 초과 된 모든 이동을 E가 D를 밀 수있는 가장 가까운 위치에 할당 한 다음 D (E 도움말 사용)가 H에 도달 할 수 있는지 확인하십시오.

어떤 주사위가 여전히 어떤 구멍에 도달 할 수 없거나 어떤 구멍에 닿을 수없는 금형이 있거나 어떤 금형으로도 도달 할 수없는 구멍이 있으면 그 위치는 해결할 수 없습니다. 마찬가지로 N 개의 별개의 구멍에 도달 할 수없는 N 개의 주사위 또는 N 개의 다른 주사위로 도달 할 수없는 H 개의 구멍이있는 경우 그 위치는 해결할 수 없습니다.

이 추론은 문제를 완전히 해결하지는 않지만 특정 보드 범위에서 검색 공간을보다 쉽게 관리 할 수 있습니다.

출처

2010-05-06 19:05:24 mathmike

주사위 문제에 대한 알고리즘

답변

관련 문제