Kako rešiti težko sudoku. Matematiki so prišli do formule za reševanje Sudokuja

Polje Sudoku je tabela 9x9 celic. V vsako celico se vpiše število od 1 do 9. Cilj igre je razporediti številke tako, da v vsaki vrstici, stolpcu in vsakem bloku 3x3 ni ponovitev. Z drugimi besedami, vsak stolpec, vrstica in blok mora vsebovati vse številke od 1 do 9.

Za rešitev problema lahko kandidate zapišemo v prazne celice. Na primer, razmislite o celici v 2. stolpcu 4. vrstice: v stolpcu, v katerem se nahaja, sta že številki 7 in 8, v vrstici - številke 1, 6, 9 in 4, v bloku - 1 , 2, 8 in 9 Zato od kandidatov v tej celici prečrtamo 1, 2, 4, 6, 7, 8, 9 in ostaneta nam le dva možna kandidata - 3 in 5.

Podobno upoštevamo možne kandidate za druge celice in dobimo naslednjo tabelo:

S kandidati je bolj zanimivo obravnavati in uporabiti je mogoče različne logične metode. Nato si bomo ogledali nekatere od njih.

Samotarji

Metoda je sestavljena iz iskanja samskih v tabeli, t.j. celice, v katerih je možna samo ena številka in nobena druga. To številko zapišemo v to celico in jo izključimo iz drugih celic te vrstice, stolpca in bloka. Na primer: v tej tabeli so trije "samotarji" (označeni so z rumeno).

skriti samotarji

Če je v celici več kandidatov, vendar enega od njih ni v nobeni drugi celici dane vrstice (stolpec ali blok), se tak kandidat imenuje "skriti samotar". V naslednjem primeru je kandidat "4" v zelenem bloku le v osrednji celici. Torej, v tej celici bo zagotovo "4". V to celico vnesemo "4" in jo prečrtamo iz drugih celic 2. stolpca in 5. vrstice. Podobno se v rumenem stolpcu kandidat "2" pojavi enkrat, zato v to celico vnesemo "2" in izključimo "2" iz celic 7. vrstice in ustreznega bloka.

Prejšnji dve metodi sta edini metodi, ki enolično določata vsebino celice. Naslednje metode vam omogočajo le zmanjšanje števila kandidatov v celicah, kar bo prej ali slej pripeljalo do samotarjev ali skritih samotarjev.

Zaklenjen kandidat

Včasih je kandidat v bloku samo v eni vrstici (ali v enem stolpcu). Ker bo ena od teh celic nujno vsebovala tega kandidata, je ta kandidat lahko izključen iz vseh drugih celic te vrstice (stolpca).

V spodnjem primeru osrednji blok vsebuje kandidata "2" samo v osrednjem stolpcu (rumene celice). Torej mora biti ena od teh dveh celic zagotovo "2", nobena druga celica v tej vrstici zunaj tega bloka pa ne more biti "2". Zato je mogoče "2" izključiti kot kandidata iz drugih celic v tem stolpcu (celice v zeleni barvi).

Odprti pari

Če dve celici v skupini (vrstica, stolpec, blok) vsebujeta enak par kandidatov in nič drugega, potem nobena druga celica v tej skupini ne more imeti vrednosti tega para. Ta dva kandidata sta lahko izključena iz drugih celic v skupini. V spodnjem primeru kandidata "1" in "5" v stolpcih osem in devet tvorita odprt par znotraj bloka (rumene celice). Zato, ker mora biti ena od teh celic "1", druga pa "5", sta kandidata "1" in "5" izključena iz vseh drugih celic tega bloka (zelene celice).

Enako je mogoče oblikovati za 3 in 4 kandidate, le 3 oziroma 4 celice že sodelujejo. Odprte trojke: iz zelenih celic izločimo vrednosti rumenih celic.

Odprte štirice: iz zelenih celic izločimo vrednosti rumenih celic.

skritih parov

Če dve celici v skupini (vrstica, stolpec, blok) vsebujeta kandidate, med katerimi je enak par, ki se ne pojavlja v nobeni drugi celici tega bloka, potem nobena druga celica te skupine ne more imeti vrednosti tega para. Zato je mogoče izključiti vse druge kandidate teh dveh celic. V spodnjem primeru sta kandidata "7" in "5" v osrednjem stolpcu samo v rumenih celicah, kar pomeni, da so vsi ostali kandidati iz teh celic lahko izključeni.

Podobno lahko iščete skrite trojke in štiri.

x-krilo

Če ima vrednost samo dve možni lokaciji v vrstici (stolpcu), jo je treba dodeliti eni od teh celic. Če obstaja še ena vrstica (stolpec), kjer je isti kandidat lahko tudi v samo dveh celicah in so stolpci (vrstice) teh celic enaki, potem nobena druga celica teh stolpcev (vrstic) ne more vsebovati tega števila. Razmislite o primeru:

V 4. in 5. vrstici je lahko številka "2" samo v dveh rumenih celicah in ti celici sta v istih stolpcih. Zato lahko številko "2" zapišemo le na dva načina: 1) če je "2" zapisano v 5. stolpcu 4. vrstice, je treba "2" izločiti iz rumenih celic in nato v 5. vrstici položaj "2" je enolično določen s 7. stolpcem.

2) če je v 7. stolpcu 4. vrstice napisano "2", je treba "2" izključiti iz rumenih celic in nato v 5. vrstici položaj "2" enolično določi 5. stolpec.

Zato bosta 5. in 7. stolpec nujno imela številko "2" bodisi v 4. vrstici bodisi v 5. vrstici. Potem je mogoče številko "2" izključiti iz drugih celic teh stolpcev (zelene celice).

"Mečarica" (Mečarica)

Ta metoda je različica .

Iz pravil uganke izhaja, da če je kandidat v treh vrsticah in samo v treh stolpcih, potem je lahko v drugih vrsticah ta kandidat v teh stolpcih izključen.

algoritem:

Iščemo vrstice, v katerih se kandidat ne pojavi več kot trikrat, hkrati pa sodi v natanko tri stolpce.
Kandidata iz teh treh stolpcev izključimo iz drugih vrstic.

Enaka logika velja v primeru treh stolpcev, kjer je kandidat omejen na tri vrstice.

Razmislite o primeru. V treh vrsticah (3., 5. in 7.) se kandidat "5" pojavi največ trikrat (celice so označene rumeno). Vendar spadajo le v tri stolpce: 3., 4. in 7. Po metodi "Mečarica" se lahko kandidat "5" izloči iz drugih celic teh stolpcev (zelene celice).

V spodnjem primeru je uporabljena tudi metoda Swordfish, vendar za primer treh stolpcev. Iz zelenih celic izločimo kandidata "1".

"X-wing" in "Swordfish" je mogoče posplošiti na štiri vrstice in štiri stolpce. Ta metoda se bo imenovala "Medusa".

Barve

Obstajajo situacije, ko se kandidat pojavi le dvakrat v skupini (v vrstici, stolpcu ali bloku). Potem bo želena številka zagotovo v enem od njih. Strategija metode Barve je, da si to razmerje ogledate z uporabo dveh barv, kot sta rumena in zelena. V tem primeru je raztopina lahko v celicah samo ene barve.

Izberemo vse med seboj povezane verige in se odločimo:

Če ima nek nezasenčeni kandidat dva različno obarvana soseda v skupini (vrstica, stolpec ali blok), ga je mogoče izključiti.
Če sta v skupini dve enaki barvi (vrstica, stolpec ali blok), je ta barva napačna. Kandidata iz vseh celic te barve je mogoče izključiti.

