Hulp gevraagd bij algoritme voor rummikub

[Verwijderd]

Hoi mensen,

Ik ben nu al even bezig met iets wat mij tot nu toe behoorlijk tegenvalt en waar ik wel wat hulp bij kan gebruiken.

Ik wil een controle-script ontwikkelen waarmee ik kan controleren of de stenen die iemand op zijn speelbord heeft een winnende combinatie is.

Om je een idee te geven hoe het spel werkt:
Het spel heeft in totaal 106 stenen waarvan 2 jokers en de rest verdeeld over 2 sets genummerd vanaf 1 t/m/13 in 4 kleuren (zwart, rood, blauw en groen).
In het begin van het spel krijgt iedere speler 14 stenen en met deze stenen moet de speler 'rijtjes' en 'sets' maken.

Een set is een verzameling van 3 of 4 stenen in verschillende kleuren, bijvoorbeeld een rode, zwarte en blauwe 4, of in combinatie met een joker: rode en groene 5 en een joker.

Een rij is een verzameling van ten minste 3 opeenvolgende stenen (met of zonder jokers), bv rood 5,6 en 7 of blauw 10,11,12 en 13 zijn geldige rijtjes.
Een 1-steen kan ook als 14 worden gebruikt, dus 'blauw 12,13,1' is ook geldig

Nu kan ik wel controleren of er 1 of meerdere 1-stenen beschikbaar zijn, maar als deze in een set worden gebruikt zijn ze voor de rij niet meer beschikbaar, tenzij deze set uit 4 stenen bestaat waardoor die ene steen van de set kan worden gepakt om ze aan de rij toe te voegen.

Zie ook http://www.pagat.com/rummy/okey.html voor een volledige (engelstalige) omschrijving van de spelregels.

Is hier iemand die ervaring met zulke wiskundige problemen ervaringen heeft die mij een goeie duw in de juiste richting kan geven ?

(owja, kant-en-klare oplossingen mag natuurlijk ook )

edit:
regel over de nummer-1-steen aangepast

[ Voor 4% gewijzigd door Verwijderd op 13-08-2006 16:48 ]

[djluc]

Verder mag je ook weer jokers inruilen e.d. waardoor je nog een stuk meer mogelijkheden krijgt...

[Verwijderd]

Eh ja wat de joker is is afhankelijk van de zogenaamde 'openings-steen' waarmee je het spel begint.

Als de stenen zijn verdeeld moet de eerst steen op de resterende stapel om worden gedraaid en als dit bijvoorbeeld een blauwe 10 is, is de blauwe 11 de joker.
De stenen met de smiley zijn dan niet in te zetten als een joker, maar alleen als de 'blauwe 11'.

Dat is het probleem niet, want zodra je de stenen gaat controleren kijk je dus welke steen a.d.v de openingsteen de joker is en 'verwissel' je de smileys met de stenen die ze dan vertegenwoordigen en de blauwe 11 met de joker.

Verder is het inderdaad de bedoeling dat iedereen op zijn beurt 1 steen door moet geven aan de volgende speler die dan kan beslissen of hij deze steen pakt of een steen van de stapel.

Maar dit heeft allemaal weinig invloed op de controle, omdat de controle alleen maar naar de huidige 14 stenen op het bordje hoeft te kijken, ongeacht wat er nog op de stapel ligt en welke stenen door zijn gegeven.

[ Voor 2% gewijzigd door Verwijderd op 13-08-2006 17:09 . Reden: typos ]

[NMe]

Verwijderd schreef op zondag 13 augustus 2006 @ 16:38:
(owja, kant-en-klare oplossingen mag natuurlijk ook )

Nee, want daar dient dit subforum niet voor. We willen je best helpen met brainstormen, maar kant en klare ontwerpen zul je toch echt ergens anders vandaan moeten halen.

Verder: wat is het probleem precies? Waar loop je vast? Je zal vast zelf al een opzetje gemaakt hebben; wat lukte daar niet aan en waarom niet? Je geeft nu alleen aan wat je wil hebben en effectief is dus het enige antwoord dat je hier kan verwachten een kant en klaar ontwerp, en zoals ik al zei is dat hier niet de bedoeling.

[Verwijderd]

[/quote]Nee, want daar dient dit subforum niet voor. We willen je best helpen met brainstormen, maar kant en klare ontwerpen zul je toch echt ergens anders vandaan moeten halen.[quote]

