Hogyan lehet megoldani a kemény sudokut. A matematikusok egy képletet találtak ki a Sudoku megoldására

A Sudoku mező 9x9 cellákból álló táblázat. Minden cellába egy 1-től 9-ig terjedő számot kell beírni. Más szóval, minden oszlopnak, sornak és blokknak tartalmaznia kell az összes számot 1-től 9-ig.

A probléma megoldásához a jelöltek üres cellákba írhatók. Például vegyünk egy cellát a 4. sor 2. oszlopában: abban az oszlopban, amelyben található, már van 7 és 8, a sorban - 1, 6, 9 és 4, a blokkban - 1 , 2, 8 és 9 Ezért ebben a cellában kihúzunk 1, 2, 4, 6, 7, 8, 9 jelölteket, és már csak két lehetséges jelölt marad - a 3 és az 5.

Hasonlóképpen megvizsgáljuk a lehetséges jelölteket más cellákhoz, és a következő táblázatot kapjuk:

A jelöltekkel érdekesebb foglalkozni, és különböző logikai módszereket is lehet alkalmazni. A következőkben ezek közül nézünk meg néhányat.

Magányosok

A módszer abból áll, hogy a táblázatban egyeseket keresünk, azaz. olyan cellák, amelyekben csak egy számjegy lehetséges, más nem. Ezt a számot ebbe a cellába írjuk, és kizárjuk a sor, oszlop és blokk többi cellájából. Például: ebben a táblázatban három "magányos" van (sárgával vannak kiemelve).

rejtett magányosok

Ha egy cellában több jelölt is van, de ezek közül egy nem található az adott sor (oszlop vagy blokk) másik cellájában, akkor az ilyen jelöltet „rejtett magányosnak” nevezzük. A következő példában a zöld blokkban szereplő „4” jelölt csak a középső cellában található. Tehát ebben a cellában biztosan lesz „4”. Ebbe a cellába írjuk be a „4”-et, és kihúzzuk a 2. oszlop és az 5. sor többi cellájából. Hasonlóképpen, a sárga oszlopban a "2" jelölt egyszer fordul elő, ezért ebbe a cellába írjuk be a "2"-t, és kizárjuk a "2"-t a 7. sor celláiból és a megfelelő blokkból.

Az előző két módszer az egyetlen olyan módszer, amely egyedileg határozza meg egy cella tartalmát. A következő módszerek csak a cellákban lévő jelöltek számának csökkentését teszik lehetővé, ami előbb-utóbb magányosokhoz vagy rejtett magányosokhoz vezet.

Lezárt jelölt

Vannak esetek, amikor egy jelölt egy blokkon belül csak egy sorban (vagy egy oszlopban) szerepel. Tekintettel arra, hogy ezen cellák egyike szükségszerűen tartalmazza ezt a jelöltet, ez a jelölt kizárható ennek a sornak (oszlopnak) az összes többi cellájából.

Az alábbi példában a középső blokk csak a középső oszlopban tartalmazza a „2” jelöltet (sárga cellák). Tehát e két cella egyikének feltétlenül „2”-nek kell lennie, és a sorban ezen a blokkon kívül egyetlen más cella sem lehet „2”. Ezért a „2” kizárható jelöltként az oszlop többi cellájából (zöld cellák).

Nyissa meg a Párokat

Ha egy csoport két cellája (sor, oszlop, blokk) azonos jelöltpárt tartalmaz, és semmi mást, akkor ebben a csoportban egyetlen más cella sem rendelkezhet ennek a párnak az értékével. Ez a 2 jelölt kizárható a csoport többi cellájából. Az alábbi példában az „1” és „5” jelöltek a nyolcas és kilencedik oszlopban nyitott párt alkotnak a blokkon belül (sárga cellák). Ezért, mivel ezen cellák egyikének "1"-nek, a másiknak pedig "5"-nek kell lennie, az "1" és "5" jelöltek ki vannak zárva a blokk összes többi cellájából (zöld cellák).

Ugyanez 3 és 4 jelöltre is megfogalmazható, már csak 3, illetve 4 sejt vesz részt. Nyitott hármasok: a zöld cellák közül kizárjuk a sárga cellák értékeit.

Nyitott négyes: a zöld cellák közül a sárga cellák értékeit kizárjuk.

rejtett párok

Ha egy csoportban (sor, oszlop, blokk) két cella tartalmaz jelölteket, amelyek között van olyan azonos pár, amely nem fordul elő ennek a blokknak egyetlen cellájában sem, akkor ennek a párnak az értékével a csoport más cellái sem rendelkezhetnek. Ezért ennek a két sejtnek az összes többi jelöltje kizárható. Az alábbi példában a középső oszlopban szereplő „7” és „5” jelölt csak sárga cellákban található, ami azt jelenti, hogy ezekből a cellákból az összes többi jelölt kizárható.

Hasonlóképpen kereshet rejtett hármasokat és négyeseket.

x-szárnyú

Ha egy értéknek csak két lehetséges helye van egy sorban (oszlopban), akkor az egyik cellához kell hozzárendelni. Ha van még egy olyan sor (oszlop), ahol ugyanaz a jelölt is csak két cellában szerepelhet, és ezeknek a celláknak az oszlopai (sorai) megegyeznek, akkor ezen oszlopok (sorok) másik cellája sem tartalmazhatja ezt a számot. Vegyünk egy példát:

A 4. és 5. sorban a „2” szám csak két sárga cellában lehet, és ezek a cellák ugyanabban az oszlopban vannak. Ezért a "2" szám csak kétféleképpen írható: 1) ha a 4. sor 5. oszlopába "2" van írva, akkor a sárga cellákból ki kell zárni a "2"-t, majd az 5. sorban a a "2" pozíciót egyértelműen a 7. oszlop határozza meg.

2) ha a 4. sor 7. oszlopába „2” van írva, akkor a „2”-t ki kell hagyni a sárga cellákból, majd az 5. sorban a „2” pozíciót az 5. oszlop határozza meg egyértelműen.

Ezért az 5. és 7. oszlopban szükségszerűen a „2” szám lesz a 4. vagy az 5. sorban. Ekkor a „2” szám kizárható ezen oszlopok többi cellájából (zöld cellák).

"Kardhal" (Kardhal)

Ez a módszer a .

A feladvány szabályaiból következik, hogy ha egy jelölt három sorban és csak három oszlopban szerepel, akkor a többi sorból ez a jelölt ezekben az oszlopokban kizárható.

Algoritmus:

• Olyan sorokat keresünk, amelyekben a jelölt legfeljebb háromszor fordul elő, ugyanakkor pontosan három oszlopba tartozik.
• A többi sorból kizárjuk a jelöltet ebből a három oszlopból.

Ugyanez a logika érvényes három oszlop esetén is, ahol a jelölt három sorra korlátozódik.

Vegyünk egy példát. Három sorban (3., 5. és 7.) az „5” jelölt legfeljebb háromszor fordul elő (a cellák sárgával vannak kiemelve). Ezek azonban csak három oszlopba tartoznak: a 3., 4. és 7. oszlopba. A „Kardhal” módszer szerint az „5” jelölt kizárható ezen oszlopok többi cellájából (zöld cellák).

Az alábbi példában a Swordfish módszert is alkalmazzuk, de három oszlop esetén. Az „1” jelöltet kizárjuk a zöld cellákból.

Az "X-wing" és a "Swordfish" négy sorra és négy oszlopra általánosítható. Ennek a módszernek a neve "Medusa".

Színek

Vannak helyzetek, amikor egy jelölt csak kétszer fordul elő egy csoportban (egy sorban, oszlopban vagy blokkban). Akkor a kívánt szám biztosan benne lesz az egyikben. A Színek módszer stratégiája az, hogy ezt a kapcsolatot két szín, például sárga és zöld használatával tekintsük meg. Ebben az esetben az oldat csak egyszínű cellákban lehet.

Kiválasztjuk az összes összekapcsolt láncot, és meghozzuk a döntést:

• Ha egy árnyékolatlan jelöltnek két különböző színű szomszédja van egy csoportban (sor, oszlop vagy blokk), akkor kizárható.
• Ha két azonos szín van egy csoportban (sor, oszlop vagy blokk), akkor ez a szín hamis. Az összes ilyen színű cellából egy jelölt kizárható.

