Inledningsvis har jag väldigt dåligt tålamod med att göra tråkiga repetitiva uppgifter. Jag kom över ett spel på telefonen för en tid sedan som ja inte orkade sitta och lägga ner timtal på att klara igenom. Spelet finns på android market.
Eftersom jag inte orkade klara igenom spelet på egen hand, så tänkte jag be datorn göra det åt mig. Datorer är snabbare på repetitiva uppgifter än människor => mindre tidsanvändning.
Jag ser en spelplan som en kvadratisk matris där elementen är antingen svarta eller vita. Spelet går ut på att trycka på rutorna tills alla rutor är vita. Varje ruta representeras lämpligen av ett binärt tal. Om jag använder notationen x = svart ruta, o = vit ruta ser första banan ut som följande:
o o x
o x o
x o o
Denna plan kan serialiseras till ett 9-bitars tal 0b110101011 = 427. Detta tal kan också översättas tillbaka till en spelplan.
I spelet kan man på varje spelplan trycka var man vill på skärmen, vilket betyder att man från plan nr 427 kan få 9 st nya tal, vilka alla representerar unika spelplaner.
Vi kan nu se att varje möjlig spelstrategi är en stig i en riktad graf. Den optimala spelstrategin är den kortaste stigen från utgångspunkten (i bana nr 1 talet 427), till slutpunkten 0b111111111 = 511.
När man kommer vidare i spelet ökar storleken på banorna och det är vid storleken 5 x 5 som det börjar bli knivigt för en persondator att hitta lösningar, om man inte tänker efter. Vid denna planstorlek har grafen ~3,36e7 noder, och ~8,39e8 kopplingar.
När jag har sökt lösningar har jag varit tvungen att överväga om jag vill använda djup-först sökningar eller bredd-först sökningar. Djup-först sökningar leder till längre beräkningstid och bredd-först sökningar leder till mera minnesanvändning.
För den som blir intresserad kommer detaljerna om implementeringen som sparade mig mycket tid i mitt nästa inlägg.
/wlund@ – datör