Algoritme gesloten figuur

[jverdeyen]

Hoi,

(Ik ga er meteen bij vertellen dat dit een opdracht is voor school. Ik verwacht dan ook geen oplossing, maar ik ben op zoek naar een denkrichting voor mijn probleem.)

De bedoeling is om een algortime te schrijven dat volgende kan uitvoeren.

We krijgen volgend invoer bestand :



Hierbij staan de eerste 2 lijnen voor het grootte van een rooster, de getallen vullen het rooster in.
Dit kan ook weergegeven worden op volgende manier:



Hier zijn de getallen weergegeven als puntjes. De bedoeling is dat elk puntje/getal voor een zijde staat, door deze zijden in te vullen moet er door het algoritme een gesloten figuur gemaakt worden.

Hieronder een voorbeeldje:



Nu is mijn vraag hoe ik dit best aanpak ? In welke richting moet ik denken ?
Ik heb al veel gezocht, geprobeerd alle restricties op te schrijven, maar ik kom er maar niet uit.

Een duwtje in de rug zou handig zijn ...

Alvast bedankt,

Cheers,

[djluc]

Mag het brute force? Of moet het echt een slimme oplossing zijn?

[jverdeyen]

Ik moet de manier waarop het gebeurd kunnen toelichten, ... ik denk dat brute-force misschien te 'makkelijk' is. (ook qua performantie moeten we iets kunnen verantwoorden)

[RobIII]

jverdeyen schreef op dinsdag 06 november 2007 @ 23:07:
Ik moet de manier waarop het gebeurd kunnen toelichten, ... ik denk dat brute-force misschien te 'makkelijk' is. (ook qua performantie moeten we iets kunnen verantwoorden)

Dan is de opdracht waarschijnlijk ook duidelijker geformuleerd dan "maak iets dat deze puzzel oplost". Er wordt vast verwezen naar een techniek die je moet/kunt gebruiken en anders gaat het over het hoofdstuk (ofzo) dat je afgelopen tijd behandeld hebt. Als je afgelopen 2 weken bent bezig geweest met genetische algoritmes dan zal dat dus wel de bedoeling zijn. Ben je ergens anders mee bezig geweest in de lesstof...guess what?...

jverdeyen schreef op dinsdag 06 november 2007 @ 23:04:
Nu is mijn vraag hoe ik dit best aanpak ? In welke richting moet ik denken ?
Ik heb al veel gezocht, geprobeerd alle restricties op te schrijven, maar ik kom er maar niet uit.

Toch ben ik wel eens benieuwd naar wat je tot nu toe dan hebt, en wat je dan al gezocht/gevonden hebt. En waar je dan concreet niet uit komt. Want nu dump je gewoon je opdracht bij ons en mogen wij het voor je uitdenken zodat jij alleen nog maar de code hoeft te schrijven.

[ Voor 42% gewijzigd door RobIII op 06-11-2007 23:12 ]

[.oisyn]

jverdeyen schreef op dinsdag 06 november 2007 @ 23:04:
geprobeerd alle restricties op te schrijven

Wat heb je al?

[Depress]

Wanneer je brute force gaat oplossen, dan moet je eens kijken naar het zoeken in boomstructuren.

Overigens lijkt het me dat bruteforce voor zoiets de enige oplossing is. Je kan het algoritme wel slimmer maken door in te spelen op restricties die je van te voren al kunt voorspellen.

[jverdeyen]

De mogelijkheden die er kunnen zijn bij elk cijfer,
deze kunnen er dan in geplaatst worden,
maar dan moet het algoritme verder kijken naar de volgende,
maar die volgende is natuurlijk ook weer afhankelijk van diegene dat daarop volgt.

Ik had al gedacht om bij elk cijfer de mogelijke oplossing te zetten,
maar ik vind gewoon geen systeem om te checken of de figuur gesloten is.

Probeer voortaan het forum zélf de tekstomloop te laten regelen. Dit leest heel irritant

[ Voor 12% gewijzigd door een moderator op 06-11-2007 23:28 ]

[Nic]

