Umulig Sudoku!

[John Larsson]

Jeg bruger kun sudoku'erne til hjernegymnastik, så går de ikke op, slår jeg et stort kryds over hele feltet, så jeg ikke skal bruge mere tid på netop den! Ind imellem har jeg luret på, om de der ikke går op i virkeligheden ikke er fejlkonstruerede. I dag tog jeg mig tid til at tjekke den svære i Tante Berlinger. Det gjorde jeg på http://www.dailysudoku.com/sudoku/play.shtml for at gøre det nemt. sørme om den ikke var umulig!  ;-)

[efry]

Jeg har for flere år siden skrevet noget i Basic, der kan løse mange, men bestemt ikke alle Sodukoer. Det lille program fandt dog følgende løsning

362 741 895
186 692 473
479 358 621
213 974 586
846 215 739
957 836 214
531 487 962
724 169358
698 523 147

V.h
Erik

[efry]

For øvrigt kan den link, som du henviser til, også løse opgaven.

[John Larsson]

For øvrigt kan den link, som du henviser til, også løse opgaven.

Øv, det var dog irriterende! Ikke nok med at jeg må have lavet noget ulogisk i den manuelle løsning af opgaven, men jeg må også have tastet noget forkert i udgangspositionen, da jeg testede den maskinelt; nu virkede den også for mig!

Hvordan er logikken bagved dit program, og hvordan ved du at at det ikke kan løse alle løselige opgaver?Min tilgang, sådan historisk, var at jeg var interesseret i at lave et program som kunne konstruere opgaver med en objektiv mærkning af sværhedsgrader, men der gik jeg i stå...

Kun for nørder:

Opgaven i "Tanten" var:

3,_,_/7,_,_/8,_,5
_,_,_/6,9,_/_,_,_
_,7,_/_,_,_/_,2,1

_,_,_/9,_,_/5,_,6
_,_,_/2,1,_/_,_,9
_,5,_/_,3,_/_,_,_

_,_,1/_,8,_/_,_,_
_,_,4/_,_,_/3,_,_
6,_,8/_,_,3/_,_,7


;-)  (Dét sidste skulle bare forestille en smiley!)

[efry]

Mit program, der er skrevet i Basic 6.0, dvs. fra før .NET kom frem, er opbygget således at man kan prøve forskellige principper i vilkårlig rækkefølge.

Programmet er udelukkende skrevet for sjov og egentligt kun for at kunne checke en løsning, hvis man ikke kan komme videre, idet det er min erfaring, at når man gror fuldstændigt fast, så skyldes det ofte, at man har lavet en fejl, som blokerer den videre løsning.

Der findes en side, der beskriver en række principper fra helt simple til meget avancerede. Den findes på:

http://www.sudokuwiki.org/sudoku.htm

Til højre på siden findes en liste over en række principper for løsning.

I mit program er kun principperne 1, 2, 3, 5 og 7 implementeret på en eller anden form, men det løser også så godt som alle de sodukoer, man finder i aviserne.

En god beskrivelse af løsningsmuligheder findes også på:

http://www.angusj.com/sudoku/hints.php

Det er godt nok længe siden, jeg sidst har beskæftiget mig med programmet, men hvis du (eller andre) sender mig en mail, så vil jeg da godt sende såvel program som sourcekoden, dog under den betingelse, at i undlader at kommentere sourcekoden. Da jeg på et tidspunkt overvejede at omskrive til .NET opgav jeg, for koden er lavet ved brug af copy/paste og ligner derfor spagetti af værste art. Der findes dog mange programmer på nettet, der er betydeligt bedre end mit og som er skrevet i mere moderne sprog. Mit blev lavet den gang adgangen til nettet foregik via opkobling over ISDN og dermed tog en betragtelig tid for at få forbindelsen etableret.

Når du spørger om hvordan jeg kan vide, at programmet ikke kan løse alle sodukoer, så er det jo ret simpelt at finde en soduko, der kræver anvendelse af et af de mere avancerede principper for løsning, og herefter fastslå at programmet selvfølgelig ikke kan løse denne.