Sudoku

Vikipēdijas lapa
Jump to navigation Jump to search
Neatrisināta 9x9 rūtiņu sudoku

Sudoku (no japāņu: 数独 sūdoku) ir mīkla, kurā jāizvieto ciparus (vai citus simbolus) tā, lai katrā mīklas rindā, kolonnā un blokā tie neatkārtotos. Klasiskā sudoku izmērs is 9x9 rūtiņas, kas sadalītas blokos pa deviņiem kvadrātiskiem lauciņiem. Taču bieži vien sastopami sudoku varianti ar atšķirīgu rūtiņu skaitu, mīklas laukumu vai bloku formu, vai papildus noteikumiem.

Izcelsme[labot šo sadaļu | labot pirmkodu]

Lai gan līdzīgas mīklas bija sastopamas jau 19. gs. Francijā, tiek uzskatīts, ka mūsdienās pazīstamo sudoku variantu izgudroja kāds amerikānis, kurš to publicēja 1979. gadā. 1984. gadā mīkla tika publicēta Japānā, kur tā iemantoja lielu popularitāti, tikai 21. gs. sākumā mīkla no Japānas izplatījās citās pasaules valstīs. Sudoku spēlē katrs trešais japānietis.[nepieciešama atsauce]

Terminoloģija[labot šo sadaļu | labot pirmkodu]

Sudoku jēdzieniem nav oficiālas terminoloģijas, taču kopienā ir nostiprinājušies savi termini.[1]

Termins Termins angliski Skaidrojums
Tabula, režģis Grid Mīklas laukums.
Šūna, rūtiņa, lauciņš Cell, square Lauciņš tabulā, kurā ierakstīts vai jāieraksta viens simbols. Konkrētu šūnu adresē, nosaucot tās rindu un kolonnu. Piemēram, otrās rindas 4. šūna ir r2c4 vai b4.
Cipars, simbols, skaitlis Digit, number, symbol, value Simbols, kas ierakstāms šūnā.
Bloks, kaste Box, block, region, subgrid, unit Šūnu laukums, kas no pārējās tabulas atdalīts ar biezāku līniju. Klasiskajā sudoku bloku veido 3x3 šūnu laukumi. Blokus numurē sākot ar kreiso augšējo stūri, tam pa labi blakus esošais bloks ir otrais un tad trešais, nākamajā rindā ceturtais, piektais, utt.
Rinda Row Visas vienā horizontālā līnijā (cita citai blakus) izvietotās šūnas. Uz noteiktu rindu norāda izmantojot kārtas numuru (numurēšanu sākot no augšas) vai burtu līdzīgi kā šahā (t.s. k9 adresācijā). Izmantojot burtus, i un j netiek lietoti, tātad a ir pirmā rinda un k — pēdējā.
Kolonna Column Visas vienā vertikālā līnijā (cita virs citas) izvietotās šūnas. Uz noteiktu kolonnu norāda izmantojot kārtas numuru (numurēšanu sākot no kreisās puses).
Līnija Line Rinda vai kolonna
Minikolonna un minirinda Boxcol, mini-col & boxrow, mini-row 3 šūnas, kas ietilpst vienā blokā un vienā kolonnā vai rindā.
Klasika Classic 9x9 (9 rindu un 9 kolonnu) sudoku variants ar 3x3 blokiem (t.i. bloku robežām ik pa trim rindām/kolonnām), kurā nav citu ierobežojumu kā vien nosacījums, ka cipari nedrīkst atkārtoties rindas, kolonnas un bloka ietvaros.
Dotie Given, clue, hint Simboli, ko mīklā ierakstījis sastādītājs. Risinot mīklu jāatrod tāds risinājums, kas izpilda sudoku nosacījumus, saglabājot dotos nemainītus.
Stāvs, josla Floor, band Trīs blakus esoši bloki.
Tornis Tower, stack Trīs viens virs otra esoši bloki.
Kandidāti Candidate Simboli, kas varētu būt ierakstāmi vēl neatrisinātā šūnā (par citiem simboliem var būt skaidrs, ka tie šai šūnā nebūs, jo ir izslēgti kā sudoku nosacījumu vai risināšanas tehniku rezultātā).
Grupa House, set, group Šūnu kopums, kurā jāievieto pa vienam no katra izmantojamā simbola. Klasiskajā sudoku grupas ir rindas, kolonnas un bloki, kur katrā jāieraksta pa vienam ciparam no 1 līdz 9.
Biedrs Peer, buddy, family Šūna, kas ietilpst tajā pašā grupā, kurā aplūkojamā šūna. Piemēram, r3c3 ir r3c8 biedrs, jo abas ietilpst trešajā rindā.