Klinkt als iets dat ik recursief zou proberen op te lossen.
In het kort:

1 - begin ergens op een punt
2 - is het al klaar? ja: stop, nee: ga naar 3
3 - kun je vanaf het huidige punt een streepje zetten dat voldoet aan de regels en dat je nog niet hebt geprobeerd?
4 - zo ja, zet het streepje en ga naar 2
5 - zo nee, haal het vorige streepje weg en ga naar 2

maar ik vind gewoon geen systeem om te checken of de figuur gesloten is.

Als je bij het zetten van het streepje in stap 3 terug kunt komen op het beginpunt dan is je figuur gesloten.

[ Voor 22% gewijzigd door Nic op 06-11-2007 23:31 ]

[djluc]

Checken of een figuur gesloten is is enorm simpel: Als je alles als lijntje ziet (x,y), dus een lijn (0.0 - 1.0) bijvoorbeeld, dan weet je wat er nog meer moet zijn. Er moet een andere lijn zijn op punt 1.0 die naar 1.2 of naar 1.1 gaan. Dat kan je zo per punt bepalen.

[XiN-eViL]

dsltv schreef op dinsdag 06 november 2007 @ 23:27:
Klinkt als iets dat ik recursief zou proberen op te lossen.
In het kort:

1 - begin ergens op een punt
2 - is het al klaar? ja: stop, nee: ga naar 3
3 - kun je vanaf het huidige punt een streepje zetten dat voldoet aan de regels en dat je nog niet hebt geprobeerd?
4 - zo ja, zet het streepje en ga naar 2
5 - zo nee, haal het vorige streepje weg en ga naar 2


[...]


Als je bij het zetten van het streepje in stap 3 terug kunt komen op het beginpunt dan is je figuur gesloten.

Zover ik geleerd heb is dit btw ook bruteforce, je tekent namelijk een lijntje, en dan ga je alle mogelijkheden vanaf daar proberen totdat je er één hebt.
Ik heb ooit een vak gehad op de uni over dit soort problemen, en er waren een paar aanpakken:

• Greedy: kun je meteen het volgende lijntje kiezen? Dat kan hier niet, valt af
• Dynamisch: heb je er iets aan als je een gesloten figuur voor een deelvak hebt (dus 5x5 ofzo)? Zover ik weet niet, dus heb je ook niks aan
• Bruteforce: als de rest niet kan, hier heb ik zelfs een quasi-standaard-algoritme voor gehad waar je alleen implementatie-stuk moest invullen

Ik zou voor bruteforce gaan dus, en dan wat dsltv zegt, zoek gewoon het vakje meest linksboven waar je een lijntje mag zetten, zet er op een kant één, en ga maar verder proberen. Loop je vast, ga dan vanaf het laatste keuze-moment een andere kant op en kijk of dat wel lukt.

[NMe]

Aangezien je niet op zoek bent naar code maar een algemene denkrichting/algoritme om je probleem op te lossen zet ik je topic in een subforum neer waar het meer tot zijn recht komt.

PRG>>SEA

Zie ook Waar hoort mijn topic?

[Enfer]

Zoals altijd is het meestal wat makkelijker om het probleem iets kleiner aan te pakken.. Neem eens een vierkant van 3x3 en kijk of je daar een algoritme van kan maken.
Heel vaak werkt dat algoritme van 3x3 ook wel bij 10x10

[Voutloos]

Tja, zal ik dan maar wat eenvoudige restricties inkoppen?
Indien 0, markeer dan alle edges als leeg.
Indien X en maar X edges welke niet per se leeg moeten zijn, markeer als gebruikt.
Indien edge alleen maar als leeg gemarkeerde edges aan een bepaalde kant heeft, markeer als leeg.

Dit zijn allemaal inkoppertjes die je toch wel mag bedenken als je het puzzeltje ook maar 1x gedaan hebt.

Verder doe je ook je best om bepaalde regels niet te noemen, want dit puzzeltje kennende is er ook een regel dat de lijn zichzelf niet kruist of aanraakt.