A következő példában alkalmazza a "Colors" módszert a "9" jelölt cellákra. A színezést a bal felső blokk cellájából kezdjük (2. sor, 2. oszlop), fessük sárgára. A blokkjában csak egy szomszédja van "9-essel", fessük zöldre. Neki is csak egy szomszédja van az oszlopban, azt zöldre festjük.

Hasonlóképpen dolgozunk a "9" számot tartalmazó cellák többi részével is. Kapunk:

A „9” jelölt lehet csak az összes sárga cellában vagy teljesen zöldben. A jobb középső blokkban két azonos színű cella találkozott, ezért a zöld szín helytelen, mivel ez a blokk két "9-est" produkál, ami elfogadhatatlan. A "9"-et kizárjuk minden zöld cellából.

Egy másik példa a "Színek" módszerre. Jelöljünk páros cellákat a jelölthez "6".

A felső központi blokkban (lilával kiemelve) lévő "6"-os cellában két többszínű jelölt található:

A "6" szükségszerűen sárga vagy zöld cellában található, ezért a "6" kizárható ebből a lila cellából.

Az első dolog, amit a problémamegoldás módszertanában meg kell határozni, az a kérdés, hogy valóban megértsük, mit érünk el és érhetünk el a problémamegoldás terén. A megértésre általában úgy gondolunk, mint ami magától értetődő, és szem elől tévesztjük azt a tényt, hogy a megértésnek van egy határozott kiindulópontja a megértésnek, csak ehhez képest mondhatjuk, hogy a megértés valóban egy általunk meghatározott pillanattól fogva megtörténik. A Sudoku itt, véleményünk szerint, abból a szempontból kényelmes, hogy példáján keresztül bizonyos mértékig lehetővé teszi a problémák megértésének és megoldásának a modellezését. Mindazonáltal számos más, a Sudokunál nem kevésbé fontos példával kezdjük.

Egy speciális relativitáselméletet tanulmányozó fizikus beszélhet Einstein „kristálytiszta” tételeiről. Az egyik internetes oldalon bukkantam erre a kifejezésre. De hol kezdődik a „kristálytisztaság” megértése? A posztulátumok matematikai jelölésének asszimilációjával kezdődik, amelyből ismert és érthető szabályok szerint az SRT összes többszintű matematikai konstrukciója felépíthető. De amit a fizikus, hozzám hasonlóan nem ért, az az, hogy az SRT posztulátumai miért így működnek, és miért nem másként.

Először is, a doktrínát tárgyalók túlnyomó többsége nem érti, hogy pontosan mi rejlik a fénysebesség állandóságának posztulátumában a matematikai alkalmazásból a valóságba történő fordításban. És ez a posztulátum magában foglalja a fénysebesség állandóságát minden elképzelhető és felfoghatatlan értelemben. A fénysebesség minden nyugvó és egyidejűleg mozgó objektumhoz képest állandó. A fénysugár sebessége a posztulátum szerint a szembejövő, keresztirányú és távolodó fénysugárhoz képest is állandó. És ugyanakkor a valóságban csak olyan méréseink vannak, amelyek közvetve kapcsolódnak a fénysebességhez, annak állandóságaként értelmezve.

Newton törvényei a fizikusok és még azok számára is, akik egyszerűen csak fizikát tanulnak, annyira ismerősek, hogy annyira érthetőnek tűnnek, mint valami magától értetődőnek, és nem is lehet másként. De mondjuk az univerzális gravitáció törvényének alkalmazása a matematikai jelölésével kezdődik, amely szerint még az űrobjektumok pályái és a pályák jellemzői is kiszámíthatók. De hogy ezek a törvények miért így működnek, és miért nem másként – ezt nem értjük.

Ugyanígy a Sudokuval. Az interneten ismételten találhat leírásokat a Sudoku-problémák "alapvető" módjairól. Ha emlékszik ezekre a szabályokra, akkor megértheti, hogyan oldható meg ez vagy az a Sudoku probléma az „alap” szabályok alkalmazásával. De van egy kérdésem: értjük-e, hogy ezek az "alap" módszerek miért így működnek, és miért nem másként.

Tehát továbblépünk a problémamegoldó módszertan következő kulcsfontosságú pontjára. A megértés csak olyan modell alapján lehetséges, amely alapot ad ehhez a megértéshez és valamilyen természetes vagy gondolati kísérlet elvégzésének képességéhez. E nélkül csak a tanult kiindulópontok alkalmazására lehetnek szabályaink: az SRT posztulátumai, Newton törvényei vagy „alapvető” Sudoku-módszerek.

Nincsenek és elvileg nem is lehetnek olyan modelljeink, amelyek kielégítik a fénysebesség korlátlan állandóságának posztulátumát. Mi nem, de a Newton-törvényekkel összhangban lévő, bizonyíthatatlan modelleket ki lehet találni. És vannak ilyen "newtoni" modellek, de valahogy nem nyűgöznek le egy teljes körű vagy gondolatkísérlet végrehajtásának produktív lehetőségeivel. De a Sudoku olyan lehetőségeket kínál számunkra, amelyeket felhasználhatunk a Sudoku tényleges problémáinak megértésére, és a modellezés mint a problémák megoldásának általános megközelítése szemléltetésére.

A Sudoku problémák egyik lehetséges modellje a munkalap. Ez úgy jön létre, hogy egyszerűen kitölti a feladatban megadott táblázat összes üres celláját (celláját) az 123456789 számokkal. Ezután a feladat leredukálódik az összes extra számjegy szekvenciális eltávolítására a cellákból, amíg a táblázat összes cellája el nem fogy. egyetlen (kizárólagos) számjegyekkel töltve, amelyek kielégítik a probléma feltételét.

Egy ilyen munkalapot készítek Excelben. Először kijelölöm a táblázat összes üres celláját (celláját). Megnyomom az F5-"Select"-"Empty cell"-"OK"-t. A kívánt cellák kijelölésének általánosabb módja: tartsa lenyomva a Ctrl billentyűt, és kattintson az egérrel a cellák kijelöléséhez. Ezután a kiválasztott celláknál kékre állítottam a színt, 10-es méretre (eredeti - 12) és betűtípusra Arial Narrow. Mindez azért van, hogy a táblázat későbbi változásai jól láthatóak legyenek. Ezután az üres cellákba beírom a 123456789 számot, amit a következőképpen teszek: Leírom és elmentem egy külön cellába. Ezután megnyomom az F2-t, kiválasztom és a Ctrl + C művelettel kimásolom ezt a számot. Ezután a táblázat celláira lépek, és sorra megkerülve az összes üres cellát, a Ctrl + V művelettel beírom az 123456789 számot, és kész is a munkalap.

A további számokat, amelyekről később lesz szó, az alábbiak szerint törlöm. A Ctrl + egérkattintással művelettel kijelölöm a cellákat extra számmal. Ezután lenyomom a Ctrl + H billentyűket és a megnyíló ablak felső mezőjébe beírom a törölni kívánt számot, az alsó mező pedig teljesen üres legyen. Ezután kattintson a "Minden cseréje" lehetőségre, és az extra szám eltávolításra kerül.

Abból a tényből ítélve, hogy általában a megszokott "alap" módszerekkel haladóbb táblázatfeldolgozást sikerül elvégeznem, mint az interneten feladott példákban, a munkalap a legegyszerűbb eszköz a Sudoku feladatok megoldásában. Sőt, az úgynevezett „alap” szabályok legbonyolultabb alkalmazásával kapcsolatos számos helyzet egyszerűen nem merült fel a munkalapomon.

A munkalap egyben modell is, amelyen kísérleteket lehet végezni, az összes „alap” szabály utólagos azonosításával és alkalmazásának a kísérletekből fakadó különféle árnyalataival.

