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.

Opgave

Schrijf een Python-functie plant(rooster: list) die een rooster binnenkrijgt als argument. De functie moet een optimale mijnenconfiguratie teruggeven. Een bovengrens wordt voorgesteld als een getal, een leeg veld als False en een mijn als True.

Voorbeelden

>>> plant([[False]])
[[True]]
>>> plant([[8]])
[[8]]
>>> plant([[1, False], [1, 1], [1, 1]])
[[1, True], [1, 1], [1, 1]]
>>> plant([[False, False], [False, 3]])
[[True, True], [True, 3]]
>>> plant([[False, False, False], [False, 0, False], [False, False, False]])
[[False, False, False], [False, 0, False], [False, False, False]]
>>> plant([[False, False, False], [False, False, False], [False, False, False]])
[[True, True, True], [True, True, True], [True, True, True]]
>>> plant([[3, False, 4, False, False, 1], [2, False, 2, 1, False, False], [8, 8, 8, 8, 8, 8]])
[[3, True, 4, False, True, 1], [2, True, 2, 1, False, False], [8, 8, 8, 8, 8, 8]]