Ja weet ik, maarja, je weet nooit

Het begin van mijn opzetje is dat ik de joker-stenen vervang door de kleur-nummer-combinatie die ze op dat moment vertegenwoordigen en de juiste kleur-nummer-combinatie vervang door jokers die overal inzetbaar zijn.
Verder maak ik gebruik van codes als a1, c3, d11 waarbij de letters een kleur vertegenwoordigen en sla deze op in een numerieke array.

Omdat je ook kunt winnen met 7 sets van 2 identieke stenen komt die controle als eerst:
versimpeld scriptje als voorbeeld)

code:

if((count(array_unique($stones)) - $aantal_jokers) <= 7){
    return TRUE;
}

( Omdat ik lokaal een webservertje heb draaien met php en hier het beste mee bekend ben omschrijf ik de tests in een php-scriptje )

Als bovenstaande evaluatie niet TRUE teruggeeft gaan we dus verder.
Nu kan ik wel de array met stenen filteren naar een array gesorteerd op kleur en 1 gesorteerd op getallen, de rijen en de sets opzoeken en deze en alle geassocieerd elementen verwijderen om op een restant van 0 stenen uit te komen, maar het lastige is dus dat de kans groot is dat je stenen wegstreept die door de speler voor andere sets of rijen bedoeld waren.

Kijk, setjes van 3 nummer-x-stenen is makkelijk te filteren, maar als je bv 5 nummer-1-stenen hebt, zijn er dan 1 of 2 gereserveerd voor een rij van 12-13-1.

Of moet ik juist iedere kleinst mogelijke juiste combinatie van stenen beschrijven en de stenen van de speler op de een of andere manier hier doorheen filteren.

Misschien denk ik wel te moeilijk (of veel te makkelijk) en zit ik in de verkeerde hoek te zoeken maar daar draait het in feite ook om:
Door gebrek aan kennis en ervaring op dit gebied weet ik (nog) niet waar ik de oplossing moet zoeken

[dewil1990]

leuk voor mijn profiel werkstuk volgend jaar mar ik denk niet dat ik deruit kom.

[joepP]

Feitelijk boeit de huidige staat van het bord niet, aangezien je toch alles mag verplaatsen.

Wat je wilt oplossen is de vraag of er, gegeven het bord en de stenen in de hand, een geldige layout is waarbij al deze stenen geplaatst zijn. Ik vermoed dat dit probleem zeer ingewikkeld is, en dat er geen perfecte methode is om dit op te lossen. Wat je wel kan doen is proberen de stenen een voor een te plaatsen, maar dat is verre van optimaal.

Lastig probleem...

[Verwijderd]

Feitelijk boeit de huidige staat van het bord niet, aangezien je toch alles mag verplaatsen.

Wat je wilt oplossen is de vraag of er, gegeven het bord en de stenen in de hand, een geldige layout is waarbij al deze stenen geplaatst zijn

??
Misschien heb ik ergens de verkeerde suggestie gewekt, maar een speler heeft constant 14 stenen in zijn handen.
De vraag is hoe te controleren of deze 14 stenen uit meerdere geldige sets en rijen bestaat.

[Janoz]

Constant 14 stenen? Als ik wat opleg heb ik een stuk minder stenen. Als ik niet kan heb ik er weer 1tje bij. Als ik uit wil kan ik alle stenen die al op het bord liggen gebruiken.

Ikzelf kende trouwens de regel niet dat een joker, 1 keer gebruikt, die waarde kreeg.

[SeatRider]

Janoz schreef op maandag 14 augustus 2006 @ 10:34:
Constant 14 stenen? Als ik wat opleg heb ik een stuk minder stenen. Als ik niet kan heb ik er weer 1tje bij. Als ik uit wil kan ik alle stenen die al op het bord liggen gebruiken.

Ikzelf kende trouwens de regel niet dat een joker, 1 keer gebruikt, die waarde kreeg.

Ik kende zelf de regel niet dat je steeds een steen doorgeeft en dat je mag kiezen of je die neemt, of 1 van de stapel. Maar goed, het zal wel net zo zijn als met monopoly, iedereen verzint zijn eigen regels er omheen.

[BCC]

Je pakt alle losse stenen op de tafel + alle stenen op je bord.

Dan blaas je via een brute-force alle mogelijke oplossingen door (niet zo heel veel mogelijkheden) en dan weet je of het past.

