3 op een rij

[Herbie]

Hallo allemaal,

Ik loop al een tijdje met het volgende puzzeltje in mijn hoofd maar ik kom er niet uit.

Stel je hebt een speelbord met 16 vakjes (4 x 4).
Op elk vakje staat een steen die een van de 4 kleuren rood, groen, blauw of oranje heeft (random door elkaar).
Je kunt de stenen niet verplaatsen maar wel van kleur laten veranderen. Als er 3 of meer stenen met dezelfde kleur op een rij staan (horizontaal, verticaal of diagonaal) verdwijnen de stenen.
Hoeveel mogelijkheden zijn er nu om het hele bord leeg te spelen? Is dat in een formule uit te drukken?

[David]

Als er 3 of meer stenen met dezelfde kleur op een rij staan (horizontaal, verticaal of diagonaal) verdwijnen de stenen.

Welke stenen verdwijnen dan, de drie op een rij of de zestien in het veld?

[Herbie]

De drie op een rij verdwijnen dan.

[David]

Dan zijn er 0 mogelijkheden. Er verdwijnt een veelvoud van 3 stenen van het veld terwijl er 16 op het bord staan. Of zou je aanvoeren dat stel, bijv. alle stenen zijn rood, dan zijn alle stenen in zo'n rijtje dus verdwijnen ze allemaal?

[Herbie]

Als er 3 of meer op een rij staan verdwijnen ze, dus er zullen een keer ergens 4 stenen van dezelfde kleur op een rij moeten staan.
Ik zal proberen het vanavond iets duidelijker te maken met een plaatje.

[David]

Ik zie nu wat je zegt. In plaats van precies 3, 3 of meer stenen van dezelfde kleur.

[David]

Korte start. Er kunnen alleen rijtjes verdwijnen van 3 of 4 stenen van dezelfde kleur op een rij.
Stel, d is het aantal rijtjes van 3 op een rij en v is het aantal rijtjes van 4 op een rij.
Dan, als alle stenen verdwijnen, moet gelden:
3d + 4v = 16.
Dit heeft als enige mogelijke oplossingen:
(d, v) = (4, 1) of (0, 4)
Als er 4 rijtjes van 4 verdwijnen, zijn er voor elk rijtje 4 mogelijke kleuren.
Vanaf hier moet je definieren wat "verschillende mogelijkheden" zijn. Bijvoorbeeld gegeven een set rijtjes met lengte 4, bijv. 3 rode rijtjes en 1 groene. Telt het bord om een symmetrie-as draaien als extra mogelijkheid?

[Herbie]

Ik heb ook al een programmaatje gemaakt waarin 16 stenen met 4 verschillende kleuren random geplaatst liggen.
Wanneer met de muis op een steen geklikt wordt, verandert deze van kleur.
Direct na de kleurverandering controleert het programma of er ergens minimaal 3 van dezelfde kleur op een rij staan (horizontaal, verticaal en diagonaal). Als dat het geval is, verdwijnen deze stenen.
Er wordt door het programma ook gecontroleerd of er, na het verdwijnen van bepaalde stenen, stenen zijn die geen groep van minimaal 3 meer kunnen vormen. Alleen wordt het in het programma niet echt wiskundig aangepakt maar met een soort trial and error. Niet erg efficiënt.
Ik heb ook het vermoeden dat er situaties kunnen voorkomen waarbij het programma denkt dat er nog mogelijkheden zijn terwijl dat niet meer zo is (1 steen verantwoordelijk voor 2 verschillende groepen van 3 bijvoorbeeld).

Ik vraag me af of het mogelijk is om alle mogelijkheden in een database te hebben en dat het programma dan na elke zet kijkt of het veld nog overeen komt met een oplossing uit de database. Maar als er zeer veel mogelijke oplossingen zijn, wordt dat haast ondoenlijk.

Nog mooier zou zijn als er een formule op te stellen is waar je 16 stenen met een bepaalde kleur kunt invullen. Maar hoe zet je in de formule op welke plek een steen op het bord staat?

Als ik er een beetje over nadenk lijkt het me haast onmogelijk om het anders te doen dan trial and error.

[David]

Waar heb je je programma in gemaakt?
Je zou in je programma voordat je een rijtje stenen weghaalt eerst kijken of een van de stenen meer dan een rijtje vormt. Zo ja, eerst een ander rijtje zoeken. Let wel op wat je zou moeten doen als alle steentjes dezelfde kleur hebben. Dan kunnen alle stenen in meerderen rijen.

