Kā atrisināt sarežģīto sudoku. Matemātiķi izdomāja formulu Sudoku risināšanai

Sudoku lauks ir tabula ar 9x9 šūnām. Katrā šūnā tiek ievadīts skaitlis no 1 līdz 9. Spēles mērķis ir sakārtot skaitļus tā, lai katrā rindā, kolonnā un katrā 3x3 blokā nebūtu atkārtojumu. Citiem vārdiem sakot, katrā kolonnā, rindā un blokā ir jābūt visiem skaitļiem no 1 līdz 9.

Lai atrisinātu problēmu, kandidātus var ierakstīt tukšās šūnās. Piemēram, apsveriet šūnu 4. rindas 2. kolonnā: kolonnā, kurā tā atrodas, jau ir skaitļi 7 un 8, rindā - skaitļi 1, 6, 9 un 4, blokā - 1. , 2, 8 un 9 Tāpēc šajā šūnā no kandidātiem izsvītrojam 1, 2, 4, 6, 7, 8, 9, un mums paliek tikai divi iespējamie kandidāti - 3 un 5.

Līdzīgi mēs apsveram iespējamos kandidātus citām šūnām un iegūstam šādu tabulu:

Ar kandidātiem ir interesantāk nodarboties, un var pielietot dažādas loģiskās metodes. Tālāk mēs apskatīsim dažus no tiem.

Vientuļnieki

Metode sastāv no singlu atrašanas tabulā, t.i. šūnas, kurās ir iespējams tikai viens cipars un neviens cits. Mēs ierakstām šo skaitli šajā šūnā un izslēdzam to no citām šīs rindas, kolonnas un bloka šūnām. Piemēram: šajā tabulā ir trīs "vientuļnieki" (tie ir iezīmēti dzeltenā krāsā).

slēptie vientuļnieki

Ja šūnā ir vairāki kandidāti, bet viens no tiem nav atrodams nevienā citā dotās rindas (kolonnas vai bloka) šūnā, tad šādu kandidātu sauc par “slēpto vientuļnieku”. Nākamajā piemērā kandidāts "4" zaļajā blokā ir atrodams tikai centrālajā šūnā. Tātad šajā šūnā noteikti būs “4”. Šajā šūnā ievadām "4" un izsvītrojam to no citām 2. kolonnas un 5. rindas šūnām. Tāpat dzeltenajā kolonnā kandidāts "2" parādās vienreiz, tāpēc šajā šūnā ievadām "2" un izslēdzam "2" no 7. rindas šūnām un atbilstošā bloka.

Iepriekšējās divas metodes ir vienīgās metodes, kas unikāli nosaka šūnas saturu. Sekojošās metodes ļauj tikai samazināt kandidātu skaitu šūnās, kas agrāk vai vēlāk novedīs pie vientuļniekiem vai slēptiem vientuļniekiem.

Bloķēts kandidāts

Ir gadījumi, kad kandidāts blokā atrodas tikai vienā rindā (vai vienā kolonnā). Sakarā ar to, ka vienā no šīm šūnām noteikti būs šis kandidāts, šo kandidātu var izslēgt no visām pārējām šīs rindas (kolonnas) šūnām.

Tālāk esošajā piemērā centrālajā blokā ir kandidāts "2" tikai centrālajā kolonnā (dzeltenās šūnas). Tātad vienai no šīm divām šūnām noteikti ir jābūt "2", un neviena cita šūna šajā rindā ārpus šī bloka nevar būt "2". Tāpēc "2" var izslēgt kā kandidātu no citām šīs kolonnas šūnām (šūnas zaļā krāsā).

Atveriet Pairs

Ja divās grupas šūnās (rindā, kolonnā, blokā) ir identisks kandidātu pāris un nekas cits, tad nevienai citai šīs grupas šūnai nevar būt šī pāra vērtība. Šos 2 kandidātus var izslēgt no citām grupas šūnām. Tālāk esošajā piemērā kandidāti "1" un "5" astotajā un devītajā kolonnā veido atvērtu pāri blokā (dzeltenās šūnas). Tāpēc, tā kā vienai no šīm šūnām ir jābūt "1", bet otrai jābūt "5", kandidāti "1" un "5" tiek izslēgti no visām pārējām šī bloka šūnām (zaļajām šūnām).

To pašu var noformulēt 3 un 4 kandidātiem, piedalās jau attiecīgi tikai 3 un 4 šūnas. Atvērtie trīskārši: no zaļajām šūnām mēs izslēdzam dzelteno šūnu vērtības.

Atvērtie četrinieki: no zaļajām šūnām mēs izslēdzam dzelteno šūnu vērtības.

slēptie pāri

Ja grupas divās šūnās (rindā, kolonnā, blokā) ir kandidāti, starp kuriem ir identisks pāris, kas neatrodas nevienā citā šī bloka šūnā, tad nevienai citai šīs grupas šūnai nevar būt šī pāra vērtība. Tāpēc visus pārējos šo divu šūnu kandidātus var izslēgt. Tālāk esošajā piemērā kandidāti "7" un "5" centrālajā kolonnā ir tikai dzeltenās šūnās, kas nozīmē, ka visus pārējos kandidātus no šīm šūnām var izslēgt.

Tāpat jūs varat meklēt slēptos trīskāršos un četriniekus.

x-wing

Ja vērtībai ir tikai divas iespējamās atrašanās vietas rindā (kolonnā), tad tā ir jāpiešķir vienai no šīm šūnām. Ja ir vēl viena rinda (kolonna), kur viens un tas pats kandidāts var atrasties arī tikai divās šūnās un šo šūnu kolonnas (rindas) ir vienādas, tad nevienā citā šo kolonnu (rindu) šūnā šis skaitlis nevar būt. Apsveriet piemēru:

4. un 5. rindiņā skaitlis "2" var būt tikai divās dzeltenās šūnās, un šīs šūnas atrodas tajās pašās kolonnās. Tāpēc skaitli "2" var rakstīt tikai divos veidos: 1) ja 4. rindas 5. ailē ir ierakstīts "2", tad no dzeltenajām šūnām jāizslēdz "2" un tad 5. rindā pozīciju "2" unikāli nosaka 7. kolonna.

2) ja 4.rindas 7.ailē ir ierakstīts “2”, tad no dzeltenajām šūnām jāizslēdz “2” un tad 5.rindā pozīciju “2” unikāli nosaka 5.aile.

Tāpēc 5. un 7. slejā noteikti būs skaitlis "2" vai nu 4. rindā, vai 5. rindā. Tad skaitli "2" var izslēgt no citām šo kolonnu šūnām (zaļajām šūnām).

"Zobenzivs" (zobenzivs)

Šī metode ir .

No mīklas noteikumiem izriet, ka, ja kandidāts atrodas trīs rindās un tikai trīs kolonnās, tad pārējās rindās šo kandidātu šajās ailēs var izslēgt.

Algoritms:

• Mēs meklējam rindas, kurās kandidāts parādās ne vairāk kā trīs reizes, bet tajā pašā laikā tas pieder tieši trim kolonnām.
• Mēs izslēdzam kandidātu no šīm trim kolonnām no citām rindām.

Tāda pati loģika attiecas uz trīs kolonnām, kur kandidāts ir ierobežots līdz trim rindām.

Apsveriet piemēru. Trīs rindās (3., 5. un 7.) kandidāts "5" parādās ne vairāk kā trīs reizes (šūnas ir iezīmētas dzeltenā krāsā). Taču tās pieder tikai trim kolonnām: 3., 4. un 7.. Saskaņā ar “Zobenzivs” metodi kandidātu “5” var izslēgt no citām šo kolonnu šūnām (zaļajām šūnām).

Tālāk esošajā piemērā tiek izmantota arī Zobenzivs metode, bet trīs kolonnu gadījumā. Kandidātu "1" izslēdzam no zaļajām šūnām.

"X-wing" un "Swordfish" var vispārināt līdz četrām rindām un četrām kolonnām. Šī metode tiks saukta par "Medusa".

Krāsas

Ir situācijas, kad kandidāts grupā parādās tikai divas reizes (rindā, kolonnā vai blokā). Tad vēlamais cipars noteikti būs kādā no tiem. Krāsu metodes stratēģija ir skatīt šīs attiecības, izmantojot divas krāsas, piemēram, dzelteno un zaļo. Šajā gadījumā šķīdums var būt tikai vienas krāsas šūnās.

Mēs atlasām visas savstarpēji saistītās ķēdes un pieņemam lēmumu:

• Ja kādam neēnotam kandidātam grupā ir divi dažādu krāsu kaimiņi (rinda, kolonna vai bloks), to var izslēgt.
• Ja grupā (rindā, kolonnā vai blokā) ir divas identiskas krāsas, šī krāsa ir nepatiesa. Kandidātu no visām šīs krāsas šūnām var izslēgt.

