Inhoud:
- de puzzel
- benadering
- programma afloop
- invoer
- voorbeeld
- code
Hoe kunnen acht koninginnen op een schaakbord worden geplaatst, zodanig dat geen van hen elkaar kan slaan ? En: hoeveel oplossingen zijn er ? Via trial-and-error kunnen waarschijnlijk een aantal oplossingen worden gevonden. Dit klassieke vraagstuk vraagt om een aanpak met de computer.
De computer kan ervoor zorgen dat alle oplossingen worden gevonden. Een mogelijkheid is alle varianten van 8 koninginnen op een schaakbord door te laten rekenen; dit zou echter veel teveel tijd kosten. De manier die hier wordt uitgewerkt is, te beginnen met 1 koningin, te bepalen welke posities vrij zijn voor een tweede koningin, de tweede koningin te plaatsen op een van die posities, te bepalen welke posities vrij zijn voor een derde koningin, enz. Als de ingeslagen weg doodloopt, dan een koningin terugnemen en bepalen welke andere posities vrij zijn, enz.
Ter voorbereiding wordt (eenmalig) voor ieder vakje alle aangrenzende vakjes bepaald (horizontaal, vertikaal, diagonaal) waarnaar een koningin zich mag bewegen ( geldige_zetten() ). Eerst wordt een koningin in het eerste vakje geplaats (linksboven), en bepaald wat nu de vrije posities zijn voor de rest van het speelbord. Dan wordt in de volgende kolom (kolom 2) gekeken of er nog een vrije positie is ( vrije_zetten() ), zo ja dan wordt deze oplossing op de 'stack' geplaatst ( queenspos.append() ), zo niet dan wordt de vorige goede oplossing van de stack gehaald ( queenspos.pop(), principe 'last in, first out'). Door dit te herhalen ('recursive backtracking') worden uiteindelijk alle oplossingen gevonden.
Deze puzzel kent weinig varianten, behalve dan het formaat van het speelbord. Dit is in te stellen met de variabele 'veld_afmeting'.
Het voorbeeld hieronder geeft alle oplossingen voor een speelbord met afmeting 8 (veld_afmeting = 8, een schaakbord).
De afmeting is zelf aan te passen, evenals de variabele verbose (True laat tussenstappen zien; False laat alleen het eindresultaat zien).
#!/usr/bin/env python
# -*- coding: utf-8 -*
# 2019-03-25
import datetime
import re
import sys
import time
'''
berekent alle mogelijke oplossingen van het 'acht koninginnen probleem'
(https://en.wikipedia.org/wiki/Eight_koningins_puzzle)
gebruik makend van recursive backtracking
'''
veld_afmeting = 8
verbose = False # True: laat tussenstappen zien (langzamer), of False: alleen eindresultaat (sneller)
def druk_af(koningin_positities):
if not verbose:
print('oplossing: {}'.format(koningin_positities, ))
joined = ''
vrije_zetten_ = vrije_zetten(koningin_positities)
for indx in range(veld_afmeting**2):
if indx in koningin_positities:
joined += 'Q '
elif indx in vrije_zetten_:
joined += '. '
elif verbose:
joined += '~ '
else:
joined += '. '
out = "\n".join(re.findall('[Q~\s\.]{' + str(2*veld_afmeting) + '}', joined))
return out
def geldige_zetten(veld_afmeting):
# voor iedere positie in de grid, geeft de geldige posities waarnaar toe kan mogen verplaatst
for i in range(veld_afmeting**2):
lib = {}
for indx in range(veld_afmeting**2):
rij,kolom = divmod(indx, veld_afmeting)
geldig = [x*veld_afmeting + y for x in range(veld_afmeting) for y in range(veld_afmeting) if x+y == rij+kolom or x-y == rij-kolom or x == rij or y == kolom]
lib[indx] = list(sorted(set(geldig) - set([indx])))
return lib
def vrije_zetten(koningin_positities):
# geeft een lijst met vrije zetten (velden die niet kunnen worden aangevallen door een koningin)
vrij = set(range(veld_afmeting**2))
for i in koningin_positities:
vrij -= set(buren[i]).union(set([i]))
return sorted(list(vrij))
def is_vrije_zet(indx, koningin_positities):
# retourneert of een veld vrij is
return indx in vrije_zetten(koningin_positities)
def is_geldige_oplossing(koningin_positities):
# retourneert of een oplossing geldig is
if len(koningin_positities) != veld_afmeting:
return False
taken = []
for boxindx in koningin_positities:
taken += buren[boxindx]
return (len(set(range(veld_afmeting**2)).difference(set(koningin_positities).union(set(taken))))==0)
if __name__ == '__main__':
timerstart = datetime.datetime.now()
buren = geldige_zetten(veld_afmeting) # eenmalig bepaald om processortijd te besparen
gridpos = 0
queenspos, oplossingen = [], []
while gridpos < (veld_afmeting**2):
show = False
if is_vrije_zet(gridpos, queenspos):
queenspos.append(gridpos)
gridpos = (gridpos//veld_afmeting+1)*veld_afmeting # start bovenin volgende rij
if verbose:
show = True
else:
while gridpos%veld_afmeting == veld_afmeting-1: # einde van rij bereikt
try:
gridpos = queenspos.pop()
except IndexError:
break
gridpos += 1
if show:
print("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n")
print(druk_af(queenspos))
time.sleep(0.5)
if is_geldige_oplossing(queenspos):
oplossingen.append(queenspos[:])
queenspos.pop()
gridpos = queenspos.pop()
while gridpos%veld_afmeting == veld_afmeting-1: # einde van rij bereikt
gridpos = queenspos.pop()
gridpos += 1
if show:
print('oplossing {}'.format(len(oplossingen)))
time.sleep(3)
if not verbose:
for oplossing in oplossingen:
print(druk_af(oplossing))
print('een bord met afmetingen {0}x{0} velden heeft: {1} oplossingen'.format(veld_afmeting, len(oplossingen), ))
if not verbose:
timerend = datetime.datetime.now()
delta = timerend - timerstart
print('duur: {:0.3f} sec.'.format(delta.seconds + delta.microseconds/1000000))
op deze website worden geanonimiseerde bezoeker aantallen bijgehouden