n 퍼즐 솔루션에서 공백의 위치가 유효한 퍼즐 세트에 영향을 줍니까?

Question

내 n-puzzle solver에 문제가 있습니다. 그것이 작동하고 있다고 생각했지만, 그것은 불용성 퍼즐을 푸는 것으로 밝혀졌습니다. 나는 그것을 추적하려고 노력했지만, 그것은 많은 추적이고, 지금까지 나는 부정 행위를 볼 수 없다. 나는 용해도를 결정하는 알고리즘을 이해하고 있다고 생각합니다. 그리고 구현은 웹의 일부 예제의 홀수/짝수 패리티와 일치합니다. 즉, 주어진 타일 다음에 타일 수가 더 작 으면 모든 타일에 대해, 그리고 나서 빈 타일의 행 인덱스를 추가하면 다른 사람들이 얻은 것과 동일한 홀수 또는 짝수가됩니다.

그래서 나에게 일어난 생각. 8 퍼즐, 말, 내 모델에서 내 용액 상태는 다음과 같습니다

_ 1 2 
3 4 5 
6 7 8 

오히려

1 2 3 
8 _ 4 
7 6 5 

보다 또는

1 2 3 
4 5 6 
7 8 _ 

이 다른 제제에서와 같이. 이것이 어떤 퍼즐에 용해되고 어떤 퍼즐에 영향을 미칠 수 있습니까?

감사합니다.

z.

Answer 1

일반적으로 예 : 표준 솔루션에서 구성을 해결할 수없는 경우 해결할 수없는 구성으로 해결할 수 없습니다.

특히 솔루션으로 사용하는 정확한 구성에 따라 다릅니다. 해당 구성에서 표준 구성으로 해결할 수 있는지 확인해야합니다.

편집 : 그것의이이 방법 :

는 A가 표준 용액하자. B를 원하는 솔루션으로 지정하십시오. C를 시작 구성으로 설정하십시오.

당신이 A에서 B로 얻을 수 있습니다, 당신은 A와 C에서 얻을 수있는 경우에, 당신은 C에서 B. 에 그러나 당신은에서 얻을 수없는 경우 B에 도달 할 수 있으며,얻을 수 있습니다 C에서 A로 가면 C에서 B로 갈 수 없습니다.