andere opgaven: acht koninginnen | boter, kaas en eieren | logiquiz | sudoku

Logiquiz puzzel oplossen

Hoe een logiquiz puzzel oplossen, of hoe zelf een logiquiz ontwerpen ? Hier wordt uitgelegd hoe je dat met behulp van de computer kan doen.

Inhoud:
de puzzel
benadering
programma afloop
invoer
voorbeeld
zelf logiquiz ontwerpen
code
 
contact

De puzzel:

Een logiquiz puzzel (ook wel logikwis of logigram genoemd, logic grid puzzle) is een puzzel waarbij je met behulp van van allerlei aanwijzingen moet achterhalen hoe een gebeurtenis (wie-wat-waar-wanneer-hoeveel-...) heeft plaatsgevonden. Voor een voorbeeld: zie hier.
Als deze puzzel met de hand wordt opgelost, worden de aanwijzingen gebruikt om (on)mogelijke eigenschappen te matchen, net zolang tot er één combinatie overblijft. De moeilijkheidsgraad wordt o.a. bepaald door de afmetingen van het grid, en de soort aanwijzingen (bevestigingen, ontkenningen, relatieve (on)waarheden).

Benadering:

Een andere aanpak om zo'n puzzel op te lossen, is: werk alle mogelijke oplossingen uit, en elimineer de oplossingen die niet voldoen aan de aanwijzingen, dan blijft er (als het goed is) één oplossing over: dè oplossing.
 
Om alle mogelijke oplossingen te vinden, is het begrip permutatie interessant, dat geeft aan hoeveel mogelijke combinaties er bestaan.
Bijvoorbeeld: op hoeveel verschillende manieren zijn drie gekleurde ballen (rood, groen, blauw) te verdelen over drie posities ?
dat zijn 6 verschillende manieren:

hoeveel permutaties mogelijk zijn, is te berekenen met het begrip faculteit. Op een standaard rekenmachine is dit te vinden onder de '!'-knop: bv faculteit 3 = 3! = 3 x 2 x 1 = 6
 
om het voorbeeld van de gekleurde ballen automatisch te kunnen verwerken wordt hier een getalnotatie gebruikt:

 
Bovenstaande geldt voor één eigenschap ('kleur'), dit kan worden uitgebreid met een extra eigenschap (bijvoorbeeld 'vorm'):

het aantal combinaties is nu 3! x 3! = 36 (kartesiaans produkt)
 
In dit script wordt gesproken over actoren, eigenschappen en waarden. In de opgave zijn deze te vinden als in dit voorbeeld:

 
De moeilijkere logiquiz puzzels hebben 5 'actoren' met ieder 3 'eigenschappen', dat betekent (5!)3 = 1,728,000 mogelijke combinaties (!).
 
De bouwstenen van de aanwijzingen van een puzzel, zijn:
• wat is de actor, die bij een waarde (van een eigenschap) hoort (zie gele pijl in de figuur);
• wat is de waarde (van een eigenschap) van een actor (zie blauwe pijl);
 
Deze zijn in de code te vinden als resp.:
• act(eigenschap, waarde)
• val(eigenschap, actor)
met deze twee bouwstenen zijn alle puzzels op te lossen (!)
 
bijvoorbeeld, om een actor te vergelijken op basis van zijn eigenschappen (zie groene pijl):
• act(ene_eigenschap, waarde) == act(andere_eigenschap, waarde)
 
Of bijvoorbeeld door middel van 'nesten' (dwz combineren):
• act(ene_eigenschap, val(andere_eigenschap, actor)) == act(ene_eigenschap, waarde)
 
(zie deze pdf voor de uitwerking van enkele puzzels)

Programma afloop:

1. nieuwe instantie van de Puzzel-klasse ( Puzzel() ) wordt aagemaakt, waarbij de actoren, eigenschappen en waarden worden meegegeven.
Alle permutaties ('oplossingen') worden berekend. De starttijd wordt onthouden.
 
2. de aanwijzingen worden toegevoegd aan de puzzel ( append_rule() )
 
3. een voor een worden de aanwijzingen losgelaten op de oplossingen ( apply_rules ); bij iedere aanwijzing wordt de groep van (tot dan toe nog) geldige oplossingen kleiner
 
4. de resultaten worden samengevat ( summarize() )
 
5. bij minder dan 10 oplossingen, worden deze getoond ( export_solution() )
 