[joepP]

BCC schreef op maandag 14 augustus 2006 @ 10:40:
Je pakt alle losse stenen op de tafel + alle stenen op je bord.

Dan blaas je via een brute-force alle mogelijke oplossingen door (niet zo heel veel mogelijkheden) en dan weet je of het past.

Je bent niet goed wijs

Er zijn juist belachelijk veel mogelijkheden, en ik maak me sterk dat je dit helemaal niet kan bruteforcen. Probeer het eens zou ik zeggen.

[BCC]

Ik had misschien iets duidelijker moeten zijn: Het valt best mee, want er valt enorm veel af. Je kunt niet een 3 naast een 5 leggen enzo. Je kan alleen maar groepjes maken van dezelfde soort en van oplopende dingen. Daar heb je helemaal niet zoveel mogelijkheden voor. En met de stenen op tafel en die op je bordje, zit je aan een steen of 40. Maar dat is iets wat de TS mooi zelf mag uitrekenen

Je moet 't zien als een zoekboom. Ik zal even een voorbeeldje geven:

Stel je hebt 4 stenen: 1,2,3,4, dan begin je 16 bomen:

code:

1,2
1,3
1,4
2,1
2,3
2,4
3,1
3,2
3,4
4,1
4,2
4,3

Van deze 16 bomen hoef je er maar met 3 verder te gaan:

code:

1,2
2,3
3,4

Er vallen zo dus enorme stukken weg die je niet meer hoeft te bekijken. Met mooie truuks als Tabu-searching kun je het allemaal nog een stuk sneller maken.

Ik ben voor mijn opleiding van dit soort dingen bezig en daar worden 80! dingen die een stuk complexer zijn dan dit in een seconde of 10 uitgerekend op mijn 2 GHz bakje.

[ Voor 66% gewijzigd door BCC op 14-08-2006 11:13 ]

[joepP]

Ik begrijp wel hoe een zoekboom werkt, en ook hoe je die voor dit probleem kan toepassen, maar volgens mij onderschat je de complexiteit van het gegarandeerd oplossen gigantisch. Verder is een techniek als Tabu-search leuk en aardig, maar leidt niet tot gegarandeerd optimale oplossingen, en ik zie dan ook niet wat dat met je zoekboom van doen heeft. Samengevat bespeur ik een hoog klok-klepel gehalte in je post.

Stel nou eens dat er -geen- oplossing is met 40 stenen, een hele normale situatie. Ondanks alle leuke trucjes moet je toch -alle- permutaties aflopen waarvan het begin geldig is. Het is direct duidelijk dat dit er al veel teveel zijn om te kunnen aftellen binnen normale rekentijd.

Een mogelijke methode om toch tot een oplossing te komen is om alle mogelijke setjes te genereren, en te kijken of je met een subset daarvan de verzameling stenen kan overdekken. Een soort set-cover dus. Helaas is set-cover NP compleet, en zal je je tot heuristieken (local-search bv) moeten wenden om proberen de boel op te lossen. Ik denk dat je hiermee nog het verst komt, omdat er waarschijnlijk niet al teveel setjes zijn (ik gok iets van 1000).

[MicroWhale]

het probleem heeft volgens mij twee delen:

1. bedenk een oplossing met de stenen op tafel + stenen op je bordje,
2. verzin een pad wat van de huidige stenen op tafel, naar de nieuwe situatie leidt.

nu is deel 2 op zich veel minder complex en omvangrijk dan deel 1, maar het moet zeker niet onderschat worden.

[Janoz]

Waarvoor zou dat pad nodig zijn?

[MicroWhale]

voor het eerste deel van de oplossing kun je het volgende doen:

1. voeg alle stenen van de tafel samen met je eigen stenen,
2. maak een lijst met alle mogelijke geldige sets (zie engelstalige handleiding)
3. maak een lijst met alle mogelijke geldige runs
4. zijn er stenen over? zo ja, geen volledige oplossing,
5. sorteer de sets op grootte,
6. probeer, door het samenvoegen van sets & runs, nul (of zo min mogelijk, zie stap 4) stenen over te houden.

De laatste stap moet op zich met niet al te veel permutaties te doen zijn. Bij het toevoegen van een set of run aan de test-tafel, worden de sets en runs die de stenen bevatten van de neergelegde set of run, tijdelijk weggestreept.

