8 Rätsel Lösbarkeit Testfälle Fehler

Question

Ich habe ein 3 x 3 Puzzle. Um zu wissen, ob es lösbar ist oder nicht, muss ich die Anzahl der Inversionen zählen. Wenn die Anzahl der Inversionen gerade ist, dann ist es lösbar. fand ich einen Beispielcode online:

https://gist.github.com/caseyscarborough/6544636

Hier sagt er {1, 0, 3, 7, 2, 5, 8, 4, 6} auflösbar ist. Aber meine Rechnung sagt etwas anderes. Ich habe (10,32,72,75,74,76,54,84,86). Also ist die Anzahl der Inversionen für diesen Fall 9, was nicht lösbar ist, da es ungerade ist.

Ein anderer Fall, den ich mit dem Code getestet habe, ist (3,0,7,6,8,2,1,4,5). Es gibt mir (30,31,32,62,61,64,65,76,72,71,74,75,82,81,84,85,21), was 17 Inversionen ist. Es ist also nicht lösbar, aber der Code sagt, dass es lösbar ist.

Mache ich irgendwelche Fehler? Oder gibt es Fehler im Code?

Answer 1

Ihre Methode ist leicht falsch. Angenommen, 0 ist das leere Quadrat, sollten Sie es in Ihrer Inversionszählung ignorieren.

Wenn Sie diese Änderung vornehmen, wird in beiden Beispielen genau eine Inversion ausgeschlossen, sodass beide falsch sind.