V naslednjem primeru uporabite metodo "Barve" za celice s kandidatom "9". Barvati začnemo iz celice v zgornjem levem bloku (2. vrstica, 2. stolpec), jo pobarvamo rumeno. V svojem bloku ima samo enega soseda z "9", pobarvajmo ga zeleno. V koloni ima tudi samo eno sosedo, pobarvamo jo v zeleno.

Podobno delamo s preostalimi celicami, ki vsebujejo številko "9". Dobimo:

Kandidat "9" je lahko samo v vseh rumenih celicah ali v vseh zelenih. V desnem srednjem bloku sta se srečali dve celici iste barve, zato je zelena barva napačna, saj ta blok proizvaja dve "9", kar je nesprejemljivo. Izključimo "9" iz vseh zelenih celic.

Še en primer metode "Barve". Označimo seznanjene celice za kandidata "6".

Celica s "6" v zgornjem osrednjem bloku (poudarjena z lila) ima dva večbarvna kandidata:

"6" bo nujno v rumeni ali zeleni celici, zato je mogoče "6" izključiti iz te lila celice.

Prva stvar, ki jo je treba določiti v metodologiji reševanja problemov, je vprašanje dejanskega razumevanja, kaj dosegamo in lahko dosežemo v smislu reševanja problemov. Razumevanje se običajno pojmuje kot nekaj samoumevnega, pri čemer izgubimo izpred oči, da ima razumevanje določeno izhodišče razumevanja, le v zvezi s katerim lahko rečemo, da razumevanje res poteka od določenega trenutka, ki smo ga določili. Sudoku je tukaj, v našem obravnavi, priročen, ker na svojem primeru do neke mere omogoča modeliranje vprašanj razumevanja in reševanja problemov. Vendar pa bomo začeli z več drugimi in nič manj pomembnimi primeri kot Sudoku.

Fizik, ki preučuje posebno relativnost, bi lahko govoril o Einsteinovih "kristalno jasnih" predlogih. Ta stavek sem naletel na eno od spletnih mest na internetu. Toda kje se začne to razumevanje "kristalne jasnosti"? Začne se z asimilacijo matematičnega zapisa postulatov, iz katerega je mogoče zgraditi vse večnivojske matematične konstrukcije SRT po znanih in razumljivih pravilih. Toda fizik, tako kot jaz, ne razume, zakaj postulati SRT delujejo na ta način in ne drugače.

Prvič, velika večina tistih, ki razpravljajo o tej doktrini, ne razume, kaj točno leži v postulatu o konstantnosti svetlobne hitrosti v prevodu iz njegove matematične uporabe v realnost. In ta postulat implicira konstantnost svetlobne hitrosti v vseh predstavljivih in nepredstavljivih čutih. Hitrost svetlobe je konstantna glede na vse mirujoče in premikajoče se objekte hkrati. Hitrost svetlobnega snopa je po postulatu konstantna tudi glede na prihajajoči, prečni in odmikajoči svetlobni žarek. Hkrati pa imamo v resnici le meritve, ki so posredno povezane s hitrostjo svetlobe, razložene kot njena konstantnost.

Newtonovi zakoni za fizike in celo za tiste, ki fiziko preprosto študirajo, so tako znani, da se zdijo tako razumljivi kot nekaj samoumevnega in ne more biti drugače. Toda, recimo, uporaba zakona univerzalne gravitacije se začne z njegovo matematično notacijo, po kateri je mogoče izračunati celo trajektorije vesoljskih objektov in značilnosti orbit. Zakaj pa ti zakoni delujejo tako in ne drugače – takega razumevanja nimamo.

Enako s sudokujem. Na internetu lahko najdete večkrat ponavljajoče se opise "osnovnih" načinov reševanja problemov Sudoku. Če se spomnite teh pravil, potem lahko razumete, kako je ta ali ta problem Sudoku rešen z uporabo "osnovnih" pravil. Imam pa vprašanje: ali razumemo, zakaj te "osnovne" metode delujejo tako in ne drugače.

Torej gremo na naslednjo ključno točko v metodologiji reševanja problemov. Razumevanje je možno le na podlagi nekega modela, ki daje osnovo za to razumevanje in zmožnost izvedbe kakšnega naravnega ali miselnega eksperimenta. Brez tega imamo lahko le pravila za uporabo naučenih izhodišč: postulatov SRT, Newtonovih zakonov ali "osnovnih" načinov v Sudokuju.

Nimamo in načeloma ne moremo imeti modelov, ki bi izpolnjevali postulat o neomejeni konstantnosti svetlobne hitrosti. Ne, lahko pa si izmislimo nedokazljive modele, ki so skladni z Newtonovimi zakoni. In obstajajo takšni "newtonovski" modeli, ki pa nekako ne navdušujejo s produktivnimi možnostmi za izvedbo obsežnega ali miselnega eksperimenta. Toda Sudoku nam ponuja priložnosti, ki jih lahko uporabimo za razumevanje dejanskih problemov Sudokuja in za ponazoritev modeliranja kot splošnega pristopa k reševanju problemov.

Eden od možnih modelov za težave Sudoku je delovni list. Ustvari se tako, da se vse prazne celice (celice) tabele, določene v nalogi, preprosto izpolnijo s številkami 123456789. Nato se naloga zmanjša na zaporedno odstranjevanje vseh dodatnih števk iz celic, dokler niso vse celice tabele. napolnjena z enojnimi (izključnimi) številkami, ki izpolnjujejo pogoj problema.

Takšen delovni list izdelujem v Excelu. Najprej izberem vse prazne celice (celice) tabele. Pritisnem F5-"Izberi"-"Prazne celice"-"V redu". Bolj splošen način za izbiro želenih celic: držite Ctrl in kliknite miško, da izberete te celice. Nato za izbrane celice nastavim barvo na modro, velikost 10 (izvirnik - 12) in pisavo Arial Narrow. To je vse zato, da so kasnejše spremembe v tabeli jasno vidne. Nato v prazne celice vpišem številke 123456789. To naredim takole: to številko zapišem in shranim v ločeno celico. Nato pritisnem F2, izberem in kopiram to številko z operacijo Ctrl + C. Nato grem do celic tabele in zaporedoma obidem vse prazne celice, vanje vnesem številko 123456789 z operacijo Ctrl + V in delovni list je pripravljen.

Dodatne številke, o katerih bo govora kasneje, izbrišem na naslednji način. Z operacijo Ctrl + klik miške - izberem celice z dodatno številko. Nato pritisnem Ctrl + H in v zgornje polje okna, ki se odpre, vnesem številko za brisanje, spodnje polje pa naj bo popolnoma prazno. Nato ostane klikniti na možnost "Zamenjaj vse" in dodatna številka je odstranjena.

Sodeč po tem, da mi običajno uspe naprednejšo obdelavo tabel opraviti na običajne "osnovne" načine kot v primerih, ki jih dajejo na internetu, je delovni list najbolj preprosto orodje pri reševanju problemov Sudoku. Poleg tega se veliko situacij v zvezi z uporabo najbolj zapletenih tako imenovanih "osnovnih" pravil preprosto ni pojavilo na mojem delovnem listu.

Hkrati je delovni list tudi model, na katerem se lahko izvajajo eksperimenti z naknadno identifikacijo vseh »osnovnih« pravil in različnih odtenkov njihove uporabe, ki izhajajo iz poskusov.

