Logiquiz puzzel automatisch oplossen

 
© Mark Nauta
 
Op deze site wordt uitgelegd hoe een logiquiz puzzel automatisch opgelost kan worden, mbv de programmeertaal Python.
 
Er is meer dan genoeg informatie beschikbaar over het handmatig oplossen van zo'n puzzel, zie Google.
Wil je weten hoe dit automatisch kan, of de wiskunde erachter begrijpen, blijf dan op deze site.

inhoud:
1. permutatie
2. faculteit
3. pseudocode
4. afloop van het programma
5. logica invoeren
6. voorbeeld logica
7. opgave logica
8. python code

reageren op deze pagina

permutatie

Om de aanpak te kunnen begrijpen is wat basiskennis nodig van statistiek, te weten 'permutatie': permutatie geeft aan welke combinaties er mogelijk zijn voor een verdeling.
 
Bijvoorbeeld: op hoeveel mogelijke manieren zijn drie gekleurde ballen (rood, groen, blauw) te verdelen over drie personen (eva, jan en pien) ?
dat zijn 3 x 2 x 1 = 6 verschillende manieren:

 
computers rekenen liever met getallen:

bovenstaande geldt voor één eigenschap ('kleur')
dit kan worden uitgebreid met een extra eigenschap (zie figuur hiernaast):
het aantal combinaties is nu 3! x 3! = 36 (kartesiaans produkt)

faculteit

Het aantal mogelijkheden van een permutatie wordt berekend met de wiskundige functie faculteit ('!'):
faculteit 3 =  3! = 3 x 2 x 1 = 6 

pseudocode

Door de programmeer opgave op een hoog niveau te beschrijven, helpt het de programmeur (en anderen) de grote lijn te volgen, dan wel aan anderen uit te leggen hoe de programma afloop zal zijn. Dit wordt pseudocode genoemd. De pseudocode luidt hier:
 
alle aanwijzingen worden toegepast op alle mogelijke combinaties. Als het goed is, is voldoet slechts één combinatie aan de aanwijzingen. Dit is de oplossing van de puzzel...

afloop van het programma

afloop van het Python script:
 
1. verzamelen alle permutaties van het probleem (def permutations(): )
hiermee kan, voor een permutatie, de waarde uit een kolom worden bepaald voor een persoon
 
2. verzamelen van alle inverse permutaties (def invpermutations(): )
hiermee kan het omgekeerde worden gedaan: gegeven een permutatie, bepalen van de persoon behorend bij een kolom/waarde
 
let op: de index voor 1. en 2. is gelijk, dwz betreffen dezelfde permutatie
 
3. verzamelen van alle mogelijke (combinaties) van permutaties (kartesiaans product) (def allsolutions(): )
 
stap 1,2 en 3 worden vooraf doorgerekend (ipv tijdens de executie), om rekentijd te besparen
 
4. invoeren van de opgave (def thispuzzle(): ) en (def applylogic(): )
 
5. toepassen van ieder van de logische aanwijzingen op de oplossingen (main() )
hiervoor kunnen twee functies gebruikt worden: def wp(): en def pw():. Zie hieronder.
 
6. indien oplossing(en) zijn gevonden: afdrukken in leesbaar formaat (def showuserfriendlysolution(): )
 

logica invoeren

voor het invoeren van de aanwijzingen/logica, zijn twee functies voorhanden, waarmee alle voorkomende logica kan worden vastgelegd:
 
def pw(persoonnaam, kolomnaam):
voor de gegeven permutatie en de persoon, retourneert de waarde van de gegeven kolom
 
def wp(kolomnaam, waardenaam):
voor de gegeven permutatie en de waarde uit de kolom, retourneert de persoon die daarbij hoort
 

voorbeeld logica

voor de fictieve opgave 'reistijd' moet worden bepaald:
'wat is ieders reistijd, en hoe komt hij/zij op het werk ?'
 
Hier volgen enkele aanwijzingen, met de manier waarop de aanwijzing kan worden vastgelegd:
aanwijzing: 'Mark reist iedere dag met de auto':
wp('vervoermiddel', 'auto') == 'mark'
 
aanwijzing: 'Daphne's reistijd verschilt met die van de wandelaar':
pw('daphne', 'reistijd') != pw(wp('vervoermiddel', 'benenwagen'), 'reistijd')
wp('vervoermiddel', 'benenwagen') != 'daphne'

opgave logica

Onderstaande puzzel is afkomstig van de website: logiquiz.nl
 
Opgave Gastsprekers © logiquiz.nl
 
Groep 8 ontvangt dit schooljaar enkele gastsprekers.
 
Aanwijzingen:
 
1. in december komt iemand, die geen tycho heet, over vuurwerk vertellen.
In mei spreekt een 45-jarige over vrijheid.
 
wp('maand', 'december') == wp('onderwerp', 'vuurwerk')
wp('onderwerp', 'vuurwerk') != 'tycho'
wp('maand', 'mei') == wp('onderwerp', 'vrijheid')
wp('onderwerp', 'vrijheid') == wp('leeftijd', '45')
 
2. Jeanet vertelt over nepwapens.
 
wp('onderwerp', 'nepwapens') == 'jeanet'
 
3. Degene die in februari over alcohol spreekt is 2 jaar jonger dan Peter.
 
wp('maand', 'februari') == wp('onderwerp', 'alcohol')
int(pw(wp('onderwerp', 'alcohol'), 'leeftijd')) + 2 == int(pw('peter', 'leeftijd'))
 
4. Tycho is 42 jaar oud. Cor is ouder dan Nina.
 
int(pw('tycho', 'leeftijd')) == 42
int(pw('cor', 'leeftijd')) > int(pw('nina', 'leeftijd'))
 