[ Voor 14% gewijzigd door MicroWhale op 14-08-2006 14:02 ]

[MicroWhale]

Janoz schreef op maandag 14 augustus 2006 @ 13:58:
Waarvoor zou dat pad nodig zijn?

Omdat je je oplossing ook neer moet kunnen leggen. Dat gaat irl ook zo. Je legt niet meteen heel de oplossing neer, je motiveert je oplossing aan de andere speler zodat ook hij kan zien dat deze klopt.

[joepP]

Als jij de boel blind door elkaar husselt, 3x een dansje doet, en daarna de stenen in een legale ordening neerlegt is het toch perfect?

[Janoz]

De oplossing klopt omdat er aan het einde van je beurt een geldige verzameling op tafel ligt en je geen stenen van tafel weer 'in de hand genomen' hebt. Hoe de status van het speelveld is tussen het begin en het einde van de beurt maakt neit uit. Desnoods neem je telkens 1 steen en leg je deze in de nieuwe situatie.

edit : @Joep: Nee, niet geldig, je bent de koprol vergerten

[ Voor 9% gewijzigd door Janoz op 14-08-2006 14:08 ]

[MicroWhale]

joepP schreef op maandag 14 augustus 2006 @ 14:05:
Als jij de boel blind door elkaar husselt, 3x een dansje doet, en daarna de stenen in een legale ordening neerlegt is het toch perfect?

dat is technisch gezien ook zo. Ik zou er als jou tegenspeler alleen absoluut niet blij mee zijn als ik niet wist hoe je daaraan gekomen was. Vooral niet als de halve tafel opeens anders ligt.

Stel: je zit te rummikubben en je moet opeens ongelofelijk naar de plee. Je maakt je beurt af en je tegenspeler is nu aan zet. Als je terugkomt zegt hij enthousiast: "ik ben uit!" en je ziet inderdaad een legale ordening op tafel liggen die vrij veel verschilt van de situatie zoals je die kende voordat je wegging.

Zou je dat leuk vinden/accepteren?

[MicroWhale]

Janoz schreef op maandag 14 augustus 2006 @ 14:07:
De oplossing klopt omdat er aan het einde van je beurt een geldige verzameling op tafel ligt en je geen stenen van tafel weer 'in de hand genomen' hebt. Hoe de status van het speelveld is tussen het begin en het einde van de beurt maakt neit uit. Desnoods neem je telkens 1 steen en leg je deze in de nieuwe situatie.

Dat is inderdaad de bedoeling ja, het wordt alleen bemoeilijkt doordat volgorde hier van belang is. Sommige stenen kunnen niet neergelegd worden voordat andere stenen zijn gelegd.

[Janoz]

Met een stappenplan ga je er vanuit dat de nieuwe situatie afhankelijk is van de ordening van de oude. Dit is niet het geval. De enige overeenkomst is welke stenen er op tafel liggen. Je hebt als het ware geen overgang. Het enige dat je moet aantonen is dat alle stenen die in de vorige beurt op tafel lagen er nu nog steeds liggen.

Dat is inderdaad de bedoeling ja, het wordt alleen bemoeilijkt doordat volgorde hier van belang is. Sommige stenen kunnen niet neergelegd worden voordat andere stenen zijn gelegd.

Waarom niet? Er is toch geen enkele beperking over wanneer er wel of niet een steen gelegd kan worden?

[ Voor 31% gewijzigd door Janoz op 14-08-2006 14:15 ]

[Grijze Vos]

Ik heb zo'n donkerbruin vermoeden dat dit een exponentieel algoritme is. Gelukkig ben je gelimiteerd in aantal stenen en zou je dat dus misschien kunnen brute forcen, zoals hierboven vermeld wordt.

[Dido]

Volgens mij heeft niet iedereen de link in de TS doorgelezen. Er worden helemaal geen combinaties op tafel gelegd bij dit spel

De titelfix maakt het er ook niet duidelijker op dat het niet om rummikub gaat, maar om een spel in diezelfde familie

[MicroWhale]

Janoz schreef op maandag 14 augustus 2006 @ 14:14:
Met een stappenplan ga je er vanuit dat de nieuwe situatie afhankelijk is van de ordening van de oude. Dit is niet het geval. De enige overeenkomst is welke stenen er op tafel liggen. Je hebt als het ware geen overgang. Het enige dat je moet aantonen is dat alle stenen die in de vorige beurt op tafel lagen er nu nog steeds liggen.