Nākamajā piemērā izmantojiet metodi "Krāsas" šūnām ar kandidātu "9". Mēs sākam krāsot no šūnas augšējā kreisajā blokā (2. rinda, 2. kolonna), krāsojam to dzeltenā krāsā. Savā blokā tam ir tikai viens kaimiņš ar "9", nokrāsosim zaļu. Arī viņai kolonnā ir tikai viena kaimiņiene, krāsojam pāri zaļā krāsā.

Līdzīgi mēs strādājam ar pārējām šūnām, kurās ir skaitlis "9". Mēs iegūstam:

Kandidāts "9" var būt vai nu tikai visās dzeltenajās šūnās, vai pilnīgi zaļā krāsā. Labajā vidējā blokā satikās divas vienādas krāsas šūnas, tāpēc zaļā krāsa ir nepareiza, jo šis bloks rada divus "9", kas ir nepieņemami. Mēs izslēdzam "9" no visām zaļajām šūnām.

Vēl viens "Krāsu" metodes piemērs. Atzīmēsim sapārotas šūnas kandidātam "6".

Šūnā ar "6" augšējā centrālajā blokā (izcelta ceriņkrāsā) ir divi daudzkrāsaini kandidāti:

"6" noteikti būs dzeltenā vai zaļā šūnā, tāpēc "6" var izslēgt no šīs ceriņu krāsas šūnas.

Pirmā lieta, kas būtu jānosaka problēmu risināšanas metodoloģijā, ir jautājums par reālu izpratni par to, ko mēs sasniedzam un varam sasniegt problēmu risināšanas ziņā. Sapratne parasti tiek uzskatīta par kaut ko pašsaprotamu, un mēs aizmirstam par to, ka izpratnei ir noteikts izpratnes sākumpunkts, tikai attiecībā uz kuru mēs varam teikt, ka izpratne patiešām notiek no konkrēta mūsu noteikta brīža. Sudoku šeit, mūsuprāt, ir ērts ar to, ka, izmantojot savu piemēru, tas ļauj zināmā mērā modelēt problēmu izpratnes un risināšanas jautājumus. Tomēr sāksim ar vairākiem citiem un ne mazāk svarīgiem piemēriem kā Sudoku.

Fiziķis, kurš pēta īpašo relativitāti, varētu runāt par Einšteina "kristāldzidrajiem" priekšlikumiem. Es uzgāju šo frāzi vienā no interneta vietnēm. Bet kur sākas šī "kristāla skaidrības" izpratne? Tas sākas ar postulātu matemātiskā apzīmējuma asimilāciju, no kuras pēc zināmiem un saprotamiem noteikumiem var uzbūvēt visas SRT daudzlīmeņu matemātiskās konstrukcijas. Bet tas, ko fiziķis, tāpat kā es, nesaprot, kāpēc SRT postulāti darbojas tā, nevis citādi.

Pirmkārt, lielais vairums šo doktrīnu apspriežošo nesaprot, kas īsti slēpjas postulātā par gaismas ātruma nemainīgumu tulkojumā no tā matemātiskā pielietojuma uz realitāti. Un šis postulāts nozīmē gaismas ātruma nemainīgumu visās iedomājamās un neiedomājamās nozīmēs. Gaismas ātrums ir nemainīgs attiecībā pret jebkuriem vienlaicīgi atpūšošiem un kustīgiem objektiem. Gaismas stara ātrums saskaņā ar postulātu ir nemainīgs pat attiecībā pret pretimnākošo, šķērsvirziena un attālināto gaismas staru. Un tajā pašā laikā mums ir tikai tādi mērījumi, kas ir netieši saistīti ar gaismas ātrumu, kas tiek interpretēts kā tā noturība.

Ņūtona likumi fiziķim un pat tiem, kas vienkārši studē fiziku, ir tik pazīstami, ka šķiet tik saprotami kā kaut kas pašsaprotams, un citādi nevar būt. Bet, teiksim, universālās gravitācijas likuma piemērošana sākas ar tā matemātisko apzīmējumu, pēc kura var aprēķināt pat kosmosa objektu trajektorijas un orbītu raksturlielumus. Bet kāpēc šie likumi darbojas tā un ne citādi - tādas izpratnes mums nav.

Tāpat ar Sudoku. Internetā jūs varat atrast vairākkārt atkārtotus aprakstus par "pamata" veidiem, kā atrisināt Sudoku problēmas. Ja atceraties šos noteikumus, varat saprast, kā šī vai cita Sudoku problēma tiek atrisināta, piemērojot "pamata" noteikumus. Bet man ir jautājums: vai mēs saprotam, kāpēc šīs "pamata" metodes darbojas tā, nevis citādi.

Tāpēc mēs pārejam uz nākamo galveno punktu problēmu risināšanas metodoloģijā. Izpratne ir iespējama tikai pamatojoties uz kādu modeli, kas dod pamatu šai izpratnei un spējai veikt kādu dabisku vai domu eksperimentu. Bez tā mums var būt tikai noteikumi apgūto sākumpunktu piemērošanai: SRT postulāti, Ņūtona likumi vai Sudoku "pamata" veidi.

Mums nav un principā nevar būt modeļu, kas atbilstu gaismas ātruma neierobežotās konstantes postulātam. Mēs to nedarām, taču var izgudrot nepierādāmus modeļus, kas atbilst Ņūtona likumiem. Un ir tādi "Ņūtona" modeļi, bet tie kaut kā nepārsteidz ar produktīvām iespējām veikt pilna mēroga vai domu eksperimentu. Taču Sudoku sniedz mums iespējas, ko varam izmantot, lai izprastu faktiskās Sudoku problēmas un ilustrētu modelēšanu kā vispārēju pieeju problēmu risināšanai.

Viens no iespējamiem Sudoku problēmu modeļiem ir darblapa. Tas tiek izveidots, vienkārši aizpildot visas uzdevumā norādītās tabulas tukšās šūnas (šūnas) ar cipariem 123456789. Pēc tam uzdevums tiek reducēts līdz visu lieko ciparu secīgai izņemšanai no šūnām, līdz tiek aizpildītas visas tabulas šūnas. aizpildīts ar atsevišķiem (ekskluzīviem) cipariem, kas apmierina problēmas nosacījumu.

Es veidoju šādu darblapu programmā Excel. Pirmkārt, es atlasu visas tukšās tabulas šūnas (šūnas). Nospiežu F5-"Atlasīt"-"Tukšas šūnas"-"Labi". Vispārīgāks veids, kā atlasīt vēlamās šūnas: turiet nospiestu taustiņu Ctrl un noklikšķiniet ar peli, lai atlasītu šīs šūnas. Pēc tam atlasītajām šūnām iestatīju krāsu uz zilu, izmēru 10 (oriģināls - 12) un fontu Arial Narrow. Tas viss, lai turpmākās izmaiņas tabulā būtu skaidri redzamas. Tālāk tukšās šūnās ievadu skaitļus 123456789. Daru šādi: pierakstu un saglabāju šo numuru atsevišķā šūnā. Tad es nospiežu F2, atlasu un nokopēju šo numuru ar Ctrl + C darbību. Tālāk dodos uz tabulas šūnām un, secīgi apejot visas tukšās šūnas, ar operāciju Ctrl+V ievadu tajās numuru 123456789, un darblapa gatava.

Papildu numurus, kas tiks apspriesti vēlāk, es svītroju šādi. Ar operāciju Ctrl + peles klikšķis - es atlasu šūnas ar papildu numuru. Tad es nospiežu Ctrl + H un atveramā loga augšējā laukā ievadu dzēšamo numuru, un apakšējam laukam jābūt pilnīgi tukšam. Pēc tam atliek noklikšķināt uz opcijas "Aizstāt visu", un papildu numurs tiek noņemts.

Spriežot pēc tā, ka man ierastajos "pamata" veidos parasti izdodas veikt sarežģītāku tabulu apstrādi nekā internetā sniegtajos piemēros, darblapa ir visvienkāršākais rīks Sudoku uzdevumu risināšanā. Turklāt daudzas situācijas saistībā ar sarežģītāko tā saukto "pamata" noteikumu piemērošanu manā darblapā vienkārši neradās.

Tajā pašā laikā darblapa ir arī modelis, uz kura var veikt eksperimentus, pēc tam identificējot visus "pamata" noteikumus un dažādas to piemērošanas nianses, kas izriet no eksperimentiem.