Tehát előtted van egy kilenc blokkból álló munkalap töredéke, balról jobbra és fentről lefelé számozva. Ebben az esetben a negyedik blokk 123456789 számokkal van kitöltve. Ez a mi modellünk. A blokkon kívül piros színnel kiemeltük az "aktivált" (végül meghatározott) számokat, jelen esetben négyeseket, amelyeket a készülő táblázatban pótolni kívánunk. A kék ötösök olyan figurák, amelyek jövőbeni szerepüket még nem határozták meg, amiről később lesz szó. Az általunk hozzárendelt aktivált számok mintegy áthúzódnak, kinyomnak, törlődnek - általában ugyanazokat a számokat helyezik el a blokkban, így ott halvány színnel jelennek meg, szimbolizálva azt a tényt, hogy ezek a halvány számok törölve. Ezt a színt szerettem volna még halványabbá tenni, de akkor az interneten nézegetve teljesen láthatatlanná válhattak.

Ennek eredményeként a negyedik blokkban, az E5 cellában volt egy, szintén aktiválva, de négy rejtett. "Aktiválva", mert ő viszont el tudja távolítani a plusz számjegyeket, ha útban vannak, és "rejtett", mert a többi számjegy között van. Ha az E5 cellát megtámadják a többiek, kivéve a 4 aktivált 12356789 számot, akkor egy "meztelen" magányos jelenik meg az E5 - 4-ben.

Most távolítsunk el egy aktivált négyet, például az F7-ből. Ekkor a kitöltött blokkban lévő négyes már és csak az E5 vagy F5 cellában lehet, miközben az 5. sorban aktív marad. Ha ebben a helyzetben aktivált ötösök érintettek, F7=4 és F8=5 nélkül, akkor az E5 és F5 cellában ott csupasz vagy rejtett aktivált pár lesz 45.

Miután kellőképpen kidolgozta és megértette a különböző lehetőségeket a meztelen és rejtett szinglik, kettesek, hármasok stb. nemcsak blokkokban, hanem sorokban és oszlopokban is áttérhetünk egy másik kísérletre. Hozzunk létre egy csupasz 45-ös párt, mint korábban, majd kössük össze az aktivált F7=4 és F8=5 értékeket. Ennek eredményeként az E5=45 helyzet áll elő. Hasonló helyzetek nagyon gyakran előfordulnak egy munkalap feldolgozása során. Ez a helyzet azt jelenti, hogy ezen számjegyek egyikének, jelen esetben 4-nek vagy 5-nek, szükségszerűen az E5 cellát tartalmazó blokkban, sorban és oszlopban kell lennie, mivel ezekben az esetekben két számjegynek kell lennie, nem pedig az egyiknek.

És ami a legfontosabb, most már tudjuk, hogy milyen gyakran előfordulnak olyan helyzetek, mint az E5=45. Hasonló módon fogjuk meghatározni azokat a helyzeteket, amikor egy cellában három számjegy jelenik meg stb. És amikor ezeknek a helyzeteknek a megértésének és észlelésének fokát a magától értetődő és az egyszerűség állapotára hozzuk, akkor a következő lépés, úgymond, a helyzetek tudományos megértése: akkor képesek leszünk a helyzetek statisztikai elemzésére. Sudoku táblázatok, minták azonosítása és a felhalmozott anyagok felhasználása a legösszetettebb problémák megoldására.

Így a modellen kísérletezve vizuális, sőt "tudományos" reprezentációt kapunk a rejtett vagy nyílt szinglikről, párokról, hármasokról stb. Ha a leírt egyszerű modellel végzett műveletekre korlátozza magát, akkor néhány ötlete pontatlannak vagy akár hibásnak bizonyul. Amint azonban rátérünk a konkrét problémák megoldására, gyorsan fény derül a kezdeti elképzelések pontatlanságaira, de át kell gondolni, finomítani azokat a modelleket, amelyeken a kísérleteket végezték. Ez a hipotézisek és finomítások elkerülhetetlen útja bármely probléma megoldásában.

Azt kell mondanom, hogy a rejtett és nyitott szinglik, valamint a nyílt párok, hármasok és még négyesek is gyakori helyzetek, amelyek a Sudoku feladatok munkalappal történő megoldása során merülnek fel. A rejtett párok ritkák voltak. És itt vannak a rejtett hármasok, négyesek stb. A munkalapok feldolgozása során valahogy nem akadtam rá, mint ahogy az interneten már többször leírt „x-szárnyú” és „kardhal” kontúrok kikerülési módszereire sem, amelyekben bármelyik törlésre „jelöltek” vannak. két alternatív módja a kontúrok megkerülésének. Ezeknek a módszereknek a jelentése: ha megsemmisítjük az x1 "jelölt"-et, akkor az x2 kizárólagos jelölt marad, és egyben az x3 jelölt törlődik, ha pedig az x2-t, akkor a kizárólagos x1 marad, de ebben az esetben a jelölt Az x3 is törlésre kerül, tehát minden esetben az x3-at kell törölni, egyelőre nem érintve az x1 és x2 jelölteket. Általánosabban, ez a helyzet speciális esete: ha két alternatív módszer ugyanarra az eredményre vezet, akkor ez az eredmény felhasználható egy Sudoku probléma megoldására. Ebben az általánosabb szituációban találkoztam helyzetekkel, de nem az "x-wing" és a "swordfish" változatban, és nem a Sudoku feladatok megoldásánál, amelyekhez csak az "alap" megközelítések ismerete elegendő.

A munkalap használatának jellemzőit a következő nem triviális példa mutatja be. Az egyik sudoku megoldó fórumon http://zforum.net/index.php?topic=3955.25;wap2 találkoztam egy olyan problémával, amelyet az egyik legnehezebb sudoku-problémaként mutattak be, és nem oldható meg a szokásos módon, felsorolás nélkül. feltételezések a cellákban helyettesített számokról . Mutassuk meg, hogy egy munkaasztallal meg lehet oldani ezt a problémát ilyen felsorolás nélkül:

Jobb oldalon az eredeti feladat, bal oldalon a "törlés" utáni munkatábla, azaz. rutin művelet a plusz számjegyek eltávolítására.

Először is állapodjunk meg a jelölésben. Az ABC4=689 azt jelenti, hogy az A4, B4 és C4 cellák a 6, 8 és 9 számokat tartalmazzák – cellánként egy vagy több számjegyet. Ugyanez a helyzet a húrokkal. Így a B56=24 azt jelenti, hogy a B5 és B6 cellák a 2-es és 4-es számokat tartalmazzák. A ">" jel egy feltételes akciójel. Így a D4=5>I4-37 azt jelenti, hogy a D4=5 üzenet miatt a 37-es szám kerüljön az I4-es cellába. Az üzenet lehet explicit – „meztelen” – és rejtett, amit fel kell fedni. Az üzenet hatása lehet szekvenciális (közvetetten továbbítható) a lánc mentén és párhuzamos (közvetlenül más cellákra hathat). Például:

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

Ez a bejegyzés azt jelenti, hogy D3=2, de ezt a tényt fel kell fedni. D8=1 átadja a műveletét a láncon A3-nak, a 4-et pedig A3-nak kell írni; ugyanakkor a D3=2 közvetlenül a G9-re hat, ami G9-3-at eredményez. (D8=1)+(G9=3)>G8-7 – a tényezők együttes hatása (D8=1) és (G9=3) a G8-7 eredményhez vezet. Stb.

A rekordok tartalmazhatják a H56/68 típusú kombinációt is. Ez azt jelenti, hogy a 6-os és a 8-as számok tilosak a H5 és H6 cellában, pl. el kell távolítani ezeket a sejtekből.

Tehát elkezdünk dolgozni a táblázattal, és kezdetnek alkalmazzuk az ABC4=689 jól megnyilvánuló, észrevehető feltételt. Ez azt jelenti, hogy a 4. blokk (középen, balra) és a 4. sor összes többi (A4, B4 és C4 kivételével) cellájában a 6-os, 8-as és 9-es számokat törölni kell:

Ugyanígy alkalmazza a B56=24-et. Együtt D4=5 és (D4=5>I4-37 után) HI4=37, valamint (B56=24>C6-1 után) C6=1. Alkalmazzuk ezt egy munkalapra:

I89=68rejtett>I56/68>H56-68-ban: i.e. az I8 és I9 cellák rejtett 5-ös és 6-os számjegypárt tartalmaznak, ami megtiltja, hogy ezek a számjegyek az I56-ban legyenek, ami a H56-68 eredményt eredményezi. Ezt a töredéket másképpen is felfoghatjuk, akárcsak a munkalapmodellel végzett kísérleteknél: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. Vagyis egy kétirányú "támadás" (G23=68) és (AD7=68) oda vezet, hogy csak a 6 és 8 számok lehetnek az I8-ban és I9-ben. További (I89=68) a " támadás" a H56 ellen a korábbi feltételekkel együtt, ami a H56-68-hoz vezet. Ezen túlmenően "támadás" is kapcsolódik (ABC4=689), ami ebben a példában feleslegesnek tűnik, viszont ha munkaasztal nélkül dolgoznánk, akkor az impakt faktor (ABC4=689) rejtve lenne, és elég célszerű külön odafigyelni rá.

Következő művelet: I5=2>G1-2,G6-9,B6-4,B5-2.

Remélem, már kommentár nélkül is világos: cserélje ki a gondolatjel utáni számokat, nem tévedhet:

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

A következő akciósorozat:

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,

vagyis az "áthúzás" - plusz számjegyek törlése - eredményeként az F8 és F9 cellákban egy nyitott, "csupasz" 89 pár jelenik meg, amit a rekordban feltüntetett egyéb eredményekkel együtt a táblázatra is alkalmazunk:

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

Eredményük:

Ezt meglehetősen rutinszerű, nyilvánvaló cselekvések követik:

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

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

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

Eredményük: a probléma végső megoldása:

Így vagy úgy, de feltételezzük, hogy a Sudokuban vagy a szellemi alkalmazás más területein az "alapvető" módszereket egy erre alkalmas modell alapján találtuk ki, sőt, megtanultuk az alkalmazásukat is. De ez csak egy része a problémamegoldó módszertanban elért haladásunknak. Továbbá, ismétlem, a következőket nem mindig veszik figyelembe, hanem elengedhetetlen szakasza annak, hogy a korábban tanult módszereket a könnyű alkalmazási állapotba hozzuk. Példák megoldása, e megoldás eredményeinek, módszereinek megértése, az anyag újragondolása az elfogadott modell alapján, újra végiggondolva az összes lehetőséget, megértésének mértékét az automatizmusba hozva, amikor az „alap” rendelkezéseket használó megoldás rutinná válik. és problémaként eltűnik. Amit ad: mindenki érezze a saját tapasztalata alapján. A lényeg pedig az, hogy amikor a problémahelyzet rutinszerűvé válik, az értelem keresőmechanizmusa egyre bonyolultabb rendelkezések kidolgozására irányul a megoldandó problémák terén.

És mi az "összetettebb rendelkezések"? Ezek csak új "alap" rendelkezések a probléma megoldásában, amelyek megértése pedig szintén az egyszerűség állapotába hozható, ha találunk erre a célra megfelelő modellt.

A cikkben Vasilenko S.L. "Numeric Harmony Sudoku" Találtam egy példát a 18 szimmetrikus billentyű problémájára:

Ezzel a feladattal kapcsolatban leszögezik, hogy "alap" módszerekkel csak egy bizonyos állapotig oldható meg, aminek elérése után már csak egy egyszerű felsorolást kell alkalmazni próbahelyettesítéssel valamilyen feltételezett kizárólagos (egyes, egyszeri) celláiba. ) számjegyek. Ez az állapot (kicsit tovább haladva, mint Vasilenko példájában) így néz ki:

Van ilyen modell. Ez egyfajta forgatási mechanizmus az azonosított és azonosítatlan kizárólagos (egyetlen) számjegyekhez. A legegyszerűbb esetben a kizárólagos számjegyek néhány hármasa jobbra vagy balra forog, sorról sorra vagy oszlopról oszlopra haladva e csoport mellett. Általánosságban elmondható, hogy egyidejűleg három számhármas csoport forog egy irányba. Bonyolultabb esetekben három pár exkluzív számjegy forog egy irányba, és egy három pár az ellenkező irányba. Így például a vizsgált feladat első három sorának kizárólagos számjegyei el vannak forgatva. És ami a legfontosabb, ez a fajta elforgatás látható, ha figyelembe vesszük a számok helyét a feldolgozott munkalapon. Ez az információ egyelőre elegendő, és a probléma megoldása során megértjük a rotációs modell egyéb árnyalatait.

Tehát az első (felső) három sorban (1, 2 és 3) észrevehetjük a (3+8) és (7+9), valamint a (2+x1) párok forgását ismeretlen x1-el és a egyesek hármasa (x2+4+ 1) ismeretlen x2-vel. Ennek során azt tapasztalhatjuk, hogy x1 és x2 egyaránt lehet 5 vagy 6.

A 4., 5. és 6. sor a (2+4) és (1+3) párokat nézi. Kell egy harmadik ismeretlen pár és egy hármas szingli is, amelyek közül csak egy 5-ös számjegy ismert.

Hasonlóképpen nézzük a 789. sort, majd az ABC, DEF és GHI oszlopok hármasait. Az összegyűjtött információkat szimbolikus és remélem érthető formában írjuk le:

Eddig csak az általános helyzet megértéséhez van szükségünk ezekre az információkra. Gondold át alaposan, és akkor továbbléphetünk a következő, kifejezetten erre készült táblázathoz:

Az alternatívákat színekkel emeltem ki. A kék jelentése "engedélyezett", a sárga pedig "tilos". Ha mondjuk megengedett A2=79 megengedett A2=7, akkor C2=7 tiltott. Vagy fordítva – engedélyezett A2=9, tiltott C2=9. Ezután az engedélyek és tilalmak egy logikai lánc mentén kerülnek továbbításra. Ez a színezés a különböző alternatívák könnyebb áttekintése érdekében történik. Általában ez némi analógia a táblázatok feldolgozásakor korábban említett "x-wing" és "swordfish" módszerekhez.

A B6=7, illetve a B7=9 opciókat tekintve rögtön találunk két pontot, ami nem kompatibilis ezzel az opcióval. Ha B7=9, akkor a 789-es sorban szinkronosan forgó hármas lép fel, ami elfogadhatatlan, hiszen vagy csak három pár (és hozzájuk aszinkron módon három szingli), vagy három hármas (egyesek nélkül) tud szinkronosan (egy irányba) forogni. Ráadásul, ha B7=9, akkor a 7. sorban lévő munkalap több lépéses feldolgozása után találunk inkompatibilitást: B7=D7=9. Tehát a két alternatíva közül az egyetlen elfogadhatót helyettesítjük B6=9, és akkor a probléma megoldása egyszerű hagyományos feldolgozási módszerrel, vak felsorolás nélkül:

Következőnek van egy kész példám egy rotációs modell segítségével a Sudoku Világbajnokság egyik problémájának megoldására, de ezt a példát kihagyom, hogy ne feszítsem túl ezt a cikket. Ezen túlmenően, mint kiderült, ennek a problémának három megoldása van, ami nem alkalmas a számjegyforgatási modell kezdeti fejlesztésére. Sokat pöfögtem Gary McGuire internetről előhúzott 17 kulcsos feladatán is, hogy megfejtse a rejtvényét, mígnem még nagyobb bosszúsággal rájöttem, hogy ennek a „rejtvénynek” több mint 9 ezer megoldása van.

Így akarva-akaratlanul tovább kell lépnünk az Arto Inkala által kifejlesztett "világ legnehezebb" Sudoku-problémára, amelynek, mint tudod, egyedi megoldása van.

Két teljesen nyilvánvaló exkluzív szám beírása és a munkalap feldolgozása után a feladat így néz ki:

Az eredeti problémához rendelt billentyűk feketével és nagyobb betűtípussal vannak kiemelve. A probléma megoldásában való előrelépéshez ismét egy erre a célra alkalmas, megfelelő modellre kell támaszkodnunk. Ez a modell egyfajta mechanizmus a számok forgatására. Ebben és a korábbi cikkekben már többször szó volt róla, de a cikk további anyagának megértéséhez ezt a mechanizmust át kell gondolni és részletesen ki kell dolgozni. Körülbelül olyan, mintha tíz évig dolgoztál volna egy ilyen mechanizmussal. De akkor is meg fogod érteni ezt az anyagot, ha nem is az első olvasatból, akkor a második-harmadikból stb. Sőt, ha kitartasz, akkor ezt a "nehezen érthető" anyagot a rutin és az egyszerűség állapotába hozza. Ebben a tekintetben nincs semmi újdonság: ami eleinte nagyon nehéz, az fokozatosan nem lesz olyan nehéz, és a további szakadatlan kidolgozással minden a legnyilvánvalóbbá válik, és nem igényel szellemi erőfeszítést a megfelelő helyén, ami után felszabadíthatod a szellemedet. további előrelépés lehetősége a megoldandó vagy más problémákkal kapcsolatban.

Az Arto Incal-probléma szerkezetének alapos elemzése azt mutatja, hogy az egész probléma három szinkronosan forgó pár és egy háromszoros aszinkron forgó pár elvén épül fel: (x1+x2)+(x3+x4)+(x5+) x6)+(x7+x8+ x9). Az elforgatási sorrend például a következő lehet: az első három sorban (123) az első pár (x1+x2) az első blokk első sorából a második blokk második sorába, majd a harmadik sorba kerül. a harmadik blokkból. A második pár az első blokk második sorából a második blokk harmadik sorába ugrik, majd ebben a forgatásban a harmadik blokk első sorába ugrik. Az első blokk harmadik sorából a harmadik pár a második blokk első sorába ugrik, majd ugyanabban a forgásirányban a harmadik blokk második sorába ugrik. Az egyesek triója hasonló forgási mintában mozog, de a párosokéval ellentétes irányban. Hasonlóan néz ki a helyzet az oszlopokkal is: ha a táblázatot gondolatban (vagy ténylegesen) 90 fokkal elforgatjuk, akkor a sorok oszlopokká válnak, az egyesek és párok mozgása ugyanaz, mint korábban a soroknál.

Ha ezeket a forgatásokat az Arto Incal-problémával kapcsolatban elménkben átgondoljuk, fokozatosan megértjük a nyilvánvaló korlátozásokat, amelyek a kiválasztott sorok vagy oszlopok hármasára vonatkozóan ennek a forgatásnak a változatainak kiválasztására vonatkoznak:

Nem lehetnek szinkronban (egy irányban) forgó hármasok és párok - az ilyen hármasokat, ellentétben az egyesek hármasával, a jövőben hármasoknak nevezzük;

Nem lehetnek egymással aszinkron párok vagy egymással aszinkron egyesek;

Nem szabad, hogy egy (például jobbra) irányba forogjanak párok és egyesek - ez a korábbi korlátozások megismétlése, de érthetőbbnek tűnhet.

Ezen kívül vannak más korlátozások is:

A 9 sorban nem lehet egyetlen olyan pár sem, amely megfelelne egyik oszlopban sem, és ugyanez az oszlopok és sorok esetében is. Ennek nyilvánvalónak kell lennie: mert az a tény, hogy két szám egy sorban van, azt jelzi, hogy különböző oszlopokban vannak.

Azt is mondhatjuk, hogy nagyon ritkán vannak párok egyezése a sorok különböző hármasában, vagy hasonló egyezés az oszlopok hármasában, és ritkán találkozik egyesek hármasa is sorokban és/vagy oszlopokban, de ezek úgymond , valószínűségi minták.

Kutatási blokkok 4,5,6.

A 4-6 blokkban (3+7) és (3+9) párok lehetségesek. Ha elfogadjuk (3+9), akkor a triplet érvénytelen szinkron forgását kapjuk (3+7+9), így van egy párunk (7+3). E pár helyettesítése és a táblázat hagyományos módszerekkel történő feldolgozása után a következőket kapjuk:

Ugyanakkor elmondhatjuk, hogy a B6=5-ben az 5-ös csak magányos, aszinkron (7+3) lehet, az I5=6-ban pedig a 6-os paragenerátor, mivel a hatodik H5=5-ben ugyanabban a sorban van. blokk, ezért nem lehet egyedül, és csak szinkronban mozoghat a (7+3.

és a szingli jelölteket aszerint rendezte, hogy hány megjelenésük volt ebben a táblázatban:

Ha elfogadjuk, hogy a leggyakrabban előforduló 2, 4 és 5 egyesek, akkor a forgatás szabályai szerint csak párok kombinálhatók velük: (7 + 3), (9 + 6) és (1 + 8) - a pár (1 + 9) eldobva, mivel tagadja a (9+6) párt. Továbbá, miután ezeket a párokat és egyeseket helyettesítjük, és a táblázatot hagyományos módszerekkel tovább feldolgozzuk, a következőt kapjuk:

Egy ilyen ellenszegülő táblázatnak bizonyult - nem akarja a végsőkig feldolgozni.

Keményen kell dolgoznia, és észre kell vennie, hogy az ABC oszlopokban van egy pár (7 + 4), és a 6 szinkronban mozog a 7-tel ezekben az oszlopokban, ezért a 6 egy párosítás, tehát csak a (6 + 3) kombinációk lehetségesek az oszlopban. A 4. blokk "C" +8 vagy (6+8)+3. Ezen kombinációk közül az első nem működik, mert akkor a "B" oszlop 7. blokkjában egy érvénytelen szinkron hármas jelenik meg - egy triplet (6 + 3 + 8). Nos, akkor a (6 + 8) + 3 opció behelyettesítése és a táblázat szokásos módon történő feldolgozása után elérkezünk a feladat sikeres teljesítéséhez.

A második lehetőség: térjünk vissza a 456. sorban a (7 + 3) + 5 kombináció azonosítása után kapott táblázathoz, és folytassuk az ABC oszlopok tanulmányozását.

Itt észrevehetjük, hogy a pár (2+9) nem mehet be az ABC-ben. Más kombinációk (2+4), (2+7), (9+4) és (9+7) szinkron hármast adnak – triplettet az A4+A5+A6 és B1+B2+B3-ban, ami elfogadhatatlan. Marad egy elfogadható pár (7+4). Sőt, a 6 és az 5 szinkronban mozog 7, ami azt jelenti, hogy gőzképzők, pl. alkossanak néhány párt, de ne 5 + 6-ot.

Készítsünk egy listát a lehetséges párokról és azok kombinációiról egyesével:

A (6+3)+8 kombináció nem működik, mert egyébként egy oszlopban (6 + 3 + 8) egy érvénytelen hármashármas keletkezik, amiről már volt szó, és amit az összes opció ellenőrzésével még egyszer ellenőrizhetünk. Az egyesekre pályázók közül a 3-as szám éri a legtöbb pontot, és a legvalószínűbb a fenti kombinációk közül: (6 + 8) + 3, azaz. (C4=6 + C5=8) + C6=3, ami:

Továbbá az egyedülállók legvalószínűbb jelöltje a 2 vagy a 9 (mindegyik 6 pont), de ezekben az esetekben az 1. jelölt (4 pont) érvényes marad. Kezdjük az (5+29)+1-gyel, ahol az 1 aszinkron 5-tel, azaz. tegyen 1-et B5=1-ből aszinkron szingliként az ABC összes oszlopába:

A 7. blokk A oszlopában csak (5+9)+3 és (5+2)+3 opció lehetséges. De jobb, ha odafigyelünk arra, hogy az 1-3 sorban most megjelentek a (4 + 5) és (8 + 9) párok. Helyettesítésük gyors eredményre vezet, i.e. a feladat befejezéséig a táblázat normál eszközökkel történő feldolgozása után.

Nos, most, miután gyakoroltuk az előző opciókat, megpróbálhatjuk megoldani az Arto Incal problémát statisztikai becslések bevonása nélkül.

Ismét visszatérünk a kiinduló helyzetbe:

A 4-6 blokkban (3+7) és (3+9) párok lehetségesek. Ha elfogadjuk (3 + 9), akkor a hármas érvénytelen szinkron forgatását kapjuk (3 + 7 + 9), így a táblázatban a helyettesítésre csak a (7 + 3) lehetőségünk van:

5 itt, mint látjuk, magányos, 6 egy paraformer. Az ABC5 érvényes opciói: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1) +2. De (2+1) aszinkron a (7+3)-hoz, tehát vannak (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. Mindenesetre az 1 szinkron (7 + 3), és ezért parageneráló. Helyettesítsünk 1-et ebben a minőségben a táblázatban:

A 6-os szám itt egy paragenerátor a bl. 4-6, de a feltűnő pár (6+4) nem szerepel az érvényes párok listáján. Ezért az A4=4 négyes aszinkron 6:

Mivel D4+E4=(8+1) és a forgásanalízis szerint ezt a párt alkotja, így kapjuk:

Ha a C456 cellák=(6+3)+8, akkor a B789=683, azaz. szinkron tripla-hármast kapunk, így marad a (6+8)+3 opció és a behelyettesítésének eredménye:

A B2=3 itt egyetlen, a C1=5 (aszinkron 3) párosítás, az A2=8 szintén párosítás. A B3=7 lehet szinkron és aszinkron is. Most már összetettebb trükkökben is bizonyíthatunk. Gyakorlott szemmel (vagy legalábbis számítógépen történő ellenőrzéskor) azt látjuk, hogy bármely B3=7 - szinkron vagy aszinkron - állapot esetén ugyanazt az eredményt kapjuk A1=1. Ezért ezt az értéket behelyettesíthetjük A1-be, majd a szokásosabb egyszerű eszközökkel teljesíthetjük a feladatunkat, vagy inkább Arto Incala:

Így vagy úgy, három általános problémamegoldási megközelítést tudtunk megfontolni, sőt szemléltetni: meghatározni a probléma megértésének pontját (nem egy hipotetikus vagy vakon deklarált, hanem egy valós pillanatot, amelyből kiindulva a probléma megértéséről beszélhetünk). ), olyan modellt válasszunk, amely lehetővé teszi a megértés megvalósítását természetes vagy mentális kísérletekkel, és – harmadszor – az elért eredmények megértésének és észlelésének fokát a magától értetődő és az egyszerűség állapotába hozni. Van egy negyedik megközelítés is, amelyet én személy szerint használok.