dat is inderdaad waar ja, en met een computer is dit ook makkelijk visueel te maken...
betere en snellere oplossing.

[Dido]

Behalve dus dat er geen ordening is van stenen op de tafel

[joepP]

Dido schreef op maandag 14 augustus 2006 @ 14:27:
Volgens mij heeft niet iedereen de link in de TS doorgelezen. Er worden helemaal geen combinaties op tafel gelegd bij dit spel

Oeps.

Het spel wat de TS bedoelt is een stuk eenvoudiger. Je hebt maar 14 stenen, en je moet deze in een keer op tafel leggen in sets (gelijk nummer, ongelijke kleur) en in runs (opeenvolgend nummer, gelijke kleur).

[BCC]

joepP schreef op maandag 14 augustus 2006 @ 13:44:
Samengevat bespeur ik een hoog klok-klepel gehalte in je post.

Ja, daarom ben ik er bijna op afgestudeerd

Stel nou eens dat er -geen- oplossing is met 40 stenen, een hele normale situatie. Ondanks alle leuke trucjes moet je toch -alle- permutaties aflopen waarvan het begin geldig is. Het is direct duidelijk dat dit er al veel teveel zijn om te kunnen aftellen binnen normale rekentijd.

Nee, want zoals ik en jezelf al aangaf, moet je setjes gaan maken. Dit is inderdaad een NP compleet probleem, maar zeker geen heel complex probleem. Vooral omdat je maar met 14 stenen op je bord bezig bent.

[ Voor 4% gewijzigd door BCC op 14-08-2006 17:53 ]

[Verwijderd]

Woei, het lijkt erop dat het probleem alsmaar groter wordt ipv kleiner

Misschien had ik inderdaad de titel van de topic beter moeten kiezen, maar als ik 'Okey' zeg kan dat mogelijk net zo verwarrend werken, vandaar de link in de TS

Anyway, als ik de oplossing moet zoeken in iets als een NP-probleem begin ik te begrijpen waarom ik erover struikel: het is gewoon complex als je niet over de ervaring / kennis beschikt

Maar goed, eerst maar eens gaan slapen nu en morgen de zaken weer eens met een frisse blik bekijken

[joepP]

BCC schreef op maandag 14 augustus 2006 @ 17:53:
Ja, daarom ben ik er bijna op afgestudeerd

offtopic:
Ah, het autoriteitsargument. Als je ergens een "expert" in claimt te zijn moet je dat onderbouwen met kennis en kunde, niet door op je opleiding of status te wijzen. Verder zitten we hier allebei nogal te falen door in eerste instantie aan te nemen dat het om normaal rummikub ging, terwijl het om een veel eenvoudigere variant gaat. Jouw methode werkt niet voor 40 stenen, maar voor 14 wel.

Inzake het echte probleem van de TS: de eerder door BCC genoemde methode zal daar wel voor werken. Je kan alle mogelijke ordeningen van de stenen recursief genereren, en tijdens die generatie direct checken of er nog een oplossing mogelijk is. Met 14 stenen heb je ongeveer 87 miljard permutaties, maar je hoeft slechts een fractie daarvan af te tellen.

[Verwijderd]

Ok.. Dit is geen NP-HARD problem. De TS vraagt het volgende:
Is het een toegelaten oplossing of is het geen toegelaten oplossing? Het is een beslissingsprobleem.

De oplossing is vrij simpel volgens mij en ik zou het als volgt doen.

1. controleer of het een toegelaten oplossing is met paren.
sorteer de stenen op kleur en daarna op volgorde. Check of alle stenen 2tallen van dezelfde tiles vormen. Is dat het geval, dan is het een toegelaten oplossing. Zo niet, ga naar 2.

2. Controleer of het een toegelaten oplossing is met runs en sets.
Dit is wat lastiger. Ik zou geen ingewikkelde dingen hier doen. Het is een klein probleem; 14 stenen zijn niet zoveel. Je zou hier met brute force kunnen werken en ik verwacht dat dit binnen een seconde een antwoord geeft. Als je toch wat slimmer wil doen, dan kan je bijvoorbeeld het volgende doen:
a. geef alle 14 stenen een uniek id. Sorteer ze daarna op kleur en daarna binnen de kleur op volgorde. Kijk welke mogelijke runs er zijn. Sla deze mogelijke runs op. Sorteer daarna op nummers en daarna op kleur. Bekijk welke mogelijke sets er zijn en sla deze op. NU heb je alle mogelijke sets en runs. Als er een combinatie bestaat van sets en runs waarbij alle 14 unieke stenen gebruikt zijn, dan heb je een toegelaten oplossing.

