Sudoku

Sudoku (no  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 ir 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 
Lai gan līdzīgas mīklas bija sastopamas jau 19. gadsimtā 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. gadsimta sākumā mīkla no Japānas izplatījās citās pasaules valstīs.
Sudoku spēlē katrs trešais Japānas iedzīvotājs.

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

+TerminsTermins angliskiSkaidrojumsTabula, režģisGridMīklas laukums.Šūna, rūtiņa, lauciņšCell, squareLauciņš 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, skaitlisDigit, number, symbol, valueSimbols, kas ierakstāms šūnā.Bloks, kasteBox, 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.RindaRowVisas 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ā.KolonnaColumnVisas 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īnijaLineRinda vai kolonna.Minikolonna un minirindaBoxcol, mini-col & boxrow, mini-row3 šūnas, kas ietilpst vienā blokā un vienā kolonnā vai rindā.KlasikaClassic9x9 (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.DotieGiven, clue, hintSimboli, 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, joslaFloor, bandTrīs blakus esoši bloki.TornisTower, stackTrīs viens virs otra esoši bloki.KandidātiCandidateSimboli, 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ā).GrupaHouse, 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.BiedrsPeer, 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 
alt=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.|thumb|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.

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 
Šū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).

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). Š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 
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 
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).

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.

 Slēptie pāri 
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.thumb|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 
Avīzēs publicētos sudoku visbiežāk var atrisināt ar augstāk uzskaitītajām metodēm. Taču ir arī vesels lērums citu metožu, kuras ir vai nu krietni sarežģītākas, vai pielietojamas tikai specifiskos gadījumos.

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 
Par dažām metodēm sudoku kopiena nav vienisprātis, vai tās ir pielietojamas risināšanā — unikalitātes un minēšanas metodes.

 Unikalitāte 
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.

 Minēšana 
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 metode — pattern 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.

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

 Atsauces 

 Ārējās saites 
 EUROSUDOKU

 Skatīt arī 
 Krustvārdu mīkla
 Sudoku matemātika

Kategorija:Prāta spēles