6. bij het vervallen van de instantie wordt berekend hoe lang eea heeft geduurd. ( Puzzle.__del__() )
 
 
Voorbeeld: voor de fictieve opgave 'schoolverkeer' moet worden bepaald:
'Hoe komt iedere scholier op school, hoe lang duurt het om daar te komen, en wat is hun standaard smoes als ze te laat zijn ?'

aanwijzinglogica (python)
'Mark komt iedere dag met de taxi' act(vervoer, taxi) == mark
'Daphne's reistijd verschilt met die van de wandelaar' val(reistijd, daphne) != val(reistijd, act(vervoer, te_voet))
'de fietser is twee keer zo lang onderweg als Diederik en degene zich niet lekker voelde, samen' val(reistijd, act(vervoer, fiets)) == 2 * ( val(reistijd, diederik) + val(reistijd, act(smoes, misselijk)))
'Karel heeft niet als smoes dat zijn band lek is' act(smoes, lekke_band) != karel
'de stepper stond niet voor een open brug' act(vervoer, step) != act(smoes, brug_open)
degene die een kapotte wekker had, deed er niet 10 of 15 minuten over' val(reistijd, act(smoes, wekker_kapot)) not in [10,15]
'de wandelaar voelde zich niet zo lekker' act(smoes, misselijk) == act(vervoer, te_voet)
'de stepper deed er langer over dan de taxi-er' val(reistijd, act(vervoer, step)) > val(reistijd, act(vervoer, taxi))
 
Tips:
• dit script kan zowel overweg met absolute (on)waarheden ('Piet is boos', 'Jan heeft geen rode auto', 'de fietser ging niet naar school'), als ook met relatieve waarheden ('Karel is langer dan Marie', 'een appel is 10 cent duurder dan een ei')
• dit script kan overweg met getallen. Echter alleen met gehele getallen, en niet met fracties. Dit kan altijd creatief worden opgelost, door in zo'n geval de getallen te vermenigvuldigen met de gemeenschappelijke deler, of komma's te verplaatsen.
• dit script kan niet overweg met actoren die een getal zijn. Zo'n actor kan gerust geruild worden met een eigenschap
• voor een snellere verwerking kunnen de waarheden die de meeste oplossingen uitsluiten, bovenaan worden geplaatst
• gebruik geen spaties in eigenschappen of waarden: vervang spaties door underscores, of verzin een andere naam zonder spaties
• streef ernaar alleen kleine letters te gebruiken, dat voorkomt verwarring en problemen

Voorbeeld

Onderstaande puzzel is afkomstig van de website: logiquiz.nl
 
Opgave Gastsprekers © logiquiz.nl
 
Groep 8 ontvangt dit schooljaar enkele gastsprekers.

aanwijzinglogica
1. in december komt iemand, die geen tycho heet, over vuurwerk vertellen.
In mei spreekt een 45-jarige over vrijheid.
act(maand, december) == act(onderwerp, vuurwerk)
act(maand, december) != tycho
act(maand, mei) == act(onderwerp, vrijheid)
act(maand, mei) == act(leeftijd, 45)
2. Jeanet vertelt over nepwapensact(onderwerp, nepwapens) == jeanet
3. Degene die in februari over alcohol spreekt is 2 jaar jonger dan Peteract(maand, februari) == act(onderwerp, alcohol)
val(leeftijd, act(maand, februari)) == val(leeftijd, peter) - 2
4. Tycho is 42 jaar oud. Cor is ouder dan Ninaval(leeftijd, tycho) == 42
val(leeftijd, cor) > val(leeftijd, nina)
5. Wie in juni spreekt, heeft het niet over EHBOact(maand, juni) != act(onderwerp, ehbo)
 
Deze opgave is uitgewerkt in onderstaande python code.

Zelf een logiquiz ontwerpen

Met dit programma is het ook eenvoudig om zelf een logiquiz te ontwerpen:
 
1. bedenk een onderwerp met bijbehorende actoren, eigenschappen, en waarden.
 
2. zet deze op papier (of Excel) tegen elkaar uit, en kies één enkele oplossing.
 
3. bedenk nu enkele aanwijzingen die overeenkomen met de oplossing, en vertaal die in logica regels.
 
4. run het script, en bekijk hoeveel oplossingen dit oplevert:
   → als er geen (0) oplossingen zijn dan is een aanwijzing strijdig met de oplossing
   → als er nog ~10 (of meer) oplossingen zijn dan zullen nog meer aanwijzingen moeten worden toegevoegd
   → als er slechts enkele oplossingen overblijven, vergelijk dan die oplossingen onderling om specifieke aanwijzingen te bedenken.
 