Je zou een matrixnotatie kunnen gebruiken, bijv. met i = 1,2,3,4 en j=1,2,3,4. Zo heb je 16 velden. Elk veld kan de waarde 1,2,3 of 4 krijgen. Introduceer eventueel een vijfde "kleur" voor een steen is weggehaald.

Ik had een opzet gegeven voor het rekenen. Snap je dat zover?

[Herbie]

Ik heb dat programma gemaakt in een soort javascript dat lijkt op Csharp.
Gisteravond heb ik nog een bug uit mijn programma gehaald en moet zeggen dat het tot nu toe foutloos werkt.
Volgens mij is het alleen niet echt mooi en efficiënt geprogrammeerd en daarom wil ik het nog steeds wel wat meer wiskundig aanpakken. Ook omdat ik het dan denk ik makkelijker kan schalen. Dus van 4 x 4 naar 8 x 8 bijvoorbeeld.

Ik doe inderdaad vergelijkbare dingen die je noemt. Als een steen in meerdere rijtjes zit, worden beide rijtjes weg gehaald. Ik maak ook al gebruik van een "vijfde" kleur.

De opzet begrijp ik zover.

[David]

Ik ken Javascript niet maar misschien is het te lezen.

Als een steen in meerdere rijtjes zit, worden beide rijtjes weg gehaald.

Dit had ik niet verwacht maar goed om te weten.

De opzet begrijp ik zover.

Mooi. Er ligt nog een aantal keuzes open. Kan je je keuzes geven?

[Herbie]

Ik begrijp denk ik nog niet goed welke keuzes ik dan heb.
De situatie (kleuren patroon) die je hebt bij een bepaalde stand van het bord (zeg 0 graden), kun je ook hebben op 90 graden gedraaid of 180 graden gedraaid.
Het bord wordt niet "fysiek" gedraaid maar de kleuren van alle stenen kunnen zo veranderen zodat het lijkt alsof het gedraaid is.

Hier heb je nog een situatie waarvan mijn programma zegt dat het nog kan terwijl dat niet zo is (grijs = weggespeeld).
http://tinypic.com/view.php?pic=2zf1hd1&s=5
De groene steen kan maar op 1 manier weggespeeld worden. Als je dat dan doet, kan oranje niet meer weggespeeld worden.

(trouwens bedankt voor het reageren)

[Sjoerd Job]

Ik zou zeggen: laat de code zien. Ik vermoed dat er naast mij nog wel enkele andere mensen zitten met een minime kennis van programmeren, en de meeste hebben vast wel verstand van algoritmes.

[David]

Als meerdere rijtjes (van dezelfde kleur en minstens 3 lang) helemaal worden verwijderd als ze gemeenschappelijke stenen hebben, kan je bijv. voor elke steen kijken of die in zo'n rijtje ligt. Zo ja, kunnen alle stenen worden verwijderd. Anders blijven er steentjes over.

Op het plaatje zijn al stenen verwijderd. Zouden er volgens jou vanaf zoals het plaatje nu is nog stenen verwijderd kunnen worden?

[Herbie]

Het werkt inderdaad al zo dat rijen met een gemeenschappelijke steen allemaal worden verwijderd.

Als in het plaatje de oranje steen rood zou worden gemaakt, verdwijnt de rode diagonaal. Daarna kan er niks meer gedaan worden. Ook zou je de bovenste blauwe steen rood kunnen maken zodat de bovenste rij verdwijnt. En je zou de tweede rij horizontale stenen kunnen laten verdwijnen door ze dezelfde kleur te geven. En je kun ook nog de twee blauwe stenen en de oranje steen rood maken zodat de hele hoek rechtsboven verdwijnt (5 stenen).
Maar er zullen altijd 1 of meer stenen overblijven dus je kunt nu al zien dat het niet meer leeg te spelen is.
Vanaf hier weet ik nog niet hoe ik dat moet detecteren.
Zo zullen er zog wel meer situaties zijn en om nu zeker te zijn dat elke situatie "gedekt" wordt, wil ik het graag wiskundig aanpakken. Maar dat vind ik erg lastig.

Het heeft nu niet zo veel zin om de code te laten zien omdat dat alleen maar heel veel controles zijn in de vorm van if "dit" then "dat".