Tātad, pirms jums ir darblapas fragments ar deviņiem blokiem, kas numurēti no kreisās puses uz labo un no augšas uz leju. Šajā gadījumā mums ir ceturtais bloks, kas aizpildīts ar numuriem 123456789. Šis ir mūsu modelis. Ārpus bloka mēs sarkanā krāsā iezīmējām "aktivizētos" (galīgi definētos) skaitļus, šajā gadījumā četriniekus, kurus mēs plānojam aizstāt veidojamajā tabulā. Zilie piecinieki ir skaitļi, kas vēl nav noteikti attiecībā uz viņu turpmāko lomu, par ko mēs runāsim vēlāk. Mūsu piešķirtie aktivizētie cipari it kā izsvītro, izstumj, dzēš - kopumā tie blokā izspiež vienus un tos pašus ciparus, tāpēc tur ir attēloti bālā krāsā, simbolizējot to, ka šie bālie cipari ir bijuši dzēsts. Gribējās šo krāsu padarīt vēl bālāku, bet tad tās varētu kļūt pavisam neredzamas, skatoties internetā.

Rezultātā ceturtajā blokā, šūnā E5, bija viens, arī aktivizēts, bet paslēpts četri. "Aktivizēta", jo viņa, savukārt, var arī noņemt papildu ciparus, ja tie ir ceļā, un "paslēpta", jo viņa ir starp citiem cipariem. Ja šūnai E5 uzbrūk pārējie, izņemot 4, aktivizētie numuri 12356789, tad E5 parādīsies "pliks" vientuļnieks - 4.

Tagad noņemsim vienu aktivizēto četrinieku, piemēram, no F7. Tad četrinieks aizpildītajā blokā var būt jau un tikai šūnā E5 vai F5, paliekot aktivizēts 5. rindā. Ja šajā situācijā ir iesaistīti aktivizētie piecinieki, bez F7=4 un F8=5, tad šūnās E5 un F5 tur ir. būs pliks vai slēpts aktivizēts pāris 45.

Pēc tam, kad esi pietiekami izstrādājis un sapratis dažādas iespējas ar plikiem un slēptiem vieniniekiem, divniekiem, trijiem utt. ne tikai blokos, bet arī rindās un kolonnās varam pāriet uz citu eksperimentu. Izveidosim tukšu pāri 45, kā to darījām iepriekš, un tad savienosim aktivizētos F7=4 un F8=5. Rezultātā izveidosies situācija E5=45. Līdzīgas situācijas ļoti bieži rodas darba lapas apstrādes procesā. Šī situācija nozīmē, ka vienam no šiem cipariem, šajā gadījumā 4 vai 5, obligāti jābūt blokā, rindā un kolonnā, kas ietver šūnu E5, jo visos šajos gadījumos ir jābūt diviem cipariem, nevis vienam no tiem.

Un pats galvenais, mēs jau zinām, cik bieži rodas situācijas, piemēram, E5=45. Līdzīgā veidā mēs definēsim situācijas, kad vienā šūnā parādās ciparu trīskāršs utt. Un, kad mēs novedam šo situāciju izpratnes un uztveres pakāpi līdz pašsaprotamības un vienkāršības stāvoklim, tad nākamais solis ir, tā sakot, situāciju zinātniska izpratne: tad mēs varēsim veikt statistisku analīzi par šīm situācijām. Sudoku tabulas, identificējiet modeļus un izmantojiet uzkrāto materiālu, lai atrisinātu vissarežģītākās problēmas.

Tādējādi, eksperimentējot ar modeli, mēs iegūstam vizuālu un pat "zinātnisku" slēptu vai atvērtu singlu, pāru, trīskāršu utt. Ja aprobežojaties ar darbībām ar aprakstīto vienkāršo modeli, dažas jūsu idejas izrādīsies neprecīzas vai pat kļūdainas. Taču, tiklīdz pāries uz konkrētu problēmu risināšanu, sākotnējo ideju neprecizitātes ātri vien nāks gaismā, bet modeļi, uz kuriem veikti eksperimenti, būs jāpārdomā un jāpilnveido. Tas ir neizbēgams hipotēžu un precizējumu ceļš jebkuru problēmu risināšanā.

Man jāsaka, ka slēptie un atvērtie singli, kā arī atvērtie pāri, trīskārši un pat četrinieki ir izplatītas situācijas, kas rodas, risinot Sudoku problēmas ar darblapu. Slēptie pāri bija reti. Un šeit ir slēptie trīskārši, četrinieki utt. Man kaut kā nesanāca apstrādājot darblapas, tāpat kā internetā vairākkārt aprakstītās “x-wing” un “zobenzivs” kontūru apiešanas metodes, kurās ir “kandidāti” dzēšanai ar kādu no divi alternatīvi kontūru apiešanas veidi. Šo metožu nozīme: ja iznīcinām "kandidātu" x1, tad paliek ekskluzīvais kandidāts x2 un tajā pašā laikā kandidāts x3 tiek dzēsts, un ja iznīcinām x2, tad paliek ekskluzīvais x1, bet šajā gadījumā kandidāts Arī x3 tiek dzēsts, tāpēc jebkurā gadījumā x3 ir jāsvītro , pagaidām neskarot kandidātus x1 un x2. Vispārīgāk runājot, šis ir īpašs situācijas gadījums: ja divi alternatīvi veidi rada vienu un to pašu rezultātu, tad šo rezultātu var izmantot, lai atrisinātu Sudoku problēmu. Šajā, vispārīgākā, situācijā es sastapu situācijas, bet ne "x-wing" un "swordfish" variantos, un ne risinot Sudoku problēmas, kurām pietiek ar zināšanām tikai par "pamata" pieejām.

Darblapas izmantošanas iespējas var parādīt šajā netriviālajā piemērā. Vienā no sudoku risinātāju forumiem http://zforum.net/index.php?topic=3955.25;wap2 es saskāros ar problēmu, kas tika pasniegta kā viena no grūtākajām sudoku problēmām, kas nav atrisināma parastajos veidos, neizmantojot uzskaiti ar pieņēmumi par šūnās aizvietotajiem skaitļiem. Parādīsim, ka ar darba tabulu šo problēmu var atrisināt bez šāda uzskaitījuma:

Labajā pusē ir sākotnējais uzdevums, pa kreisi ir darba tabula pēc "dzēšanas", t.i. parastā papildu ciparu noņemšanas darbība.

Pirmkārt, vienosimies par apzīmējumu. ABC4=689 nozīmē, ka šūnās A4, B4 un C4 ir skaitļi 6, 8 un 9 — viens vai vairāki cipari katrā šūnā. Tāpat ir ar stīgām. Tādējādi B56=24 nozīmē, ka šūnās B5 un B6 ir skaitļi 2 un 4. Zīme ">" ir nosacījuma darbības zīme. Tādējādi D4=5>I4-37 nozīmē, ka ziņojuma D4=5 dēļ šūnā I4 jāievieto skaitlis 37. Vēstījums var būt izteikts – “kails” – un slēpts, kas būtu jāatklāj. Ziņojuma ietekme var būt secīga (pārraidīta netieši) pa ķēdi un paralēli (darboties tieši uz citām šūnām). Piemēram:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3; (D8=1)+(G9=3)>G8-7>G7-1>G5-5

Šis ieraksts nozīmē, ka D3=2, bet šis fakts ir jāatklāj. D8=1 nodod savu darbību uz ķēdi uz A3 un 4 jāraksta uz A3; tajā pašā laikā D3=2 iedarbojas tieši uz G9, kā rezultātā G9-3. (D8=1)+(G9=3)>G8-7 – faktoru (D8=1) un (G9=3) kopējā ietekme noved pie rezultāta G8-7. utt.

Ieraksti var ietvert arī H56/68 tipa kombināciju. Tas nozīmē, ka skaitļi 6 un 8 ir aizliegti šūnās H5 un H6, t.i. tie ir jāizņem no šīm šūnām.

Tātad, sākam strādāt ar tabulu un iesākumam piemērojam labi manifestēto, pamanāmo nosacījumu ABC4=689. Tas nozīmē, ka visās pārējās (izņemot A4, B4 un C4) 4. bloka šūnās (vidū, pa kreisi) un 4. rindā skaitļi 6, 8 un 9 ir jāsvītro:

Uzklājiet B56=24 tādā pašā veidā. Kopā mums ir D4=5 un (pēc D4=5>I4-37) HI4=37, kā arī (pēc B56=24>C6-1) C6=1. Piemērosim šo darblapai:

In I89=68slēpts>I56/68>H56-68: t.i. šūnās I8 un I9 ir slēpts 5. un 6. ciparu pāris, kas aizliedz šiem cipariem atrasties I56, kā rezultātā tiek iegūts rezultāts H56-68. Šo fragmentu varam aplūkot savādāk, tāpat kā to darījām eksperimentos ar darblapas modeli: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. Tas ir, divvirzienu "uzbrukums" (G23=68) un (AD7=68) noved pie tā, ka I8 un I9 var atrasties tikai skaitļi 6 un 8. Tālāk (I89=68) ir savienots ar " uzbrukums" H56 kopā ar iepriekšējiem nosacījumiem, kas noved pie H56-68. Papildus šim "uzbrukumam" ir pieslēgts (ABC4=689), kas šajā piemērā izskatās lieks, tomēr, ja strādātu bez darba galda, tad trieciena faktors (ABC4=689) tiktu paslēpts, un tas būtu diezgan lietderīgi tam pievērst īpašu uzmanību.