Pred vami je torej delček delovnega lista z devetimi bloki, oštevilčenimi od leve proti desni in od zgoraj navzdol. V tem primeru imamo četrti blok napolnjen s številkami 123456789. To je naš model. Zunaj bloka smo z rdečo označili »aktivirane« (dokončno določene) številke, v tem primeru štiri, ki jih nameravamo nadomestiti v preglednici, ki se sestavlja. Modre petice so figure, ki še niso določene glede svoje prihodnje vloge, o kateri bomo govorili kasneje. Aktivirane številke, ki smo jih dodelili, tako rekoč prečrtajo, potisnejo, izbrišejo - na splošno premaknejo enake številke v bloku, zato so tam predstavljene v bledi barvi, kar simbolizira dejstvo, da so bile te blede številke izbrisano. Želel sem narediti to barvo še bolj bledo, potem pa bi lahko postale popolnoma nevidne, ko jih gledamo na internetu.

Posledično je bil v četrtem bloku, v celici E5, eden, prav tako aktiviran, a skrite štiri. "Aktivirana", ker lahko tudi odstrani dodatne števke, če so na poti, in "skrita", ker je med drugimi številkami. Če celico E5 napadejo ostale, razen 4, aktivirane številke 12356789, se bo v E5 - 4 pojavil "goli" samotar.

Zdaj pa odstranimo eno aktivirano štiri, na primer iz F7. Potem so štiri v zapolnjenem bloku lahko že in samo v celici E5 ali F5, medtem ko ostanejo aktivirane v vrstici 5. Če so v tej situaciji vključene aktivirane petice, brez F7=4 in F8=5, potem so v celicah E5 in F5 bo gol ali skrit aktiviran par 45.

Ko ste dovolj premislili in doumeli različne možnosti z golimi in skritimi samskimi, dvojkami, trojkami itd. ne samo v blokih, ampak tudi v vrsticah in stolpcih, lahko preidemo na drug poskus. Ustvarimo goli par 45, kot smo to storili prej, in nato povežimo aktivirana F7=4 in F8=5. Posledično bo prišlo do situacije E5=45. Podobne situacije se zelo pogosto pojavijo v procesu obdelave delovnega lista. Ta situacija pomeni, da mora biti ena od teh števk, v tem primeru 4 ali 5, nujno v bloku, vrstici in stolpcu, ki vključuje celico E5, ker morata biti v vseh teh primerih dve števki in ne ena od njiju.

In kar je najpomembneje, zdaj že vemo, kako pogosto se pojavljajo situacije, kot je E5=45. Na podoben način bomo definirali situacije, ko se v eni celici pojavi trojnik itd. In ko stopnjo razumevanja in dojemanja teh situacij spravimo v stanje samoumevnosti in preprostosti, potem je naslednji korak tako rekoč znanstveno razumevanje situacij: takrat bomo lahko naredili statistično analizo Sudoku tabele, prepoznajte vzorce in uporabite nakopičeno gradivo za reševanje najbolj zapletenih problemov.

Tako z eksperimentiranjem na modelu dobimo vizualno in celo »znanstveno« predstavo skritih ali odprtih samskih, parov, trojk itd. Če se omejite na operacije z opisanim preprostim modelom, se bodo nekatere vaše zamisli izkazale za netočne ali celo napačne. Toda takoj, ko boste prešli na reševanje konkretnih problemov, bodo netočnosti začetnih idej hitro prišle na dan, vendar bo treba modele, na katerih so bili izvedeni poskusi, ponovno premisliti in izpopolniti. To je neizogibna pot hipotez in izpopolnjevanj pri reševanju kakršnih koli problemov.

Moram reči, da so skriti in odprti samski, pa tudi odprti pari, trojke in celo četvorke pogoste situacije, ki nastanejo pri reševanju problemov Sudoku z delovnim listom. Skriti pari so bili redki. In tukaj so skrite trojke, četverice itd. Pri obdelavi delovnih listov nekako nisem naletel, tako kot na večkrat opisane na internetu metode za obhod obrisov "x-wing" in "mečarice", v katerih so "kandidati" za izbris s katerim koli od dva alternativna načina zaobidenja kontur. Pomen teh metod: če uničimo "kandidata" x1, ostane izključni kandidat x2 in se hkrati izbriše kandidat x3, in če uničimo x2, ostane izključni x1, vendar v tem primeru kandidat Izbriše se tudi x3, zato je treba v vsakem primeru izbrisati x3, ne da bi to zaenkrat vplivalo na kandidata x1 in x2. Na splošno je to poseben primer situacije: če dva alternativna načina vodita do istega rezultata, potem je ta rezultat mogoče uporabiti za rešitev problema Sudoku. V tej, bolj splošni, situaciji sem se srečal s situacijami, vendar ne v variantah "x-wing" in "swordfish" in ne pri reševanju sudoku problemov, za katere zadostuje poznavanje le "osnovnih" pristopov.

Značilnosti uporabe delovnega lista je mogoče prikazati v naslednjem netrivialnem primeru. Na enem od forumov za reševanje sudokuja http://zforum.net/index.php?topic=3955.25;wap2 sem naletel na problem, predstavljen kot enega najtežjih problemov sudokuja, ki ga ni mogoče rešiti na običajne načine, brez uporabe oštevilčevanja z predpostavke o številkah, ki so zamenjane v celicah. Pokažimo, da je z delovno tabelo mogoče rešiti ta problem brez takega naštevanja:

Na desni je izvirna naloga, na levi je delovna miza po "izbrisu", t.j. rutinsko operacijo odstranjevanja dodatnih števk.

Najprej se dogovorimo za zapis. ABC4=689 pomeni, da celice A4, B4 in C4 vsebujejo številke 6, 8 in 9 – eno ali več števk na celico. Enako je s strunami. Tako B56=24 pomeni, da celici B5 in B6 vsebujeta številki 2 in 4. Znak ">" je znak pogojnega dejanja. Tako D4=5>I4-37 pomeni, da je treba zaradi sporočila D4=5 številko 37 postaviti v celico I4. Sporočilo je lahko eksplicitno – »golo« – in skrito, kar bi moralo biti razkrito. Vpliv sporočila je lahko zaporeden (posredno se prenaša) vzdolž verige in vzporeden (deluje neposredno na druge celice). Na primer:

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

Ta vnos pomeni, da je D3=2, vendar je to dejstvo treba razkriti. D8=1 prenese svoje delovanje na verigo na A3 in 4 je treba zapisati v A3; hkrati pa D3=2 deluje neposredno na G9, kar ima za posledico G9-3. (D8=1)+(G9=3)>G8-7 – kombiniran vpliv faktorjev (D8=1) in (G9=3) vodi do rezultata G8-7. itd.

Zapisi lahko vsebujejo tudi kombinacijo tipa H56/68. To pomeni, da sta številki 6 in 8 prepovedani v celicah H5 in H6, tj. jih je treba odstraniti iz teh celic.

Torej, začnemo delati s tabelo in za začetek uporabimo dobro manifestiran, opazen pogoj ABC4=689. To pomeni, da je treba v vseh drugih (razen A4, B4 in C4) celicah bloka 4 (sredina, leva) in 4. vrstice izbrisati številke 6, 8 in 9:

Na enak način uporabite B56=24. Skupaj imamo D4=5 in (po D4=5>I4-37) HI4=37 in tudi (po B56=24>C6-1) C6=1. Uporabimo to na delovnem listu:

V I89=68skrito>I56/68>H56-68: tj. celici I8 in I9 vsebujeta skriti par števk 5 in 6, ki prepoveduje, da bi bile te števke v I56, kar ima za posledico rezultat H56-68. Ta fragment lahko obravnavamo na drugačen način, tako kot smo to počeli pri poskusih na modelu delovnega lista: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. To pomeni, da dvosmerni "napad" (G23=68) in (AD7=68) vodi do dejstva, da sta lahko samo številki 6 in 8 v I8 in I9. Nadalje (I89=68) je povezan z " napad" na H56 skupaj s prejšnjimi pogoji, kar vodi do H56-68. Poleg tega je povezan tudi "napad" (ABC4=689), ki je v tem primeru videti odveč, vendar če bi delali brez delovne mize, bi bil faktor vpliva (ABC4=689) skrit in bi bilo precej primerno, da se temu posebej posvetimo.

Naslednje dejanje: I5=2>G1-2,G6-9,B6-4,B5-2.

Upam, da je že brez komentarjev jasno: zamenjaj številke, ki prihajajo za pomišljajem, ne moreš zgrešiti:

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

Naslednja serija dejanj:

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,

to pomeni, da se kot posledica "prečrtanja" - izbrisa dodatnih števk - v celicah F8 in F9 pojavi odprt, "goli" par 89, ki ga skupaj z drugimi rezultati, navedenimi v zapisu, uporabimo v tabeli:

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

Njihov rezultat:

Temu sledijo dokaj rutinska, očitna dejanja:

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- osem;

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

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

Njihov rezultat: končna rešitev problema:

Tako ali drugače bomo domnevali, da smo "osnovne" metode v Sudokuju ali na drugih področjih intelektualne uporabe ugotovili na podlagi za to primernega modela in se celo naučili, kako jih uporabljati. Toda to je le del našega napredka pri metodologiji reševanja problemov. Nadalje, ponavljam, sledi ne vedno upoštevano, ampak nepogrešljiva faza pripeljevanja predhodno naučenih metod do stanja enostavne uporabe. Reševanje primerov, razumevanje rezultatov in metod te rešitve, premislek o tem gradivu na podlagi sprejetega modela, ponovno premislek o vseh možnostih, speljevanje stopnje njihovega razumevanja do avtomatizacije, ko rešitev z uporabo "osnovnih" določb postane rutinska in izgine kot problem. Kaj daje: vsak naj to občuti na lastni izkušnji. In bistvo je, da ko problemska situacija postane rutinska, je iskalni mehanizem intelekta usmerjen v razvoj vse bolj kompleksnih določil na področju problemov, ki se rešujejo.

In kaj so "kompleksnejše določbe"? To so le nove »temeljne« določbe pri reševanju problema, katerih razumevanje pa se lahko tudi poenostavi, če se za ta namen najde ustrezen model.

V članku Vasilenko S.L. "Numeric Harmony Sudoku" Najdem primer težave z 18 simetričnimi tipkami:

V zvezi s to nalogo je navedeno, da jo je mogoče z "osnovnimi" metodami rešiti le do določenega stanja, po doseganju katerega ostane le uporabiti preprosto naštevanje s poskusno zamenjavo v celice neke domnevne izključitve (enojne, posamezne ) števke. To stanje (napredno nekoliko dlje kot v Vasilenkovem primeru) izgleda tako:

Obstaja tak model. To je neke vrste rotacijski mehanizem za identificirane in neidentificirane izključne (enojne) številke. V najpreprostejšem primeru se neka trojka izključnih števk vrti v desno ali levo smer in gre mimo te skupine iz vrstice v vrstico ali iz stolpca v stolpec. Na splošno se hkrati vrtijo tri skupine trojk številk v eno smer. V bolj zapletenih primerih se trije pari izključnih števk vrtijo v eno smer, trojka enojnih pa se vrti v nasprotni smeri. Tako se na primer zasukajo izključne številke v prvih treh vrsticah obravnavanega problema. In kar je najpomembneje, takšno rotacijo lahko vidimo, če upoštevamo lokacijo številk v obdelanem delovnem listu. Te informacije so za zdaj dovolj, druge nianse modela rotacije pa bomo razumeli v procesu reševanja problema.

Tako lahko v prvih (zgornjih) treh vrsticah (1, 2 in 3) opazimo rotacijo parov (3+8) in (7+9), pa tudi (2+x1) z neznanim x1 in trojka enojnih (x2+4+ 1) z neznanim x2. Pri tem lahko ugotovimo, da je vsak od x1 in x2 lahko 5 ali 6.

Vrstice 4, 5 in 6 gledajo na pare (2+4) in (1+3). Obstajati mora tudi 3. neznani par in trojka enojnih, od katerih je znana samo ena številka 5.

Podobno si ogledamo vrstice 789, nato trojke stolpcev ABC, DEF in GHI. Zbrane podatke bomo zapisali v simbolični in, upam, povsem razumljivi obliki:

Zaenkrat te informacije potrebujemo samo za razumevanje splošne situacije. Dobro premislite in potem se lahko premaknemo naprej do naslednje tabele, posebej pripravljene za to:

Alternative sem poudaril z barvami. Modra pomeni "dovoljeno", rumena pa "prepovedano". Če je recimo dovoljeno v A2=79 dovoljeno A2=7, potem je C2=7 prepovedano. Ali obratno – dovoljeno A2=9, prepovedano C2=9. In potem se dovoljenja in prepovedi prenašajo po logični verigi. To barvanje je narejeno, da bi olajšali ogled različnih alternativ. Na splošno je to neka analogija z metodama "x-wing" in "mečarica", omenjenim prej pri obdelavi tabel.

Če pogledamo možnosti B6=7 oziroma B7=9, lahko takoj najdemo dve točki, ki nista združljivi s to možnostjo. Če je B7=9, se v vrsticah 789 pojavi sinhrono vrteča se trojka, kar je nesprejemljivo, saj se lahko sinhrono (v eno smer) vrtijo samo trije pari (in tri enojne asinhrono do njih) ali tri trojke (brez enojnih). Poleg tega, če je B7=9, potem po več korakih obdelave delovnega lista v 7. vrstici najdemo nezdružljivost: B7=D7=9. Torej nadomestimo edino sprejemljivo od dveh alternativ B6=9, nato pa se problem reši s preprostimi sredstvi konvencionalne obdelave brez kakršnega koli slepega naštevanja:

Nato imam že pripravljen primer uporabe modela rotacije za reševanje težave s svetovnega prvenstva v sudokuju, vendar sem ta primer izpustil, da tega članka ne bi preveč raztegnil. Poleg tega, kot se je izkazalo, ima ta problem tri rešitve, kar je slabo primerno za začetni razvoj modela rotacije številk. Prav tako sem veliko napihoval problem s 17 tipkami Garyja McGuireja, ki je bil povlečen iz interneta, da bi rešil njegovo uganko, dokler nisem s še več sitnosti ugotovil, da ima ta "uganka" več kot 9 tisoč rešitev.

Torej, hočeš ali nočeš, moramo preiti na "najtežji na svetu" problem Sudoku, ki ga je razvil Arto Inkala, ki ima, kot veste, edinstveno rešitev.

Po vnosu dveh povsem očitnih ekskluzivnih številk in obdelavi delovnega lista naloga izgleda takole:

Tipke, dodeljene izvirnemu problemu, so označene s črno in z večjo pisavo. Za napredek pri reševanju tega problema se moramo ponovno zanesti na ustrezen model, primeren za ta namen. Ta model je neke vrste mehanizem za vrtenje številk. V tem in prejšnjih člankih je bilo že večkrat obravnavano, a da bi razumeli nadaljnje gradivo članka, je treba ta mehanizem premisliti in podrobno izdelati. Približno tako, kot da bi s takšnim mehanizmom delali deset let. Toda to gradivo boste še vedno lahko razumeli, če ne iz prvega branja, pa iz drugega ali tretjega itd. Poleg tega, če boste vztrajali, boste to "težko razumljivo" gradivo spravili v stanje njegove rutine in preprostosti. V zvezi s tem ni nič novega: kar je sprva zelo težko, postopoma ne postane tako težko, z nadaljnjim nenehnim izpopolnjevanjem pa postane vse najbolj očitno in ne zahteva duševnega napora na svojem mestu, nato pa lahko osvobodite svoje duševno stanje. možnosti za nadaljnji napredek pri reševanju problema ali pri drugih težavah.

Natančna analiza strukture problema Arto Incal kaže, da je celoten problem zgrajen na principu treh sinhrono vrtečih se parov in trojke asinhrono vrtečih se parov enojnih: (x1+x2)+(x3+x4)+(x5+). x6)+(x7+x8+ x9). Vrstni red vrtenja je lahko na primer naslednji: v prvih treh vrsticah 123 gre prvi par (x1+x2) iz prve vrstice prvega bloka v drugo vrstico drugega bloka, nato v tretjo vrstico tretjega bloka. Drugi par skoči iz druge vrste prvega bloka v tretjo vrstico drugega bloka, nato pa v tej rotaciji skoči v prvo vrstico tretjega bloka. Tretji par iz tretje vrste prvega bloka skoči v prvo vrsto drugega bloka in nato v isti smeri vrtenja skoči v drugo vrsto tretjega bloka. Trojica samskih se giblje v podobnem vzorcu vrtenja, vendar v nasprotni smeri kot pri parih. Situacija s stolpci je videti podobno: če je tabela miselno (ali dejansko) zasukana za 90 stopinj, bodo vrstice postale stolpci z enakim značajem gibanja posameznih in parov kot prej za vrstice.

Če te rotacije v mislih obrnemo v zvezi s problemom Arto Incal, postopoma razumemo očitne omejitve pri izbiri variant te rotacije za izbrano trojko vrstic ali stolpcev:

Ne bi smelo biti sinhrono (v eni smeri) vrtečih se trojk in parov - takšne trojke se bodo v nasprotju s trojko samskih nadalje imenovale trojke;

Ne sme biti med seboj asinhronih parov ali med seboj asinhronih singlov;

Ne bi smeli biti tako pari kot posamezniki, ki se vrtijo v eni (na primer v desno) smeri - to je ponovitev prejšnjih omejitev, vendar se morda zdi bolj razumljivo.

Poleg tega obstajajo še druge omejitve:

V 9 vrsticah ne sme biti niti enega para, ki se ujema s parom v nobenem od stolpcev in enak za stolpce in vrstice. To bi moralo biti očitno: ker že samo dejstvo, da sta dve številki v isti vrstici, pomeni, da sta v različnih stolpcih.

Lahko tudi rečete, da se zelo redko pojavljajo ujemanja parov v različnih trojkah vrstic ali podobno ujemanje v trojkah stolpcev, prav tako pa so redko ujemanja trojk enojnih v vrsticah in/ali stolpcih, a to so tako rekoč , verjetnostni vzorci.

Raziskovalni bloki 4,5,6.

V blokih 4-6 so možni pari (3+7) in (3+9). Če sprejmemo (3+9), potem dobimo neveljavno sinhrono rotacijo trojke (3+7+9), torej imamo par (7+3). Po zamenjavi tega para in naknadni obdelavi tabele z običajnimi sredstvi dobimo:

Hkrati lahko rečemo, da je 5 v B6=5 lahko samo samotar, asinhroni (7+3), 6 v I5=6 pa je paragenerator, saj je v isti vrstici H5=5 v šestem blok in zato ne more biti sam in se lahko premika samo sinhronizirano s (7+3.

in razporedil kandidate za samske po številu nastopov v tej vlogi v tej tabeli:

Če sprejmemo, da so najpogostejši 2, 4 in 5 samski, potem se po pravilih rotacije z njimi lahko kombinirajo samo pari: (7 + 3), (9 + 6) in (1 + 8) - a par (1 + 9) zavrže, ker negira par (9+6). Nadalje, po zamenjavi teh parov in posameznih in nadaljnji obdelavi tabele z običajnimi metodami, dobimo:

Izkazalo se je, da je tako nepopustljiva miza - ne želi biti obdelana do konca.

Morali se boste potruditi in opazili, da je v stolpcih ABC par (7 + 4) in da se 6 giblje sinhrono s 7 v teh stolpcih, zato je 6 par, tako da so v stolpcu možne samo kombinacije (6 + 3). "C" 4. bloka +8 ali (6+8)+3. Prva od teh kombinacij ne deluje, ker se potem v 7. bloku v stolpcu "B" prikaže neveljavna sinhrona trojka - trojka (6 + 3 + 8). No, potem po zamenjavi možnosti (6 + 8) + 3 in obdelavi tabele na običajen način pridemo do uspešnega zaključka naloge.

Druga možnost: vrnimo se na tabelo, pridobljeno po identifikaciji kombinacije (7 + 3) + 5 v vrsticah 456, in nadaljujmo s preučevanjem stolpcev ABC.

Tu lahko opazimo, da se par (2+9) ne more zgoditi v ABC. Druge kombinacije (2+4), (2+7), (9+4) in (9+7) dajejo sinhrono trojko – trojko v A4+A5+A6 in B1+B2+B3, kar je nesprejemljivo. Ostane en sprejemljiv par (7+4). Poleg tega se 6 in 5 premikata sinhrono 7, kar pomeni, da tvorita paro, tj. tvori nekaj parov, vendar ne 5 + 6.

Naredimo seznam možnih parov in njihovih kombinacij s samci:

Kombinacija (6+3)+8 ne deluje, ker sicer se v enem stolpcu (6 + 3 + 8) oblikuje neveljaven trojček, o čemer smo že govorili in ga lahko še enkrat preverimo s preverjanjem vseh možnosti. Od kandidatov za samske največ točk doseže številka 3, najverjetnejša pa od vseh zgornjih kombinacij: (6 + 8) + 3, t.j. (C4=6 + C5=8) + C6=3, kar daje:

Poleg tega je najverjetnejši kandidat za samske 2 ali 9 (vsak po 6 točk), v katerem koli od teh primerov pa kandidat 1 (4 točke) ostane veljaven. Začnimo s (5+29)+1, kjer je 1 asinhrona s 5, tj. vstavite 1 iz B5=1 kot asinhroni singleton v vse stolpce ABC:

V bloku 7, stolpec A, sta možni samo možnosti (5+9)+3 in (5+2)+3. Toda bolje bodite pozorni na dejstvo, da so se v vrsticah 1-3 zdaj pojavili pari (4 + 5) in (8 + 9). Njihova zamenjava vodi do hitrega rezultata, t.j. do zaključka naloge, potem ko je bila tabela obdelana z običajnimi sredstvi.

No, zdaj, ko smo vadili prejšnje možnosti, lahko poskusimo rešiti problem Arto Incal brez statističnih ocen.

Ponovno se vrnemo v začetni položaj:

V blokih 4-6 so možni pari (3+7) in (3+9). Če sprejmemo (3 + 9), potem dobimo neveljavno sinhrono rotacijo trojke (3 + 7 + 9), zato imamo za zamenjavo v tabeli samo možnost (7 + 3):

5 je tukaj, kot vidimo, samotar, 6 je paraformer. Veljavne možnosti v ABC5: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1) +2. Toda (2+1) je asinhrono z (7+3), zato obstajajo (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. V vsakem primeru je 1 sinhrona (7 + 3) in zato paragenerirajoča. Zamenjajmo 1 v tej funkciji v tabeli:

Številka 6 tukaj je paragenerator v bl. 4-6, vendar vidnega para (6+4) ni na seznamu veljavnih parov. Zato je quad v A4=4 asinhroni 6:

Ker D4+E4=(8+1) in glede na rotacijsko analizo tvori ta par, dobimo:

Če celice C456=(6+3)+8, potem B789=683, tj. dobimo sinhroni trojček, tako da nam ostane možnost (6+8)+3 in rezultat njene zamenjave:

B2=3 je tukaj enojni, C1=5 (asinhroni 3) je seznanjanje, A2=8 je tudi seznanjanje. B3=7 je lahko sinhroni in asinhroni. Zdaj se lahko izkažemo v bolj zapletenih trikih. Z izurjenim očesom (ali vsaj pri preverjanju na računalniku) vidimo, da za kateri koli status B3=7 – sinhroni ali asinhroni – dobimo enak rezultat A1=1. Zato lahko to vrednost nadomestimo z A1 in nato dokončamo našo, oziroma Arto Incalo, nalogo na bolj običajen preprost način:

Tako ali drugače smo uspeli razmisliti in celo ponazoriti tri splošne pristope k reševanju problemov: določiti točko razumevanja problema (ne hipotetično ali slepo deklarirano, ampak realen trenutek, iz katerega lahko govorimo o razumevanju problema). ), izberite model, ki nam omogoča realizacijo razumevanja z naravnim ali miselnim eksperimentom in – tretjič – da stopnjo razumevanja in zaznavanja v tem primeru doseženih rezultatov spravimo v stanje samoumevnosti in preprostosti. Obstaja tudi četrti pristop, ki ga osebno uporabljam.

