Här kan man utnyttja att antalet möjliga tillstånd i spelet är ganska litet, närmare bestämt 8! = 40320. Om vi kan hitta ett smart sätt att komma ihåg om ett tillstånd redan är använt, blir det då ganska lätt att testa alla möjligheter. Till detta behövs en funktion från en permutation till ett heltal (ofta kallad Rank) och dess invers (Unrank). Måste tänkas ut, annars är här ett förslag på en rekursiv funktion (implementeras dock enklast med en loop):

Rank(P[1..k]) = (P[1] - 1)(k - 1) + Rank(P[2..k])  med Rank(P[1..1]) = 0

Sedan är det hela ganska enkelt. För att bara lösa Subtask A, räcker det med DFS, men utan att sudda ut taken-markeringarna eftersom vägens längd inte spelar någon roll. Du hittar ändå en väg med mindre än 40320 drag. För att lösa Subtask B och hitta den kortaste vägen, behöver du BFS, som kan användas på precis samma sätt som i labyrint-exemplet, utom att du i kön sparar ställningarnas Rank-värden istället för koordinater.

Tillbaka