Det må vel være tilladt at følge op på spørgsmålet og svaret. En alm. sudoku har 81 felter, og det fremgår af svaret, at mindst 17 og højst 77 (!) af disse skal være kendt. MEN, når en sudoku-computer genererer tusindvis af forskellige udgaver - med normalt 25-35 kendte tal - Er det så nødvendigt, at computeren tester ALLE kombinationer for at sikre os, at der kun er en løsning??? Eller starter man med færdigt udfyldte sudoku'er og derefter fjerner "tilpas" mange tal for at opnå den ønskede sværhedsgrad? - Og samtidig kontrollerer, at de resterende tal stadig er nødvendige og tilstrækkelige til at give kun én løsning. PS. Alle Politikens sudokuer har forøvrigt den ekstra finesse, at de opgivne tal står i et perfekt symmetrisk mønster! - Det er derfor, jeg holder Politiken!!! , hvordan sikrer

PS. Alle Politikens sudokuer har forøvrigt den ekstra finesse, at de opgivne tal står i et perfekt symmetrisk mønster! - Det er derfor, jeg holder Politiken!!!

ATS kunne også være et argument, men så kan jeg til gengæld heller ikke finde på flere :-)

"Hvis man får bevist at de Sudoku'er med entydige løsninger, som har færrest forud givne tal, har netop 17 af slagsen, vil man hermed også få bevist at alle Sudoku'er med 16 eller færre forudgivne tal må have mindst to løsninger. Men det er som nævnt indtil videre kun en formodning. Formodningen er dog eksperimentelt understøttet af omfattende computer-beregninger som har genereret titusindvis af entydige Sudoku'er med 17 forud givne tal, men endnu ingen med 16 eller derunder.

Det vides også at der i hvert fald skal mindst 8 forudgivne tal til at garantere en entydig løsning, for alle Sudoku'er der kun benytter 7 eller færre forskellige tal i de forudgivne felter vil nødvendigvis have mindst to løsninger (idet de to resterende tal som ikke er benyttet i de forudgivne felter kan ombyttes i løsningen)."

Der er masser af spejlbilleder af det totale antallet kombinationer, men det jeg savner mest i Thomas Bolanders svar, er en kommentar til betydningen af distributionen af de forudgivne felter. Det ville også være velkomment med en kommentar til hvordan man vurderer opgavens sværhedsgrad, altså sådan som det tit ses i aviserne?

Det er ikke nødvendigt at gå igennem alle mulige kombinationsmuligheder for at sikre sig at en Sudoku kun har een løsning. Der findes forskellige standart-strategier hvormed man på entydig hvis kan tilføje et eller flere nye tal til en delvist udfyldt Sudoku (disse standart-strategier har eksotiske navne som "skjulte par", "nøgne par", "X-wing" m.fl.). Hvis man kan fuldstændiggøre en Sudoku udelukkende ved brug af disse standart-strategier har man dermed sikret sig entydigheden af løsningen. Der er forholdsvist ligetil at lade en computer afprøve disse standart-strategier og se om det kan lede til en fuldstændig løsning. Der findes dog Sudoku'er som er så vanskelige at man på visse trin i fuldstændiggørelsen står i situationer hvor ingen af de kendte standart-strategier kan anvendes. I disse tilfælde kan man så være tvunget til at afprøve flere forskellige kombinationsmuligheder. Det er dog noget som optræder forholdsvist sjældent og stort set aldrig i den slags Sudoku'er som man finder i avisen.

Konstruktion af Sudoku-gåder foregår i dag primært ved brug af computer. Der findes mange metoder til at konstruere sådanne på en computer. En simpel metode er at starte med en tom Sudoku og så trinvist tilføje flere og flere forudgivne tal til man ender med en Sudoku med en entydig løsning som kan beregnes ved hjælp af standart-strategierne (dette checkes med metoden angivet ovenfor). Hvis computeren i stedet ender med en uløselig Sudoku vil den 'backtracke', træffe nye valg og prøve igen.

De oprindelige Sudoku'er blev lavet i hånden og havde altid symmetriske mønstre i de forudgivne tal. Da computerne overtog blev de symmetriske mønstre ofte ignoreret, men nogle computerprogrammer genererer symmetriske mønstre netop for at give Sudoku'erne et mere menneskeligt præg (og for at sælge flere aviser?). Man sikrer sig et symmetrisk mønster ved på forhånd at beslutte placeringen af de forudgivne tal. Det vil typisk lede til mere backtracking før man finder en Sudoku med en entydig løsning, men det ligger stadig indenfor hvad en moderne computer kan klare på forholdsvis kort tid.