Vsak človek ima stanja, ko se intelektualne naloge in težave, s katerimi se sooča, rešujejo lažje, kot je običajno. Ta stanja so precej ponovljiva. Če želite to narediti, morate obvladati tehniko izklopa misli. Sprva vsaj za delček sekunde, nato pa vse bolj in bolj raztegovanje tega odklopnega trenutka. Več o tem ne morem povedati, oziroma priporočati, kaj v zvezi s tem, saj je trajanje uporabe te metode čisto osebna stvar. A k tej metodi se zatekam včasih dlje časa, ko se pred mano pojavi problem, do katerega ne vidim možnosti, kako bi se ga dalo približati in rešiti. Posledično se slej ko prej iz shrambe spomina pojavi ustrezen prototip modela, ki razjasni bistvo tega, kar je treba rešiti.

Problem Incal sem rešil na več načinov, vključno s tistimi, ki so opisani v prejšnjih člankih. In vedno sem tako ali drugače uporabljal ta četrti pristop z izklopom in naknadno koncentracijo miselnih naporov. Najhitrejšo rešitev problema sem dobil s preprostim naštevanjem - kar se imenuje "metoda pokeja" -, vendar z uporabo samo "dolgih" možnosti: tistih, ki bi lahko hitro privedle do pozitivnega ali negativnega rezultata. Druge možnosti so mi vzele več časa, saj sem večino časa porabil za vsaj grobi razvoj tehnologije za uporabo teh možnosti.

Dobra možnost je tudi v duhu četrtega pristopa: prilagodite se reševanju problemov Sudoku, pri čemer v procesu reševanja problema nadomestite samo eno številko na celico. To pomeni, da se večina naloge in njenih podatkov »pomika« v mislih. To je glavni del procesa intelektualnega reševanja problemov in to veščino je treba trenirati, da bi povečali svojo sposobnost reševanja problemov. Na primer, nisem profesionalni reševalec Sudokuja. Imam druge naloge. Toda kljub temu si želim zastaviti naslednji cilj: pridobiti sposobnost reševanja problemov Sudokuja večje kompleksnosti, brez delovnega lista in brez zamenjave več kot ene številke v eno prazno celico. V tem primeru je dovoljen kakršen koli način reševanja Sudokuja, vključno s preprostim naštevanjem možnosti.

Ni naključje, da se tukaj spomnim naštevanja možnosti. Vsak pristop k reševanju problemov Sudoku vključuje niz določenih metod v svojem arzenalu, vključno z eno ali drugo vrsto naštevanja. Poleg tega ima katera koli metoda, ki se uporablja zlasti v Sudokuju ali pri reševanju kakršnih koli drugih težav, svoje področje učinkovite uporabe. Torej, pri reševanju sorazmerno preprostih problemov Sudoku so najučinkovitejše preproste "osnovne" metode, opisane v številnih člankih na to temo na internetu, bolj zapletena "metoda vrtenja" pa je tukaj pogosto neuporabna, saj le oteži potek enostavna rešitev in hkrati kaj -ne daje novih informacij, ki se pojavijo pri reševanju problema. Toda v najtežjih primerih, kot je problem Arto Incal, lahko igra ključno vlogo "metoda vrtenja".

Sudoku v mojih člankih je le ilustrativen primer pristopov k reševanju problemov. Med težavami, ki sem jih rešil, so tudi red velikosti težji od Sudokuja. Na primer, računalniški modeli kotlov in turbin, ki se nahajajo na naši spletni strani. Tudi jaz ne bi imel nič proti, da bi govoril o njih. Zaenkrat pa sem se odločil za Sudoku, da bi svojim mladim sodržavljanom na precej nazoren način prikazal možne načine in faze premika proti končnemu cilju reševanja problemov.

To je vse za danes.

VKontakte Facebook Odnoklassniki

Za tiste, ki radi sami in počasi rešujejo uganke Sudoku, se formula, ki vam omogoča hitro izračunavanje odgovorov, morda zdi kot priznanje slabosti ali goljufanja.

Toda za tiste, ki se jim zdi sudoku pretežko rešiti, je to lahko dobesedno popolna rešitev.

Dva raziskovalca sta razvila matematični algoritem, ki vam omogoča, da sudoku rešite zelo hitro, brez ugibanja ali vračanja nazaj.

Raziskovalca kompleksnih omrežij Zoltan Torozhkai in Maria Erksi-Ravaz z Univerze Notre Dame sta lahko razložila tudi, zakaj so nekatere uganke Sudoku težje od drugih. Edina pomanjkljivost je, da potrebujete doktorat iz matematike, da razumete, kaj ponujajo.

Ali lahko rešite to uganko? Ustvaril ga je matematik Arto Incala in naj bi bil najtežji sudoku na svetu. Fotografija iz nature.com

Torozhkai in Erksi-Rawaz sta začela analizirati Sudoku kot del svojih raziskav teorije optimizacije in računske kompleksnosti. Pravijo, da večina navdušencev nad sudokujem za reševanje teh težav uporablja pristop brutalne sile, ki temelji na ugibanju. Tako se ljubitelji sudokuja oborožijo s svinčnikom in preizkušajo vse možne kombinacije številk, dokler se ne najde pravilen odgovor. Ta metoda bo neizogibno vodila do uspeha, vendar je naporna in dolgotrajna.

Namesto tega sta Torozhkai in Erksi-Ravaz predlagala univerzalni analogni algoritem, ki je popolnoma determinističen (ne uporablja ugibanja ali naštevanja) in vedno najde pravilno rešitev problema, in to precej hitro.

Raziskovalci so za dokončanje tega sudokuja uporabili "deterministični analogni reševalec". Fotografija iz nature.com

Raziskovalci so tudi ugotovili, da je čas, potreben za reševanje uganke z uporabo njihovega analognega algoritma, korelira s stopnjo težavnosti naloge, kot jo oceni oseba. To jih je navdihnilo, da so razvili lestvico za razvrstitev težavnosti uganke ali problema.

Ustvarili so lestvico od 1 do 4, kjer je 1 »lahko«, 2 »povprečno«, 3 »težko«, 4 »zelo težko«. Uganka z oceno 2 zahteva povprečno 10-krat več časa za reševanje kot uganka z oceno 1. Po tem sistemu ima najtežja doslej znana uganka oceno 3,6; bolj zapletene uganke Sudoku še niso znane.

Teorija se začne s preslikavo verjetnosti za vsak posamezen kvadrat. Fotografija iz nature.com

»Sudoku me ni zanimal, dokler nismo začeli delati na bolj splošnem razredu izpolnjevanja logičnih problemov,« pravi Torozhkay. - Ker je sudoku del tega razreda, se je latinski kvadrat 9. reda izkazal za dobro polje za testiranje, zato sem jih spoznal. Jaz in mnoge raziskovalce, ki preučujemo takšne probleme, fascinira vprašanje, kako daleč lahko ljudje gremo pri reševanju Sudokuja, deterministično, brez razpada, kar je naključna izbira, in če ugibanje ni pravilno, se morate vrniti nazaj. korak ali več korakov in začnite znova. Naš analogni model odločanja je determinističen: v dinamiki ni naključne izbire ali ponavljanja.

Teorija kaosa: Stopnja zapletenosti ugank je tukaj prikazana kot kaotična dinamika. Fotografija iz nature.com

Torozhkai in Erksi-Ravaz verjameta, da ima njun analogni algoritem potencial za uporabo pri najrazličnejših problemih v industriji, računalniški znanosti in računalniški biologiji.

Zaradi raziskovalnih izkušenj je Torozhkay postal tudi velik oboževalec Sudokuja.

»Z ženo imava več aplikacij Sudoku na naših iPhonih in verjetno sva igrala že na tisoče krat in tekmovala v krajšem času na vsaki ravni,« pravi. - Pogosto intuitivno vidi kombinacije vzorcev, ki jih jaz ne opazim. Moram jih vzeti ven. Postane mi nemogoče rešiti številne uganke, ki jih naša lestvica kategorizira kot težke ali zelo težke, ne da bi verjetnost zapisala s svinčnikom.

Metodologija Torozhkay in Erksi-Ravaz je bila najprej objavljena v Nature Physics in kasneje v Nature Scientific Reports.

Uporabite številke od 1 do 9

Sudoku se igra na mreži 9 krat 9, s skupno 81 mrežami. Znotraj igralnega polja je 9 "kvadratov" (sestavljenih iz 3 x 3 celic). Vsaka vodoravna vrstica, navpični stolpec in kvadrat (vsak po 9 celic) morajo biti napolnjeni s številkami 1-9, ne da bi se ponovile številke v vrstici, stolpcu ali kvadratu. Se sliši zapleteno? Kot lahko vidite na spodnji sliki, ima vsako igralno polje Sudoku več celic, ki so že zapolnjene. Več celic kot je na začetku zapolnjenih, lažja je igra. Manj celic je na začetku zapolnjenih, težja je igra.

Ne ponavljajte nobenih številk

Kot lahko vidite, je zgornji levi kvadrat (obkrožen z modro) že zapolnil 7 od 9 celic. Edini številki, ki manjkajo v tem kvadratu, sta številki 5 in 6. Če vidimo, katera števila manjkajo v vsakem kvadratu, vrstici ali stolpcu, se lahko s postopkom izločanja in deduktivnega sklepanja odločimo, katera števila naj bodo v vsaki celici. .

Na primer, v zgornjem levem kvadratu vemo, da moramo za dokončanje kvadrata sešteti številki 5 in 6, a če pogledamo sosednje vrstice in kvadratke, še vedno ne moremo jasno določiti, katero število dodati kateri celici. To pomeni, da bi morali zdaj preskočiti zgornji levi kvadratek in namesto tega poskusiti zapolniti vrzeli na drugih mestih na igrišču.

Ni treba ugibati

Sudoku je logična igra, zato ni treba ugibati. Če ne veste, katero številko bi vnesli v določeno celico, nadaljujte s pregledovanjem drugih območij igralnega polja, dokler ne vidite možnosti za vstavljanje želene številke. A ne poskušajte ničesar »na silo« – sudoku nagrajuje potrpežljivost, razumevanje in reševanje različnih kombinacij, ne pa slepe sreče ali ugibanja.

Uporabite metodo izločanja

Kaj naredimo, ko uporabimo "metodo izločanja" v igri Sudoku? Tukaj je primer. V tej mreži Sudoku (prikazano spodaj) manjka le nekaj številk v levem navpičnem stolpcu (obkroženo z modro): 1, 5 in 6.

Eden od načinov, kako ugotoviti, katera števila se lahko prilegajo vsaki celici, je uporaba "izločevalne metode", tako da preverite, katera druga števila so že v vsakem kvadratku, saj številk 1-9 ni dovoljeno podvajati v vsakem kvadratu, vrstici ali stolpec.

V tem primeru lahko hitro opazimo, da je v zgornjem levem in sredinskem levem kvadratku že številka 1 (številke 1 so obkrožene z rdečo). To pomeni, da je v skrajnem levem stolpcu samo eno mesto, kamor se lahko vstavi številka 1 (obkrožena zeleno). Takole deluje eliminacijski način v Sudoku – ugotovite, katere celice so proste, katere številke manjkajo, nato pa odstranite številke, ki so že prisotne v kvadratu, stolpcih in vrsticah. V skladu s tem izpolnite prazne celice z manjkajočimi številkami.

Pravila Sudokuja so razmeroma preprosta - vendar je igra izjemno raznolika, z milijoni možnih kombinacij številk in širokim naborom težavnostnih stopenj. Toda vse temelji na preprostih načelih uporabe številk 1-9, zapolnjevanju vrzeli na podlagi deduktivnega razmišljanja in nikoli ponavljanju številk v vsakem kvadratu, vrstici ali stolpcu.

vadnica

1. Osnove

Večina nas hekerjev ve, kaj je sudoku. Ne bom govoril o pravilih, ampak takoj preidimo na metode.
Za rešitev uganke, ne glede na to, kako zapletena ali preprosta, se najprej iščejo celice, ki jih je očitno zapolniti.

1.1 "Zadnji junak"

Razmislite o sedmem kvadratu. Samo štiri proste celice, tako da se lahko kaj hitro napolni.
"8 "na D3 oblazinjenje blokov H3 in J3; podobno " 8 "na G5 zapre G1 in G2
S čisto vestjo smo postavili " 8 "na H1

1.2 "Zadnji junak" zapored

Po ogledu kvadratov za očitne rešitve pojdite na stolpce in vrstice.
Razmislite " 4 " na igrišču. Jasno je, da bo nekje v vrsti A .
Imamo " 4 "na G3 ki pokriva A3, tukaj je " 4 "na F7, čiščenje A7. In še ena" 4 " v drugem kvadratku prepoveduje njegovo ponavljanje naprej A4 in A6.
"Zadnji junak" za naš " 4 "To A2

1.3 "Brez izbire"

Včasih je za določeno lokacijo več razlogov. " 4 "v J8 bi bil odličen primer.
modra puščice kažejo, da je to zadnje možno število na kvadrat. rdeča in modra puščice nam dajejo zadnjo številko v stolpcu 8 . Zelenice puščice kažejo zadnje možno število v vrstici J.
Kot lahko vidite, nimamo druge izbire, kot da to postavimo " 4 "na mestu.

1.4 "In kdo, če ne jaz?"

Izpolnjevanje številk je lažje izvesti z zgoraj opisanimi metodami. Vendar pa tudi preverjanje števila kot zadnje možne vrednosti daje rezultate. Metodo je treba uporabiti, ko se zdi, da so vse številke tam, vendar nekaj manjka.
"5 "v B1 je nastavljen na podlagi dejstva, da so vse številke od " 1 "pred" 9 ", poleg tega" 5 " je v vrstici, stolpcu in kvadratu (označeno z zeleno).

V žargonu je " goli samotar". Če izpolnite polje z možnimi vrednostmi(kandidati), bo v celici taka številka edina možna. Z razvojem te tehnike lahko iščete " skriti samotarji" - edinstvene številke za določeno vrstico, stolpec ali kvadrat.

2. "Gola milja"

2.1 Goli pari

""Goli" par" - niz dveh kandidatov, ki se nahajata v dveh celicah, ki pripadata enemu skupnemu bloku: vrstica, stolpec, kvadrat.
Jasno je, da bodo pravilne rešitve uganke le v teh celicah in samo s temi vrednostmi, vse ostale kandidate iz splošnega bloka pa je mogoče odstraniti.

V tem primeru je več "golih parov".
rdeča v vrsti AMPAK celice so poudarjene A2 in A3, oba vsebujeta " 1 "in" 6 ". Ne vem še točno, kako se tukaj nahajajo, vendar lahko varno odstranim vse druge " 1 "in" 6 "iz niza A(označeno z rumeno). Tudi A2 in A3 pripadajo skupnemu kvadratu, zato odstranimo " 1 "od C1.

2.2 "Troje"

"Gole trojke"- zapletena različica "golih parov".
Vsaka skupina treh celic v enem bloku, ki vsebuje glede na vse trije kandidati so "goli trio". Ko se najde takšna skupina, lahko te tri kandidate odstranimo iz drugih celic bloka.

Kombinacije kandidatov za "goli trio" lahko je takole:

// tri številke v treh celicah.
// poljubne kombinacije.
// poljubne kombinacije.

V tem primeru je vse precej očitno. V petem kvadratu celice E4, E5, E6 vsebujejo [ 5,8,9 ], [5,8 ], [5,9 ] oziroma. Izkazalo se je, da imajo te tri celice na splošno [ 5,8,9 ] in tam so lahko samo te številke. To nam omogoča, da jih odstranimo iz drugih kandidatov za blok. Ta trik nam daje rešitev " 3 "za celico E7.

2.3 "Fab Four"

"Goli štirje" zelo redek pojav, zlasti v polni obliki, vendar ob odkritju daje rezultate. Logika rešitve je enaka kot "goli trojčki".

V zgornjem primeru v prvem kvadratu celice A1, B1, B2 in C1 na splošno vsebujejo [ 1,5,6,8 ], zato bodo te številke zasedle samo te celice in nobene druge. Kandidate, označene z rumeno, odstranimo.

3. "Vse skrito postane jasno"

3.1 Skriti pari

Odličen način za odpiranje polja je iskanje skritih parov. Ta metoda vam omogoča, da odstranite nepotrebne kandidate iz celice in ustvarite bolj zanimive strategije.

V tej uganki to vidimo 6 in 7 je v prvem in drugem kvadratku. Poleg tega 6 in 7 je v stolpcu 7 . Če združimo te pogoje, lahko trdimo, da v celicah A8 in A9 obstajajo samo te vrednosti in odstranimo vse druge kandidate.

Bolj zanimiv in zapleten primer skritih parov. Par [ 2,4 ] v D3 in E3, čiščenje 3 , 5 , 6 , 7 iz teh celic. Z rdečo sta označena dva skrita para, sestavljena iz [ 3,7 ]. Po eni strani so edinstveni za dve celici v 7 stolpec, na drugi strani - za vrstico E. Kandidati, označeni z rumeno, se odstranijo.

3.1 Skriti trojčki

Lahko se razvijamo skritih parov prej skriti trojčki ali celo skrite štirice. Skriti trije je sestavljen iz treh parov številk, ki se nahajajo v enem bloku. Kot so in. Vendar, tako kot v primeru z "goli trojčki", ni nujno, da vsaka od treh celic vsebuje tri številke. bo delovalo Skupaj tri številke v treh celicah. Na primer , , . Skriti trojčki bodo prikrili drugi kandidati v celicah, zato se morate najprej prepričati trojka velja za določen blok.

V tem zapletenem primeru sta dva skriti trojčki. Prvi, označen z rdečo, v stolpcu AMPAK. Celica A4 vsebuje [ 2,5,6 ], A7 - [2,6 ] in celico A9 -[2,5 ]. Te tri celice so edine, kjer je lahko 2, 5 ali 6, zato bodo edine tam. Zato odstranimo nepotrebne kandidate.

Drugič, v koloni 9 . [4,7,8 ] so edinstvene za celice B9, C9 in F9. Po isti logiki odstranimo kandidate.

3.1 Skrite štirice

Popoln primer skrite štirice. [1,4,6,9 ] v petem kvadratku je lahko le v štirih celicah D4, D6, F4, F6. Po naši logiki odstranimo vse ostale kandidate (označene z rumeno).

4. "brez gume"

Če se katera koli od številk pojavi dvakrat ali trikrat v istem bloku (vrstica, stolpec, kvadrat), lahko to številko odstranimo iz konjugiranega bloka. Obstajajo štiri vrste seznanjanja:

Par ali tri v kvadratu - če se nahajajo v eni vrstici, lahko odstranite vse druge podobne vrednosti iz ustrezne vrstice.
Par ali tri v kvadratu - če se nahajajo v enem stolpcu, lahko odstranite vse druge podobne vrednosti iz ustreznega stolpca.
Par ali tri v vrsti - če se nahajajo v istem kvadratu, lahko odstranite vse druge podobne vrednosti iz ustreznega kvadrata.
Par ali tri v stolpcu - če se nahajajo v istem kvadratu, lahko odstranite vse druge podobne vrednosti iz ustreznega kvadrata.

4.1 Kazalni pari, trojke

Naj vam pokažem to uganko kot primer. V tretjem kvadratu 3 "je samo notri B7 in B9. Po izjavi №1 , odstranimo kandidate iz B1, B2, B3. Prav tako " 2 " iz osmega kvadrata odstrani možno vrednost iz G2.

Posebna uganka. Zelo težko rešiti, a če natančno pogledate, lahko vidite nekaj kazalne pare. Jasno je, da ni vedno treba poiskati vseh, da bi napredovali pri rešitvi, a nam vsaka taka najdba olajša nalogo.

4.2 Zmanjšanje nereducibilnega

Ta strategija vključuje natančno razčlenitev in primerjavo vrstic in stolpcev z vsebino kvadratov (pravila №3 , №4 ).
Razmislite o vrstici AMPAK. "2 "so možne samo v A4 in A5. po pravilu №3 , Odstrani " 2 " njim B5, C4, C5.

Nadaljujmo z reševanjem uganke. Imamo eno lokacijo 4 " znotraj enega kvadrata 8 stolpec. Po pravilu №4 , odstranimo nepotrebne kandidate in poleg tega dobimo rešitev " 2 "za C7.