Op een schaakbord staan een aantal koninginnen, paarden en pionnen opgesteld. Bepaal hoeveel onbezette vierkanten er zijn op het schaakbord. Dit zijn vierkanten die door geen enkele koningin en door geen enkel paard kunnen aangevallen worden. We noemen dit de veilige vierkanten van het schaakbord. Hierbij dienen de pionnen enkel om de bewegingsruimte van de koninginnen af te blokken. Ze kunnen zelf geen aanvallen uitvoeren.

Voor zij die de regels van het schaakspel niet kennen, geven we nog mee dat een paard elk onbezet vierkant van het schaakbord kan aanvallen dat gelegen is op het overstaande hoekpunt van een $$2 \times 3$$ rechthoek ten opzichte van zijn huidige positie. Een koningin kan een aanval uitvoeren op elk zichtbaar vierkant in elk van de acht horizontale, verticale of diagonale richtingen ten opzichte van zijn huidige positie. Merk hierbij op dat een aanvalsbeweging van een koningin afgeblokt wordt door elk ander stuk op het schaakbord, terwijl de aanval van een paard nooit door andere stukken kan geblokkeerd worden.

Opgave

Bepaal het aantal veilige vierkanten op een schaakbord waarop een aantal koninginnen, paarden en pionnen werden neergezet.

Hiervoor moet je de volgende drie functies schrijven waaraan telkens drie argumenten moeten doorgegeven worden die de configuratie van het schaakbord beschrijven: i) het aantal rijen $$r \in \mathbb{N}$$ (int) van het schaakbord ($$r \geq 2$$), ii) het aantal kolommen $$k \in \mathbb{N}$$ (int) van het schaakbord ($$k \geq 2$$) en iii) een reeks (list of tuple) met de posities van de stukken op het schaakbord. De positie van een stuk wordt omschreven door een reeks (list of tuple) met drie elementen. Het eerste element is een string (str) die aangeeft over welk soort stuk het gaat (Q voor koningin, K voor paard en P voor pion). Het tweede en derde element geven de rij (int) en de kolom (int) aan waarop het stuk zich bevindt. Rijen en kolommen worden hierbij steeds genummerd vanaf nul, zoals bij de schaakborden in bovenstaande afbeeldingen.

• Een functie schaakbord die een roostervoorstelling van het gegeven schaakbord teruggeeft. Het rooster wordt voorgesteld als een lijst (list) met de rijen van het schaakbord (opgelijst van boven naar onder). Elke rij wordt voorgesteld als een lijst (list) met strings (str) die de schaakstukken op elk vierkant van de rij omschrijven (opgelijst van links naar rechts). Een koningin wordt voorgesteld door de hoofdletter Q, een paard door de hoofdletter K, een pion door de hoofdletter P, en een vierkant zonder schaakstuk door de lege string.

• Een functie onveilige_vierkanten die dezelfde roostervoorstelling van het gegeven schaakbord teruggeeft als de functie schaakbord, maar waarbij onbezette vierkanten worden aangeduid door een asterisk (*) als ze door een koningin of een paard kunnen aangevallen worden.

• Een functie veilige_vierkanten die teruggeeft hoeveel veilige vierkanten (int) er zijn op het gegeven schaakbord.

Voorbeeld

>>> schaakbord(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
[['', 'K', '', 'Q'], ['', '', 'P', 'Q'], ['', '', '', ''], ['', '', '', '']]
>>> schaakbord(2, 3, (('Q', 0, 1), ('K', 0, 0)))
[['K', 'Q', ''], ['', '', '']]
>>> schaakbord(8, 8, (('Q', 4, 3), ))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', 'Q', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', '']]
>>> schaakbord(8, 8, (('K', 4, 3), ('K', 7, 7)))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', 'K', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', 'K']]

>>> onveilige_vierkanten(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
[['', 'K', '*', 'Q'], ['', '', 'P', 'Q'], ['*', '', '*', '*'], ['', '*', '', '*']]
>>> onveilige_vierkanten(2, 3, (('Q', 0, 1), ('K', 0, 0)))
[['K', 'Q', '*'], ['*', '*', '*']]
>>> onveilige_vierkanten(8, 8, (('Q', 4, 3), ))
[['', '', '', '*', '', '', '', '*'], ['*', '', '', '*', '', '', '*', ''], ['', '*', '', '*', '', '*', '', ''], ['', '', '*', '*', '*', '', '', ''], ['*', '*', '*', 'Q', '*', '*', '*', '*'], ['', '', '*', '*', '*', '', '', ''], ['', '*', '', '*', '', '*', '', ''], ['*', '', '', '*', '', '', '*', '']]
>>> onveilige_vierkanten(8, 8, (('K', 4, 3), ('K', 7, 7)))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '*', '', '*', '', '', ''], ['', '*', '', '', '', '*', '', ''], ['', '', '', 'K', '', '', '', ''], ['', '*', '', '', '', '*', '*', ''], ['', '', '*', '', '*', '*', '', ''], ['', '', '', '', '', '', '', 'K']]

>>> veilige_vierkanten(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
6
>>> veilige_vierkanten(2, 3, (('Q', 0, 1), ('K', 0, 0)))
0
>>> veilige_vierkanten(8, 8, (('Q', 4, 3), ))
36
>>> veilige_vierkanten(8, 8, (('K', 4, 3), ('K', 7, 7)))
52