XiN-eViL schreef op dinsdag 06 november 2007 @ 23:48:
Ik heb ooit een vak gehad op de uni over dit soort problemen, en er waren een paar aanpakken

De regeltjes zoals ik die hierboven heb genoemd vallen in de categorie elimineren. Of noem jij dat het greedy als niet mogelijk markeren?

Overigens is eenvoudigweg brute-force, met misschien enkel de eerste eliminatie regel als optimalisatie, wellicht de eenvoudigste aanpak. Ik heb dus al ooit na zo'n puzzeltje gedaan te hebben het plan gehad om een niet brute-force scriptje te schrijven (brute-forcen zie ik hier niet als uitdaging), maar ik heb me nog niet een avondje doodverveeld.

[jvdmeer]

Volgens mij moet je het over een andere boeg gooien.
Vergeet het gesloten figuur!

Probeer het op te lossen zoals Minesweeper.

[.oisyn]

Dat werkt niet, want allemaal losse lijnstukken is volgens de "minesweeper-methode" een juiste oplossing, wat natuurlijk niet klopt.

De methode van dsltv lijkt me het meest practisch, vooral omdat het duidelijk is wanneer je niet meer verder kan en je dan makkelijker kunt backtracken.

[XiN-eViL]

Voutloos schreef op woensdag 07 november 2007 @ 08:19:
Tja, zal ik dan maar wat eenvoudige restricties inkoppen?
Indien 0, markeer dan alle edges als leeg.
Indien X en maar X edges welke niet per se leeg moeten zijn, markeer als gebruikt.
Indien edge alleen maar als leeg gemarkeerde edges aan een bepaalde kant heeft, markeer als leeg.

Dit zijn allemaal inkoppertjes die je toch wel mag bedenken als je het puzzeltje ook maar 1x gedaan hebt.

Verder doe je ook je best om bepaalde regels niet te noemen, want dit puzzeltje kennende is er ook een regel dat de lijn zichzelf niet kruist of aanraakt.

[...]
De regeltjes zoals ik die hierboven heb genoemd vallen in de categorie elimineren. Of noem jij dat het greedy als niet mogelijk markeren?

Overigens is eenvoudigweg brute-force, met misschien enkel de eerste eliminatie regel als optimalisatie, wellicht de eenvoudigste aanpak. Ik heb dus al ooit na zo'n puzzeltje gedaan te hebben het plan gehad om een niet brute-force scriptje te schrijven (brute-forcen zie ik hier niet als uitdaging), maar ik heb me nog niet een avondje doodverveeld.

Greedy is echt meteen de goede keuze maken in ALLE gevallen, dat is hier niet.
Wat jij zegt is bruteforce met pruning (dingen die geen zin hebben overslaan). Daar wordt t ook een stuk sneller op

[Voutloos]

Als je maar genoeg van dat soort regels implementeert hoeft je geen edges te gokken (bruteforcen), behalve dan voor moeilijke (lees: slechte) puzzels

[WVL_KsZeN]

Check voor gesloten figuur is natuurlijk simpel.

Je moet

a) geen los einde hebben, dus niet ___
b) geen splitsingen, zoals een y splitsing _|_
c) verder moet het aantal streepjes natuurlijk kloppen met het getalletje

OEF! wacht... mag er eigenlijk maar 1 gesloten figuur zijn? Als het er maar 1 mag zijn moet je misschien een extra check inbouwen. Een soort van globale check. Dus iets van :

kies een vakje met een lijnstukje - kan ik van uit deze lijn alle andere lijnstukjes bereiken door de lijn te volgen? - ja -> dan is er dus maar figuur.

[ Voor 42% gewijzigd door WVL_KsZeN op 07-11-2007 12:48 ]

[RobIII]

WVL_KsZeN schreef op woensdag 07 november 2007 @ 12:42:
b) geen splitsingen, zoals een y splitsing _|_

code:

________________
|    |         |
|    |    |    |
|    |    |    |
|    |    |    |
|         |    |
----------------

[Verwijderd]

dsltv schreef op dinsdag 06 november 2007 @ 23:27:
1 - begin ergens op een punt
......