Minden embernek vannak állapotai, amikor az előtte álló intellektuális feladatok és problémák könnyebben megoldódnak, mint általában. Ezek az állapotok meglehetősen reprodukálhatók. Ehhez el kell sajátítania a gondolatok kikapcsolásának technikáját. Eleinte legalább a másodperc töredékéig, majd egyre jobban megfeszítve ezt a szétkapcsoló pillanatot. Ezzel kapcsolatban nem tudok többet mondani, vagy inkább ajánlani valamit, mert a módszer alkalmazásának időtartama tisztán személyes kérdés. De néha sokáig folyamodom ehhez a módszerhez, amikor olyan probléma merül fel előttem, amihez nem látok lehetőségeket, hogyan lehetne megközelíteni és megoldani. Ennek eredményeként előbb-utóbb az emlékezet tárházából előkerül a modell megfelelő prototípusa, amely tisztázza a megoldandó lényegét.

Az Incal-problémát többféle módon oldottam meg, beleértve a korábbi cikkekben leírtakat is. És így vagy úgy mindig ezt a negyedik megközelítést alkalmaztam a kikapcsolással, majd a mentális erőfeszítések koncentrálásával. A probléma leggyorsabb megoldását egyszerű felsorolással kaptam - amit "poke módszernek" neveznek -, azonban csak "hosszú" opciókat használtam: azokat, amelyek gyorsan pozitív vagy negatív eredményhez vezethetnek. Más lehetőségek több időt vettek el tőlem, mert az idő nagy részét az ilyen lehetőségek alkalmazási technológiájának legalább durva fejlesztésére fordítottam.

Egy jó lehetőség a negyedik megközelítés szellemében is: ráhangolódni a Sudoku-feladatok megoldására, cellánként csak egy számjegyet helyettesíteni a probléma megoldása során. Vagyis a feladat nagy része és adatai "gördülnek" az elmében. Ez a fő része az intellektuális problémamegoldás folyamatának, és ezt a képességet képezni kell, hogy növelje problémamegoldó képességét. Például nem vagyok profi Sudoku megoldó. más feladataim vannak. Ennek ellenére a következő célt szeretném kitűzni magam elé: megszerezni a képességet a fokozott összetettségű Sudoku-problémák megoldására, munkalap nélkül és anélkül, hogy egynél több számot kellene behelyettesíteni egy üres cellába. Ebben az esetben a Sudoku megoldásának bármilyen módja megengedett, beleértve a lehetőségek egyszerű felsorolását.

Nem véletlen, hogy eszembe jut itt a lehetőségek felsorolása. A Sudoku-problémák megoldásának bármely megközelítése bizonyos módszereket foglal magában, beleértve az egyik vagy másik típusú felsorolást. Ezen túlmenően, a Sudokuban használt módszerek bármelyikének, vagy bármely más probléma megoldásának megvan a maga hatékony alkalmazási területe. Tehát viszonylag egyszerű Sudoku-feladatok megoldása során a leghatékonyabbak az egyszerű "alap" módszerek, amelyeket számos cikkben leírtak a témában az interneten, és a bonyolultabb "forgatási módszer" itt sokszor hiábavaló, mert csak bonyolítja a folyamat menetét. egyszerű megoldás és egyben mi -nem ad új információt, ami a probléma megoldása során megjelenik. De a legnehezebb esetekben, mint például Arto Incal problémájában, a „forgatási módszer” kulcsszerepet játszhat.

A cikkeimben szereplő Sudoku csak egy szemléltető példa a problémamegoldás megközelítésére. Az általam megoldott problémák között vannak a Sudokunál egy nagyságrenddel nehezebbek is. Például a weboldalunkon található kazánok és turbinák számítógépes modelljei. Én sem bánnám, ha beszélnék róluk. Egyelőre azonban a Sudoku mellett döntöttem, hogy fiatal polgártársaimnak meglehetősen vizuálisan mutassam meg a megoldandó problémák végső célja felé való elmozdulás lehetséges módjait és szakaszait.

Ez minden mára.

VKontakte Facebook Odnoklassniki

Azok számára, akik szeretnek önállóan és lassan megfejteni a Sudoku-rejtvényeket, egy olyan képlet, amely lehetővé teszi a válaszok gyors kiszámítását, a gyengeség vagy a csalás beismerésének tűnhet.

De azok számára, akiknek túl nehéz a Sudoku megoldása, ez szó szerint tökéletes megoldás lehet.

Két kutató kifejlesztett egy matematikai algoritmust, amellyel nagyon gyorsan, találgatások és visszalépések nélkül oldhatja meg a Sudoku-t.

A komplex hálózatkutatók, Torozhkai Zoltán és Maria Erksi-Ravaz, a Notre Dame Egyetem munkatársai szintén meg tudták magyarázni, hogy egyes Sudoku-rejtvények miért nehezebbek, mint mások. Az egyetlen hátránya, hogy matematikából PhD-re van szüksége ahhoz, hogy megértse, mit kínálnak.

Meg tudod oldani ezt a rejtvényt? Arto Incala matematikus készítette, és azt állítják, hogy ez a világ legnehezebb Sudokuja. Fotó a nature.com-ról

Torozhkay és Erksi-Rawaz elkezdték elemezni a Sudoku-t az optimalizálás elméletével és a számítási összetettséggel kapcsolatos kutatásaik részeként. Azt mondják, hogy a legtöbb sudoku-rajongó a találgatási technikán alapuló nyers erő megközelítést alkalmazza ezeknek a problémáknak a megoldására. Így a Sudoku szerelmesei ceruzával fegyverkeznek fel, és minden lehetséges számkombinációt kipróbálnak, amíg meg nem találják a helyes választ. Ez a módszer elkerülhetetlenül sikerhez vezet, de fáradságos és időigényes.

Ehelyett Torozhkai és Erksi-Ravaz egy univerzális analóg algoritmust javasoltak, amely abszolút determinisztikus (nem használ találgatást vagy felsorolást), és mindig megtalálja a helyes megoldást a problémára, méghozzá meglehetősen gyorsan.

A kutatók egy "determinisztikus analóg megoldót" használtak a sudoku elkészítéséhez. Fotó a nature.com-ról

A kutatók azt is megállapították, hogy egy rejtvény analóg algoritmusával történő megoldásához szükséges idő korrelál a feladat nehézségi fokával, ahogyan azt a személy megítéli. Ez arra ösztönözte őket, hogy dolgozzanak ki egy rangsorolási skálát egy rejtvény vagy probléma nehézségére.

Létrehoztak egy 1-től 4-ig terjedő skálát, ahol az 1 a „könnyű”, a 2 az „átlagos”, a 3 a „nehéz”, a 4 a „nagyon nehéz”. Egy 2-es értékelésű rejtvény megfejtése átlagosan 10-szer hosszabb ideig tart, mint egy 1-es értékelésű. E rendszer szerint az eddig ismert legnehezebb feladvány 3,6-os értékelést kapott; bonyolultabb Sudoku rejtvények még nem ismertek.

Az elmélet minden egyes négyzet valószínűségi leképezésével kezdődik. Fotó a nature.com-ról

„Nem érdekelt a Sudoku, amíg el nem kezdtünk dolgozni a Boole-problémák általánosabb kielégítési osztályán” – mondja Torozhkay. - Mivel a sudoku ennek az osztálynak a része, a 9. rendű latin négyzet jó pályának bizonyult számunkra a tesztelésre, így megismerkedtem velük. Engem és sok kutatót, akik ilyen problémákat tanulmányoznak, lenyűgöz a kérdés, hogy mi, emberek meddig mehetünk el a Sudoku megoldásában, determinisztikusan, tönkretétel nélkül, ami véletlenszerű választás, és ha a találgatás nem helyes, vissza kell térnie egy lépés vagy több lépés.és kezdje elölről. Analóg döntési modellünk determinisztikus: nincs véletlenszerű választás vagy ismétlődés a dinamikában.”

Káoszelmélet: A rejtvények bonyolultsági foka itt kaotikus dinamikaként jelenik meg. Fotó a nature.com-ról

Torozhkai és Erksi-Ravaz úgy vélik, hogy analóg algoritmusukban megvan a lehetőség, hogy az ipar, a számítástechnika és a számítási biológia számos problémájára alkalmazhatók.

A kutatási tapasztalatok Torozhkayt is a Sudoku nagy rajongójává tette.

„A feleségem és én több Sudoku alkalmazásunk van az iPhone-unkon, és biztosan több ezerszer játszottunk már, és minden szinten rövidebb idő alatt versenyeztünk” – mondja. - Gyakran intuitív módon látja a minták kombinációit, amelyeket nem veszek észre. ki kell szednem őket. Lehetetlenné válik számomra, hogy sok olyan rejtvényt megoldjak, amelyeket a skálánk nehéznek vagy nagyon nehéznek minősít a valószínűségek ceruzával való felírása nélkül.”

A Torozhkay és Erksi-Ravaz módszertana először a Nature Physics-ben, majd a Nature Scientific Reports-ban jelent meg.

Használjon 1 és 9 közötti számokat

A Sudoku-t egy 9:9-es rácson játsszák, összesen 81 rácsot. A játéktéren belül 9 "négyzet" található (3 x 3 cellából áll). Minden vízszintes sort, függőleges oszlopot és négyzetet (mindegyik 9 cellát) ki kell tölteni az 1-9 számokkal, anélkül, hogy a sorban, oszlopban vagy négyzetben számokat ismételnének. Bonyolultan hangzik? Amint az alábbi képen látható, minden Sudoku játékmezőnek több cellája van, amelyek már meg vannak töltve. Minél több cellát töltenek ki először, annál könnyebb a játék. Minél kevesebb cellát töltenek meg először, annál nehezebb a játék.

Ne ismételje meg a számokat

Mint látható, a bal felső négyzet (kék bekarikázva) már kitöltött 7-et a 9 cellából. Csak az 5-ös és a 6-os számok hiányoznak ebből a négyzetből. Ha megnézzük, hogy mely számok hiányoznak az egyes négyzetekből, sorokból vagy oszlopokból, akkor az eliminálás és a deduktív érvelés segítségével eldönthetjük, mely számok legyenek az egyes cellákban. .

Például a bal felső négyzetben tudjuk, hogy a négyzet kitöltéséhez hozzá kell adni az 5-ös és a 6-os számokat, de a szomszédos sorokat és négyzeteket nézve továbbra sem tudjuk egyértelműen meghatározni, hogy melyik cellához melyik számot adjuk. Ez azt jelenti, hogy most a bal felső mezőt kell most kihagynunk, és ehelyett a játéktér más helyein próbáljuk pótolni a hiányosságokat.

Nem kell találgatni

A Sudoku egy logikai játék, így nem kell találgatni. Ha nem tudja, milyen számot írjon be egy bizonyos cellába, folytassa a játékmező más területeinek pásztázását, amíg meg nem jelenik a kívánt szám beszúrásának lehetősége. De ne próbálj meg semmit "erőltetni" – a Sudoku a türelmet, a különböző kombinációk megértését és megoldását jutalmazza, nem a vakszerencsét vagy a találgatást.

Használja az eliminációs módszert

Mit tegyünk, ha a „kizárási módszert” használjuk egy Sudoku játékban? Íme egy példa. Ebben a Sudoku-rácsban (lásd lent) csak néhány szám hiányzik a bal függőleges oszlopból (kék bekarikázva): 1, 5 és 6.

Az egyik módja annak, hogy kitaláljuk, milyen számok férnek el az egyes cellákban, ha a "kizárási módszert" használjuk, és ellenőrizzük, hogy milyen számok vannak már az egyes négyzetekben, mivel az 1-től 9-ig tartó számok nem duplikálhatók minden egyes négyzetben, sorban vagy sorban. oszlop.

Ilyenkor gyorsan észrevehetjük, hogy a bal felső és a bal középső négyzetben már van egy 1-es szám (az 1-esek pirossal vannak bekarikázva). Ez azt jelenti, hogy a bal szélső oszlopban csak egy helyen lehet beszúrni az 1-es számot (zöld bekarikázva). Így működik az eliminációs módszer a Sudokuban – megtudod, mely cellák szabadok, mely számok hiányoznak, majd kiküszöbölöd azokat a számokat, amelyek már jelen vannak a négyzetben, az oszlopokban és a sorokban. Ennek megfelelően töltse ki az üres cellákat a hiányzó számokkal.

A Sudoku szabályai viszonylag egyszerűek – de a játék rendkívül változatos, milliónyi lehetséges számkombinációval és sokféle nehézségi szinttel. De mindez az 1-től 9-ig tartó számok egyszerű elvein alapul, deduktív gondolkodás alapján pótolja a hiányosságokat, és soha ne ismételje meg a számokat minden négyzetben, sorban vagy oszlopban.

• oktatóanyag

1. Alapok

A legtöbb hackerünk tudja, mi az a sudoku. Nem a szabályokról fogok beszélni, hanem azonnal rátérek a módszerekre.
Egy rejtvény megfejtéséhez, legyen az bármilyen bonyolult vagy egyszerű is, először olyan cellákat kell keresni, amelyek kitöltése nyilvánvaló.

1.1 "Az utolsó hős"

Tekintsük a hetedik négyzetet. Csak négy szabad cella, így valamit gyorsan meg lehet tölteni.
"8 " a D3 blokkok párnázás H3és J3; hasonló" 8 " a G5 bezár G1és G2
Tiszta lelkiismerettel azt mondjuk, 8 " a H1

1.2 "Utolsó hős" a sorban

Miután megtekintette a négyzeteket a nyilvánvaló megoldásokért, lépjen tovább az oszlopokra és sorokra.
Fontolgat " 4 "A pályán. Egyértelmű, hogy valahol a sorban lesz A .
Nekünk van " 4 " a G3 amely kiterjed A3, van " 4 " a F7, takarítás A7. És még egy" 4 A második mezőben tiltja az ismétlődést A4és A6.
"Az utolsó hős" nekünk" 4 "Ezt A2

1.3 „Nincs választás”

