| WikiPedia | Almost-Squares | Kakuro | Eternity | Cirkelpuzzels |
 |
 |
 |
 |
 |
|
|
|
|
|
|
Mind the gap
Dit stuk is nog under construction. Jeffrey de Loof heeft een heel mooi onderzoekje opgezet, maar hoe en of het wordt voortgezet is nog under consideration. Spoedig meer. |
Waarschuwing Dit is een pittige opdracht waarvan de uitkomst onzeker is. Je krijgt zeer regelmatige coaching van een docent en twee ouderejaars, maar het blijft een pittige opdracht. Inleiding "Almost squares" zijn tegels die bijna vierkant zijn. Tegels van 3x4, 15x16 of 21x22 zijn voorbeelden van almost squares. Als je een aantal opvolgende almost-squares neemt, beginnend bij de eerste, en er een invoervak bestaat dat ook een almost square is, spreken we van een almost square tiling problem. Daar zijn er precies vijf van, weten we dankzij onze student Florian Braam. De vijfde is onopgelost, ondanks dat Florian goede vorderingen heeft gemaakt. Opdracht Het lijkt erop dat je een groot deel van de toestandsruimte niet hoeft te doorzoeken als je het probleem splitst in een rand en een binnenwerk. De randen kunnen voor een groot gedeelte uitgerekend worden op een stand-alone PC, met de binnenwerken is het probleem dat sommige binnenwerken een grote toestandsruimte hebben, maar heel veel een hele kleine. We moeten werken met de DAS, en hier iets slims op verzinnen. Florian zal persoonlijk helpen in de coaching. 1) Schrijf een randengenerator die voor gegeven randensets alle oplossingen in een tekstfile output. 2) Schrijf een programma voor de DAS dat een tekstfile met randen eet, controleert en het binnenwerk uitrekent. Bedenk iets van een timeout-functie |
Inleiding De kakuro is een interessante variant op de sudoku. In iedere rij en kolom moet een aantal verschillende cijfers staan, die opgeteld aan de kantlijnwaarde moeten voldoen. We denken dat er verschil bestaat tussen makkelijke en moeilijke kakuro's, maar we zijn nog nergens. Een eerste stap zou kunnen zijn het genereren van vierkante of rechthoekige kakuro's van één formaat, en kijken wat kantlijnwaardes voor invloed hebben op de invulmogelijkheden. 
Is de eerste kakuro makkelijker of moeilijker dan de twedde? En wat bepaalt die moeilijkheid? |
Inleiding Eternity II is een prijspuzzel met een beloning van $2.000.000 voor de oplossing. De deadline is verstreken, en de puzzel is niet opgelost. Nu zijn er natuurlijk nog wel veel kudos te halen voor de oplosser van de puzzel, maar waarschijnlijk is hij zo moeilijk dat hij niet op te lossen is. Dat is opmerkelijk, want het is een heel klein puzzeltje, en er bestaat zeker een oplossing. We willen weten wat deze puzzel zo moeilijk maakt. Er is een goede kans dat het ligt aan de kleurverdelingen op de stukjes. Nu is er een paper van Antosegui et al van de universiteit van Lleida waarin het volgende experiment wordt beschreven: Men neme heel veel verschillende kleuren, generere een puzzel en late een solver de losse stukjes aan elkaar puzzelen. Nu doet men hetzelfde voor een puzzel met minder verschillende kleuren, en laat een solver het weer aan elkaar puzzelen. Dat doet men voor heel veel verschillende kleurzettingen en men meet de tijd dat de solver nodig heeft om tot een oplossing te komen. Het resultaat is een enorme piek in rekentijd voor puzzels met niet teveel, maar ook niet te weinig kleuren. Zie eerdere link. Nu denken we dat de auteurs mogelijk iets over het hoofd gezien hebben en we willen het experiment herhalen. Het goede nieuws: we hebben al een solver, geschreven door ouderejaars Patrick van Rietschoten, en die zal, samen met de docent, begeleding en technische ondersteuning bieden. Dit experiment vraagt een laboratoriumachtige instelling, omdat de tijdsmetingen nauwkeurig moeten verlopen. Ook moet je iets van programmeren weten om de solver te kunnen bedienen en aan te passen, maar zelf heel veel coderen hoeft niet (al kan dat naar wens bijgesteld worden). Maar het belangrijkste is interesse voor puzzels, voor wat puzzels moeilijk maakt, en voor wonderlijke natuurfenomenen. |
Inleiding Cirkelpuzzels zijn in essentie edge-matching-puzzels, maar dan supereenvoudig. Ze bestaan uit een aantal stukjes die op elkaar passen als de egdes overeenkomen, en dienen als speeltje om erachter te komen wat problemen moeilijk maakt. Er is wat vordering op dit gebied. Puzzels met meer stukjes zijn in principe moeilijker, maar voor twee evengrote puzzels geldt dat het aantal soorten edges uitmaakt voor de moeilijkheid. Maar zelfs als twee puzzels exact dezelfde edges hebben, kan de een nog steeds moeilijker zijn dan de ander. Opdracht Maak cirkelpuzzels van meer dan acht stukjes die in alle opzichten gelijk zijn, behalve in hun moeilijkheid. Er zijn hiervoor concrete ideeen, zie bijgevoegd werkdocument. |
