Schuifpuzzels - combinatoriek - 10 mei 2023

• Wiskunde
• HBO
• Studiejaar 1-3

Schuifpuzzel EXPERIENCE

Wat gaan we doen

1. Verkennen
2. Configuraties
3. Oplosbaarheid
4. Optimalisatie

Verkenning

• Typ de link op je werkblad https://bit.ly/42cZcLU
   en los de puzzel op
• Klaar?
• Druk op reset voor een andere startpositie(s)
  
• Scan de QR code

• en werk gerust verder op je werkblad!
  
• Na 20 minuten komen we weer in de lucht

Wat valt je op bij het oplossen van
schuifpuzzels?
Denk aan oplostechnieken en zetten ...

Uitgangspunten configuraties
van een legpuzzel

• Een configuraties is hetzelfde als een startpositie,
  
•   waarin de tegels op een bepaalde plek worden geplaatst.
•  Een n-schuifpuzzel, afgekort n-puzzel:
     heeft n bewegende tegels en n+1 vakjes.
  
•  Een schuifpuzzel heeft minimaal twee rijen
     of twee kolommen en is  rechthoekig van vorm.
• Werk gerust verder op je werkblad!
  
• Na 20 minuten komen we weer in de lucht, dan sluiten we de les af!

De afronding!

+ een stukje theorie

Configuraties en oplosbaarheid

• Aantal startposities (configuraties) bij n-puzzel en m-tegels:
• n_k (m, n+1) = n_k (n+1) = (n+1)!
  
• Hoe kun je bereken hoeveel configuraties oplosbaar zijn?
   n_k (n+1) / 2= (n+1)! /2

https://bollebus.be/blog/de-schuifpuzzelschuifpuzzel-1

Optimalisatie: minst aantal zetten

Algoritmes bekend van:

• Korf, R. E. (1985). Depth-first iterative-deepening:
    An optimal admissible tree search. Artificial Intelligence, 27, 97-109.
• Nilsson, N. J. (1971). Problem-solving methods in artificial intelligence. 
• Pyramide algoritme
• Grafentheorie
• Kun jij het sneller dan de algortimes?
• Bij grote schuifpuzzels waarschijnlijk wel!

Vragen?

Hoe heb je deze les
ervaren?

😒🙁😐🙂😃