-Ik zou juist ergens op een punt grenzend aan een 3 beginnen. Er kunnen punten zijn waar de lijn niet raakt, en daar kom je anders een heleboel CPU cycles later pas achter...


-van te voren kun je al zoveel mogelijk invullen: (dit leer je door zelf wat te puzzelen)
3en naast elkaar -> |3|3|
0 -> 4 x open
3 in hoek -> waar de 3 grenst aan rand lijnstuk
3en die elkaar diagonaal rajen

[.oisyn]

RobIII schreef op woensdag 07 november 2007 @ 12:49:
[...]

code:

________________
|    |         |
|    |    |    |
|    |    |    |
|    |    |    |
|         |    |
----------------

Dat is geen goede oplossing hoor. Het moet 1 polygoon waarbij de graad van elke vertex 2 is.

[ Voor 8% gewijzigd door .oisyn op 07-11-2007 13:01 ]

[WVL_KsZeN]

RobIII schreef op woensdag 07 november 2007 @ 12:49:
[...]

code:

________________
|    |         |
|    |    |    |
|    |    |    |
|    |    |    |
|         |    |
----------------

oef... TS : mag dit of niet?

[Voutloos]

Het is gewoon een standaard puzzeltje en TS doet zijn best om niet de complete regels te vertellen. En dit mag dus volgens de standaard regels niet.

[WVL_KsZeN]

Voutloos schreef op woensdag 07 november 2007 @ 13:04:
Het is gewoon een standaard puzzeltje en TS doet zijn best om niet de complete regels te vertellen. En dit mag dus volgens de standaard regels niet.

Dat zou mooi zijn, want dan is de gesloten check dus simpel

[RobIII]

Voutloos schreef op woensdag 07 november 2007 @ 13:04:
Het is gewoon een standaard puzzeltje en TS doet zijn best om niet de complete regels te vertellen. En dit mag dus volgens de standaard regels niet.

Daar is dus niets over gezegd in dit topic inderdaad. En dan mag 't volgens mij dus prima.

[jvdmeer]

.oisyn schreef op woensdag 07 november 2007 @ 11:36:
Dat werkt niet, want allemaal losse lijnstukken is volgens de "minesweeper-methode" een juiste oplossing, wat natuurlijk niet klopt.

De methode van dsltv lijkt me het meest practisch, vooral omdat het duidelijk is wanneer je niet meer verder kan en je dan makkelijker kunt backtracken.

Waarom niet? Begin bij de 0 aan de linkerkant:

 2   2

 2   2

 0   2

 2   3

Om de 0 mag niets staan:

 2   2

 2   2
....
 0 . 2
....
 2   3

De 2 boven en onder de 0 hebben nu nog maar 1 mogelijkheid:

  2   2
*****
  2 * 2
....*
  0 . 2
....*
  2 * 3
*****

De 2 daarboven heeft nu ook nog maar 1 mogelijkheid:

*....
* 2 . 2
*****
. 2 * 2
....*
. 0 . 2
....*
. 2 * 3
*****

En de 2 naast de 0 heeft ook maar een mogelijkheid en daarna de cijfers onder(3) en boven(2) die 2:

*...*****
* 2 . 2 *
*****...*
. 2 * 2 .
....*****
. 0 . 2 .
....*****
. 2 * 3 *
*****...*

En zo verder, compleet zonder brute-force.

/me Zie nu dat ik eigenlijk de zelfde methode omschrijf af dsltv

[ Voor 3% gewijzigd door jvdmeer op 07-11-2007 13:57 ]

[frickY]

Kijk eens naar algoritmes die Sudoku puzzels oplossen?

[Grijze Vos]

Verwijderd schreef op woensdag 07 november 2007 @ 12:51:
[...]

-van te voren kun je al zoveel mogelijk invullen: (dit leer je door zelf wat te puzzelen)
3en naast elkaar -> |3|3|

Tegenvoorbeeldje:

grid van 4x3:

code:

0 1 1 0 
 -----
1|3 3|1
 -----
0 1 1 0

@hieronder, idd.