Ja, der er helt klart masser af ting man kunne savne i mit svar. Det er nok substans i Sudoku-problematikken til at man kunne opbygge en hel videnskab omkring det. Det er faktisk på en måde allerede gjort, idet det kan vises at Sudoku-problematikken tilhører en større klasse af matematiske problemer kaldet graf-farvningsproblemer. Vi har faktisk en verdensmester på området, Carsten Thomassen på Institut for Matematik, DTU.

Med hensyn til placering af de forudgivne tal findes der mig bekendt ikke nogle generelle resultater omkring dette. Man kan ofte lave Sudoku'er af meget forskellig sværhedsgrad, hvor placeringen af de forudgivne tal er den samme.

Der findes heller ikke en standartiseret metode til at måle sværhedsgraden af en Sudoku, men den metode man oftest benytter er at se på hvor mange og hvor avancerede strategier der kræves for at løse den. Nogle strategier som f.eks. X-wing er forholdsvist komplicerede, så hvis en Sudoku kræver denne strategi for at blive løst vil den få en relativt høj rating.

Tak til Thomas Bolander for svar på de fleste spørgsmål. - Måske flere spørgsmål senere! Og til Uffe Kousgaard: Ja, jeg glemte at nævne ATS. Måske er vi enige, hvis jeg afslører, at jeg i 20 år holdt Politiken, fordi dens læsere trængte allermest til at få lidt jordforbindelse mht. energi- og miljøpolitikken. - Jeg har i den forbindelse fået bragt mindst 200 indlæg (bl.a. et par kronikker) om kernekraft, vindmøller og klima på debatsiderne. I mange år var P stort set lige så useriøs som Ekstrabladet, men tog dog også andres meninger. Nu har piben heldigvis fået en anden lyd, og bladets redaktion og journalister er mere åbne for at formidle viden end blot for politisk korrekthed.

Hvis vi begrænser os til 9x9 standard sudokuer, så er der altså kun omkring 43000 måder at placere det første tal (f.x. "1") på så betingelserne er opfyldt. For hver af disse er der langt færre måder at placere det næste tal (uden at have beregnet det præcist, vil jeg anslå at der højest kan være omkring 10000 muligheder), osv. til vi har placeret alle tallene fra 1 til 8. Der er så kun een måde at placere det sidste tal på. Det giver altså kun et par tusind milliarder måder ialt. Det burde altså ikke være helt umuligt simpelt hen at prøve dem alle sammen med en tilstrækkeligt stor computer.

Jeg får det til 963642321 = 46656 måder at placere alle 1-tallerne. Det bliver så lidt kompliceret at beregne hvor mange måder 2-tallerne kan placeres, og selv hvis man kunne gøre dette er det svært at fortsætte denne metode (når man har placeret tallene fra 1-7 er det jo ikke sikkert at det overhovedet er muligt at placere 8- og 9-tallerne, så man skal ikke bare tælle alle muligheder med).

Nå, men allerede i 2005 blev det beregnet [1] hvor mange færdig-udfyldte sudokuer der findes, og tallet er noget mere end "et par tusind millarder", nærmere bestemt 6,670,903,752,021,072,936,960 ~ 6.67E21, altså et par tusind millarder millarder muligheder.

For hver af disse kan man selvfølgelig udtynde på mange forskellige måder og opnå en sudoku-opgave med en entydig løsning. Hvis vi kalder en sudoku-opgave /reduceret/ hvis det ikke er muligt at fjerne flere af de givne tal uden at entydigheden af løsningen ødelægges, hvor mange reducerede sudoku-opgaver findes der så?

Et måske nemmere spørgsmål er om man kender en øvre grænse for hvor mange givne tal der kan være til stede i en reduceret sudoku-opgave?

[1] http://en.wikipedia.org/wiki/Sudoku#Mathem...

Jeg kan ikke helt gennemskue de tal der bliver brugt i indlægget. I en artikel "Mathematics of Sudoku" af Felgenhauer og Jarvis (som kan findes på nettet) bliver det vist at antallet af forskellige Sudoku'er er 610^21 når der ikke tages hensyn til symmetri. Tages der hensyn til symmetri bliver tallet noget mere håndterbart, men hvis det handler om at sætte en computer til brute force at finde alle Sudoku'er vil symmetrierne først opdages når Sudoku'erne *er genereret, dvs. man kommer op i nærheden af at skulle generere alle 6*10^21 Sudoku'er. Det er langt udenfor rækkevidde af en computer. Selv hvis en supercomputer kunne generere een ny Sudoku per nano-sekund (hvilket i sig selv er temmelig optimistisk), ville det tage 200.000 år at gøre den opgave færdig.

