[java] schuifpuzzel

[Verwijderd]

dag allemaal,

ik heb een paar weken geleden al iets gezegd over mijn project op school om een schuifpuzzel te maken. Ik had hulp gevraagd, maar dat mocht blijkbaar niet. Nu heb ik al een wat code geschreven om alle blokjes te scrambelen.

Java:

public void Shuffle()
{
String temp;
int r1,r2;
for (int i=1;i<1000;i++) // 2 blokjes worden 1000 keer van plaats gewisseld
{
r1=(int)Math.round(Math.random()*15);
r2=(int)Math.round(Math.random()*15);
// Moeten aan elkaar grenzen
// en één van beide moet het onzichtbaar blokje zijn

if (GrenstAan(r1,r2)&&(r1==OnzichtbaarBlokje || r2==OnzichtbaarBlokje)) // het 16e blokje is onzichtbaar zodat men de zwarte achtergrond ziet.
{

temp=Knop[r1].getLabel();
Knop[r1].setLabel(Knop[r2].getLabel()); //getLabel() zorgt voor de waarde die op het blokje staat.

Knop[r2].setLabel(temp);
}

Nu is dit werkt niet zo goed, want ik denk dat die random functie 2 keer dezelfde waarde kan geven. Wat dus niet mag. Weet iemand hoe dit wel zou gaan?

Hopelijk een reply

[ Voor 4% gewijzigd door Verwijderd op 02-05-2003 15:33 ]

[.oisyn]

Doe je code eens tussen [norml]

Java:

...

[/] tags

Verder kun je niet zomaar 2 blokjes van plaats verwisselen, aangezien de puzzel dan onoplosbaar wordt. Dat kan weer natuurlijk weer opgelost worden door 2 andere blokjes te verwisselen, maar ik weet niet of dat altijd het geval is, en je doet het sowieso een oneven aantal verwisselingen, wat dus altijd zorgt voor een onoplosbare puzzel

[ Voor 74% gewijzigd door .oisyn op 02-05-2003 15:37 ]

[Verwijderd]

ok

[Verwijderd]

ik heb die math.round gevonden op het net. Maar wat doet die functie eigenlijk?

[crisp]

Is laatst nog een leuk topic over geweest in W&G: Uniek random getal

Bedenk ook dat als je lukraak gaat shuffelen, je wel eens een onoplosbare puzzel kan krijgen. Daar is een (simpele) oplossing voor, die ook ergens in W&G te vinden moet zijn

[Alarmnummer]

check de docs zou ik zo zeggen

[Soultaker]

Misschien moet je het eens anders bekijken. Je wilt blijkbaar de puzzel scramblen door een aantal willekeurige zetten te doen en nu wil je eerst weten hoe je zo'n willekeurige zet genereert.

In feite komt dit neer op het vinden van alle mogelijke zetten in een situatie en er daar één uitpakken. Het is dan handig om eerst te bedenken welke zetten er eigenlijk allemaal mogelijk zijn. Een zet bestaat uit het verschuiven van een blokje naar het lege vakje. Anders gezegd: het lege vakje wordt gevuld met één van zijn buren! In een zekere stelling zijn er dus maximaal vier zetten nodig. Het aantal mogelijke zetten is gelijk aan het aantal buren van het lege vakje. Ligt het lege vakje in het midden dan zijn dit er dus 4, aan de rand 3, en in een hoekje 2.

Je hoeft dus alleen maar vast te stellen om welke situatie het geldt, de buren te nummeren (in het algemene geval met 4 buren dus bijvoorbeeld: boven is 1, rechts is 2, onder is 3, links is 4) en vervolgens een willekeurig getal te kiezen (tussen 1 en 4, inclusief, in hetzelfde voorbeeld). Vervolgens schuif je de buur met dat nummer in het lege vakje.

Dit kun je een aantal keer herhalen en dan heb je waarshijnlijk wel een aardig door elkaar gehusseld veld. Overigens zijn er ook andere, meer wiskundig verantwoorde, manieren om een beginsituatie te verkrijgen. Je kunt bijvoorbeeld alle stukjes op een willekeurige plaats neerzetten en dan testen of de situatie oplosbaar is (als ik me niet vergis kan dit zonder de puzzel daadwerkelijk op te lossen, wat erg ingewikkeld is). Het zou helemaal mooi zijn als je een willekeurige beginsituatie zou constructueren die direct oplosbaar is, maar of dat mogelijk is en hoe dat dan zou moeten, zou ik niet zo 1-2-3 weten.

[Soultaker]

crisp schreef op 02 May 2003 @ 15:36:
Bedenk ook dat als je lukraak gaat shuffelen, je wel eens een onoplosbare puzzel kan krijgen. Daar is een (simpele) oplossing voor, die ook ergens in W&G te vinden moet zijn

Nee: hij wisselt alleen twee vakjes om als ze naast elkaar liggen en één ervan het lege vakje is. Aangezien dit precies een geldige zet is, is het resulterende speelveld gegarandeerd oplosbaar (aangezien je altijd alle zetten in omgekeerde volgorde kunt uitvoeren).

[crisp]

Soultaker schreef op 02 May 2003 @ 15:40:
...een heel verhaal...

Ik zal het maar verklappen
Om een schuifpuzzel te shuffelen dusdanig dat 'ie wel oplosbaar blijft moet je een x aantal keer 2 blokjes met elkaar verwisselen. In het topic wat ik eerder gaf zit een algoritme wat werkt op basis van verwisseling en ook redelijk random resultaten oplevert

Soultaker schreef op 02 May 2003 @ 15:41:
[...]

Nee: hij wisselt alleen twee vakjes om als ze naast elkaar liggen en één ervan het lege vakje is. Aangezien dit precies een geldige zet is, is het resulterende speelveld gegarandeerd oplosbaar (aangezien je altijd alle zetten in omgekeerde volgorde kunt uitvoeren).

Een echte shuffle als in array_shuffle() werkt niet op basis van zetten doen hoor

[ Voor 37% gewijzigd door crisp op 02-05-2003 15:47 ]

[kvdveer]

Een oplosbare shuffle werkt op een van de volgende manieren:
1. Je verwisselt een even aantal maal twee blokjes.
2. Je 'roteert' een oneven aantal blokjes. dwz: je schuift ze allemaal een door.
3. Je verwisselt een blokje met het lege vakje.

[Verwijderd]

misschien een hele domme oplossing voor het onoplosbare puzzel probleem:

begin met je puzzel in de opgeloste stand (dan heb je dus ergens een leeg vakje),
vervolgens een aantal keer schuiven (net als oplossen, maar dan andersom).

heb je nooit een onoplosbare puzzel.

random getal niet zelfde:
array bijhouden waarin je alle getallen bijhoudt
bij elk random getal checken of ie in array voorkomt,
zoja: nieuw random getal.
etc etc.

maarre, dit is toch ook hulp?

[Alarmnummer]

backtracken dus

[kvdveer]

Verwijderd schreef op 02 May 2003 @ 16:05:
misschien een hele domme oplossing voor het onoplosbare puzzel probleem:

begin met je puzzel in de opgeloste stand (dan heb je dus ergens een leeg vakje),
vervolgens een aantal keer schuiven (net als oplossen, maar dan andersom).

Da's niet erg efficient (alsof dat uit maakt), en tevens minder leuk om te verzinnen...

[Soultaker]

kvdveer schreef op 02 May 2003 @ 15:57:
Een oplosbare shuffle werkt op een van de volgende manieren:
[..]
3. Je verwisselt een blokje met het lege vakje.

Nee, dat kan niet, tenzij je met "een blokje" een naburig blokje bedoelt. Anders kom je uit op de beroemde 15-16 puzzel van Loyd (?):

code:

+--+--+--+--+
| 1| 2| 3| 4|
+--+--+--+--+
| 5| 6| 7| 8|
+--+--+--+--+
| 9|10|11|12|
+--+--+--+--+
|14|16|15|  |
+--+--+--+--+

(Doel is de getallen op volgorde krijgen met het lege vakje rechtsonder). Deze puzzel is duidelijk te verkrijgen uit het wisselen van de 15 en 16 met het lege vakje, maar hij is toch echt onoplosbaar.

Het probleem zit 'm erin dat als je mogelijk configuraties van de puzzel als punten beschouwd, en de mogelijke "zetten" als verbindingen tussen die punten, je twee onverbonden graven krijgt (in als geheel een bipartiete graaf). Nu weet ik niet meer exact hoe het zat, maar ik geloof dat je door twee naast elkaar gelegen vakjes om te wisselen, altijd van de ene partitie naar de andere partitie gaat of weer terug.

Als je met een oplosbare puzzel begint, kun je 'm dus husselen én oplosbaar houden, door een even aantal keer twee naburige vakjes om te wisselen. De kans is groot dat dat ook geldt als de vakjes een oneven aantal stappen van elkaar liggen (maar dat ga ik niet bewijzen ).

crisp schreef op 02 May 2003 @ 15:45:
Een echte shuffle als in array_shuffle() werkt niet op basis van zetten doen hoor

Sinds wanneer bepalen de PHP ontwikkelaars hoe je in Java een spelletje mag programmeren?!

[ Voor 45% gewijzigd door Soultaker op 02-05-2003 17:47 ]

[Verwijderd]

Verwijderd schreef op 02 mei 2003 @ 15:30:

Java:

public void Shuffle()
{
String temp;
int r1,r2;
for (int i=1;i<1000;i++) // 2 blokjes worden 1000 keer van plaats gewisseld
{
r1=(int)Math.round(Math.random()*15);
r2=(int)Math.round(Math.random()*15);
// Moeten aan elkaar grenzen
// en één van beide moet het onzichtbaar blokje zijn

if (GrenstAan(r1,r2)&&(r1==OnzichtbaarBlokje || r2==OnzichtbaarBlokje)) // het 16e blokje is onzichtbaar zodat men de zwarte achtergrond ziet.
{

temp=Knop[r1].getLabel();
Knop[r1].setLabel(Knop[r2].getLabel()); //getLabel() zorgt voor de waarde die op het blokje staat.

Knop[r2].setLabel(temp);
}

Nu is dit werkt niet zo goed, want ik denk dat die random functie 2 keer dezelfde waarde kan geven. Wat dus niet mag. Weet iemand hoe dit wel zou gaan?

Hopelijk een reply

ligt het aan mij? Ik dacht dat JAVA object georiënteerd was?
Blokje extends JButton??
blokje.grenstAan(Blokje buurman) ??
int r1,r2 => Blokje r1,r2??
r1.visible??
..
????
Dit komt me toch niet echt Object Georiënteerd over.
('k moet wel toegeven dat ikzelf ook niet zo'n grote OO kennis heb )

[crisp]

Soultaker schreef op 02 May 2003 @ 17:40:
[...]
Als je met een oplosbare puzzel begint, kun je 'm dus husselen én oplosbaar houden, door een even aantal keer twee naburige vakjes om te wisselen. De kans is groot dat dat ook geldt als de vakjes een oneven aantal stappen van elkaar liggen (maar dat ga ik niet bewijzen ).

het hoeven geen naburige vakjes te zijn, en ook hoever ze van elkaar liggen maakt niet uit, zolang je maar een even aantal keer 2 vakjes verwisseld (en ik ga het ook niet bewijzen )

[...]

Sinds wanneer bepalen de PHP ontwikkelaars hoe je in Java een spelletje mag programmeren?!

* crisp is geen PHP ontwikkelaar per se, irl ben ik nl RPG-programmeur. Was gewoon het eerste wat me te binnen schoot

[hobbit_be]

ik doe toch ook een 'back track' hoor wat zijn nou een hondertal zets? een paar ms?

Doet me denken aan een opdracht van een vriend van me die Informatica deed. Ze moesten een algo voor vier op een rij. Ik dacht dat ie steeds won door: gewoon heel snel heel veel mogelijke spelletjes te spelen. Er bestaat wel een 'optimum' strategy (16 pagina dissertation) waaruit blijkt dat als je begint je eigenlijk nooit kunt verliezen (maar wel gelijk spel) ...

[kvdveer]

Soultaker schreef op 02 May 2003 @ 17:40:
[...]

Nee, dat kan niet, tenzij je met "een blokje" een naburig blokje bedoelt.

Dat bedoel ik inderdaad.
methode 2 is trouwens af te leiden uit methode 1:

code:

rotR(6,7,8) ==  xng(7,8) , xng(6,7)        
                                           
 1  2  3  4      1  2  3  4      1  2  3  4
       ____         ____                   
 5  6  7  8      5  6  8  7      5  8  6  7
             =>              =>            
 9 10 11 12      9 10 11 12      9 10 11 12
                                           
13 14 15        13 14 15        13 14 15

[Soultaker]

crisp schreef op 02 May 2003 @ 17:54:
het hoeven geen naburige vakjes te zijn, en ook hoever ze van elkaar liggen maakt niet uit, zolang je maar een even aantal keer 2 vakjes verwisseld (en ik ga het ook niet bewijzen )

Hmz, je lijkt zowaar gelijk te hebben. Ik ga er nog even over nadenken, though.

[crisp]

Soultaker schreef op 02 May 2003 @ 18:56:
[...]

Hmz, je lijkt zowaar gelijk te hebben. Ik ga er nog even over nadenken, though.

Ik heb ongeveer een jaar geleden zo'n schuifpuzzel gemaakt in javascript (ik zal de link maar niet posten, zou een spoiler zijn ) en heb toen van dat principe gebruik gemaakt. Ik heb 'm nog nooit niet uit kunnen spelen

[kenneth]

Verwijderd schreef op 02 mei 2003 @ 17:48:
[...]
ligt het aan mij? Ik dacht dat JAVA object georiënteerd was?

Kan je jezelf even toelichten? Ik zie het probleem namelijk niet echt.

[Verwijderd]

het is mij gelukt, bedankt daarvoor

[Verwijderd]

Ik ben nu bezig aan een functie om te controleren of een bepaald blokje grenst aan het onzichtbaar blokje. Nu ben ik aan het zoeken gegaan of er een mogelijk is om de coördinaten te krijgen van een blokje in de GridLayout, maar ik vind er niks van. Dus zou het antwoord kunnen liggen in het gebruik van de gescrambelde array. En zo de array telkens aanpassen wanneer de layout verandert?