Results 1 to 6 of 6

Thread: hoe afstand berekenen in hidato puzzle

  1. #1

    hoe afstand berekenen in hidato puzzle

    Ik ben begonnen aan een Hidato programmaatje.

    De regels van hidato zijn simpel:
    Je moet de getallen 1 t/m 81 invullen in een grid van 9 bij 9.
    Opeenvolgende getallen moeten in schuin of recht aangenzende cellen komen.
    De voorgegeven getallen laten slechts een unieke oplossing toe, die moet worden gevonden.

    Nu zit ik even met de afstandsbepaling tussen twee cellen.

    In onderstaand voorbeeld is de afstand tussen A en B 2:
    Code:
    .  .  .  .  .  .  .  .  .
    C  .  D  .  18 .  .  .  .
    .  .  .  .  17 .  .  .  .
    .  .  .  .  16 .  .  .  .
    .  .  .  A  .  B  .  .  .
    .  .  .  .  14 .  .  .  .
    .  .  .  .  13 .  .  .  .
    .  .  .  .  12 .  10 .  .
    .  .  .  .  .  11 .  .  .
    Stel dat 15 op de open plek wordt ingevuld, dan moet de afstand tussen A en B weer herberekend worden
    en dan zou er 8 uit moeten komen:
    Code:
    .  .  .  .  .  .  .  .  .
    C  .  D  .  18 .  .  .  .
    .  .  .  .  17 .  .  .  .
    .  .  .  .  16 .  .  .  .
    .  .  .  A  15 B  .  .  .
    .  .  .  .  14 .  .  .  .
    .  .  .  .  13 .  .  .  .
    .  .  .  .  12 .  10 .  .
    .  .  .  .  .  11 .  .  .
    Nu heb ik de afstandsbepaling op zich ook al weer geschreven en dat werkt wel.
    (Komt er kortweg op neer dat ik vanuit elke cel cirkels naar buiten trek die met een steeds oplopende afstand
    worden gevuld - en daarbij wordt dan rekening gehouden met de obstakels.)

    Maar waar ik mee zit:
    Nu moet ik na het invullen van een enkel getal de afstanden over de hele grid herberekenen.
    Terwijl in bovenstaand voorbeeld duidelijk is dat de afstand tussen C en D niet wijzigt en dus ook niet opnieuw berekend hoeft te worden.

    Kan ik hier een optimalisatie bereiken?
    Het is me i.h.a. niet duidelijk of je afstanden aan kunt wijzen die niet meer herberekend hoeven te worden.

  2. #2
    Ik ken Hidato verder niet, maar ik zou je wel de tip willen geven dat het waarschijnlijk slimmer is om het eerst werkend te maken, en daarna pas die optimalisatie te gaan bepalen. Bij puzzeltjes als deze komt nogal wat denkwerk kijken, en het is fijn om een redelijk eenvoudig stuk code te kunnen testen en te concluderen dat het werkt. Als je dan gaat optimaliseren en het werkt niet meer, dan heb je een fout gemaakt bij het optimaliseren.
    Op die manier in stappen werken werkt een stuk bevredigender, omdat je heel gericht problemen kunt constateren en er oplossingen voor te bedenken, terwijl je je anders bij een probleem zit af te vragen in welke hoek je het überhaupt moet zoeken.
    1+1=b

  3. #3
    Delphi & OO in Vlaanderen SamWitse's Avatar
    Join Date
    Sep 2007
    Location
    Brussel
    Posts
    833
    Als je de afstanden tussen verschillende posities bijhoudt, kun je dan ook niet telkens de reeks van plaatsen bijhouden waarlangs deze afstand berekend is?
    Vb. De afstand van C naar D is 2, en is berekend met tussenpositie (B,2).
    Zolang (B,2) niet opgevuld wordt, verandert de afstand tussen C en D niet.
    De afstand van A naar B verliep over cel (E,5) en die is opgevuld, dus meot de afstand tussen A en B herberekend worden.
    (In de voorbeelden geef ik c?Âordinaten aan de cellen: elke kolom een letter, elke rij een cijfer.

    Vraagje: hou je de afstanden bij tussen *elk* paar cellen? Dat zijn er 81 x 81 = ... euh veel!
    Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

    Sam Witse.
    Delphi & OO in Vlaanderen

  4. #4
    Dat biedt in elk geval weer stof tot nadenken.

    Mijn huidige werkwijze is: vanuit elke cel een olievlek laten uitstromen, en daarbij houd ik geen routes bij. Elke volgende linie krijgt afstand = vorige afstand + 1.

    De afstand tussen C en D is misschien niet gewijzigd, maar wel die tussen bijvoorbeeld C en B.
    Dus ik vrees dat ik de olievlek vanuit C hoe dan ook overnieuw zal moeten doen.

    Tenzij er nog een geheel alternatief algoritme bestaat voor die afstanden.

    Ik heb wel het volgende bedacht:
    De afstand van A tot B is gelijk aan de afstand van B tot A.

    Dus als ik de cellen behandel op volgorde van co?Ârdinaten, dan hoef ik de olievlek alleen uit te laten stromen naar hogere co?Ârdinaten. Dat scheelt 50% performance.

  5. #5
    Ik heb mijn hidato programmaatje nu in concept afgerond.

    Een puzzle die ik hier heb gevonden lost hij op:
    Code:
    00;09;10;00;00;00;00;23;00
    00;00;00;00;28;27;26;00;00
    04;00;00;00;00;30;00;32;00
    00;00;15;17;38;00;36;00;00
    00;00;00;00;00;41;00;00;48
    00;00;61;01;00;43;44;00;00
    00;00;55;66;00;00;00;00;00
    63;00;00;00;53;68;51;00;00
    81;80;00;00;00;00;00;00;00
    En hij kan zelf nieuwe puzzles maken.

    Het random geheel vullen van een lege grid duurt helaas uren, dus ik zal nog wel optimalisaties moeten gaan zoeken.

    Attached Files Attached Files

  6. #6
    Quote Originally Posted by evert
    Het random geheel vullen van een lege grid duurt helaas uren,
    Hier heb ik het hele weekend aan gespendeerd, en het is opgelost.

    Vorige werkwijze:
    Kies random een lege cel en plaats daarin random een cijfer wat daar nog mag.

    Nieuwe werkwijze:
    Cijfers in oplopende volgorde plaatsen - dus kies het kleinste nog niet geplaatste cijfer en plaats
    die random in een cel waar dat cijfer nog mag.

    Sinds dat erin zit duurt het minder dan een halve minuut in plaats van uren.
    Dit intrigeert me wel: proefondervindelijk weet ik nu dat dit sneller is maar hoe had ik het op voorhand kunnen bedenken??

    Een tweede optimalisatie heeft de halve minuut nog teruggebracht tot enkele seconden.
    Die komt erop neer dat ik bij het bereiken van een dood pad niet meteen helemaal terugga naar de
    lege grid - maar slechts een paar cijfers weggooi en de meeste gewoon laat staan.
    Attached Files Attached Files
    Last edited by evert; 17-Dec-08 at 02:16.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •