Senda inn spurningu
Sólin Sólin Rís 05:36 • sest 21:19 í Reykjavík
Tunglið Tunglið Rís 16:44 • Sest 05:50 í Reykjavík
Flóð Flóð Árdegis: 04:37 • Síðdegis: 17:05 í Reykjavík
Fjaran Fjara Árdegis: 10:57 • Síðdegis: 23:09 í Reykjavík
Visit the English version

Flokkun:

Náttúruvísindi og verkfræði Stærðfræði

Hvað er hægt að búa til margar mismunandi sudokuþrautir?

Mark Dukes

Fjöldi mismunandi sudokumynstra (e. Sudoku grids) á borði af stærðinni 9×9 er 6.670.903.752.021.072.936.960. Þessi tala er gefin upp í grein eftir Þjóðverjann Felgenhauer og breska stærðfræðinginn Jarvis sem kallast Enumerating possible Sudoku grids (Talning mögulegra sudokumynstra). Til þess að reikna þessa tölu út þá gerðu höfundarnir nokkrar athuganir á talnaröðunum (e. configurations) sem þyrfti að athuga. Síðan notuðu þeir tölvu til að finna þær afstöður sem leiddu til fullgilds sudokumynsturs.

Ekki er til þekkt formúla fyrir fjölda sudokumynstra á borði af stærð n×n. Sudokumynstur eru sérstök gerð af svokölluðum latneskum ferningum (e. Latin square). Það er ekki auðvelt að fást við þessa kassa með hefðbundnum talningaraðferðum. Mörg vandamál talningarfræðinnar eiga einnig við þennan vanda að stríða. Það merkir þó ekki að við getum ekki rannsakað eiginleika þessara fyrirbæra.

Ástæðan fyrir þessum vandamálum er frelsið sem felst í því að búa til gilt sudokuborð. Til þess að búa til gilt borð þá verður að tryggja að hver og ein af þeim 27 hlutröðunum sem sudoku miðast við (línur, dálkar og 3×3 kassar) séu umröðun mengisins {1,2,3,4,5,6,7,8,9}. Þar sem ekki er hægt að gefa nákvæma formúlu grípa stærðfræðingar oft til þess að gefa efri og neðri mörk á fjölda mismunandi afstaða talnanna.

Spurningin sem snýr að fjölda mismunandi sudokuþrauta er jafnvel enn erfiðari. Í vandamálum af þessari gerð er ekki alltaf ljóst hvenær tvær þrautir eru eins. Ef sudokuþraut er snúið um 90 gráður þá er auðséð að ekkert hefur í raun breyst. Ef henni er snúið á hvolf þá hefur í raun heldur ekkert breyst.

Einnig má spyrja, ef tölunum 1, 2, 3, 4, 5, 6, 7, 8, 9 er breytt í 5, 8, 3, 2, 6, 9, 1, 4, 7, er það þá sama þraut? Þó svo að svarið sé kannski ekki jafnaugljóst og við hinar aðgerðirnar þá er svarið að sjálfsögðu já. Frá upphaflegum gildum talna í reitnum, þá eru nákvæmlega sömu rök notuð til að leysa þrautina. Nokkrar aðrar svipaðar aðgerðir er hægt að framkvæma til að búa til nýja sudokuþraut, sem lítur öðruvísi út en sú upprunalega, en er í meginatriðum eins. Þær þrautir sem hægt er að búa til með þessum aðgerðum mynda það sem stærðfræðingar kalla jafngildisflokka (e. equivalence class).

Slík fyrirbæri spretta oft upp í stærðfræði, og raunar í daglega lífinu líka. Sem dæmi getum við skilgreint jafngildisflokka af heiltölum þannig að tvær heilar tölur n og m séu jafngildar ef mismunur þeirra er margfeldi af 3, og skrifum þá

n = m (mod 3)

Jafngildisflokkur heillar tölu er þá safn allra þeirra talna sem eru jafngildar henni. Það má reikna með þessum flokkum, og þá fáum við undarlegri útkomur úr útreikningum en við eigum að venjast, til dæmis verður eftirfarandi allt rétt:

1 + 1 = 2 (mod 3)
1 + 2 = 0 (mod 3)
2 + 2 = 1 (mod 3)

Þó þetta virðist skrýtið við fyrstu sýn nota næstum allir í heiminum slíka útreikninga daglega þegar þeir líta á úrskífu og vilja vita hvað klukkan verði síðar um daginn. Ef klukkan er til dæmis 9 að morgni og við fáum skilaboð um að hitta einhvern 6 tímum síðar, þá reiknum við 9 + 6 og fáum út 3, af því að 3 og 15 er jafngilt.

Lykilatriðið er, að þó heiltölurnar séu óendanlega margar fáum við bara þrjá jafngildisflokka; 0, 1 og 2. Á sama hátt getum við myndað jafngildisflokka af sudokumynstrum með umröðunaraðgerðunum sem var lýst hér að ofan. Þessa jafngildisflokka köllum við sudokuþrautir, og þannig geta mörg mismunandi sudokumynstur svarað til sömu sudokuþrautarinnar. Það er fjöldi ólíkra sudokuþrauta sem við höfum áhuga á hér, og líkt með heilu tölurnar okkar er fjöldi ólíkra sudokuþrauta mun minni en fjöldi sudokumynstra.

Í grein sinni beittu Russel og Jarvis þessum og fleiri aðferðum stærðfræðinnar, og ákvörðuðu að fjöldi mismunandi sudokuþrauta er um 5.472.730.538.

Heimildir og mynd:

Upprunalega hljóðaði spurningin svona:
Hvað er hægt að búa til margar sudokuþrautir (venjuleg stærð 9 x 9 - eins og þær eru í flestum dagblöðum). Og hvernig er það reiknað út?