5. totdat er één oplossing overblijft.
 
 
Veel plezier en succes !!
 

De code




#!/usr/bin/env python
"""will search for a solution of a Logiquiz puzzle"""
__author__ = "Mark Nauta"
__copyright__ = "Copyright 2020"
__credits__ = "Mark Nauta"
__license__ = "GPL"
__version__ = "0.0.3"
__maintainer__ = "Mark Nauta"
__email__ = "markatnadropuntnl"
__status__ = "Production"

# lees het volledige verhaal: https://nadro.nl/mark/puzzels/logiquiz.html  

from datetime import datetime
from itertools import permutations
from itertools import product
from math import factorial
import ast
import os
import re
import sys

# voor het geval 5 actoren, drie eigenschappen:
# EEn oplossing is bv (103, 56, 78) (drie permutation_indexes voor de drie properties)
# een permutation_index (bv 103) verwijst naar een permutatie, bv [4, 1, 0, 3, 2]
# een permutatie (bv [4, 1, 0, 3, 2]) geeft voor ieder van de actors (0..4) aan welke waarde_index ze hebben
# bijv. actor2 heeft waarde_index 0
# waarde_index 0 is de eerste waarde in de lijst

class Puzzle():
    def __init__(self, actoren, eigenschappen, waarden, title='', description=''):
        self.title = title
        self.description = description
        self.timerstart = datetime.now()
        self.actors = actoren
        self.properties = eigenschappen
        self.values = waarden
        self.property_type = [ type(waarde[0]) for waarde in waarden ]
        self.solutions = self.generate_solutions()
        self.rules = []
        print('er zijn {} mogelijke oplossingen'.format(factorial(len(self.actors))**(len(self.properties)), ) )
        if any([ len(item.split()) > 1 or type(item) == float for item in actoren + eigenschappen + [str(item) for sublist in waarden for item in sublist] ]):
            sys.exit('\nfout: een van de actoren, eigenschappen of waarden bevat een spatie, of is van het verkeerde type')
        if any([ type(item) == int for item in actoren ]):
            sys.exit('\nfout: een actor mag geen getal zijn')
        
    def __del__(self):
        duration = (datetime.now() - self.timerstart).seconds
        print('{} oplossing(en) over in {} sec.'.format(len(self.solutions), duration, ))

    def generate_solutions(self):
        return [ xx for xx in product(range(factorial(len(self.actors))), repeat=len(self.properties)) ] 

    def append_rule(self, description, clue):
        if len(re.findall(r'\(', clue)) != len(re.findall(r'\)', clue)):
            sys.exit(r'\n  fout: het aantal open \'\(\') en gesloten \'\)\' haakjes moet gelijk zijn, zie:\n{}'.format(clue, ))
        rule = clue.replace(', ',',')
        node = re.compile(r'(?P<function>(act|val))\((?P<arguments>[\w,]+)\)')
        m = node.search(rule)
        while m:
            fie = m.group('function')
            args = m.group('arguments').split(',')
            if fie == 'val': 
                if len(args) >= 0:
                    property_index = self.properties.index(args[0])
                    actor_index = self.actors.index(args[1])
                    replacement = 'v(solution,{},{})'.format(property_index, actor_index, )
                    rule = rule.replace(m.group(0), replacement)
                m = node.search(rule)
            elif fie == 'act': 
                if len(args) >= 0:
                    property_index = self.properties.index(args[0])
                    if self.property_type[property_index] == int: 
                        actor_index = self.values[property_index].index(int(args[1]))
                    else:
                        actor_index = self.values[property_index].index(args[1])
                    replacement = 'a(solution,{},{})'.format(property_index, actor_index)
                    rule = rule.replace(m.group(0), replacement)
                m = node.search(rule)

        restant = re.compile( '(' + '|'.join(self.properties) + ')' )
        m = restant.search(rule)
        while m:
            replacement = self.properties.index(m.group(0))
            rule = rule.replace(m.group(0), str(replacement))
            m = restant.search(rule)

        restant = re.compile( '(' + '|'.join(self.actors) + ')' )
        m = restant.search(rule)
        while m:
            replacement = '{}'.format(self.actors.index(m.group(0)))
            rule = rule.replace(m.group(0), replacement)
            m = restant.search(rule)

        rule = rule.replace('val(', 'val(solution,')
        rule = rule.replace('v(', 'val(').replace('a(', 'act(')
        self.rules.append( (description, rule) )

