Har du någonsin spelat schack? Om ja, vet du redan att damen är den viktigaste pjäsen och att den kan flytta hur många rutor som helst vertikalt, horisontellt eller diagonalt. Om du inte har gjort det, oroa dig inte: idag ska vi bara lära oss hur man placerar 8 drottningar på schackbrädet så att ingen drottning kan flytta till en ruta som är upptagen av en annan drottning. På schackjargong säger vi att drottningarna inte kommer att kunna attackera varandra. Hur gör vi detta? Vi använder backtracking.
Backtracking-algoritmen hittar en lösning på problem där vissa begränsningar måste respekteras. Den testar alla möjliga lösningar tills den hittar den rätta. Låt oss prova ett exempel, med fyra damer och ett litet bräde. Vi börjar med att placera den första damen:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Den kommer också att visa dig många andra beräkningsstrategier som hjälper dig att lösa intressanta problem!
Nu när du vet hur backtracking fungerar kan vi lösa problemet med 8 drottningar i full storlek. Nedan finns ett schackbräde som du kan spela med för att öva dina färdigheter och hitta en lösning. Börja med att placera den första drottningen genom att klicka på den övre vänstra rutan på schackbrädet. Du kommer att se att den drottning du placerade kommer att listas under listan ”Current queens”.
Current queens
Du kan nu placera ytterligare en drottning i en position som gör att de inte kan angripa varandra. Vår första dam står på a8, den andra kan till exempel placeras på c7. Fortsätt att placera drottningar tills det inte finns någon säker ruta kvar på schackbrädet. Då är det dags att backa tillbaka genom att klicka på ”ångra”. Detta kommer att rensa den sista dam som du placerade och låta dig välja en annan ruta att placera den på. Du kan också ta bort en dam från brädet genom att klicka direkt på den.
Om du spelar det interaktiva spelet kan du börja få en känsla för backtracking. Som människor kan det bli svårt för oss att hålla reda på alla tidigare placeringar av drottningar. Det är här som programmering hjälper till! Nedan hittar du en animation som genereras av ett program som visar sina felfria backtracking-färdigheter:
Pseudokod:
- Start med att placera den första drottningen på den övre vänstra rutan på schackbrädet.
- Om vi har placerat de 8 drottningarna är vi klara. Är det annars möjligt att placera en annan dam i en säker position?
- Om ja, markera detta som en del av lösningen och gå tillbaka till punkt 2.
- Om nej, ändra den föregående damens position (backtracking) och gå tillbaka till punkt 2.