Upprunalega svarið birtist í enskri gerð á Vísindavefnum (How many different Sudoku's is it possible to make?) Það var þýtt og aðlagað af Birgi Urbancic Ásgeirssyni og Gunnari Þór Magnússyni.

Höfundur

Mark Dukes

sérfræðingur á stærðfræðistofu við Raunvísindastofnun HÍ

Útgáfudagur

4.6.2008

Spyrjandi

Kristján Júlíusson
Magnús Ólafsson

Efnisorð

Tilvísun

Mark Dukes. „Hvað er hægt að búa til margar mismunandi sudokuþrautir?“ Vísindavefurinn, 4. júní 2008. Sótt 20. apríl 2024. http://visindavefur.is/svar.php?id=47845.

Mark Dukes. (2008, 4. júní). Hvað er hægt að búa til margar mismunandi sudokuþrautir? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=47845

Mark Dukes. „Hvað er hægt að búa til margar mismunandi sudokuþrautir?“ Vísindavefurinn. 4. jún. 2008. Vefsíða. 20. apr. 2024. <http://visindavefur.is/svar.php?id=47845>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki
Spyrja

Sendu inn spurningu LeiðbeiningarTil baka

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Senda grein til vinar

=

Hvað er hægt að búa til margar mismunandi sudokuþrautir?
Fjöldi mismunandi sudokumynstra (e. Sudoku grids) á borði af stærðinni 9×9 er 6.670.903.752.021.072.936.960. Þessi tala er gefin upp í grein eftir Þjóðverjann Felgenhauer og breska stærðfræðinginn Jarvis sem kallast Enumerating possible Sudoku grids (Talning mögulegra sudokumynstra). Til þess að reikna þessa tölu út þá gerðu höfundarnir nokkrar athuganir á talnaröðunum (e. configurations) sem þyrfti að athuga. Síðan notuðu þeir tölvu til að finna þær afstöður sem leiddu til fullgilds sudokumynsturs.

Ekki er til þekkt formúla fyrir fjölda sudokumynstra á borði af stærð n×n. Sudokumynstur eru sérstök gerð af svokölluðum latneskum ferningum (e. Latin square). Það er ekki auðvelt að fást við þessa kassa með hefðbundnum talningaraðferðum. Mörg vandamál talningarfræðinnar eiga einnig við þennan vanda að stríða. Það merkir þó ekki að við getum ekki rannsakað eiginleika þessara fyrirbæra.

Ástæðan fyrir þessum vandamálum er frelsið sem felst í því að búa til gilt sudokuborð. Til þess að búa til gilt borð þá verður að tryggja að hver og ein af þeim 27 hlutröðunum sem sudoku miðast við (línur, dálkar og 3×3 kassar) séu umröðun mengisins {1,2,3,4,5,6,7,8,9}. Þar sem ekki er hægt að gefa nákvæma formúlu grípa stærðfræðingar oft til þess að gefa efri og neðri mörk á fjölda mismunandi afstaða talnanna.

Spurningin sem snýr að fjölda mismunandi sudokuþrauta er jafnvel enn erfiðari. Í vandamálum af þessari gerð er ekki alltaf ljóst hvenær tvær þrautir eru eins. Ef sudokuþraut er snúið um 90 gráður þá er auðséð að ekkert hefur í raun breyst. Ef henni er snúið á hvolf þá hefur í raun heldur ekkert breyst.

Einnig má spyrja, ef tölunum 1, 2, 3, 4, 5, 6, 7, 8, 9 er breytt í 5, 8, 3, 2, 6, 9, 1, 4, 7, er það þá sama þraut? Þó svo að svarið sé kannski ekki jafnaugljóst og við hinar aðgerðirnar þá er svarið að sjálfsögðu já. Frá upphaflegum gildum talna í reitnum, þá eru nákvæmlega sömu rök notuð til að leysa þrautina. Nokkrar aðrar svipaðar aðgerðir er hægt að framkvæma til að búa til nýja sudokuþraut, sem lítur öðruvísi út en sú upprunalega, en er í meginatriðum eins. Þær þrautir sem hægt er að búa til með þessum aðgerðum mynda það sem stærðfræðingar kalla jafngildisflokka (e. equivalence class).

Slík fyrirbæri spretta oft upp í stærðfræði, og raunar í daglega lífinu líka. Sem dæmi getum við skilgreint jafngildisflokka af heiltölum þannig að tvær heilar tölur n og m séu jafngildar ef mismunur þeirra er margfeldi af 3, og skrifum þá

n = m (mod 3)

Jafngildisflokkur heillar tölu er þá safn allra þeirra talna sem eru jafngildar henni. Það má reikna með þessum flokkum, og þá fáum við undarlegri útkomur úr útreikningum en við eigum að venjast, til dæmis verður eftirfarandi allt rétt:

1 + 1 = 2 (mod 3)
1 + 2 = 0 (mod 3)
2 + 2 = 1 (mod 3)

Þó þetta virðist skrýtið við fyrstu sýn nota næstum allir í heiminum slíka útreikninga daglega þegar þeir líta á úrskífu og vilja vita hvað klukkan verði síðar um daginn. Ef klukkan er til dæmis 9 að morgni og við fáum skilaboð um að hitta einhvern 6 tímum síðar, þá reiknum við 9 + 6 og fáum út 3, af því að 3 og 15 er jafngilt.

Lykilatriðið er, að þó heiltölurnar séu óendanlega margar fáum við bara þrjá jafngildisflokka; 0, 1 og 2. Á sama hátt getum við myndað jafngildisflokka af sudokumynstrum með umröðunaraðgerðunum sem var lýst hér að ofan. Þessa jafngildisflokka köllum við sudokuþrautir, og þannig geta mörg mismunandi sudokumynstur svarað til sömu sudokuþrautarinnar. Það er fjöldi ólíkra sudokuþrauta sem við höfum áhuga á hér, og líkt með heilu tölurnar okkar er fjöldi ólíkra sudokuþrauta mun minni en fjöldi sudokumynstra.

Í grein sinni beittu Russel og Jarvis þessum og fleiri aðferðum stærðfræðinnar, og ákvörðuðu að fjöldi mismunandi sudokuþrauta er um 5.472.730.538.

Heimildir og mynd:

Upprunalega hljóðaði spurningin svona:
Hvað er hægt að búa til margar sudokuþrautir (venjuleg stærð 9 x 9 - eins og þær eru í flestum dagblöðum). Og hvernig er það reiknað út?

Upprunalega svarið birtist í enskri gerð á Vísindavefnum (How many different Sudoku's is it possible to make?) Það var þýtt og aðlagað af Birgi Urbancic Ásgeirssyni og Gunnari Þór Magnússyni....