Néha több oka is van egy adott helynek. " 4 " ban ben J8 nagyszerű példa lenne.
Kék a nyilak azt mutatják, hogy ez az utolsó lehetséges négyzetszám. Pirosés kék a nyilak az utolsó számot adják az oszlopban 8 . Zöldek a nyilak az utolsó lehetséges számot adják a sorban J.
Amint látja, nincs más választásunk, mint ezt feltenni" 4 "a helyén.

1.4 "És ki, ha nem én?"

A számok kitöltése egyszerűbb a fent leírt módszerekkel. Azonban a szám utolsó lehetséges értékként való ellenőrzése is eredményt hoz. A módszert akkor kell használni, ha úgy tűnik, hogy minden szám megvan, de valami hiányzik.
"5 " ban ben B1 azon a tényen alapul, hogy a " 1 "előtt" 9 ", Kívül " 5 " van a sorban, oszlopban és négyzetben (zölddel jelölve).

A zsargonban ez " meztelen magányos". Ha kitölti a mezőt lehetséges értékekkel​​(jelöltek), akkor a cellában ez a szám lesz az egyetlen lehetséges. Ezt a technikát fejlesztve rákereshet a " rejtett magányosok" - egy adott sorhoz, oszlophoz vagy négyzethez egyedi számok.

2. "Meztelen mérföld"

2.1 Meztelen párok

""meztelen" pár" - két jelölt halmaza, amelyek egy közös blokkhoz tartozó két cellában találhatók: sor, oszlop, négyzet.
Nyilvánvaló, hogy a rejtvény helyes megoldásai csak ezekben a cellákban és csak ezekkel az értékekkel lesznek, míg az összes többi jelölt az általános blokkból eltávolítható.


Ebben a példában több "csupasz pár" van.
piros Sorban DE cellák kiemelve A2és A3, mindkettő tartalmaz " 1 "és" 6 " 1 "és" 6 " karakterláncból A(sárgával jelölve). Is A2és A3 közös térhez tartoznak, ezért eltávolítjuk a " 1 " tól től C1.

2.2 "Hármas"

"Meztelen hármasok"- a "meztelen párok" bonyolult változata.
Bármely három cellából álló csoport egy blokkban, amely tartalmazza összességében három jelölt az "meztelen trió". Ha ilyen csoportot találunk, akkor ez a három jelölt eltávolítható a blokk többi cellájából.

Jelölt kombinációk a "meztelen trió" ilyen lehet:

// három szám három cellában.
// bármilyen kombináció.
// bármilyen kombináció.

Ebben a példában minden elég nyilvánvaló. A cella ötödik négyzetében E4, E5, E6 tartalmaz [ 5,8,9 ], [5,8 ], [5,9 ], ill. Kiderült, hogy általában ennek a három sejtnek [ 5,8,9 ], és csak ezek a számok lehetnek ott. Ez lehetővé teszi számunkra, hogy eltávolítsuk őket a többi blokk-jelölt közül. Ez a trükk megadja nekünk a megoldást" 3 " cellához E7.

2.3 "Fab Four"

"meztelen négyes" nagyon ritka előfordulás, különösen teljes formájában, de észlelésekor mégis eredményeket hoz. A megoldás logikája ugyanaz, mint "meztelen hármasikrek".

A fenti példában a cella első négyzetében A1, B1, B2és C1általában tartalmaz [ 1,5,6,8 ], így ezek a számok csak azokat a cellákat foglalják el, másokat nem. A sárgával kiemelt jelölteket eltávolítjuk.

3. "Minden, ami el van rejtve, világossá válik"

3.1 Rejtett párok

A mező megnyitásának nagyszerű módja a keresés rejtett párok. Ezzel a módszerrel eltávolíthatja a felesleges jelölteket a cellából, és érdekesebb stratégiákat hozhat létre.

Ebben a rejtvényben ezt látjuk 6 és 7 az első és a második mezőben van. kívül 6 és 7 oszlopban van 7 . Ezeket a feltételeket kombinálva kijelenthetjük, hogy a sejtekben A8és A9 csak ezek az értékek lesznek, és az összes többi jelöltet eltávolítjuk.


Érdekesebb és összetettebb példa rejtett párok. A pár [ 2,4 ] ban ben D3és E3, takarítás 3 , 5 , 6 , 7 ezekből a sejtekből. Pirossal kiemelve két rejtett pár látható, amelyek a [ 3,7 ]. Egyrészt két cella esetében egyediek 7 oszlop, másrészt - egy sorra E. A sárgával kiemelt jelöltek eltávolításra kerülnek.

3.1 Rejtett hármasikrek

Tudunk fejlődni rejtett párok előtt rejtett hármasikrek vagy akár rejtett négyes. A Rejtett Három három számpárból áll, amelyek egy blokkban helyezkednek el. Mint például, és. Azonban, mint abban az esetben "meztelen hármasikrek", a három cellának nem kell három számot tartalmaznia. működni fog Teljes három szám három cellában. Például , , . Rejtett hármasikrek a cellákban lévő többi jelölt maszkolja, ezért először meg kell győződnie arról trojka adott blokkra alkalmazható.


Ebben az összetett példában kettő van rejtett hármasikrek. Az első, pirossal jelölt, az oszlopban DE. Sejt A4 tartalmaz [ 2,5,6 ], A7 - [2,6 ] és cella A9 -[2,5 ]. Ez a három cella az egyetlen, ahol 2, 5 vagy 6 lehet, tehát ezek lesznek az egyetlenek. Ezért a szükségtelen jelölteket eltávolítjuk.

Másodszor, egy oszlopban 9 . [4,7,8 ] egyediek a sejtekre B9, C9és F9. Ugyanezzel a logikával eltávolítjuk a jelölteket.

3.1 Rejtett négyes

Tökéletes példa rejtett négyes. [1,4,6,9 ] az ötödik négyzetben csak négy cellában lehet D4, D6, F4, F6. Logikánkat követve az összes többi jelöltet eltávolítjuk (sárgával jelölve).

4. "Nem gumi"

Ha valamelyik szám kétszer vagy háromszor szerepel ugyanabban a blokkban (sor, oszlop, négyzet), akkor azt a számot eltávolíthatjuk a konjugált blokkból. Négyféle párosítás létezik:

1. Pár vagy három egy négyzetben - ha egy sorban találhatók, akkor az összes többi hasonló értéket eltávolíthatja a megfelelő sorból.
2. Pár vagy három egy négyzetben - ha egy oszlopban vannak, akkor eltávolíthatja az összes többi hasonló értéket a megfelelő oszlopból.
3. Pár vagy három egymás után - ha ugyanabban a négyzetben találhatók, akkor az összes többi hasonló értéket eltávolíthatja a megfelelő négyzetből.
4. Pár vagy három egy oszlopban - ha egy négyzetben találhatók, akkor az összes többi hasonló értéket eltávolíthatja a megfelelő négyzetből.

4.1 Mutatópárok, hármasok

Hadd mutassam meg ezt a rejtvényt példaként. A harmadik téren 3 "csak bent van B7és B9. A nyilatkozat nyomán №1 , eltávolítjuk a jelölteket innen B1, B2, B3. Hasonlóképpen, " 2 " a nyolcadik négyzetből eltávolítja a lehetséges értéket G2.


Különleges puzzle. Nagyon nehéz megoldani, de ha alaposan megnézed, láthatsz néhányat mutató párok. Nyilvánvaló, hogy nem mindig szükséges mindegyiket megtalálni a megoldásban való előrelépéshez, de minden ilyen lelet megkönnyíti a dolgunkat.

4.2 Az irreducibilis csökkentése

Ez a stratégia magában foglalja a sorok és oszlopok gondos elemzését és összehasonlítását a négyzetek tartalmával (szabályok №3 , №4 ).
Vegye figyelembe a vonalat DE. "2 "csak itt lehetségesek A4és A5. szabályt követve №3 , távolítsa el " 2 " őket B5, C4, C5.


Folytassuk a rejtvény megfejtését. Egyetlen telephelyünk van 4 "egy négyzetméteren belül 8 oszlop. A szabály szerint №4 , eltávolítjuk a felesleges jelölteket, és emellett megkapjuk a megoldást " 2 "ért C7.