Programmeringsmetodik, dt079g

Sudoku uppgift

Sudoku

Hur sudoku fungerar kan du se på   web-sudoku.com/.

Uppgift

Uppgiften har följande krav

• Olika sudokupussel ska kunna lösas utan omkompilering av programmet. Löses med fördel genom att läsa in pusslet från en textfil.
• Den ska lösa de som på www.stonline.se/sudoku.php är uppmärkta som "lätta". Det finns vissa typer av pussel som kräver "gissningar", dessa behöver inte hanteras.
• Pussel med flera lösningar behöver inte hanteras. Denna punkt är relaterad till den ovan; Om ett pussel har fler än en lösning kommer det vid något tillfälle att finnas två sätt att fortskrida, gissning krävs.
• Lösningen ska vara anständigt kommenterad, med meningsfulla variabel och funktionsnamn.
• Globala variabler är tillåtna i begränsad utsträckning. Typiskt bör de begränsas till sudoku-pusslets matris, eller motsvarande. Konstanter är naturligtvis ej räknade.
• Algoritmen och programkoden ska kunna redogöras för i detalj vid redovisning.
• Programmet får under inga omständigheter överstiga 700 rader programkod. Detta ska inte vara ett problem, typiska lösningar ligger på kring 200-300 rader. Om du mot förmodan får en lösning som är längre än 700 rader har du misslyckats med att dela upp lösningen i deluppgifter/funktionsanrop.
• Programmet måste inte delas upp i olika filer (.h .cpp etc.). Vissa lösningar kan emellertid vinna på detta.

Tips

Det finns naturligtvis sudoku-lösare att finna på nätet. Jag rekommenderar emellertid er att hålla er ifrån frestelsen att "tjuvkika" på någon lösning, och istället komma fram till en algoritm genom att själv spela några sudoku och sedan fundera och skissa. Att tjuvkika på en lösningsmetod kommer oundvikligen innebära att man låser sig till den lösningsmetoden. En egenhändigt hopsnickrad lösning kommer sannolikt att bli en smula osmidig, men istället ha charm, karaktär och en hel del finurlighet i sig.

Redovisning

Redovisning sker genom en demonstration av program och en enkel förklaring av källkoden, eller om dator inte finns att tillgå, en förklaring av programmet utskrivet på papper.

Redovisningen görs innan första tentamenstillfället. Om det av någon anledning finns acceptabla förhinder skickas ett mail till martin.kjellqvist@miun.se innan ordinarie tentamens början.

Mycket goda lösningar => Tårta

Om någon av lösningarna skulle baseras på en mycket finurlig egenhändigt skapad algoritm, eller på annat sätt utmärka sig som en mycket berömvärd prestation kommer Martin att bjuda på tårta det sista tillfället 19/10. Detta förutsätter naturligtvis att den berörda lösningen lämnas in i rimlig tid innan sista tillfället samt att berörd konstruktör/konstruktörer åtar sig att kort presentera lösningen vid detta tillfälle.