[Tuyaux] Examenvragen IP Praktijk augustus 2010

[Manfr3d]

1. Basisversie
In de basisversie zijn volgende acties beschikbaar als commando's vanuit je Tool-bestand:
* Lees een Sudoku spel in vanuit een MSK-bestand (zie Sectie 3 voor een beschrijving van het MSK-formaat) en sla de ingelezen puzzel op in een tweedimensionale array.

* Vul een getal in een vakje op een bepaalde coordinaat in. Bij het invullen moet gecontroleerd worden of aan alle regels van het Sudoku-spel voldaan is. Geef een foutboodschap als dat niet het geval is.
* Maak een vakje terug leeg. Uiteraard kunnen de reeds vooraf ingevulde vakjes niet leeggemaakt worden.
* Maak het gehele spelbord terug leeg.

2. Uitbreidingen
Om extra punten te verdienen, kunnen volgende uitbreidingen toegevoegd worden aan je programma.
Meer sterren betekent meer punten, maar ook meer benodigde tijd!
(*) Voorzie een commando info, dat voor een bepaald vakje weergeeft welke cijfers toegelaten en welke niet toegelaten zijn.
(*) Voorzie een commando hint, dat het eerste vakje zoekt waarvoor slechts 1 cijfer is toegelaten, en dat cijfer daar ook invult.
(*) Voorzie een commando save, dat de (tussentijdse of volledige) oplossing opslaat naar een SOL-bestand met dezelfde bestandsnaam als het ingelezen bestand. Een SOL-bestand heeft hetzelfde formaat als een MSK-bestand.
(**) Voorzie een commando solve, dat door het herhaald uitvoeren van het algoritme uit hint een oplossing zoekt voor eenvoudige puzzels.
(**) Maak gebruik van een gelinkte lijst in plaats van een tweedimensionale array als onderliggende datastructuur.
(**) Controleer bij het invoeren van een cijfer niet alleen of aan alle regels voldaan is, maar controleer ook of de puzzel in zijn nieuwe staat nog oplosbaar is, en geef een foutboodschap als dat niet het geval is. Een puzzel is oplosbaar als er voor elk nog leeg vakje minstens 1 cijfer toegelaten is.
(***) Schrijf het geheel door gebruik te maken van OO.
(***) Ondersteun niet enkel 9x9 puzzels, maar ook 4x4, 16x16, 25x25, 36x36... Maak voor getallen groter dan 9 gebruik van hun hexadecimale (letter-)notatie.
(***) Schrijf een brute-force algoritme dat een oplossing voor alle Sudoku-puzzels kan zoeken. Een brute-force algoritme lost een puzzel op door het cijfer 1 in de eerste cel te plaatsen en te controleren of dat toegelaten is. Als er geen inbreuk tegen de regels is, gaat het algoritme verder naar de volgende cel, en plaatst opnieuw een 1 in die cel. Bij het controleren van de regels ontdekt het algoritme dat het cijfer 1 daar niet is toegelaten, en wordt de waarde gencrementeerd naar 2. Als een cel ontdekt wordt waar geen enkele van de 9 cijfers toegelaten is, laat het algoritme die cel leeg, en gaat het terug naar de vorige cel. De waarde in die cel wordt opnieuw gencrementeerd. Het algoritme wordt herhaald tot de toegelaten waarde in de 81e cel gevonden is.

3. MSK-formaat
In het MSK-formaat worden Sudoku-opgaven in plain text opgeslagen. Het bestand bevat 9 lijnen, en op elke lijn staan 9 karakters. Een leeg vakje wordt aangeduid met een punt. De puzzel uit Figuur 1 zou er in het bestand voorbeeld.msk als volgt uitzien:
1.......6
..6.2.7..
78945.1.3
...8.7..4
....3....
.9...42.1
31297..4.
.4..12.78
9.8......

[racekakje]

Leuk examen!
Heel gemakkelijk basisgeval en uitbreidingen die te doen zijn zonder heel uw programma aan te passen. Buiten mss die onderligende lijstenstructuur (waar ik niet echt het nut in zie..)

[nasam]

Leuk examen!
Heel gemakkelijk basisgeval en uitbreidingen die te doen zijn zonder heel uw programma aan te passen. Buiten mss die onderligende lijstenstructuur (waar ik niet echt het nut in zie..)

Die lijstenstructuur doen ze zoda ge nog eens met pointers moet werken. Wat voor de rest alleen nog maar nodig is als je het OO maakt (en zelfs dan nog niet perse, want ik kan me niet meteen voorstellen dat ineritance-polymorfisme hier gebruikt kan worden -> pointers niet echt nodig), of als je dynamische arrays gaant aanmaken (en in dat geval is het ook maar 1 NEW (allez 1 x N NEWs). Met een gelinkte lijst moet je nog dinges met je pointers gaan doen.

[Pedro]

Die lijststructuur heeft mij zwaar genaaid! Met gelinkte lijsten checken of uw input correct is is quasi onmogelijk op de korten tijd die ge hebt :/

[Robbe]

Wat je natuurlijk ook kon doen was een UniquenessUnit maken waaraan je dan een aantal cellen van je sudoku geeft (9 in het geval van een 9x9), die die dan opslaagt met een gelinkte lijst. Je moet dan in principe alleen maar een lijst van die UUnit's bijhouden en een 2D-array van Cell objecten. Correctheid kan dan gechecked worden a.d.h.v. die UUnit's.

Maar dat verwacht ik om een of andere reden niet direct van een eerstejaars

[Fristi]

Hell, zo zou ik het zelfs nu nog ni doen

[Pedro]

Wat je natuurlijk ook kon doen was een UniquenessUnit maken waaraan je dan een aantal cellen van je sudoku geeft (9 in het geval van een 9x9), die die dan opslaagt met een gelinkte lijst. Je moet dan in principe alleen maar een lijst van die UUnit's bijhouden en een 2D-array van Cell objecten. Correctheid kan dan gechecked worden a.d.h.v. die UUnit's.

Maar dat verwacht ik om een of andere reden niet direct van een eerstejaars

Ok, dat komt op mijn bezwaarschrift als ik er niet door ben

[Math Wolf]

Lijkt me doenbaar. Ik zou het snel in R kunnen programmeren, denk ik.