We spelen een variant op mijnenveger: gegeven een rooster met een aantal vlaggen op, proberen we zo veel mogelijk mijnen te plaatsen. In de acht vakjes rondom een vlag mogen echter nooit meer (wel minder) mijnen liggen dan het nummer dat op de vlag aangeduid staat.

Dit probleem is niet makkelijk met de hand op te lossen, dus zullen we het automatiseren. Schrijf een branch-and-bound-algoritme dat, gegeven een rooster met bovengrenzen, zoveel mogelijk mijnen plaatst.

Implementeer hiervoor de interface MinePlanter¹ in een klasse BNBMinePlanter. Deze vereist een methode public Sign[][] plant(int rows, int cols, Sign[][] field), die een zo vol mogelijke invulling van field (een rooster van grootte rows x cols) teruggeeft. De Sign klasse² omschrijft de inhoud van elke cel in het rooster, en heeft 3 subklassen: Empty, Mine en Bound. Een object van klasse Empty³ stelt een lege cel voor. Een object van klasse Mine⁴ geeft aan dat de cel een mijn bevat. Deze zullen niet voorkomen in de invoer, maar moet jij gebruiken om mijnen in de uitvoer aan te duiden. Een object van klasse Bound⁵ duidt een bovengrens aan op het aantal mijnen dat rondom deze cel geplaatst mag worden. De interface MinePlanter, de klasse Sign en haar subklassen mogen niet aangepast worden, maar bevatten veel methoden die wellicht nuttig zullen blijken.

Hieronder staan de java-abstracties die de diverse roosters uit bovenstaand voorbeeld voorstellen.

Sign[][] voorbeeldinvoer = new Sign[][] {
    { new Bound(3), new Empty(),  new Bound(4), new Empty(),  new Empty(),  new Bound(1) },
    { new Bound(2), new Empty(),  new Bound(2), new Bound(1), new Empty(),  new Empty() },
    { new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8) }
};

Sign[][] voorbeelduitvoer = new Sign[][] {
    { new Bound(3), new Mine(),   new Bound(4), new Mine(),   new Empty(),  new Bound(1) },
    { new Bound(2), new Empty(),  new Bound(2), new Bound(1), new Empty(),  new Mine() },
    { new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8) }
};

Sign[][] alternatieveVoorbeelduitvoer = new Sign[][] {
    { new Bound(3), new Mine(),   new Bound(4), new Empty(),  new Empty(),  new Bound(1) },
    { new Bound(2), new Mine(),   new Bound(2), new Bound(1), new Mine(),   new Empty() },
    { new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8) }
};

// Merk op hoe de limiet in cel (1,2) overschreden wordt.
Sign[][] foutieveVoorbeelduitvoer = new Sign[][] {
    { new Bound(3), new Mine(),   new Bound(4), new Mine(),   new Empty(),  new Bound(1) },
    { new Bound(2), new Mine(),   new Bound(2), new Bound(1), new Empty(),  new Mine() },
    { new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8), new Bound(8) }
};

Met behulp van SimpleTest⁶ kan je jouw oplossing lokaal uittesten.