Risināšana[labot šo sadaļu | labot pirmkodu]

Sudoku tabula, kurā izsvītrotas rindas un kolonnas ar pieciniekiem, atstājot tikai divas neizsvītrotas šūnas trešajā blokā, kurā 5 vēl nav. Viena no tām ir aizņemta ar doto, tāpēc 5 jāieraksta atlikušajā šūnā. Izcelta arī tabulas centrālā šūna, kura ir tukša, norādot, ka šīs šūnas kolonnā un rindā jau ir visi skaitļi, izņemot 5, tātad tajā rakstāms 5.
Centrālajā šūnā kailais vientuļnieks ir 5, jo nevienu citu ciparu neļauj rakstīt rindas un kolonnas biedri. Zaļā (r3c7) šūnā ir slēptais vientuļnieks 5, jo citās trešā bloka šūnās 5 nevar rakstīt to grupas biedru vai aizņemtības dēļ.

Par derīgu sudoku parasti uzskata tādu mīklu, kurai eksistē tieši viens atrisinājums. Klasiskajā sudoku nepieciešami vismaz 17 dotie, lai atrisinājums būtu unikāls.[2]

Atrisinājuma meklēšana notiek pakāpeniski. Atrisinot vienu šūnu (vai vismaz tai sašaurinot kandidātu loku), bieži atklājas jauni ierobežojumi citām šūnām. Risināšanas gaitā risinātājs parasti tabulā veic piezīmes, atzīmējot informāciju, kas par mīklu jau atrasta. Piemēram, atzīmē šūnās kandidātus.

Pamatsoļi[labot šo sadaļu | labot pirmkodu]

Šūnu, kurā ir tikai viens kandidāts (visi pārējie simboli tajā nav iespējami, jo izslēgti kā kādas grupas biedri vai citu loģisku spriedumu rezultātā), sauc par kailo vientuļnieku (naked single) jeb uzspiesto šūnu (forced cell).[3]

Ja grupā kāds cipars ierakstāms tikai vienā no šūnām, to sauc apslēpto vientuļnieku (hidden single) jeb uzspiesto ciparu (foced digit). Šāda situācija izveidojas, kad no visām pārējām šūnām šis cipars izslēgts no kandidātu saraksta kā šo šūnu grupas biedrs vai citu metožu pielietojuma rezultātā.

Ja kādā grupā (rindā, kolonnā vai blokā) ir atlikusi tikai viena brīva vieta, šādu situāciju sauc par pilnu māju (full house).[4] Šajā šūnā atliek ierakstīt vienīgo grupā vēl neesošo ciparu. Pilnas mājas gadījumā vienlaicīgi iestājas gan kailā, gan slēptā vientuļnieka gadījums, jo grupā palicis tikai viens simbols un tikai viena šūna.

Šos soļus izmanto ikviens risinātājs, taču tos parasti neizceļ sudoku analīzē, jo tie nepieciešami katrā sudoku. Lielāku vērību parasti pievērš sarežģītāku metožu lietojumam — tam, ar kādām izdodas kandidātu lokus sašaurināt tiktāl, ka atklājas vientuļnieki.

Kailie pāri[labot šo sadaļu | labot pirmkodu]

Par kailajiem pāriem sauc divas šūnas, kuras pieder vienai grupai un abās ir tikai divi kandidāti, turklāt vieni un tie paši. Tādā gadījumā citās šīs grupas šūnās šo ciparu nebūs — tos var izslēgt no kandidātu sarakstiem.

Piemēram, tās var būt divas šūnas vienā blokā, kur iespējami vienīgi cipari 1 un 2. Tad šajās divās šūnās šie abi cipari arī būs vienā vai otrā secībā (jo nevar būt abās viens un arī citi tur nebūs, jo citu kandidātu nav). Pārējās šī bloka šūnās tad gan 1, gan 2 ir izslēdzami no kandidātu saraksta.

Analogi var runāt arī par kailajiem trīnīšiem un četrīšiem, kur attiecīgi trijās vai četrās šūnās kandidātu vidū ir tikai trīs (vai attiecīgi četri) dažādi cipari.

Fiksētie kandidāti un Snaidera pieraksts[labot šo sadaļu | labot pirmkodu]

Reizēm izdodas atrast, ka noteikts simbols ir kandidāts tikai tādās vienas grupas šūnās, kas vienlaicīgi ietilpst arī citā grupā. Tād šis simbols svītrojams no kandidātu saraksta citās otras grupas šūnās. Šos simbolus sauc par fiksētajiem kandidātiem (locked candidates), bet metodi — par krustpunktu izslēgšanu (intersection removal), bloka-līnijas (vai līnijas-bloka) mijiedarbību vai norādošiem (pointing) pāriem (vai trīnīšiem).[5][6]

Piemēram, ja blokā izdevies atrast, ka 1 ir kandidāts tikai divās, turklāt visas šīs šūnas atrodas vienā rindā, tad skaidrs, ka vienā no tām 1 tiešām būs un nekur citur šai rindā tas nebūs, tātad rindas šūnās, kas ietilpst citos blokos, no kandidātu saraksta to var svītrot.

Fiksēto kandidātu ierakstīšana ir noderīga sudoku risināšanā arī tad, ja uzreiz nenoved pie izslēgšanas. Reizēm, īpaši risināšanas sākumā, šūnās atzīmē nevis visus kandidātus, bet tikai tādus fiksētos kandidātus, kam skaidrs, ka simbols būs vienā no tieši divām šūnām konkrētā bloka ietvaros. Šo metodi sauc par Snaidera pierakstu.[7]

Slēptie pāri[labot šo sadaļu | labot pirmkodu]

Ja ir divi simboli, kas grupas ietvaros ir kandidāti tikai divās šūnās, turklāt tajās pašās , tad citus kandidātus no šīm šūnām var svītrot. Šos skaitļus sauc par slēptajiem pāriem.

Piemēram, ja gan 1, gan 2 rindas ietvaros ir kandidāti tikai pirmajā un otrajā šūnā, tad skaidrs, ka vienam no cipariem būs jābūt vienā un otram — otrā šūnā. Tad visus pārējos kandidātus no šīm abām šūnām var svītrot. Analogi iespējami arī slēptie trīnīši utt.

X metodes (X-wing) pielietojums. Gan trešajā, gan astotajā kolonnā 7 var atrasties tikai trešajā vai piektajā rindā. Tātad, lai kāds būtu atrisinājums, abās šajās rindās 7 atradīsies vai nu trešajā, vai astotajā kolonnā. Pārējās šo rindu šūnās tad 7 nebūs un sarkanajās šūnās tas no kandidātu saraksta ir svītrojams.

Sarežģītākas metodes[labot šo sadaļu | labot pirmkodu]

Avīzēs publicētos sudoku visbiežāk var atrisināt ar augstāk uzskaitītajām metodēm.[8] Taču ir arī vesels lērums citu metožu, kuras ir vai nu krietni sarežģītākas, vai pielietojamas tikai specifiskos gadījumos.[9][10]

Populārākās no sarežģītākām metodēm ir zivju (fish) metodes, kurās salīdzina grupu kopas no vairākiem veidiem, piemēram X metode (X-wing), zobenzivs (swordfish), X ar spurām (finned X-wing). Vienkāršākā no šīs saimes ir X metode, kurā divu kolonnu kandidātus salīdzina ar divu šūnu kandidātiem.

Starp citām loģikas metodēm populārākās ir ķēdes (piemēram, vientuļnieku ķēdes, Y metode), iekrāsošanas.

Strīdīgas metodes[labot šo sadaļu | labot pirmkodu]

Par dažām metodēm sudoku kopiena nav vienisprātis, vai tās ir pielietojamas risināšanā — unikalitātes un minēšanas metodes.[11]

Unikalitāte[labot šo sadaļu | labot pirmkodu]

