het '8 koninginnen' probleem

Inhoud:
- de puzzel
- benadering
- programma afloop
- invoer
- voorbeeld
- code

De puzzel:

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.

Benadering:

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.

Programma afloop:

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.

Invoeren van een puzzel:

Deze puzzel kent weinig varianten, behalve dan het formaat van het speelbord. Dit is in te stellen met de variabele 'veld_afmeting'.

Voorbeeld

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).

De code

#!/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))