Programmering av løsning til såkaldt Soduko-spill

[sim]

Det virker som slike Soduko/Sudoku-spill har blitt veldig populært. Finner det i avisen hver dag osv. Jeg har løst et par slike, og synes egentlig det er ganske gøy. Ja, sommerferie er litt kjedelig når man har snudd døgnrytmen.

 

Spillet/oppgaven i seg selv er ikke så forferdelig avansert. Et brett består av 81 ruter. 9 rader og 9 kolonner. Reglene er som følger:

- I hver rad skal tallene 1-9 forekomme

- I hver kolonne skal tallene 1-9 forekomme

- I hvert kvadrat (3x3) skal tallene 1-9 forekomme

 

Et brett ser slik ut.

 

Vanskelighetsgraden varierer etter hvor mange tall man får opplyst.

 

Andre ting som kanskje er greie å vite er at det kun finnes èn løsning til oppgaven hvis:

- Det er minst ett tall i hver rad

- Det er minst ett tall i hver kolonne

- Minst en forekomst av hvert siffer (1-9)

 

Det jeg er interesert i er å finne ut hvordan man kan lage et program/skript som løser dette. Jeg er fullstendig klar over at det allerede finnes slike script tilgjengelig, men jeg ønsker å lære noe av dette i tillegg, ikke bare løse oppgaven .

 

Har dere forslag til hvordan dere ville løst denne oppgaven?

[aadnk]

Nå forleden postet kaffenils et Visual Basic-program som kunne løse Sudoku-brett. Du kan finne programmet her:

http://forum.hardware.no/index.php?showtop...0entry4522434

[mar]

En gasnke enkel løsning:

 

1. let etter en rute der det kun er ett tall som kan plaseres.

2. sett inn dette tallet.

3. dersom det fremdeles er tomme ruter, gå til 1.

[sim]

En gasnke enkel løsning:

 

1. let etter en rute der det kun er ett tall som kan plaseres.

2. sett inn dette tallet.

3. dersom det fremdeles er tomme ruter, gå til 1.

Vil dette fungere da ? Det er jo ganger der det er to tall som passer i samme rute.

[mar]

En gasnke enkel løsning:

 

1. let etter en rute der det kun er ett tall som kan plaseres.

2. sett inn dette tallet.

3. dersom det fremdeles er tomme ruter, gå til 1.

Vil dette fungere da ? Det er jo ganger der det er to tall som passer i samme rute.

Er klar over det, og det er derfor man må finne en rute hvor det bare er ett tall som passer. Dersom det er to eller flere tall som passer går man videre til neste tomme rute og sjekker hvor mange muligheter der er, er det bare 1 så setter man inn det tallet, så leiter man videre. Slik holder man på til det ikke er flere tomme ruter.

Endret 25. juli 2005 av mar

[Mr.Garibaldi]

Ville kanskje løst det på en lignende måte som Dronningoppgave/Travelling Salesman...

 

Sjekk om du kan plassere ett tall i ruten

minMetode(int plass){
  for(int i = 0; i < 6; i++){
     if(kanManPlassereTalletHer(plass, i)){
        <plasser tall>
       minMetode(plass+1);
     }
   }
   return;
}

 

Må selvsagt fylles ut mye mer, men du kan kanskje forstå prinsippet?

 

Når man kommer til slutten av brettet skriver man ut svaret.

[sim]

Joda, jeg ser hva dere tenker på. I noen tilfeller kan det være at det er fler enn ett tall som passer. Man kan godt sitte igjen med 4 ruter der to forskjellige tall kan plasseres. Da vil ikke den metoden med å lete etter ruter der det kun passer et tall fungere.

 

Som sagt, det er ikke så enkelt som å bare sjekke at et tall kan plasseres i den ruten.

 

Jeg takker for innspill. Gøy dette

[aadnk]

Jeg vil anbefale å lese den relaterte artikkelen på Wikipedia. Der beskrives flere fremgangsmåter for å løse et Sudoko-spill programveien. Især dette er verd å bemerke seg:

 

Counting 1–9 in regions, rows, and columns to identify missing numbers. Counting based upon the last number discovered may speed up the search. It also can be the case (typically in tougher puzzles) that the value of an individual cell can be determined by counting in reverse — that is, scanning its region, row, and column for values it cannot be to see which is left.

 

Det du altså kan gjøre, er å finne de manglende numrene i hver eneste kolonne, tatt i betrakning av alle tallene verikalt, horisontalt og i segmentet utifra en celle. Deretter prøver du ut om disse manglende tallene passer, en etter en. For å prøve om tallet er korrekt, antar du at tallet faktisk stemmer, og går videre i kolonnen. Du finner dernest de manglende tallene utifra cellen deretter, og prøver ut dens tall, en etter en; og slik fortsetter du, til neste kolonne og deretter neste rad. Dersom noe går galt, og du har funnet alle mulighetene for en gitt celle, går du tilbake til den forrige, og tester videre der. Slik fortsetter du inntil alle tallene er funnet.

 

Ellers kan du jo gjøre det som Mr.Garibaldi foreslår, dog er dette en langt fra effektiv metode. Eksempel i Java.

[Mr.Garibaldi]

Ellers kan du jo gjøre det som Mr.Garibaldi foreslår, dog er dette en langt fra effektiv metode.

Nå mente ikke jeg at han kun skulle kun bruke den lille snutten jeg postet over.

I så fall ville det ta evigheter før han fant en løsning, men snarere å bruke noe lignende som basis, og så lage avskjæringer som f.eks. de du beskrive i din post og andre han måtte komme på.

 

Men ja, jeg burde nok utdypet det en smule mer...

[mar]

Er det noen som har et eksempel på et brett som ikke lar seg løse ved å søke etter ruter med bare en mulighet? Driver og tester litt, men alle brettene jeg har testet med lar seg løse på den enkle måten. Så da får jeg ikke testet skikkelig.

[josteinaj]

mar: http://www.sudokusolver.co.uk/grids_nologic.html

 

sim: http://www.blott-online.com/sudoku/

 

prøv dere på denne : http://www.mathschallenge.net/index.php?se...=problems&id=96