Dažreiz kandidātu izvietojums ir tāds, ka var spriest — vairāku nezināmo šūnu vidū jābūt kādam dotajam vai noteiktam kandidātam, citādi atrisinājums nebūs unikāls. Piemēram, ja pirmo divu rindu pirmajās un pēdējās šūnās būtu 1 un 2, tad kādam no šiem cipariem būtu jābūt dotiem, citādi tos varētu izvietot jebkādā secībā, neatkarīgi no citu šūna saruna. Ja doto šajās šunās nav, tad vismaz vienā no šūnām jābūt kādam citam ciparam, citādi atrisinājums nebūtu unikāls. Ne visi uzskata, ka šo metodi ir pieļaujams izmantot, jo loģika balstās ne tikai sudoku noteikumos, bet arī mīklas sastādītāja apgalvojumā, ka atrisinājums ir unikāls. Visām zināmajām unikalitātes metodēm ir atrasti arī alternatīvas metodes, kas sniedz šo pašu informāciju, neizmantojot unikalitātes kritēriju.[11]

Minēšana[labot šo sadaļu | labot pirmkodu]

Sudoku iespējams risināt arī izdarot minējumus. Piemēram, ierakstot kādu minējumu, var risināt mīklu tālāk un vai nu to atrisināt vieglāk nekā tas ir bijis paredzēts, vai nonākt pie pretrunas, kas, savukārt, nozīmē, ka šajā šūnā ieliktais cipars tur nederēja un no kandidātu saraksta ir svītrojams. Iespējamas arī smalkākas metodes, kas koncentrējas uz noteiktas šūnas vai cipara izmēģinājumiem, piemēram, var pārskatīt visus iespējamos kāda cipara izvietojumus tabulā (pārklājošā raksta metodepattern overlay method).

Minēšanas metodes parasti ir lēnākas par loģiskajām, izņemot pašas risinājuma beigas, kad variantu atlicis maz. Taču tās bieži izmanto pārbaudot sastādīto mīklu ar programmas palīdzību — dators var pārbaudīt visus iespējamos tabulas aizpildījumus (veikt pilno pārlasi), lai noskaidrotu, vai mīklas atrisinājums ir unikāls. Tomēr par labu, risināšanai derīgu mīklu, uzskata tādu sudoku, ko var atrisināt tikai ar loģiku, neizmantojot minēšanu un reizēm risināšanu bez minēšanas uzskata par pareizāku. Jebkuru sudoku var atrisināt ar minēšanas palīdzību.[12]

Sudoku Latvijā[labot šo sadaļu | labot pirmkodu]

Latvijā iznāk vairāki Sudoku mīklu žurnāli[13] un Latvijas Sudoku federācija kopš 2018. gada rīko Latvijas Sudoku čempionātu.[14]

Atsauces[labot šo sadaļu | labot pirmkodu]

  1. «Terminology - Sudopedia».
  2. McGuire, Gary; Tugemann, Bastian; Civario, Gilles (2014-04-03). "There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration" (en). Experimental Mathematics 23 (2): 190–217. doi:10.1080/10586458.2013.870056. ISSN 1058-6458.
  3. «Solving sudokus - Forced cells». Skatīts: 2019-12-22.
  4. «Full House - Sudopedia». Skatīts: 2019-12-22.
  5. «Locked Candidates - Sudopedia». Skatīts: 2019-12-22.
  6. «SudoWiki.org - Intersection Removal». Skatīts: 2019-12-22.
  7. «Super Fiendish Sudoku: Is Snyder notation enough? - YouTube». Skatīts: 2019-12-22.
  8. Vanaga, Baiba (8.-14. marts, 2019). "Beigās acis visiem otrādi". SestDiena: 6.
  9. «SudokuWiki.org - Strategy Families». Skatīts: 2019-12-22.
  10. «Solving Technique - Sudopedia». Skatīts: 2019-12-22.
  11. 11,0 11,1 «Uniqueness Controversy - Sudopedia». Skatīts: 2019-12-22.
  12. «Sudoku solution by Trial and Error». Skatīts: 2019-12-22.
  13. «Sudoku Nr. 1». Skatīts: 2019-12-21.
  14. «Latvijas Sudoku federācija».

Ārējās saites[labot šo sadaļu | labot pirmkodu]

Skatīt arī[labot šo sadaļu | labot pirmkodu]