Möbius; de gedachtengang
Recursie met backtracking.
Het bord was 2*n bij m. Als je van de ``buitenkant'' doorloopt naar de
``binnenkant'' zijn er geen rare twists, als je verder doorloopt en
weer bij de ``buitenkant'' uitkomt evenmin. Bovendien sta je dan op
precies dezelfde manier op je uitgangspunt. Kortom: een array van 2*n
bij m in het geheugen voldoet als Möbiusband!
Het vaststellen van een bovengrens voor het aantal koninginnen is eenvoudig:
Het 2*n bij m bord kunnen hooguit Min(2*n,m) koninginnen aan.
Dus:
- Kan er een koningin gezet worden op een vrije niet-slaanbare plek?
- Ja,
- zet haar neer
- ga de recursie in (en kom er weer uit)
- haal haar weer weg
- Nee
- hoog eventueel huidig maximum op
- is dit gelijk aan de bovengrens, BREAK
- herhalen tot alle vrije niet-slaanbare plaatsen aan de beurt geweest zijn
Enige optimalisaties op ``alle vrije niet-slaanbare plaatsen'' zijn nog wel te maken.