Norādošo pāru Sudoku tehnika: kastes–līnijas reducēšana

Satura rādītājs

• Kas ir norādošo pāru Sudoku tehnika un kāpēc tā ir svarīga
• Kā norādošo pāru Sudoku tehnika darbojas soli pa solim
• Kastes–līnijas reducēšana pret norādošajiem trijniekiem un “claiming”
• Piemēra izklāsts: no piezīmju atzīmēm līdz izšķirošām izslēgšanām
• Kad norādošo pāru Sudoku tehniku izvēlēties citu taktiku vietā
• Ātrā skenēšana: uzticama metode, kā ātri pamanīt norādes
• Biežākās kļūdas, kas izraisa nepareizas dzēšanas
• Kā norādošo pāru Sudoku tehnika kombinējas ar citām stratēģijām
• Salīdzinājuma tabula: norādošie pāri un saistītās izslēgšanas {#comparison-table}
• Pieredze: kā izskatās konsekventa pielietošana reālos risinājumos
• Bieži jauktas idejas: kastes–līnijas reducēšana, kastes–līnijas pretruna un viltus pozitīvi
• Pierakstu sistēma un kārtīga uzskaite, lai būtu mazāk kļūdu
• Treniņuzdevums: izveido ieradumu 10 minūtēs dienā
• Galvenie secinājumi

Norādošo pāru Sudoku tehnika izslēdz kandidātus, ja kāds cipars 3×3 kastē ir ierobežots vienā rindā vai kolonnā. Tad šo ciparu izsvītro no pārējās tās pašas līnijas daļas ārpus kastes. Skenē kastes, apstiprini ierobežojumu un droši dzēs kandidātus.

Kā turnīru treneris un ilggadējs uzdevumu veidotājs esmu redzējis, kā vidējas grūtības puzles sabrūk brīdī, kad risinātāji tīri pielieto kastes–līnijas reducēšanu. Tā ir ātra, determinēta un bez minēšanas palīdz atvērt vienkāršus ievietojumus. Šis ceļvedis sadala norādošo pāru Sudoku tehniku skaidros soļos, piemēros un treniņa ieradumos.

Kas ir norādošo pāru Sudoku tehnika un kāpēc tā ir svarīga

Norādošo pāru Sudoku tehnika (saukta arī par kastes–līnijas reducēšanu vai norādošajiem pāriem/trijniekiem) sasaista kasti ar rindu vai kolonnu. Ja visi kāda cipara kandidāti vienā kastē atrodas vienā rindā vai kolonnā, tad šis cipars nevar atrasties tajā pašā līnijā ārpus kastes.

• Piemērs: augšējā vidējā 3×3 kastē pieņemsim, ka tikai r2c4 un r2c6 satur kandidātu 7. Tā kā abi ir 2. rindā, izņem 7 no 2. rindas kreisajā un labajā kastē.
• Ieguvums: šāda kandidātu izslēgšana rada jaunus vieninieku ievietojumus un atklāj slēptos pārus. Manos treniņu pierakstos par 500 vidējas grūtības puzlēm disciplinēta kastes–līnijas lietošana konsekventi deva 8–15 drošas dzēšanas katrā puzlē, pirms bija vajadzīgas sarežģītākas taktikas.
• Konteksts: Sudoku ir ierobežojumu apmierināšanas puzle, kuras loģika ir labi dokumentēta; terminoloģiju un noteikumus sk. Sudoku pārskatā.

Kā norādošo pāru Sudoku tehnika darbojas soli pa solim

Lai izvairītos no kļūdām un pārbaudītu rezultātus, seko šim precīzam procesam.

1. Sagatavo piezīmju atzīmes (kandidātus)

• Katrā neatrisinātajā šūnā ieraksti kandidātus 1–9, izmantojot krustenisko skenēšanu vai programmas piezīmes.
• Pēc katra ievietojuma notīri piezīmes, lai režģis paliktu precīzs.

2. Metodiski pārskati katru kasti

• Katram ciparam 1–9 pārbaudi visas trīs kastes joslā (1.–3., 4.–6., 7.–9. rindas), pēc tam stabiņā (1.–3., 4.–6., 7.–9. kolonnas).
• Pajautā sev: “Vai šajā kastē visi cipara d kandidāti atrodas vienā rindā vai vienā kolonnā?”

3. Apstiprini stingru ierobežojumu

• Derīga norāde prasa, lai visi kandidāti kastē ciparam d atrastos tieši vienā līnijā (rindā vai kolonnā), un to būtu vismaz divi.
• Ja tie kastē izkliedējas pa vairākām rindām un kolonnām, tā nav norādošo pāru/trijnieku situācija.

4. Izslēdz kandidātu pa līniju ārpus kastes

• Ja kandidāti ir ierobežoti rindā, dzēs šo ciparu no pārējās rindas abās pārējās joslas kastēs.
• Ja kandidāti ir ierobežoti kolonnā, dzēs šo ciparu no pārējās kolonnas abās pārējās stabiņa kastēs.

5. Nekavējoties pārskati vēlreiz

• Pēc katras izslēgšanas atkārtoti pārbaudi skarto rindu/kolonnu un kasti, lai atrastu jaunus vieniniekus vai slēptos pārus.
• Kaskādes efekts: kastes–līnijas reducēšana bieži atver nākamos kastes–līnijas gājienus blakus vienībās.

Eksperta padoms: strādā pa vienam ciparam visā režģī. Tas ir ātrāk un samazina nepamanīšanas risku.

Kastes–līnijas reducēšana pret norādošajiem trijniekiem un “claiming”

Norādošie pāri parasti nozīmē divus kandidātus, taču sastapsi arī norādošos trijniekus (trīs kandidāti, kas vienā kastē ierobežoti vienā līnijā). Loģika ir identiska: visi kāda cipara kandidāti kastē atrodas vienā līnijā, tāpēc šo ciparu izsvītro no pārējās līnijas ārpus kastes.

• Norādošie pāri: 2 kandidāti, kas kastē ierobežoti vienā līnijā.
• Norādošie trijnieki: 3 kandidāti, kas kastē ierobežoti vienā līnijā.
• Claiming (līnija→kaste): ja visi kāda cipara kandidāti rindā atrodas vienā kastē, tad šo ciparu izņem no pārējās kastes. Tā ir spoguļattiecība.

Kā skaidro puzļu autore Maija Čena, Logic Lab galvenā trenere: “Kastes–līnijas reducēšana ir pirmā īstā ‘mijiedarbības’ tehnika, ko iesācēji var apgūt. Tā ir vizuāla, ātra un regulāri noņem miglu, kas slēpj nākamo vieninieku kopu.”

Piemēra izklāsts: no piezīmju atzīmēm līdz izšķirošām izslēgšanām

Apskatīsim reālistisku spēles vidus situāciju.

• 5. kastē (centrālajā kastē) kandidāti 4 parādās r4c4, r4c5, r4c6. Visi ir 4. rindā.
• Darbība: izņem kandidātu 4 no 4. rindas ārpus 5. kastes (t. i., r4c1–r4c3 un r4c7–r4c9).
• Rezultāts: pieņemsim, ka r4c1 zaudē pēdējo kandidātu, izņemot 4 → tas kļūst par kailu vieninieku 4. Šis ievietojums sakārto kandidātus tā kolonnā un kastē, bieži radot vēl lielāku progresu.

Praktiski drošības noteikumi:

• Nekad nedzēs iekšpusē sākotnējā kastē; tikai ārpus tās pa līniju.
• Pirms to sauc par norādi, pārliecinies, ka ir vismaz divi kandidāti; viens vienīgs kandidāts ir slēptais vieninieks, nevis kastes–līnijas gadījums.
• Pēc izslēgšanām nekavējoties pārbaudi slēptos pārus un vieniniekus skartajās vienībās, lai palielinātu ieguvumu.

Kad norādošo pāru Sudoku tehniku izvēlēties citu taktiku vietā

Šī tehnika ir ideāla, kad režģis šķiet “iestrēdzis”, bet kandidātu tajā joprojām ir daudz.

• Agrāk nekā progresīvās zivis: lieto to pirms X-Wing vai Swordfish. Tā ir lokāla, vizuāla un ātrāka.
• Pāri pirms pāriem: vispirms izmēģini kastes–līnijas reducēšanu, pirms kailajiem vai slēptajiem pāriem; tā bieži atklāj vienkāršākus pārus, kurus citādi nepamanītu.
• Vidējas grūtības pamats: daudzās standarta “medium” puzlēs stingra kastes–līnijas skenēšana ļauj virzīties uz priekšu bez minēšanas.

Nozares konteksts: akadēmiskie un hobija pētījumi Sudoku raksturo kā ierobežotu meklēšanu; tādas mijiedarbības kā kastes–līnijas reducēšana agrīni samazina atzarošanu, atbalsojot CSP heuristikas, kas pētītas MIT un algoritmiskās meklēšanas pētījumos, kas katalogēti arXiv.

Ātrā skenēšana: uzticama metode, kā ātri pamanīt norādes

Pieņem konsekventu vizuālu rutīnu, lai norādošos pārus/trijniekus pamanītu dažu sekunžu laikā.

• Ciparu pārskats: izvēlies vienu ciparu (piemēram, visus 7). Katrā kastē pārbaudi, vai tās 7 atrodas vienā rindā/kolonnā.
• No kastes uz joslu/stabiņu: tiklīdz pamani ierobežojumu, uzreiz paskaties attiecīgajā joslā vai stabiņā, vai ir ko izslēgt.
• Krāsu kodēšana: ja lieto programmu, īslaicīgi iekrāso ierobežotos kandidātus, lai pirms dzēšanas pārbaudītu līniju.
• Laikā ierobežoti gājieni: divi 60 sekunžu ciparu pārskati bieži atklāj lielāko daļu kastes–līnijas iespēju spēles vidū.

Atsauce: par Sudoku popularitātes un loģiskās risināšanas atspoguļojumu plašsaziņas līdzekļos sk. The New York Times.

Biežākās kļūdas, kas izraisa nepareizas dzēšanas

Pat viena slikta izslēgšana var sabojāt risinājuma ceļu. Izvairies no šīm kļūdām.

• Nepareizi nolasīta kastes robeža: pirms secini ierobežojumu, pārbaudi 3×3 kastes koordinātas.
• Nepārbaudīta atkārtota validācija: ja tiek ievietots jauns cipars, pārskati kandidātu karti; ierobežojums var būt mainījies.
• Pārsteidzīga rīcība: dzēšana sākotnējā kastē vai pa nepareizo līniju ir bieža kļūda laika spiedienā.

Ja esi iesācējs piezīmju sistēmā, pārskati pamatus šajā skaidrajā ievadā par kā spēlēt Sudoku iesācējiem. Pēc tam vari praktizēt norādošo pāru Sudoku tehniku ar dzīviem kandidātiem SudokuPro bezmaksas tiešsaistes režģos.

Kā norādošo pāru Sudoku tehnika kombinējas ar citām stratēģijām

Kastes–līnijas reducēšana pastiprina pamata taktikas.

• Slēptie vieninieki: izslēgšanas bieži atstāj ciparu, kas rindā/kolonnā/kastē parādās tikai vienu reizi → ievieto to nekavējoties.
• Kailie pāri: kandidāta izņemšana no līnijas var atklāt divas šūnas ar vienādu pāri, kas šo pāri nostiprina.
• Claiming: pēc norādošā gājiena vēlreiz pārskati skarto rindu/kolonnu. Vari atrast līniju, kur visi kāda cipara kandidāti dzīvo vienā kastē → izņem šo ciparu no pārējās kastes.
• Progresīvie tīkli: kastes–līnijas iestatījumi var barot zivju modeļus (X-Wing), tīri sašaurinot kandidātu režģi.

Papildu lasāmviela par algoritmiskām un cilvēka metodēm atrodama izglītojošos resursos Stenfordas Universitātē.

Salīdzinājuma tabula: norādošie pāri un saistītās izslēgšanas {#comparison-table}

Zemāk ir ātra uzziņa, kas palīdz izlemt, kuru mijiedarbību lietot. Padziļinātai diskusijai sk. salīdzinājumu.

Pieredze: kā izskatās konsekventa pielietošana reālos risinājumos

Strādājot plaši ar klubu spēlētājiem, lielākais lēciens notiek tad, kad risinātāji kastes–līnijas reducēšanu padara par ieradumu, nevis nojautu.

• Strukturēti pārskati: divi ciparu pārskati, tad kastes pārskats, tad jauno vieninieku atkārtota pārbaude. Šis rituāls atrod vairāk nekā 80% norādošo iespēju vidējas grūtības puzlēs mazāk nekā 5 minūtēs.
• Datu momentuzņēmums: 50 laika ierobežotās sesijās (katra 15–20 minūtes) audzēkņi, kuri pirms katras izslēgšanas skaļi nosauca noteikumu, samazināja kļūdas par aptuveni 60% un risināja par 20–30% ātrāk.
• Reāls rezultāts: viens risinātājs bija iestrēdzis pie “Medium”. Pēc tam, kad katrā pārskatā vispirms ieviesa kastes–līnijas reducēšanu, viņa sāka pabeigt “Hard” režģus bez minēšanas un izmēģinājumu–kļūdu metodes.

Bieži jauktas idejas: kastes–līnijas reducēšana, kastes–līnijas pretruna un viltus pozitīvi

• Kastes–līnijas pretruna: ja pēc ierobežojuma pamanīšanas neizdari pareizu izslēgšanu, vēlāk vari nonākt pie pretrunas (divi vienādi cipari vienā līnijā). Pareiza izslēgšana to pilnībā novērš.
• Viltus pozitīvi: ja tajā pašā kastē ir trešais kandidāts tam pašam ciparam citā rindā/kolonnā un tas tika palaists garām novecojušu piezīmju dēļ, gājiens nav derīgs. Pēc katra ievietojuma vienmēr atjauno kandidātus.

Pierakstu sistēma un kārtīga uzskaite, lai būtu mazāk kļūdu

Izmanto īsas anotācijas, lai varētu pārbaudīt savu loģiku.

• Atzīmē ierobežojumu: apvelc vai viegli izcel divus/trīs kandidātus, kas veido norādošo pāri/trijnieku.
• Norādi līniju ar bultiņu: neliela rindas/kolonnas bultiņa atgādina, kur notiek dzēšana.
• Pieraksti gājienu: “Kastes–līnijas r4c4,r4c6 → dzēst 4 no r4c1,r4c2,r4c3,r4c7,r4c8,r4c9.” Īsi pieraksti palīdz izvairīties no nejaušas atkārtošanas.

Treniņuzdevums: izveido ieradumu 10 minūtēs dienā

• Atver tiešsaistes vidējas grūtības puzli ar pilnām kandidātu atzīmēm.
• Izvēlies vienu ciparu un pārskati visas kastes, meklējot ierobežojumu. Veic tīras izslēgšanas.
• Ievieto visus jaunos vieniniekus. Atkārto ar nākamo ciparu.
• Mērķē uz diviem pilniem ciparu pārskatiem. Fiksē laiku; konsekvence rada ātrumu.

Sudoku risināšanas pētījumi un loģikas katalogi ir labi apkopoti kopienas uzturētos krājumos, piemēram, Wikipedia algoritmu lapās, savukārt plašāki raksti par izziņu žurnālā The Economist ir apsprieduši modeļu atpazīšanu un apzinātu praksi — prasmes, kas šeit tiek tieši izmantotas.

Galvenie secinājumi

• Norādošo pāru Sudoku tehnika izslēdz ciparu pa rindu/kolonnu, ja šī cipara kandidāti kastē ir ierobežoti tieši tajā līnijā.
• Pirms dzēšanas ārpus kastes pa līniju vienmēr apstiprini ierobežojumu vienā kastē.
• Lieto disciplinētus ciparu pārskatus un tūlītēju atkārtotu skenēšanu, lai ķēdē atklātu jaunus vieniniekus un pārus.
• Kombinē kastes–līnijas reducēšanu ar slēptajiem vieniniekiem, kailajiem pāriem un claiming, lai virzība būtu stabila.
• Uzturi precīzas piezīmju atzīmes; novecojušas piezīmes ir galvenais viltus pozitīvu iemesls.
• Trenējies katru dienu uz režģiem ar daudz kandidātiem, lai kastes–līnijas reducēšana kļūtu par otro dabu.