Nākamā darbība: I5=2>G1-2,G6-9,B6-4,B5-2.

Es ceru, ka tas ir skaidrs jau bez komentāriem: aizstājiet ciparus, kas nāk aiz domuzīmes, jūs nevarat kļūdīties:

H7=9>I7-4; D6=8>D1-4,H6-6>H5-8:

Nākamā darbību sērija:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3;

(D8=1)+(G9=3)>G8-7>G7-1>G5-5;

D5=9>E5-6>F5-4:

I=4>C9-4>C7-2>E9-2>EF7-35>B7-7, F89-89,

tas ir, "izsvītrošanas" - papildu ciparu dzēšanas - rezultātā šūnās F8 un F9 parādās atvērts, "kails" pāris 89, ko kopā ar citiem ierakstā norādītajiem rezultātiem attiecinām uz tabulu:

H2=4>H3-1>F2-1>F1-6>A1-3>B8-3,C8-5,H1-7>I2-5>I3-3>I4-7>H4-3

Viņu rezultāts:

Tam seko diezgan ierastas, acīmredzamas darbības:

H1=7>C1-8>E1-5>F3-7>E2-9>E3-8,C3-9>B3-5>B2-6>C2-7>C4-6>A4-9>B4- astoņi;

B2=6>B9-9>A8-6>I8-8>F8-9>F9-8>I9-6;

E7=3>F7-5,E6-7>F6-3

Viņu rezultāts: problēmas galīgais risinājums:

Tā vai citādi mēs pieņemsim, ka mēs izdomājām "pamata" metodes Sudoku vai citās intelektuālās pielietošanas jomās, pamatojoties uz šim piemērotu modeli un pat iemācījāmies tās pielietot. Bet tā ir tikai daļa no mūsu progresa problēmu risināšanas metodoloģijā. Turklāt, es atkārtoju, tas ne vienmēr tiek ņemts vērā, bet gan neaizstājams posms iepriekš apgūto metožu nogādāšanai līdz to izmantošanas vienkāršībai. Atrisinot piemērus, izprotot šī risinājuma rezultātus un metodes, pārdomājot šo materiālu uz pieņemtā modeļa pamata, vēlreiz pārdomājot visus variantus, nogādājot to izpratnes pakāpi līdz automātiskumam, kad risinājums, izmantojot "pamata" nosacījumus, kļūst par rutīnu. un pazūd kā problēma. Ko tas dod: katram tas jājūt pēc savas pieredzes. Un būtība ir tāda, ka, problēmsituācijai kļūstot par rutīnu, intelekta meklēšanas mehānisms tiek virzīts uz arvien sarežģītāku noteikumu izstrādi risināmo problēmu jomā.

Un kas ir "sarežģītāki noteikumi"? Tie ir tikai jauni "pamata" nosacījumi problēmas risināšanā, kuru izpratni savukārt var novest arī līdz vienkāršības stāvoklim, ja tiek atrasts šim nolūkam piemērots modelis.

Rakstā Vasiļenko S.L. "Numeric Harmony Sudoku" Es atrodu problēmas piemēru ar 18 simetriskiem taustiņiem:

Attiecībā uz šo uzdevumu teikts, ka ar "pamata" metodēm to var atrisināt tikai līdz noteiktam stāvoklim, pēc kura sasniegšanas atliek tikai pielietot vienkāršu uzskaitījumu ar izmēģinājuma aizstāšanu dažu it kā ekskluzīvu (viena, vienota) šūnās. ) cipari. Šis stāvoklis (nedaudz tālāk nekā Vasiļenko piemērā) izskatās šādi:

Ir tāds modelis. Tas ir sava veida rotācijas mehānisms identificētiem un neidentificētiem ekskluzīviem (vieniem) cipariem. Vienkāršākajā gadījumā daži ekskluzīvu ciparu trīskārši griežas labajā vai kreisajā virzienā, ejot garām šai grupai no rindas uz rindu vai no kolonnas uz kolonnu. Kopumā tajā pašā laikā trīs skaitļu trīskāršu grupas griežas vienā virzienā. Sarežģītākos gadījumos trīs ekskluzīvu ciparu pāri griežas vienā virzienā, bet trīskārši ciparu griežas pretējā virzienā. Tātad, piemēram, ekskluzīvie cipari pirmajās trīs aplūkojamās problēmas rindās tiek pagriezti. Un, pats galvenais, šāda veida rotāciju var redzēt, ņemot vērā skaitļu atrašanās vietu apstrādātajā darblapā. Ar šo informāciju pagaidām pietiek, un citas rotācijas modeļa nianses sapratīsim problēmas risināšanas procesā.

Tātad pirmajās (augšējās) trīs rindās (1, 2 un 3) mēs varam pamanīt pāru (3+8) un (7+9), kā arī (2+x1) ar nezināmu x1 un singlu trīskāršs (x2+4+ 1) ar nezināmu x2. To darot, mēs varam secināt, ka katrs no x1 un x2 var būt vai nu 5, vai 6.

4., 5. un 6. rindā aplūkoti pāri (2+4) un (1+3). Jābūt arī trešajam nezināmajam pārim un singlu trīskāršam, no kuriem zināms tikai viens cipars 5.

Līdzīgi mēs aplūkojam 789. rindu, pēc tam kolonnu ABC, DEF un GHI trīskāršus. Apkopoto informāciju pierakstīsim simboliskā un, ceru, visai saprotamā formā:

Pagaidām šī informācija mums ir nepieciešama tikai, lai izprastu vispārējo situāciju. Rūpīgi pārdomājiet to, un tad mēs varam pāriet tālāk pie šādas īpaši šim nolūkam sagatavotas tabulas:

Alternatīvas izcēlu ar krāsām. Zils nozīmē "atļauts", bet dzeltens - "aizliegts". Ja, teiksim, atļauts A2=79 atļauts A2=7, tad C2=7 ir aizliegts. Vai arī otrādi – atļauts A2=9, aizliegts C2=9. Un tad atļaujas un aizliegumi tiek pārraidīti pa loģisku ķēdi. Šī krāsošana tiek veikta, lai būtu vieglāk aplūkot dažādas alternatīvas. Kopumā šī ir zināma līdzība ar "x-wing" un "swordfish" metodēm, kas minētas iepriekš, apstrādājot tabulas.

Apskatot opcijas B6=7 un attiecīgi B7=9, mēs uzreiz varam atrast divus punktus, kas nav savienojami ar šo opciju. Ja B7=9, tad rindās 789 rodas sinhroni rotējošs trīskāršs, kas nav pieļaujams, jo sinhroni (vienā virzienā) var griezties vai nu tikai trīs pāri (un tiem asinhroni trīs singli), vai trīs trīskārši (bez singliem). Turklāt, ja B7=9, tad pēc vairākām darblapas apstrādes soļiem 7. rindā konstatēsim nesaderību: B7=D7=9. Tātad mēs aizstājam vienīgo pieņemamo no abām alternatīvām B6=9, un tad problēma tiek atrisināta ar vienkāršiem tradicionālās apstrādes līdzekļiem bez aklas uzskaitīšanas:

Tālāk man ir gatavs piemērs, izmantojot rotācijas modeli, lai atrisinātu problēmu no Pasaules sudoku čempionāta, bet es izlaižu šo piemēru, lai pārāk nesastieptu šo rakstu. Turklāt, kā izrādījās, šai problēmai ir trīs risinājumi, kas ir slikti piemēroti sākotnējai ciparu rotācijas modeļa izstrādei. Es arī daudz pūžoju no interneta izvilkto Gerija Makgaira 17 taustiņu uzdevumu, lai atrisinātu viņa mīklu, līdz ar vēl lielāku īgnumu uzzināju, ka šai "mīklai" ir vairāk nekā 9 tūkstoši risinājumu.

Tā nu gribot negribot ir jāpāriet pie Arto Inkala izstrādātās "visgrūtākās pasaulē" Sudoku problēmas, kurai, kā zināms, ir unikāls risinājums.

Pēc divu diezgan acīmredzamu ekskluzīvu skaitļu ievadīšanas un darblapas apstrādes uzdevums izskatās šādi:

Sākotnējai problēmai piešķirtie taustiņi ir izcelti melnā krāsā un ar lielāku fontu. Lai virzītos uz priekšu šīs problēmas risināšanā, mums atkal jāpaļaujas uz šim nolūkam piemērotu modeli. Šis modelis ir sava veida skaitļu rotācijas mehānisms. Par to jau ir runāts ne reizi vien šajā un iepriekšējos rakstos, taču, lai izprastu tālāko raksta materiālu, šis mehānisms būtu rūpīgi jāpārdomā un jāizstrādā. Apmēram tā, it kā ar šādu mehānismu būtu strādājis desmit gadus. Bet jūs tomēr varēsiet saprast šo materiālu, ja ne no pirmā lasījuma, tad no otrā vai trešā utt. Turklāt, ja jūs neatlaidīsieties, jūs nogādāsit šo "grūti saprotamo" materiālu tā ierastajā un vienkāršības stāvoklī. Šajā ziņā nav nekā jauna: tas, kas sākumā ir ļoti grūti, pamazām kļūst ne tik sarežģīts, un, turpinot nemitīgu pilnveidošanu, viss kļūst visredzamākais un neprasa prāta piepūli savā vietā, pēc kura jūs varat atbrīvot savu garīgo. turpmāka virzība uz risināmo problēmu vai citām problēmām.

Rūpīga Arto Inkala problēmas struktūras analīze parāda, ka visa problēma ir veidota uz trīs sinhroni rotējošu pāru un asinhroni rotējošu singlu pāru trīskārša principa: (x1+x2)+(x3+x4)+(x5+ x6)+(x7+x8+ x9). Rotācijas secība var būt, piemēram, šāda: pirmajās trīs rindās 123 pirmais pāris (x1+x2) iet no pirmā bloka pirmās rindas uz otrā bloka otro rindu, tad uz trešo. trešā bloka līnija. Otrais pāris lec no pirmā bloka otrās rindas uz otrā bloka trešo rindu, tad šajā rotācijā lec uz trešā bloka pirmo rindu. Trešais pāris no pirmā bloka trešās rindas pārlec uz otrā bloka pirmo rindu un pēc tam tajā pašā rotācijas virzienā pārlec uz trešā bloka otro rindu. Vieninieku trijotne pārvietojas līdzīgā rotācijas shēmā, bet pretējā virzienā nekā pāriem. Situācija ar kolonnām izskatās līdzīgi: ja tabulu garīgi (vai faktiski) pagriež par 90 grādiem, tad rindas kļūs par kolonnām ar tādu pašu singlu un pāru kustības raksturu kā iepriekš rindām.

Pārvēršot šīs rotācijas mūsu prātā saistībā ar Arto Incal problēmu, mēs pakāpeniski saprotam acīmredzamos ierobežojumus šīs rotācijas variantu izvēlei izvēlētajam rindu vai kolonnu trīskāršam:

Nevajadzētu būt sinhroni (vienā virzienā) rotējošiem trīnīšiem un pāriem - šādi trīnīši, atšķirībā no vientuļnieku tripleta, turpmāk tiks saukti par trīnīšiem;

Nedrīkst būt savstarpēji asinhroni pāri vai viens ar otru asinhroni singli;

Nedrīkst būt gan pāriem, gan vieniniekiem, kas rotē vienā (piemēram, pa labi) virzienā – tas ir iepriekšējo ierobežojumu atkārtojums, taču tas var šķist saprotamāk.

Turklāt ir arī citi ierobežojumi:

9 rindās nedrīkst būt neviens pāris, kas atbilst pārim nevienā no kolonnām, un tas pats attiecas uz kolonnām un rindām. Tam vajadzētu būt acīmredzamam: jo pats fakts, ka divi skaitļi atrodas vienā rindā, norāda, ka tie atrodas dažādās kolonnās.

Varat arī teikt, ka ļoti reti ir pāru sakritības dažādās rindu trīskāršās vai līdzīgas sakritības kolonnu trīskāršās, kā arī reti ir singlu trīskāršu atbilstības rindās un/vai kolonnās, bet tās ir, tā sakot. , varbūtības modeļi.

Pētījuma bloki 4,5,6.

4.-6.blokos ir iespējami pāri (3+7) un (3+9). Ja pieņemam (3+9), tad iegūstam nederīgu tripleta sinhrono rotāciju (3+7+9), tātad mums ir pāris (7+3). Pēc šī pāra aizstāšanas un turpmākās tabulas apstrādes ar parastajiem līdzekļiem mēs iegūstam:

Tajā pašā laikā mēs varam teikt, ka 5 B6=5 var būt tikai vientuļnieks, asinhrons (7+3), un 6 I5=6 ir paraģenerators, jo tas atrodas tajā pašā rindā H5=5 sestajā. bloks, un tāpēc tas nevar būt viens un var pārvietoties tikai sinhroni ar (7+3.

un sakārtoja vientuļu kandidātus pēc viņu parādīšanās šajā lomā šajā tabulā:

Ja pieņemam, ka visbiežāk sastopamie 2, 4 un 5 ir vieninieki, tad saskaņā ar rotācijas noteikumiem ar tiem var apvienot tikai pārus: (7 + 3), (9 + 6) un (1 + 8) - a pāris (1 + 9) ir atmests, jo tas noliedz pāri (9 + 6). Turklāt pēc šo pāru un singlu aizstāšanas un tabulas turpmākas apstrādes, izmantojot parastās metodes, mēs iegūstam:

Tāda nepaklausīga tabula izrādījās - to negribas apstrādāt līdz galam.

Jums būs smagi jāstrādā un jāpamana, ka kolonnās ABC ir pāris (7 + 4) un ka 6 šajās kolonnās pārvietojas sinhroni ar 7, tāpēc 6 ir pāra savienojums, tāpēc kolonnā ir iespējamas tikai kombinācijas (6 + 3). 4. bloka "C" +8 vai (6+8)+3. Pirmā no šīm kombinācijām nedarbojas, jo tad 7. blokā ailē "B" parādīsies nederīgs sinhronais trīskāršs - triplets (6 + 3 + 8). Nu, pēc opcijas (6 + 8) + 3 aizstāšanas un tabulas apstrādes parastajā veidā mēs nonākam pie veiksmīgas uzdevuma izpildes.

Otrais variants: atgriezīsimies pie tabulas, kas iegūta pēc kombinācijas (7 + 3) + 5 identificēšanas 456. rindā un turpināsim kolonnu ABC izpēti.

Šeit mēs varam pamanīt, ka pāris (2+9) nevar notikt ABC. Citas kombinācijas (2+4), (2+7), (9+4) un (9+7) dod sinhronu trīskāršu - tripletu A4+A5+A6 un B1+B2+B3, kas ir nepieņemami. Paliek viens pieņemams pāris (7+4). Turklāt 6 un 5 sinhroni pārvietojas 7, kas nozīmē, ka tie ir tvaiku veidojoši, t.i. veido dažus pārus, bet ne 5 + 6.

Izveidosim iespējamo pāru sarakstu un to kombinācijas ar singliem:

Kombinācija (6+3)+8 neder, jo pretējā gadījumā vienā kolonnā (6 + 3 + 8) tiek izveidots nederīgs triple-triplets, kas jau ir apspriests un ko mēs varam vēlreiz pārbaudīt, pārbaudot visas opcijas. No vienspēļu kandidātiem visvairāk punktu gūst numurs 3, bet visticamākais no visām iepriekš minētajām kombinācijām: (6 + 8) + 3, t.i. (C4=6 + C5=8) + C6=3, kas dod:

Turklāt visticamākais kandidāts vieniniekiem ir 2 vai 9 (katrs 6 punkti), bet jebkurā no šiem gadījumiem 1. kandidāts (4 punkti) paliek spēkā. Sāksim ar (5+29)+1, kur 1 ir asinhroni ar 5, t.i. ievietojiet 1 no B5=1 kā asinhronu singlu visās ABC kolonnās:

7. blokā A ailē ir iespējamas tikai opcijas (5+9)+3 un (5+2)+3. Bet mēs labāk pievērsīsim uzmanību tam, ka 1.-3. rindā tagad ir parādījušies pāri (4 + 5) un (8 + 9). To aizstāšana noved pie ātra rezultāta, t.i. līdz uzdevuma pabeigšanai pēc tam, kad tabula ir apstrādāta ar parastajiem līdzekļiem.

Nu, tagad, praktizējot iepriekšējās iespējas, mēs varam mēģināt atrisināt Arto Incal problēmu, neiesaistot statistiskās aplēses.

Mēs atkal atgriežamies sākuma pozīcijā:

4.-6.blokos ir iespējami pāri (3+7) un (3+9). Ja mēs pieņemam (3 + 9), mēs iegūstam nederīgu tripleta sinhrono rotāciju (3 + 7 + 9), tāpēc aizvietošanai tabulā mums ir tikai iespēja (7 + 3):

5 šeit, kā redzam, ir vientuļnieks, 6 ir paraformētājs. Derīgās opcijas ABC5: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1) +2. Bet (2+1) ir asinhrons ar (7+3), tāpēc ir (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. Jebkurā gadījumā 1 ir sinhrons (7 + 3) un tādējādi paraģenerējošs. Aizstāsim tabulā 1 šajā statusā:

Skaitlis 6 šeit ir paraģenerators bl. 4-6, bet uzkrītošā pāris (6+4) nav derīgo pāru sarakstā. Tādējādi četrstūris A4=4 ir asinhrons 6:

Tā kā D4+E4=(8+1) un saskaņā ar rotācijas analīzi veido šo pāri, mēs iegūstam:

Ja šūnas C456=(6+3)+8, tad B789=683, t.i. iegūstam sinhronu trīskāršu-tripletu, tātad mums paliek iespēja (6+8)+3 un tās aizstāšanas rezultāts:

B2=3 šeit ir viens, C1=5 (asinhronais 3) ir savienošana pārī, A2=8 ir arī savienošana pārī. B3=7 var būt gan sinhrons, gan asinhrons. Tagad varam sevi pierādīt sarežģītākos trikos. Ar trenētu aci (vai vismaz pārbaudot datorā) redzam, ka jebkuram statusam B3=7 - sinhrons vai asinhrons - iegūstam tādu pašu rezultātu A1=1. Tāpēc mēs varam aizstāt šo vērtību ar A1 un pēc tam izpildīt mūsu vai drīzāk Arto Incala uzdevumu ar ierastākiem vienkāršiem līdzekļiem:

Tā vai citādi, mēs varējām apsvērt un pat ilustrēt trīs vispārīgas pieejas problēmu risināšanai: noteikt problēmas izpratnes punktu (nevis hipotētisku vai akli deklarētu, bet reālu brīdi, no kura var runāt par problēmas izpratni ), izvēlieties modeli, kas ļauj realizēt izpratni, izmantojot dabisku vai mentālu eksperimentu, un, treškārt, šajā gadījumā sasniegto rezultātu izpratnes un uztveres pakāpi novest līdz pašsaprotamības un vienkāršības stāvoklim. Ir arī ceturtā pieeja, ko es personīgi izmantoju.

Katram cilvēkam ir stāvokļi, kad intelektuālie uzdevumi un problēmas, ar kurām viņš saskaras, tiek atrisinātas vieglāk nekā parasti. Šie stāvokļi ir diezgan atkārtojami. Lai to izdarītu, jums jāapgūst domu izslēgšanas tehnika. Sākumā vismaz uz sekundes daļu, pēc tam arvien vairāk stiepjot šo atvienošanas brīdi. Es nevaru pateikt, vai drīzāk ieteikt kaut ko šajā sakarā, jo šīs metodes piemērošanas ilgums ir tīri personisks jautājums. Bet es ķeros pie šīs metodes dažreiz ilgu laiku, kad manā priekšā rodas problēma, kurai es neredzu variantus, kā tai pieiet un atrisināt. Rezultātā agri vai vēlu no atmiņu krātuvēm iznirst piemērots modeļa prototips, kas noskaidro risināmā būtību.

Es atrisināju Inkalas problēmu vairākos veidos, ieskaitot iepriekšējos rakstos aprakstītos. Un vienmēr tā vai citādi es izmantoju šo ceturto pieeju ar izslēgšanos un sekojošu garīgo spēku koncentrēšanu. Es ieguvu ātrāko problēmas risinājumu, izmantojot vienkāršu uzskaitījumu - to, ko sauc par "poke metodi", taču, izmantojot tikai "garās" iespējas: tās, kas ātri varētu novest pie pozitīva vai negatīva rezultāta. Citas iespējas no manis prasīja vairāk laika, jo lielākā daļa laika tika veltīta vismaz aptuvenai šo iespēju izmantošanas tehnoloģijas izstrādei.

Labs risinājums ir arī ceturtās pieejas garā: noskaņojieties Sudoku problēmu risināšanai, problēmas risināšanas procesā aizvietojot tikai vienu ciparu katrā šūnā. Tas ir, lielākā daļa uzdevuma un tā datu tiek "ritināti" prātā. Šī ir galvenā intelektuālo problēmu risināšanas procesa daļa, un šī prasme ir jāapmāca, lai palielinātu spēju risināt problēmas. Piemēram, es neesmu profesionāls Sudoku risinātājs. Man ir citi uzdevumi. Bet tomēr es vēlos izvirzīt sev šādu mērķi: apgūt spēju risināt paaugstinātas sarežģītības Sudoku problēmas bez darblapas un neaizstājot vairāk nekā vienu ciparu vienā tukšā šūnā. Šajā gadījumā ir atļauts jebkurš Sudoku risināšanas veids, ieskaitot vienkāršu opciju uzskaitījumu.

Tā nav nejaušība, ka es šeit atceros iespēju uzskaitījumu. Jebkura pieeja Sudoku problēmu risināšanai ietver noteiktu metožu kopumu savā arsenālā, tostarp viena vai cita veida uzskaitīšanu. Turklāt jebkurai no metodēm, ko izmanto īpaši Sudoku vai citu problēmu risināšanā, ir sava efektīva pielietojuma joma. Tātad, risinot salīdzinoši vienkāršas Sudoku problēmas, visefektīvākās ir vienkāršas "pamata" metodes, kas aprakstītas daudzos rakstos par šo tēmu internetā, un sarežģītākā "rotācijas metode" šeit bieži vien ir bezjēdzīga, jo tā tikai sarežģī vienkāršs risinājums un tajā pašā laikā kas -nesniedz jaunu informāciju, kas parādās problēmas risināšanas gaitā. Bet vissarežģītākajos gadījumos, piemēram, Arto Inkala problēmai, "rotācijas metodei" var būt galvenā loma.

Manos rakstos Sudoku ir tikai ilustratīvs piemērs problēmu risināšanas pieejām. Starp manis atrisinātajām problēmām ir arī daudz grūtākas problēmas nekā Sudoku. Piemēram, katlu un turbīnu datormodeļi, kas atrodas mūsu vietnē. Es arī neiebilstu par viņiem runāt. Taču pagaidām Sudoku esmu izvēlējies, lai saviem jaunajiem līdzpilsoņiem diezgan vizuālā veidā parādītu iespējamos ceļus un posmus virzībai uz risināmo problēmu gala mērķi.

Tas šodienai viss.

VKontakte Facebook Odnoklassniki

Tiem, kam patīk patstāvīgi un lēni risināt Sudoku mīklas, formula, kas ļauj ātri aprēķināt atbildes, var šķist vājuma vai krāpšanās atzīšana.

Bet tiem, kam Sudoku šķiet pārāk grūti atrisināms, tas var būt burtiski ideāls risinājums.

Divi pētnieki ir izstrādājuši matemātisko algoritmu, kas ļauj ļoti ātri atrisināt Sudoku, bez minējumiem vai atkāpšanās.

Sarežģītu tīklu pētnieki Zoltans Torožkai un Marija Erksi-Ravaza no Notre Dame universitātes arī spēja izskaidrot, kāpēc dažas Sudoku mīklas ir grūtākas nekā citas. Vienīgais mīnuss ir tas, ka jums ir nepieciešams doktora grāds matemātikā, lai saprastu, ko viņi piedāvā.

Vai jūs varat atrisināt šo mīklu? To ir radījis matemātiķis Arto Incala, un tiek apgalvots, ka tas ir grūtākais Sudoku pasaulē. Foto no nature.com

Torozhkay un Erksi-Rawaz sāka analizēt Sudoku kā daļu no saviem pētījumiem par optimizācijas teoriju un skaitļošanas sarežģītību. Viņi saka, ka lielākā daļa sudoku entuziastu izmanto brutāla spēka pieeju, kuras pamatā ir minēšanas tehnika, lai atrisinātu šīs problēmas. Tādējādi Sudoku cienītāji apbruņojas ar zīmuli un izmēģina visas iespējamās skaitļu kombinācijas, līdz tiek atrasta pareizā atbilde. Šī metode neizbēgami novedīs pie panākumiem, taču tā ir darbietilpīga un laikietilpīga.

Tā vietā Torozhkai un Erksi-Ravaz ierosināja universālu analogo algoritmu, kas ir absolūti deterministisks (neizmanto minējumus vai uzskaitījumus) un vienmēr atrod pareizo problēmas risinājumu, turklāt diezgan ātri.

Pētnieki izmantoja "deterministisku analogo risinātāju", lai pabeigtu šo sudoku. Foto no nature.com

Pētnieki arī atklāja, ka laiks, kas nepieciešams, lai atrisinātu mīklu, izmantojot viņu analogo algoritmu, korelē ar uzdevuma sarežģītības pakāpi, ko nosaka persona. Tas viņus iedvesmoja izstrādāt mīklas vai problēmas sarežģītības klasifikācijas skalu.

Viņi izveidoja skalu no 1 līdz 4, kur 1 ir "viegli", 2 ir "vidēji", 3 ir "grūti", 4 ir "ļoti grūti". Mīklu ar vērtējumu 2 atrisināšana aizņem vidēji 10 reizes ilgāk nekā mīklu ar vērtējumu 1. Saskaņā ar šo sistēmu līdz šim visgrūtāk zināmās mīklas vērtējums ir 3,6; sarežģītākas Sudoku mīklas vēl nav zināmas.

Teorija sākas ar varbūtības kartēšanu katram atsevišķam kvadrātam. Foto no nature.com

“Mani neinteresēja Sudoku, līdz mēs sākām strādāt pie vispārīgākas Būla problēmu atbilstības klases,” saka Torožkajs. - Tā kā sudoku ir daļa no šīs nodarbības, 9. kārtas latīņu laukums mums izrādījās labs laukums testēšanai, tāpēc es viņus iepazinu. Mani un daudzus pētniekus, kas pēta šādas problēmas, fascinē jautājums par to, cik tālu mēs, cilvēki, varam iet, risinot Sudoku deterministiski, bez pārrāvuma, kas ir nejauša izvēle, un, ja minējums nav pareizs, jums ir jāatgriežas atpakaļ. solis vai vairākas darbības un sāciet no jauna. Mūsu analogais lēmumu modelis ir deterministisks: dinamikā nav nejaušas izvēles vai atkārtošanās.

Haosa teorija: mīklu sarežģītības pakāpe šeit tiek parādīta kā haotiska dinamika. Foto no nature.com

Torozhkai un Erksi-Ravaz uzskata, ka viņu analogais algoritms var tikt pielietots visdažādākajām problēmām rūpniecībā, datorzinātnēs un skaitļošanas bioloģijā.

Pētījuma pieredze arī padarīja Torožkaju par lielu Sudoku fanu.

“Mums un manai sievai ir vairākas Sudoku lietotnes mūsu iPhone tālruņos, un līdz šim esam spēlējuši tūkstošiem reižu, katrā līmenī sacenšoties īsākā laikā,” viņš saka. – Viņa bieži intuitīvi saskata rakstu kombinācijas, kuras es neievēroju. Man tie ir jāizņem. Man kļūst neiespējami atrisināt daudzas mīklas, kuras mūsu skala klasificē kā sarežģītas vai ļoti sarežģītas, neuzrakstot varbūtības ar zīmuli.

Torozhkay un Erksi-Ravaz metodoloģija vispirms tika publicēta Nature Physics un vēlāk Nature Scientific Reports.

Izmantojiet skaitļus no 1 līdz 9

Sudoku spēlē 9 x 9 režģī, kurā kopā ir 81 režģis. Spēles laukumā ir 9 "laukumi" (sastāv no 3 x 3 šūnām). Katra horizontālā rinda, vertikālā kolonna un kvadrāts (katra 9 šūnas) jāaizpilda ar cipariem 1-9, neatkārtojot nevienu ciparu rindā, kolonnā vai kvadrātā. Vai tas izklausās sarežģīti? Kā redzams zemāk esošajā attēlā, katrā Sudoku spēles laukā ir vairākas šūnas, kas jau ir aizpildītas. Jo vairāk šūnu sākotnēji ir aizpildītas, jo vieglāka ir spēle. Jo mazāk šūnu sākotnēji ir aizpildītas, jo grūtāka ir spēle.

Neatkārtojiet nevienu ciparu

Kā redzat, augšējais kreisais kvadrāts (apvilkts zilā krāsā) jau ir aizpildījis 7 no 9 šūnām. Vienīgie skaitļi, kas trūkst šajā kvadrātā, ir skaitļi 5 un 6. Redzot, kuri skaitļi trūkst katrā kvadrātā, rindā vai kolonnā, mēs varam izmantot izslēgšanas un deduktīvās argumentācijas procesu, lai izlemtu, kuriem skaitļiem jābūt katrā šūnā. .

Piemēram, augšējā kreisajā kvadrātā mēs zinām, ka, lai pabeigtu kvadrātu, mums ir jāpievieno skaitļi 5 un 6, bet, aplūkojot blakus esošās rindas un kvadrātus, mēs joprojām nevaram skaidri noteikt, kurš skaitlis ir jāpievieno kādai šūnai. Tas nozīmē, ka mums tagad vajadzētu izlaist augšējo kreiso laukumu un tā vietā mēģināt aizpildīt nepilnības dažās citās spēles laukuma vietās.

Nav nepieciešams uzminēt

Sudoku ir loģikas spēle, tāpēc nav nepieciešams uzminēt. Ja nezināt, kādu skaitli ievietot noteiktā šūnā, turpiniet skenēt citus spēles lauka apgabalus, līdz tiek parādīta iespēja ievietot vajadzīgo numuru. Bet nemēģiniet neko "piespiest" - Sudoku atalgo pacietību, izpratni un dažādu kombināciju risināšanu, nevis aklu veiksmi vai minējumus.

Izmantojiet likvidēšanas metodi

Ko mēs darām, kad Sudoku spēlē izmantojam "izslēgšanas metodi"? Šeit ir piemērs. Šajā Sudoku režģī (parādīts tālāk) kreisajā vertikālajā kolonnā (apzīmēts zilā krāsā) trūkst tikai dažu ciparu: 1, 5 un 6.

Viens veids, kā noskaidrot, kuri skaitļi var ietilpt katrā šūnā, ir izmantot "izslēgšanas metodi", pārbaudot, kādi citi skaitļi jau ir katrā kvadrātā, jo skaitļus no 1 līdz 9 nav atļauts dublēt katrā kvadrātā, rindā vai kolonna.

Šajā gadījumā mēs varam ātri pamanīt, ka augšējā kreisajā un centrā kreisajā kvadrātā jau ir skaitlis 1 (skaitlis 1 ir apvilkts sarkanā krāsā). Tas nozīmē, ka vistālāk kreisajā kolonnā ir tikai viena vieta, kur var ievietot ciparu 1 (apvilkta ar zaļu krāsu). Lūk, kā Sudoku darbojas likvidēšanas metode – noskaidro, kuras šūnas ir brīvas, kuru skaitļu trūkst, un pēc tam noņem kvadrātā, kolonnās un rindās jau esošos skaitļus. Attiecīgi aizpildiet tukšās šūnas ar trūkstošajiem skaitļiem.

Sudoku noteikumi ir salīdzinoši vienkārši, taču spēle ir ārkārtīgi daudzveidīga, ar miljoniem iespējamo skaitļu kombināciju un plašu grūtības līmeņu klāstu. Bet tas viss ir balstīts uz vienkāršiem skaitļu 1-9 izmantošanas principiem, aizpildot nepilnības, pamatojoties uz deduktīvu domāšanu, un nekad neatkārtot skaitļus katrā kvadrātā, rindā vai kolonnā.

• pamācība

1. Pamati

Lielākā daļa no mums, hakeriem, zina, kas ir sudoku. Es nerunāšu par noteikumiem, bet nekavējoties pārietu pie metodēm.
Lai atrisinātu mīklu, neatkarīgi no tā, cik sarežģīta vai vienkārša, sākotnēji tiek meklētas šūnas, kuras ir acīmredzami jāaizpilda.

1.1 "Pēdējais varonis"

Apsveriet septīto kvadrātu. Tikai četras brīvas šūnas, lai kaut ko varētu ātri aizpildīt.
"8 " uz D3 bloku polsterējums H3 un J3; līdzīgi" 8 " uz G5 aizveras G1 un G2
Ar tīru sirdsapziņu mēs liekam " 8 " uz H1

1.2 "Pēdējais varonis" pēc kārtas

Kad esat apskatījis kvadrātus, lai atrastu acīmredzamus risinājumus, pārejiet uz kolonnām un rindām.
Apsveriet " 4 " laukumā. Skaidrs, ka tas būs kaut kur ierindā A .
Mums ir " 4 " uz G3 kas aptver A3, tur ir " 4 " uz F7, tīrīšana A7. Un vēl vienu" 4 " Otrajā laukumā aizliedz tā atkārtošanu A4 un A6.
"Pēdējais varonis" mūsu " 4 "Šo A2

1.3 “Nav izvēles”

Dažreiz konkrētai vietai ir vairāki iemesli. " 4 " iekšā J8 būtu lielisks piemērs.
Zils bultiņas norāda, ka šis ir pēdējais iespējamais skaitlis kvadrātā. sarkans un zils bultiņas dod mums pēdējo numuru kolonnā 8 . Zaļumi bultiņas norāda pēdējo iespējamo numuru rindā Dž.
Kā redzat, mums nav citas izvēles kā ievietot šo " 4 "vietā.

1.4 "Un kurš, ja ne es?"

Ciparu aizpildīšanu ir vieglāk izdarīt, izmantojot iepriekš aprakstītās metodes. Tomēr, pārbaudot skaitli kā pēdējo iespējamo vērtību, tiek iegūti arī rezultāti. Metode jāizmanto, kad šķiet, ka visi cipari ir, bet kaut kā pietrūkst.
"5 " iekšā B1 ir iestatīts, pamatojoties uz faktu, ka visi skaitļi no " 1 "pirms" 9 ", Turklāt " 5 " atrodas rindā, kolonnā un kvadrātā (atzīmēts zaļā krāsā).

Žargonā tas ir " kails vientuļnieks". Ja aizpildīsiet lauku ar iespējamām vērtībām​​(kandidāti), tad šūnā šāds skaitlis būs vienīgais iespējamais. Izstrādājot šo paņēmienu, varat meklēt " slēptie vientuļnieki" - skaitļi, kas ir unikāli konkrētai rindai, kolonnai vai kvadrātam.

2. "Kailā jūdze"

2.1 Kaili pāri

""Kails" pāris" - divu kandidātu kopa, kas atrodas divās šūnās, kas pieder vienam kopējam blokam: rinda, kolonna, kvadrāts.
Ir skaidrs, ka pareizie mīklas atrisinājumi būs tikai šajās šūnās un tikai ar šīm vērtībām, savukārt visus pārējos kandidātus no vispārējā bloka var izņemt.


Šajā piemērā ir vairāki "kaili pāri".
sarkans rindā BETšūnas ir izceltas A2 un A3, abi satur " 1 " un " 6 ". Pagaidām precīzi nezinu, kā tie šeit atrodas, bet visus pārējos varu droši noņemt" 1 " un " 6 "no virknes A(atzīmēts dzeltenā krāsā). Arī A2 un A3 pieder pie kopējā laukuma, tāpēc mēs noņemam " 1 "no C1.

2.2 "Trīsnieks"

"Kaili trijnieki"- sarežģīta "kailu pāru" versija.
Jebkura trīs šūnu grupa vienā blokā, kas satur visā visumā ir trīs kandidāti "kails trio". Kad šāda grupa tiek atrasta, šos trīs kandidātus var noņemt no citām bloka šūnām.

Kandidātu kombinācijas priekš "kails trio" var būt šādi:

// trīs skaitļi trīs šūnās.
// jebkuras kombinācijas.
// jebkuras kombinācijas.

Šajā piemērā viss ir diezgan skaidrs. Šūnas piektajā kvadrātā E4, E5, E6 satur [ 5,8,9 ], [5,8 ], [5,9 ]. Izrādās, ka kopumā šīm trim šūnām ir [ 5,8,9 ], un tur var būt tikai šie skaitļi. Tas ļauj mums tos noņemt no citiem bloķēšanas kandidātiem. Šis triks sniedz mums risinājumu " 3 "šūnai E7.

2.3 "Fab Four"

"Kailais četrinieks"ļoti reta parādība, īpaši pilnā formā, un tomēr dod rezultātus, kad tā tiek atklāta. Risinājuma loģika ir tāda pati kā "kaili trīnīši".

Iepriekš minētajā piemērā šūnas pirmajā kvadrātā A1, B1, B2 un C1 parasti satur [ 1,5,6,8 ], tāpēc šie skaitļi aizņems tikai šīs šūnas, nevis citas. Mēs noņemam dzeltenā krāsā iezīmētos kandidātus.

3. "Viss apslēptais kļūst skaidrs"

3.1 Slēptie pāri

Lielisks veids, kā atvērt lauku, ir meklēt slēptie pāri. Šī metode ļauj noņemt no šūnas nevajadzīgos kandidātus un radīt interesantākas stratēģijas.

Šajā mīklā mēs to redzam 6 un 7 atrodas pirmajā un otrajā lauciņā. Turklāt 6 un 7 atrodas kolonnā 7 . Apvienojot šos nosacījumus, mēs varam apgalvot, ka šūnās A8 un A9 būs tikai šīs vērtības, un mēs noņemam visus pārējos kandidātus.


Interesantāks un sarežģītāks piemērs slēptie pāri. Pāris [ 2,4 ] iekšā D3 un E3, tīrīšana 3 , 5 , 6 , 7 no šīm šūnām. Sarkanā krāsā iezīmēti divi slēpti pāri, kas sastāv no [ 3,7 ]. No vienas puses, tie ir unikāli divām šūnām 7 kolonnu, no otras puses - rindai E. Dzeltenā krāsā iezīmētie kandidāti tiek noņemti.

3.1 Slēptie trīnīši

Mēs varam attīstīties slēptie pāri pirms tam slēptie trīnīši vai pat slēptie četrinieki. Apslēptais trīs sastāv no trim skaitļu pāriem, kas atrodas vienā blokā. Piemēram, un. Tomēr, tāpat kā gadījumā ar "kaili trīnīši", katrā no trim šūnām nav jāsatur trīs skaitļi. strādās Kopā trīs skaitļi trīs šūnās. Piemēram , , . Slēptie trīnīši tiks maskēti no citiem kandidātiem kamerās, tāpēc vispirms jums par to jāpārliecinās trijotne attiecas uz konkrētu bloku.


Šajā sarežģītajā piemērā ir divi slēptie trīnīši. Pirmais, kas atzīmēts ar sarkanu, kolonnā BET. Šūna A4 satur [ 2,5,6 ], A7 - [2,6 ] un šūna A9 -[2,5 ]. Šīs trīs šūnas ir vienīgās, kurās var būt 2, 5 vai 6, tāpēc tās būs vienīgās. Tāpēc mēs noņemam nevajadzīgos kandidātus.

Otrkārt, kolonnā 9 . [4,7,8 ] ir unikālas šūnām B9, C9 un F9. Izmantojot to pašu loģiku, mēs noņemam kandidātus.

3.1 Slēptie četrinieki

Ideāls piemērs slēptie četrinieki. [1,4,6,9 ] piektajā kvadrātā var būt tikai četrās šūnās D4, D6, F4, F6. Sekojot mūsu loģikai, mēs noņemam visus pārējos kandidātus (atzīmēti ar dzeltenu).

4. "bez gumijas"

Ja kāds no cipariem parādās divreiz vai trīsreiz vienā blokā (rindā, kolonnā, kvadrātā), mēs varam noņemt šo skaitli no konjugāta bloka. Ir četri savienošanas pārī veidi:

1. Pāris vai Trīs kvadrātā - ja tie atrodas vienā rindā, tad visas pārējās līdzīgās vērtības varat noņemt no atbilstošās rindas.
2. Pāris vai Trīs kvadrātā - ja tie atrodas vienā kolonnā, varat noņemt visas pārējās līdzīgās vērtības no atbilstošās kolonnas.
3. Pāris vai Trīs pēc kārtas – ja tie atrodas vienā un tajā pašā laukumā, tad visas pārējās līdzīgās vērtības var noņemt no attiecīgā kvadrāta.
4. Pāris vai Trīs kolonnā - ja tie atrodas vienā kvadrātā, tad visas pārējās līdzīgās vērtības varat noņemt no attiecīgā kvadrāta.

4.1 Rādītāju pāri, trīskārši

Ļaujiet man parādīt jums šo mīklu kā piemēru. Trešajā laukumā 3 "ir tikai iekšā B7 un B9. Pēc paziņojuma №1 , mēs noņemam kandidātus no B1, B2, B3. Tāpat, " 2 " no astotā kvadrāta noņem iespējamo vērtību no G2.


Īpaša mīkla. Ļoti grūti atrisināt, bet, ja paskatās uzmanīgi, jūs varat redzēt dažus rādītāju pāri. Skaidrs, ka ne vienmēr tie visi ir jāatrod, lai virzītos uz priekšu risinājumā, taču katrs šāds atradums atvieglo mūsu uzdevumu.

4.2. Nereducējamā samazināšana

Šī stratēģija ietver rūpīgu rindu un kolonnu parsēšanu un salīdzināšanu ar kvadrātu saturu (noteikumi №3 , №4 ).
Apsveriet līniju BET. "2 "ir iespējamas tikai A4 un A5. ievērojot noteikumu №3 , noņemt " 2 "viņiem B5, C4, C5.


Turpināsim risināt mīklu. Mums ir viena vieta 4 "viena kvadrātcollas rādiusā 8 kolonna. Saskaņā ar noteikumu №4 , mēs noņemam nevajadzīgos kandidātus un papildus iegūstam risinājumu " 2 " priekš C7.