Nadat wij gisteren alle bewegingen én de opeloste toestand hebben beschreven, kunnen wij vandaag beginnen aan onze brute force methode! Wij hebben ervoor gekozen om deze implementatie niet verder te laten zoeken dan een oplossing van 7 bewegingen, om onze computers niet al te veel te belasten.
De implementatie lijkt heel simpel: voer een paar bewegingen uit en kijk of je iets goeds bereikt. Wij voorzagen al een aantal problemen...
Als eerste het probleem waarbij onze methode achter elkaar dezelfde moves blijft uitvoeren. Één keer r, dan rr, dan nog een keer r... Of eerst l dan r en dan weer l. Dat schiet niet op. Dus hebben wij twee predicaten geschreven om dit probleem op te lossen. Next/2 wordt eigenlijk alleen gebruikt voor de tweede beweging, omdat er nog maar één beweging aan vooraf is gegaan. Het controleert of de nieuwe beweging niet gemaakt wordt aan dezelfde zijde als waar de eerste beweging gemaakt werd. Daarna komt next/3, die ditzelfde nagaat, maar daarbij ook nog één stap verder terugkijkt.
Om het implementeren van deze predicaten makkelijk te houden, hebben wij bij moves/3 één argument toegevoegd, die beschrijft aan welke zijde de beweging plaatsvindt.
Onze code zou nu al heel wat meer kunnen doen, maar komt nu alleen nog maar terug met oplossingen die exact 7 bewegingen kosten, terwijl er ook oplossingen kunnen zijn die minder bewegingen gebruiken. Daarom hebben wij een nóg een extra predicaat in het leven geroepen namelijk solved1/2. Deze kijkt eerst of er een oplossing is gevonden, en zal deze als resultaat teruggeven (dit met behulp van solved/1, maar ook als er geen oplossing is gevonden zal dit predicaat slagen. Zo kan de brute force methode de hele zoekruimte doorzoeken, maar tegelijkertijd alle gevonden oplossingen teruggeven.
en mét
Als niet next/2 of next/3 gebruikt, dan is de complexiteit natuurlijk 18 * 18 * 18 * ... En dat is 'best wel groot.'
Mét next/2 of next/3 is de complexiteit kleiner, namelijk 18 * 15 * (1/5 * 12 + 4/5 * 15 = 14.4) * 14.4 * 14.4 * ...
Dit betekent dat als je 7 bewegingen diep kijkt zónder de optimalisatie dan is jouw ruimte 612 220 032 permutaties ( 18 ^ 7 ) en mét 167 176 883 ( 18 * 15 * ( 14.4 ^ 5 ) )
Alle bovengenoemde predicaten hebben wij overigens in het bestand gezet waarin de bewegingen worden beschreven, omdat wij denken dat deze bij andere methoden ook nog van pas kunnen komen.
Ons resultaat van vandaag: de methode kan binnen een redelijke tijd alle oplossingen vinden van een cube die binnen 7 bewegingen oplosbaar is. Maar, dit kan vast efficiënter...