5. Wie in juni spreekt, heeft het niet over EHBO.
 
wp('maand', 'juni') != wp('onderwerp', 'ehbo')
 
Deze opgave is uitgewerkt in onderstaande python code:

python code

(dit is een directe download link naar de Python code)

#!/usr/bin/env python
"""will search for a solution of a Logiquiz puzzle"""
__author__ = "Mark Nauta"
__copyright__ = "Copyright 2019"
__credits__ = ["Mark Nauta", "davdata.nl"]
__license__ = "GPL"
__version__ = "0.0.1"
__maintainer__ = "Mark Nauta"
__email__ = "markatnadropuntnl"
__status__ = "Production"
from __future__ import division
from math import factorial, floor
import sys
 
#global variables
koppen, waarden = [], []
 
def permuting(indx):
  out = '0123456789'[:n]
  perm = ''
  for k in range(n, 0, -1):
    div, mod = divmod(indx, factorial(k-1))
    perm += out[div]
    out = out.replace(out[div], '')
    indx = mod
  return perm
 
def permutations():
  perms = []
  for indx in range(factorial(n)):
    perms.append(permuting(indx))
  return perms
 
def invpermuting(indx):
  perm = permuting(indx)
  invperm = ''
  for k in range(n):
    invperm += str(perm.find(str(k)))
  return invperm
 
def invpermutations():
  invperms = []
  for indx in range(factorial(n)):
    invperms.append(invpermuting(indx))
  return invperms
 
def allsolutions():   solutions = []   factn = factorial(n)   if numcols == 2:     for r in range(factn):       solutions.append(r)     elif numcols == 3:     for r in range(factn):       for s in range(factn):         solutions.append( (r, s) )   elif numcols == 4:     for r in range(factn):       for s in range(factn):         for t in range(factn):           solutions.append( (r, s, t) )   return solutions
 
def pw(persoonnaam, kolomnaam):
  # zoekt een eigenschap van een persoon
  rowindex=values.index(persoonnaam) # persoon
  kolomindex = headers.index(kolomnaam)-1
  variantindex = oplossing[kolomindex]
  variant=permutaties[variantindex]
  kolindex = int(variant[rowindex])
  waarde = values[numrows:][kolindex + numrows*kolomindex]
  return waarde
 
def wp(kolomnaam, waardenaam):
  # zoekt een persoon behorend bij die eigenschap
  kolomindex = headers.index(kolomnaam)-1
  waarden = values[numrows:][numrows*kolomindex:]
  waardeindex = waarden.index(waardenaam)
  variantindex = oplossing[kolomindex]
  variant = invpermutaties[variantindex]
  rowindex = int(variant[waardeindex])
  return values[rowindex]
 
def showuserfriendlysolution():
  output = ''
  columnwidth= 15
  regel = '\n'
  for header in headers:
    header = header  + ':             '
    regel += header[:columnwidth]
  output += regel + '\n'
  for i in range(numrows):
    regel = ''     persoonnaam = values[i]
    vakje = persoonnaam + '                '
    regel += vakje[:columnwidth]
    for j in range(1, numcols, 1):
      kolomnaam = headers[j]
      vakje = pw(persoonnaam, kolomnaam) + '                 '
      regel += vakje[:columnwidth]
    output += regel + '\n'
  return output
 
def thispuzzle():
  global koppen, waarden
  koppen = 'spreker, leeftijd, onderwerp, maand'
  waarden = 'cor, jeanet, nina, peter, tycho, 40, 42, 45, 48, 50, alcohol, ehbo, nepwapens, vrijheid, vuurwerk, februari, mei, juni, oktober, december'
 
def applylogic():
  return (wp('maand', 'december') == wp('onderwerp', 'vuurwerk')) \
      and (wp('onderwerp', 'vuurwerk') != 'tycho') \
      and (wp('maand', 'mei') == wp('onderwerp', 'vrijheid')) \
      and (wp('onderwerp', 'vrijheid') == wp('leeftijd', '45')) \
      and (wp('onderwerp', 'nepwapens') == 'jeanet') \
      and (wp('maand', 'februari') == wp('onderwerp', 'alcohol')) \
      and (int(pw(wp('onderwerp', 'alcohol'), 'leeftijd')) + 2 == int(pw('peter', 'leeftijd'))) \
      and (int(pw('tycho', 'leeftijd')) == 42) \
      and (int(pw('cor', 'leeftijd')) > int(pw('nina', 'leeftijd'))) \
      and (wp('maand', 'juni') != wp('onderwerp', 'ehbo'))
 
if __name__ == '__main__':
 
  thispuzzle()
  headers = koppen.split(', ')
  values = waarden.split(', ')
  numcols = len(headers)
  numrows = len(values) // len(headers)
  n = numrows
 
  # bereken eenmmalig alle (inverse) permutaties:
  permutaties = permutations()
  invpermutaties = invpermutations()
  # bereken eenmalig alle mogelijke oplossingen:
  oplossingen = allsolutions()
  print 'er zijn ' + str(len(oplossingen)) + ' mogelijke oplossingen.'
  onepct = floor(len(oplossingen)/100)
 
  tabel = []
  i = 0
  for oplossing in oplossingen:
    if i%onepct == 0:
      print '\r' + str(int(i//onepct)) + '%',
    if applylogic():
      tabel.append(showuserfriendlysolution())
    i += 1
  print '\r100% done\n'
 
  if len(tabel) == 1:
    print 'er is 1 goede oplossing:\n' + tabel[0]
  else:
    print 'er zijn meerdere oplossingen die voldoen aan de aanwijzingen:\n'
    for item in tabel:
      print item