Nu var det jo ikke lige fordi jeg prøvede at være helt præcis i beregningerne, men der er jo sikkert nok at prøve "Principielt Forskellige" opsætninger, og de samme sider som I henviser til at der så kun er 5472730538 der skal testes. Jeg undskylder at jeg i skyndingen ikke lige slog det nøjagtige tal op, men når der nu kun er ca. 5 milliarder i stedet for mit første gæt på et par tusind milliarder, må det da være omtrent tusind gange hurtigere end jeg først anslog. OKK

en Sudoku er 9*9 felter, så hvis jeg roterer 90 grader er det så en ny? eller burde jeg retteligen dele antallet med 4?

de samme sider som I henviser til at der så kun er 5472730538 der skal testes.

Testes for hvad? Hvis man tager hensyn til de oplagte symmetrier som nævnes på http://www.afjarvis.staff.shef.ac.uk/sudok... får man det tal du nævner. Vil du producere en repræsentant for hver af disse "essentielt forskellige" sudoku-grids? Det tror jeg ikke er helt så enkelt. Selvom 5*10^9 ikke er et særlig stort tal, er beregningen alligevel ret omstændelig. Hver gang man laver et sudoku-grid skal man jo _bevise_ at det ikke er relateret til et af dem man allerede har lavet via et element i symmetrigruppen (altså repræsenterer samme "essentielle" løsning), og det er ikke-trivielt (det er stort set det der hedder "the word problem" i gruppeteori, og det er NP-komplet). Det kunne måske gøres lidt effektivt ved at man insisterer på at vælge den repræsentant som er "mindst" i en eller anden leksikografisk ordning, og så finder en effektiv algoritme til at reducere et vilkårligt grid til den kanoniske repræsentant.

Hvis man nu havde sådan en liste (som vel ville fylde nogle få GB) kunne man forsøge at gennemgå hver enkelt og se hvilke udtyndinger der efterlader en opgave med entydig løsning. Men da der er 2^81 potentielle udtyndinger bliver man aldrig færdig med den første... Nå, lidt mere effektivt ville det være at gennemgå de binom(81, 16) ~ 3*10^16 potentielle udtyndinger til 16 givne tal og se om en af disse havde en entydig løsning, for i det mindste at svare på om der findes sudoku-opgaver med entydig løsning ved færre end 17 givne tal. Men stadig virker det ikke som en overkommelig opgave, med mindre man finder på noget lidt smartere end brute force.

det er stort set det der hedder "the word problem" i gruppeteori, og det er NP-komplet

Rettelse: udskift "NP-komplet" med "meget svært". I den konkrete situation er problemet endeligt og derfor afgørligt, men det betyder ikke nødvendigvis at det kan gøres effektivt.

Tages der hensyn til symmetri bliver tallet noget mere håndterbart, men hvis det handler om at sætte en computer til brute force at finde alle Sudoku'er vil symmetrierne først opdages når Sudoku'erne er genereret,

Mnja, det er så ikke lige tilfældet.

En løsning kan representeres som et 81 ciffret tal i 9 tals systemet.

Mange overser at ciffer substitution er en symmetrioperation i denne forbindelse.

Det følger heraf, at du kun behøver at beskæftige dig med de 81 cifferede tal der starter med ciffer 1 og dermed har du allerede elimineret 8/9 af arbejdet.

Samme argument kan du bruge på de næste 8 ciffre, der ligeledes kan sættes fast til 2, 3, 4 osv.

En brute-force søgning derfor "kun" afsøge 9^72 kombinationer istedet for 9^81, en reduktion af arbejdsbyrden med en faktor 387 mio.

Men videre følger at position 10-12 ikke kan indholde ciffrene '1', '2' og '3', dermed er de første tre ciffre vi har brug for at lede igennem reduceret til 6 mulige værdier.

Dette argumentet holder for hele anden og tredje række, hvilket reducerer arbejdet til 6^18 * 9^54, en reduktion på 572 mia i forhold til 9^81

Men i hvert af de resterende 54 felter er der allerede et ciffer vi kan udelukke, nemlig det i første række i den pågældende søjle.

Dermed har vi reduceret arbejdet til 6^18 * 8 ^54, en forbedring på en faktor 3.3*10^14.

Vel at mærke uden at have sammenlignet en eneste soduko med en anden.

Tilbage er kun at afsøge 5.9*10^62 muligheder, hvilket bringer problemet fra "umuligt" til "muligt, hvis du har penge nok til at lave dine egne chips og vente den tid det tager".

Poul-Henning

Der kan laves flere reduceringer (hvoraf nogen overlapper andre).

Pladen kan roteres og spejles. Cifrene kan ombyttes vilkårligt (ciffer substitution). De lodrette og vandrette 3-grupper kan ombyttes vilkårligt. Rækker og søjler inden for en 3-gruppe kan ombyttes vilkårligt.