def act(solution, property_index, property_value_index):
    return permutations_indexed[solution[property_index]].index(property_value_index)

def val(solution, property_index, actor_index):
    answer = permutations_indexed[solution[property_index]][actor_index]
    if my_puzzle.property_type[property_index] == int:
        answer = int(my_puzzle.values[property_index][answer])
    return answer

def apply_rules(this_puzzle):
    print('toepassen van de aanwijzingen ({}):'.format(len(my_puzzle.rules), ))
    cnt = 1
    for rule in this_puzzle.rules:
        print('toepassen aanwijzing {:2d} van {} (\'{}\')... '.format(cnt, len(this_puzzle.rules), rule[0][:20]), end='')
        code = ast.parse(rule[1], mode='eval')
        this_puzzle.solutions[:]= [solution for solution in this_puzzle.solutions if eval(compile(code, '', mode='eval'))]
        print('{} oplossingen resteren'.format(len(this_puzzle.solutions), ))
        cnt += 1

def summarize(this_puzzle):
    if (len(this_puzzle.solutions) == 0):
        print('deze puzzel heeft geen oplossing')
    elif (len(this_puzzle.solutions) == 1):
        print('deze puzzel heeft 1 oplossing')
    else:
        print('\ndeze puzzel heeft {} oplossingen:\n'.format(len(this_puzzle.solutions)), )
    if (len(this_puzzle.solutions) < 25):
        for solution in this_puzzle.solutions:
            print(export_solution(this_puzzle, solution))

def export_solution(this_puzzle, this_solution):
    out = ''
    act_width = max( [ len(item) for item in this_puzzle.actors ] ) + 3
    prop_width = []
    for property_index in range(len(this_puzzle.properties)):
        property_width = len(this_puzzle.properties[property_index])
        max_prop_width = ( max( [ len(str(item)) for item in this_puzzle.values[property_index] ] ) )
        prop_width.append(max(property_width, max_prop_width) + 3)
    #headers:
    out += ' ' * act_width
    for property_index in range(len(this_puzzle.properties)):
        out += this_puzzle.properties[property_index].ljust(prop_width[property_index])
    out += '\n'
    # values:
    for actor_index in range(len(this_puzzle.actors)):
        out += this_puzzle.actors[actor_index].ljust(act_width)
        for property_index in range(len(this_puzzle.properties)):
            out += str(this_puzzle.values[property_index][permutations_indexed[this_solution[property_index]][actor_index]]).ljust(prop_width[property_index])
        out += '\n'
    return out

if __name__ == "__main__":
    my_puzzle = Puzzle([ 'cor',  'jeanet', 'nina', 'peter', 'tycho'] , [ 'leeftijd', 'onderwerp', 'maand' ], [ [40, 42, 45, 48, 50], ['alcohol', 'ehbo', 'nepwapens', 'vrijheid', 'vuurwerk'], ['oktober', 'december', 'februari', 'mei', 'juni' ] ],\
        'Gastsprekers', 'Groep 8 ontvangt dit jaar enkele gastsprekers')
    my_puzzle.append_rule('1. in december komt iemand, die geen Tycho heet, over vuurwerk vertellen. In mei spreekt een 45-jarige over vrijheid',\
        'act(maand, december) != tycho and act(maand, december) == act(onderwerp, vuurwerk) and act(maand, mei) == act(onderwerp, vrijheid) and act(maand, mei) == act(leeftijd, 45)')
    my_puzzle.append_rule('2. Jeanet vertelt over nepwapens',\
        'act(onderwerp, nepwapens) == jeanet')
    my_puzzle.append_rule('3. degene die in februari komt iemand over alcohol spreekt, is twee jaar jonger dan Peter',\
        'act(maand, februari) == act(onderwerp, alcohol) and val(leeftijd, act(maand, februari)) == val(leeftijd, peter) - 2')
    my_puzzle.append_rule('4. Tycho is 42 jaar. Cor is ouder dan Nina',\
        'val(leeftijd, tycho) == 42 and val(leeftijd, cor) > val(leeftijd, nina)')
    my_puzzle.append_rule('5. wie in juni spreekt, heeft het niet over ehbo',\
        'act(maand, juni) != act(onderwerp, ehbo)')

    permutations_indexed = [ xxx for xxx in permutations(range(len(my_puzzle.actors))) ]

    apply_rules(my_puzzle)

    summarize(my_puzzle)