12. Complete search

Complete search is een methode voor het vinden van een oplossing door systematisch alle mogelijkheden te doorlopen. Een complete search algoritme vind dus altijd het juiste antwoord voor een programmeer probleem omdat het alle mogelijke oplossingen doorloopt. Het nadeel kan wel zijn dat een complete algoritme langzaam kan zijn als je probleem veel verschillende mogelijke oplossingen heeft. Belangrijk is dus om even te berekenen wat het maximale aantal mogelijke oplossingen is voordat je een complete search algoritme schrijft.

Complete search met for-loops

De simpelste manier om alle oplossingen door te lopen is met for-loops die je in het hoofdstuk Herhalingen hebt gezien.

Opdracht 1 Schrijf een programma dat alle mogelijkheden berekent waarvoor geldt: abcde/fghij = 62, waarbij elke letter een cijfer bevat tussen 0 en 9. Elk cijfer mag maar 1 keer voorkomen. Een correct antwoord is dus: 79546/01283.

Recursive complete search (=backtracking)

In plaats van for-loops kan je ook recursie gebruiken om systematisch alle mogelijkheden door te lopen. Hieronder een aantal voorbeelden die je kan oplossen met recursie.

Opdracht 2 Je kunt een trap op verschillende manieren beklimmen. Je kunt trede voor trede naar boven lopen of af en toe een trede overslaan. Schrijf een programma dat het aantal mogelijkheden berekent om een trap met een bepaal aantal treden (N) te beklimmen. Gebruik recursie en denk goed na over de stop voorwaarde. Invoer: De invoer bevat een integer N, dit is het aantal treden Uitvoer: De uitvoer is een integer, dit is het aantal mogelijkheden dat je de trap op kan lopen Met de volgende link kan je testen of je programma werkt: Trap.

Bij complete search problemen is het altijd handig om alle mogelijkheden in een boom-structuur te plaatsen, een recursie boom. In onderstaande boom wordt weergegeven op welke trede je staat. We beginnen altijd bij de wortel van de boom, op trede = 0.

Als je de volgende code gebruikt dan doorloop je boom systematisch.

#include <iostream>
using namespace std;

int aantalOplossingen = 0;
int N = 3;

void losOp (int treden) {
  //stopconditie
  if (treden == N) {
    aantalOplossingen++;
  }
  //recursieve aanroep
  if (treden < N){
    losOp (treden + 1);
    losOp (treden + 2);
  }
}

int main() {
  losOp(0);
  cout << aantalOplossingen;
}

Opdracht 3 In welke volgorde wordt de recursie boom die hierboven getekend is doorlopen als je bovenstaande code uitvoert?

Opdracht 4 Schrijf een programma dat alle mogelijke combinaties geeft die je kan maken met de letter A, B en C. Voor je begint met programmeren: teken eerst de boom met alle mogelijkheden op papier.

Opdracht 5 Schrijf een programma dat voor een set van positieve integers en een integer K, alle subsets berekent die als som K hebben. Voorbeeld Invoer Set van integers : {10, 7, 5, 18, 12, 20, 15} K : 35 Uitvoer Mogelijke subsets : {10, 7, 18} want 10 + 7 + 18 = 35 Er zijn meer mogelijke subsets in dit voorbeeld. Je programma berekent alle mogelijke subsets.

N-koninginnen probleem

Een mooi voorbeeld waar we backtracking kunnen gebruiken is het zogenoemde ‘n-koninginnen-probleem’, dat we hieronder beschrijven:

Hoe kun je N-koninginnen op een schaakbord met NxN vakken plaatsen, zodat ze elkaar niet kunnen slaan?

Bijvoorbeeld:

Als je dit probleem met backtracken wilt oplossen, dan is het nuttig je eerst te realiseren dat een vereiste is dat er in elke kolom (en elke rij) precies 1 koningin moet komen te staan. Dat betekent dat als je een koningin ergens op kolom 1 zet, de volgende koningin op kolom 2 moet komen te staan, en de volgende op kolom 3. Enzovoorts. De vraag is dan natuurlijk waar op elke kolom ze moeten komen te staan? Dat kun je met back-tracken proberen.

Stel je voor dat je de eerste koningin in kolom 1 op rij 1 zet. Dan kan de koningin op rij 2 niet meer in kolom 1, en ook niet in kolom 2 (want dan wordt die diagonaal geslagen). Maar kolom 3 kan nog wel. Dus zet je daar de koningin neer. En kan je door naar rij 3.

Als je op deze manier doorgaat, dan zul je merken dat je op een gegeven manier ‘vast’ komt te zitten. Je kunt de koninginnen op de laatste paar kolommen niet meer kwijt. Blijkbaar was een van je plaatsingen eerder toch niet zo handig. Nu moet je dus backtracken. Je laatste zet ongedaan maken en een andere rij proberen. Zie hier: je back-track algoritme! 😊

void losOp (int bord[N][N], int kolom) { 
    //als N koninginnen geplaatst zijn dan druk het bord af.
    if (kolom >= N) {
        drukAf(bord);
    }
  
    //doorloop alle rijen van de specifieke kolom
    for (int rij = 0; rij < N; rij++) { 
        // check of de koningin geplaatst kan worden op bord[rij][kolom] 
        if (geldig(bord, rij, kolom)) { 
            // plaats de koningin op bord[rij][kolom]
            bord[rij][kolom] = 1; 
  
            //recursie om de rest van de koninginnen te plaatsen
            losOp (bord, kolom + 1);
  
            //verwijder de koningin van bord[rij][kolom].
            bord[rij][kolom] = 0; // BACKTRACK 
        } 
    } 
} 

Je plaatst de koninginnen op het schaakbord totdat:

1. Twee koningen elkaar kunnen slaan, dit is geen geldige oplossing, in dit geval backtrack je en ga je dus een stapje terug in de tree.

2. Er n koninginnen op het schaakbord staan die elkaar niet kunnen slaan, dit is een geldige oplossing, ook in dit geval backtrack je door weer een stapje terug te gaan in de tree.

Opdracht 6 - Teken op papier voor N = 4 uit hoe bovenstaande code de koninginnen op het bord plaatst en weer weghaalt. - Los het koninginnen probleem op voor N = 4. Gebruik bovenstaande code. Schrijf zelf de overige code, en de functies drukAf, en geldig. - Hoeveel verschillende oplossingen zijn er voor het koninginnen probleem waar N = 8? En N=12? - Met de volgende link kan je testen of je programma werkt: koninginnen probleem.

In onderstaande boom zie je hoe systematisch naar de oplossingen voor het probleem met 4 koninginnen wordt gezocht:

Opdracht 7 Maak de opgave aantal kamers.

Opdracht 8 Schrijf een programma dat alle permutaties weergeeft van een string met unieke letters. Bijvoorbeeld alle permutaties van ABC zijn: ABC, ACB, BAC, BCA, CBA, CAB.

Opdracht 9 Schrijf een programma dat Sudoku's oplost. Een sudoku-speelveld bestaat uit een grid van 9x9 vakjes. Het veld bevat 9 kleinere deelvelden van 3x3 vakjes. De deelvelden overlappen niet. In de vakjes moeten de getallen 1 t/m 9 worden ingevuld, zo dat - In elke rij elk getal precies één keer voorkomt - In elke kolom elk getal precies één keer voorkomt - In elk 3x3 deelveld elk getal precies één keer voorkomt. Een aantal vakjes is vooraf al ingevuld. Maak hiervoor zelf keuzes. Als er bij de vooraf ingevulde vakjes een oplossing is, laat dan je programma die oplossing afdrukken. Als er geen oplossing is, geeft je programma de uitvoer ‘geen oplossing’.