[ Voor 3% gewijzigd door Grijze Vos op 07-11-2007 17:10 ]

[jvdmeer]

Grijze Vos schreef op woensdag 07 november 2007 @ 14:03:
[...]

Tegenvoorbeeldje:

grid van 4x3:

code:

0 0 0 0 
 -----
0|3 3|0
 -----

0 0 0 0

Moet denk ik zijn:

0 1 1 0 
 -----
1|3 3|1
 -----

0 1 1 0 

[.oisyn]

jvdmeer schreef op woensdag 07 november 2007 @ 13:40:

Waarom niet?

Omdat je dan met losse lijnstukken werkt, en je derhalve een mogelijke oplossing kan vinden die aan alle vakjes voldoet, maar uiteindelijk geen gesloten polygoon als resultaat hebt. Je geeft een goed voorbeeld die precies dat aantoont. Jouw algoritme heeft een oplossing gevonden, maar het is niet de juiste (want geen gesloten polygoon, en waarschijnlijk bestaat er in dit voorbeeld ook geen juiste)

frickY schreef op woensdag 07 november 2007 @ 13:49:
Kijk eens naar algoritmes die Sudoku puzzels oplossen?

Maw, kijk naar elk ander algoritme dat een bepaalde puzzel oplost door door een zoekboom te lopen.

[ Voor 45% gewijzigd door .oisyn op 07-11-2007 15:36 ]

[Grijze Vos]

.oisyn schreef op woensdag 07 november 2007 @ 15:32:
[...]

Maw, kijk naar elk ander algoritme dat een bepaalde puzzel oplost door door een zoekboom te lopen.

Inderdaad.

Tips voor de TS:
De hoekpunten in je figuur zijn de vertices van je graaf, de lijnen zijn je edges. De hokjes vormen de restricties op de cykel die je gaat bouwen in je graaf.

Begin gewoon je cykel op te bouwen, en als je ergens niet meer verder kan, kun je backtracken. Als je in je beginpunt uitkomt met tekenen, check dan even of alle hokjes genoeg lijnen aangrenzend hebben, anders moet je weer backtracken.

Oh, en begin in een punt dat grenst aan een hokje met getal 3, want bij die hokjes zijn alle vertices tenminste een deel van je uiteindelijke cykel.

[Verwijderd]

.oisyn schreef op woensdag 07 november 2007 @ 15:32:
Maw, kijk naar elk ander algoritme dat een bepaalde puzzel oplost door door een zoekboom te lopen.

Sudokus moet je heel anders oplossen, je programma moet gewoon de "menselijke" handelingen keer op keer uitvoeren, dan heb je in ieder geval een hele snelle oplossing voor de menselijke puzzels, er zullen er ook wel wat zijn waarbij je wat moet "uitproberen".

[EfBe]

<advocate type="devil">
Topicstarter: het lijkt wellicht dat je wat hebt aan wat hier in deze thread verteld wordt. Dit is niet zo. Het doel van een opleiding is dat je leert denken en leert rudimentaire informatie te bundelen tot nieuwe informatie. Je hebt een opdracht gekregen om een zeker puzzeltje op te lossen. De fout die je maakt is dat je denkt dat het DOEL van die opdracht is het inleveren van werkende code. Dit is niet het geval, de docent heeft die waarschijnlijk al jaren in de kast liggen. Het doel van die opdracht is dat JIJ (en niemand anders, anders leer JIJ er nl. geen hol van) leert hoe je zo'n probleem aanpakt, welke mogelijkheden zie je, wat heb je geleerd qua methodieken en wat krijg je wanneer je ze toepast op deze opdracht etc. etc. Het is niet erg dat je wellicht niet een werkende oplossing kunt tonen, je zit nl. nog op school. Waar het om gaat is dat je ZELF die opdrachten oplost.

Wat je nu doet is dat anderen het je voorkauwen, althans de weg vertellen tussen de problemen door. Wat overblijft is het vertalen van de oplossing in text naar een oplossing die werkt, en dat kan iedere boerel*l, het moeilijke is nl. al gedaan.