Dit is de meest simpele oplossing die ik even snel kan bedenken. Misschien zijn er nog simpelere oplossingen. Uiteraard zijn er via local search en andere type algoritmen betere en snellere oplossingen maar dat lijkt mij voor de TS iets te ver gaan. Mocht het algortime niet snel genoeg zijn dan zal je toch ingewikkelder moeten gaan doen.

[ Voor 3% gewijzigd door Verwijderd op 15-08-2006 12:08 ]

[Soultaker]

Het hele verhaal over wel-of-niet-NP-hard is nogal irrelevant, als het om een vast, klein aantal stenen gaat.

Ik zou het als volgt aanpakken. In een geldige oplossing wordt elk van de stenen gebruikt in ófwel een set, ófwel een run. Als je de stenen dus eerst daarop indeelt, heb je 2¹⁴ = 16384 mogelijkheden -- relatief weinig voor een computer.

Vervolgens moet je uitzoeken of alle set-stenen inderdaad setjes vormen. Daarvoor hoef je steeds alleen de stenen van één enkel cijfer samen te nemen. Heb je er twee of vijf, dan kan het sowieso niet. Heb je twee van dezelfde kleur, dan heb je er minstens zes nodig, enzovoort. Al met al is dit wel uit te voeren, maar efficiënter is van te voren een look-up table voor de 3⁴ = 81 gevallen maken (die '3' staat voor het aantal stenen dat je van elke kleur hebt, 0, 1 of 2, en de '4' het aantal kleuren; er zijn zelfs minder gevallen als je de kleuren op aantal sorteert o.i.d).

Tenslotte moet je uitzoeken of alle run-stenen inderdaan runs vormen. Ik denk dat je dat simpelweg als volgt kunt doen: sorteer alle stenen, en ga ze dan één voor één in straatjes leggen, waarbij je elke steen steeds achter elk kortste straatje aanlegt dat mogelijk is, of een nieuw straatje aanlegt als het niet mogelijk is. Als er op het eind straatjes van minder dan 3 lang liggen, is het niet mogelijk om geldige runs te vormen.

Voor 1 2 3 4 5 5 6 6 7 bouw je bijvoorbeeld eerst '1 2 3 4 5' op; daarna begin je met de volgende vijf een nieuw straatje (omdat het niet anders kan); de volgende 6 komt daarachter (kortste straatje aanvullen), de 6 daarna achter het eerste straatje, en tenslotte de 7 achter het tweede straatje; resultaat 1 2 3 4 5 6 en 5 6 7. Ik heb het niet helemaal bewezen, maar ik denk dat dit optimaal is, omdat het nooit nuttig is om met een steen een nieuw straatje te beginnen als je 'm ook ergens anders achter kan leggen. Je kunt overigens al stoppen met straatjes maken zodra je een straatje hebt dat korter dan 3 is en je huidige steen mag er niet meer achter (bijvoorbeeld: er ligt 3 4, en je volgende steen is een 6). Ook maakt het niet uit welke straat een steen krijgt, als alle straten al 3 lang zijn.

Al met al moet dit wel binnen een paar honderd milliseconden uit te voeren zijn. (Misschien met PHP wat meer.)

offtopic:
Hé DesignHulp.nl, je website/nickname doet het niet.

[ Voor 9% gewijzigd door Soultaker op 19-08-2006 12:35 ]

[Soultaker]

Het checken van straatjes kan trouwens nog makkelijker. Je hebt per kleur maximaal twee stenen met hetzelfde cijfer, dus je kunt maar twee overlappende straatjes vormen. Dit komt voor als je stenen van a t/m b hebt, met c t/m d (a<=c, d <=b) dubbel. In dit geval is het in ieder geval correct om te splitsen in straatjes a..d en c..b; als beide straatjes minimaal 3 lang zijn is de combinatie geldig (als één van beide te kort is, kun je 'm onmogelijk verlengen).

[ Voor 7% gewijzigd door Soultaker op 19-08-2006 12:48 ]