Je leert hierdoor NIET hoe je een probleem aanpakt, hoe je problemen overwint. Als je dit niet leert, wordt het ook niks later, want je strandt dan op het niveau waar veel 'software engineers' op stranden: nauwelijks in staat zelf oplossingen te verzinnen en chronisch via google proberen hun werk te doen. Het nare van die situatie is dat je niet verder komt wanneer je eenmaal gestrand bent, want je hebt nooit geleerd zelf te denken, zelf kennis om te zetten in wijsheid.

Software engineering is precies dat: problemen oplossen, door toepassen van wijsheid, gebaseerd op kennis. En problemen zijn soms erg lastig en soms weet niemand de oplossing en moet je dus op zoek naar hoe het aan te pakken. En juist DAARVOOR zit je op school, om te leren hoe dat te doen. Immers, hoe je een programmaatje maakt staat in de eerste de beste sams paperbacks: learn <language> in 21 days!.

Altijd leuk is bv spoj (http://www.spoj.pl). Een waslijst aan computer problemen waar je een oplossing voor kunt indienen en als deze capabel is en snel genoeg is dan krijg je een punt. Beste Nederlander is iemand die supergoed is in het opbreken van een probleem in kleine stukjes en daar dan de oplossing voor te vinden, proberen, kennis toepassen etc. De oplossingen zijn soms echt bizar als je er zo naar kijkt, maar het zijn wel DIE oplossingen die maken dat je het probleem oplost, de voor de hand liggende flutoplossingen zijn het steevast niet. Het zijn ultieme tests of je problemen kunt oplossen met je eigen werkwijze, precies wat deze opdracht ook toetst.

In 'het echte leven' is het precies eender: als software engineer weet je nooit wat je op je pad krijgt, en vaak zit je naar een probleem te kijken waar je je echt even achter de oren krabt hoe je het moet aanpakken. Denk je dat je dan even op een forum een vraag kunt stellen hoe je het op moet lossen? Tuurlijk, 'problemen' als 'hoe open ik een file' wellicht wel, maar dat zijn niet de problemen waar ik het over heb. Ik heb het over problemen waarbij je bv input kunt verwachten van elementen in oneindig verschillende volgordes en jij daar toch wijs uit moet zien te worden en beslissingen mee moet kunnen nemen.

Je moet je voorbereiden op een wereld waarbij JIJ degene bent die het antwoord dient te geven, niet degene die de vragen stelt. Echter, als je niet de basisbeginselen leert van het zoeken naar het antwoord, dan zul je niet de voorbereiding krijgen die je nodig hebt.

Denk hier niet te licht over, want ik schat dat het meerendeel van de 'software engineers' nu in het veld niet capabel genoeg zijn. Waren ze dat wel, dan waren de software applicaties die worden afgeleverd gemiddeld wel van betere kwaliteit.

Waarschijnlijk krijg ik weer de gebruikelijke lulkoek over me heen van de mensen die vinden dat ik ongelijk heb, c'est la vie. Topicstarter, geloof me, ik weet waarover ik praat: al jaren kan ik niemand een vraag stellen over waar ik mee bezig ben omdat maar een zeer select groepje mensen snapt waar ik mee bezig ben en die werken allemaal bij concurrenten. Om de engineering problemen het hoofd te bieden moet ik dus zelf op zoek naar oplossingen. Op twee plekken is me geleerd hoe dat te doen: 1) op de HIO Enschede waar ze hamerden op het zoeken naar oplossingen, niet zozeer naar hoe je het bouwt, dat is triviaal wanneer je de oplossing hebt en 2) de demoscene, waarbij de lat erg hoog lag en je dus oplossingen moest zoeken om het (ogenschijnlijke) onmogelijke toch mogelijk te maken. Dan moet je niet vragen stellen, want daar kreeg je toch geen antwoord op, je moest nadenken, proberen, oplossingen verzinnen voor deelproblemen, het combineren van kennis wat je had tot nieuwe kennis, wijsheid daaruit distilleren en toepassen.

Je zit niet op school voor de docenten, je zit op school op je voor te bereiden op een lang leven waar je de kennis die je leert toepast en daar op voortborduurt. Zorg er dus voor dat die kennis zo groot mogelijk is wanneer je van je school afkomt, want daarna heb je geen tijd meer om de kennis en de wijsheid die je daaruit haalt dermate aan te vullen zonder veel investeringen (tijd, moeite).
</advocate>

[.oisyn]

Verwijderd schreef op donderdag 08 november 2007 @ 10:43:
[...]


Sudokus moet je heel anders oplossen, je programma moet gewoon de "menselijke" handelingen keer op keer uitvoeren, dan heb je in ieder geval een hele snelle oplossing voor de menselijke puzzels, er zullen er ook wel wat zijn waarbij je wat moet "uitproberen".

En dat is dus anders dan bij andere puzzels omdat...?

@EfBe: cheers, mooi verwoord

[RobIII]

@EfBe: Mag ik dat in de FAQ opnemen?

[EfBe]

RobIII schreef op donderdag 08 november 2007 @ 14:48:
@EfBe: Mag ik dat in de FAQ opnemen?

Tuurlijk

[MicroWhale]

Leuk puzzeltje.

Ik zou het zelf oplossen door per getal de mogelijke oplossingen af te lopen om te kijken hoeveel correcte mogelijkheden ertussen zitten. Daarna die met maar één oplossing vastleggen en vanaf daar door middel van kettingreactie gaan getallen één voor één van mogelijke oplossing te veranderen. Totdat het klopt.

[Creepy]

RobIII schreef op donderdag 08 november 2007 @ 14:48:
@EfBe: Mag ik dat in de FAQ opnemen?

GMTA
EfBe:

[Nick The Heazk]

Ik heb dezelfde opgave ook vorig jaar gehad en ik kan je zeggen dat je voor de meeste puzzels geen backtracking nodig hebt. Ik raad je aan om eerst zelf een aantal van die Slither Links op te lossen. Je merkt gouw genoeg dat er een aantal triviale regels aanwezig zijn.

Ik kan je verder vertellen dat het mogelijk is om puzzels, waarbij backtracking niet nodig is, op te lossen met juist 1 inspectie per boog.

Het is ook mogelijk om een algoritme te bouwen waarvan de tijdscomplexiteit gelijk is aan T( s ) met s de grootte van de invoer (rij * kolom). Deze tijdscomplexiteit geldt wel enkel voor puzzels die men kan oplossen zonder backtracking (en geloof me, je kan er heel veel zonder backtracking oplossen. En surplus, niemand heeft het hier over volledig brute-forcen ).

Ook leuk; je kan een algoritme bouwen waarin er geen controles moeten worden uitgevoerd om na te gaan of de lijn wel een gesloten figuur vormt. (Al maakte het vorig jaar niet echt uit of er 1 of meerdere lussen aanwezig waren).

[ Voor 43% gewijzigd door Nick The Heazk op 08-11-2007 22:05 ]

[Neverwinterx]

Ik heb dezelfde opgave ook gehad (ik vormde een groepje met Nick hierboven). Even ter verduidelijking:
De overgrote meerderheid van de puzzels kan met vaste regels opgelost worden. Maar er zijn er ook waarbij het nooit lukt met vaste regels. Je kan dus best volgende strategie volgen: eerst proberen met vaste regels en als je niet meer verder kan met regels doe je een brute-force/backtracking, waarna je weer regels probeert etc ...

De puzzel heet dus Slitherlink en je kan er zo wat informatie over vinden. Onder meer op http://en.wikipedia.org/wiki/Slither_Link
De variant op wikipedia laat lege vakjes toe waarbij je de bogen vrij mag kiezen. Jouw variant laat dit niet toe en is dus wat eenvoudiger.

Begin in het vervolg wat vroeger aan zo'n opgave.

Edit: Het is een NP-compleet probleem overigens.

[ Voor 13% gewijzigd door Neverwinterx op 08-11-2007 23:47 ]

[TeeDee]

offtopic:
fscking hell EfBe, grote klasse. Dit zou niet eens in de FAQ moeten, dit moet op een grote A0 geplot worden...