X-Wing ir Swordfish Sudoku: kada taikyti ir kaip atpažinti

Turinys

• X-Wing ir Swordfish Sudoku: trumpi apibrėžimai ir aktyvavimo sąlygos
• Kaip veikia X-Wing žingsnis po žingsnio?
• Kaip veikia Swordfish ir kodėl jis galingesnis?
• Kada Sudoku sprendime naudoti X-Wing, o kada Swordfish
• Kaip greitai pastebėti X-Wing neperkraunant užrašų
• Swordfish skenavimo metodas, kuris iš tiesų veikia masteliu
• Kodėl veikia žuvies raštai: eliminacijų logika
• Palyginimo lentelė: X-Wing, Swordfish, Jellyfish
• Praktikoje: vidutinio sunkumo sprendimas, kuris stringa, o paskui atsiveria
• Dažniausios klaidos ir kaip jų išvengti
• Treniruočių planas automatiniam atpažinimui ugdyti
• Pažangios pastabos ekspertams ir sudarytojams
• Kaip praktikuotis internete ir matuoti pažangą
• Svarbiausios išvados

X-Wing ir Swordfish Sudoku skirtumas priklauso nuo masto ir išsidėstymo. X-Wing taikykite tada, kai kandidatas tiksliai du kartus pasirodo dviejose eilutėse ar stulpeliuose ir sutampa dviejuose stulpeliuose ar eilutėse; Swordfish taikomas, kai tas pats modelis išsiplečia į tris eilutes ar stulpelius. Juos greitai pastebėsite skenuodami po vieną skaitmenį, skaičiuodami kandidatų vietas kiekvienoje linijoje ir prieš šalinant įsitikindami tiksliu stulpelių ar eilučių sutapimu.

Jei po vienetų ir porų įstrigote sudėtinguose galvosūkiuose, šių žuvies raštų įvaldymas yra kitas tikras žingsnis į priekį. Esu mokęs šimtus sprendėjų pereiti nuo vidutinio lygio kliūčių prie nuoseklių užbaigimų naudojant tvarkingus kandidatų užrašus, skenavimą eilutė po eilutės ir disciplinuotą eilučių bei stulpelių sąveikos tikrinimą. Nauda juntama iš karto: greitesnės eliminacijos, mažiau spėjimų ir užtikrintesnės pabaigos.

X-Wing ir Swordfish Sudoku: trumpi apibrėžimai ir aktyvavimo sąlygos

Tiek X-Wing, tiek Swordfish yra žuvies raštai, kurie naudoja eilučių ir stulpelių simetriją kandidatams šalinti. Skirtumas yra bazinių linijų skaičius ir kandidatų kiekio griežtumas.

• X-Wing (2x2 struktūra):

  • Sąlyga: Dviejose skirtingose eilutėse skaitmuo pasirodo tiksliai dviejose langeliuose, o tie stulpeliai sutampa abiejose eilutėse. Arba tas pats principas, kai bazė yra stulpeliai, o dengiančios linijos – eilutės.
  • Poveikis: Šalinkite tą skaitmenį iš visų kitų langelių tuose sutampančiuose stulpeliuose (ar eilutėse).

• Swordfish (3x3 struktūra):

  • Sąlyga: Trijose skirtingose eilutėse skaitmuo pasirodo tiksliai dviejuose arba trijuose langeliuose kiekvienoje, tačiau visi kandidatai kartu telpa į tuos pačius tris stulpelius. Arba analogiškas variantas su stulpeliais.
  • Poveikis: Šalinkite tą skaitmenį iš visų kitų langelių tuose trijuose stulpeliuose (ar eilutėse).

Pagal standartinį Sudoku apribojimų formalizavimą Wikipedia, šios struktūros išnaudoja tarpusavio išskirtinumą: jei skaitmuo užfiksuotas konkrečiose sankirtose, jis negali atsirasti kitur atitinkamose dengiančiose linijose. arXiv publikuoti tyrimai pabrėžia, kodėl tokia logika būtina aukštesniuose sudėtingumo lygiuose: apibendrintas Sudoku sprendimas yra NP-sunkus, todėl masteliu veikiantys kandidatų mažinimo metodai yra svarbūs.

Kaip veikia X-Wing žingsnis po žingsnio?

X-Wing yra mažiausias ne trivialus žuvies raštas. Jį lengva pastebėti ir saugu taikyti.

• Pradinė sąlyga: Turite tvarkingus kandidatų užrašus pagal skaitmenis visame tinkle.
• Apimtis: Vienas skaitmuo vienu metu; pirmiausia skenuokite eilutes arba stulpelius, priklausomai nuo matomumo.
• Tikslas: Rasti dvi eilutes, kuriose skaitmuo pasirodo tiksliai dviejose vietose ir tie stulpeliai sutampa.

Žingsnis po žingsnio (žvilgsnis iš eilučių pusės):

1. Pasirinkite skaitmenį, pavyzdžiui, 7. Peržiūrėkite visas devynias eilutes.
2. Pažymėkite eilutes, kuriose 7 yra tiksliai dviejuose langeliuose. Užsirašykite jų stulpelių indeksus.
3. Jei randate dvi eilutes su identiškomis stulpelių poromis, pavyzdžiui, c3 ir c8, turite X-Wing.
4. Pašalinkite 7 iš visų kitų c3 ir c8 langelių, kurie nepriklauso toms dviem eilutėms.

Trumpas konkretus pavyzdys:

• 2-oje eilutėje 7 yra tik r2c3 ir r2c8.
• 6-oje eilutėje 7 yra tik r6c3 ir r6c8.
• Tada šalinkite 7 iš bet kurių kitų r?c3 ar r?c8 langelių, išskyrus r2c3, r2c8, r6c3 ir r6c8.

Kodėl tai saugu:

• Jei 7 nebūtų įrašytas į tas suderintas pozicijas, viena iš bazinių eilučių netektų visų galimų 7, o tai prieštarautų Sudoku taisyklėms. Tai grynas kandidatų šalinimas, o ne spėjimas.

Kaip veikia Swordfish ir kodėl jis galingesnis?

Swordfish išplečia X-Wing nuo dviejų bazinių linijų iki trijų. Jis retesnis, bet išvalo didesnę tinklo dalį.

• Pradinė sąlyga: Tvarkingi užrašai pagal skaitmenis ir eilučių ar stulpelių skaičiavimai.
• Apimtis: Vienas skaitmuo; skenuokite visas eilutes (arba visus stulpelius) ir fiksuokite kandidatų kiekį kiekvienoje linijoje.

Eilutėmis paremtas Swordfish kontrolinis sąrašas:

• Nustatykite tris eilutes, kuriose tikslinis skaitmuo kiekvienoje pasirodo tiksliai dviejuose arba trijuose langeliuose.
• Patvirtinkite, kad per tas eilutes visi kandidatai telpa į tuos pačius tris stulpelius.
• Jei taip, šalinkite tą skaitmenį iš kitų langelių tuose trijuose stulpeliuose už trijų bazinių eilučių ribų.

Modelio pavyzdys:

• 1-oje eilutėje 5 yra c2, c9
• 5-oje eilutėje 5 yra c2, c6, c9
• 8-oje eilutėje 5 yra c2, c6
• Stulpelių sąjunga yra {c2, c6, c9} per r1, r5, r8. Tai sudaro Swordfish su 5.
• Šalinkite 5 iš c2, c6 ir c9 visuose kituose eilutėse.

Galia prieš riziką:

• Swordfish pašalina daugiau kandidatų, nes apima tris stulpelius ar eilutes.
• Vienintelė rizika yra neteisingas suskaičiavimas. Prieš bet kokias eliminacijas patikrinkite tikslų sutapimą.

Kada Sudoku sprendime naudoti X-Wing, o kada Swordfish

Šiuos modelius taikykite po pagrindinių technikų, bet prieš gilesnes grandines.

Rekomenduojama veiksmų seka:

1. Pagrindai: vienetai, paslėpti vienetai ir dėžutės–linijos sąveika.
2. Vidutinis lygis: plikos ir paslėptos poros, trejetai; nukreipimai ir pareiškimai.
3. Žuvies lygis: pirmiausia taikykite X-Wing, o tada Swordfish, jei tinklelis vis dar tankus.
4. Pažangus lygis: jei žuvies raštų nėra, svarstykite spalvinimą, XY-Wing arba grandines.

Patarimai pagal situaciją:

• Ankstyva vidurinė partija su vidutiniu kandidatų tankiu: X-Wing yra greitas ir dažnas.
• Vėlyva vidurinė partija arba sunkūs galvosūkiai su tankiais užrašais: Swordfish plačiai atveria eilutes ar stulpelius.
• Jei dirbate su laiko spaudimu internete, pirmiausia skenuokite X-Wing, o tada pereikite prie sudėtingesnių variantų. Norėdami praktikuoti šią seką gyvuose tinkleliuose, išbandykite Žaisti Sudoku internete nemokamai ir keiskite sudėtingumą, kad treniruotumėte akį.

Kaip greitai pastebėti X-Wing neperkraunant užrašų

Greitis atsiranda iš nuoseklaus skenavimo ir linijų skaičiavimo disciplinos.

• Skenuokite pagal skaitmenį, o ne pagal sritį. Tvarkykite 1–9 iš eilės.
• Kiekvienam skaitmeniui trumpai pasižymėkite linijų žemėlapį: eilutes su tiksliai dviem kandidatais ir jų stulpelius.
• Iškart sutikrinkite poras; sutampantys stulpeliai rodo galimą X-Wing.

Praktiniai patarimai:

• Eilutės pirmiau ar stulpeliai pirmiau: rinkitės tą kryptį, kurioje užrašai švaresni. Jei triukšmo daug, persijunkite.
• Naudokite tinklo simetriją: jei pastebite, kad du stulpeliai nuolat turi dvigubus kandidatus, patikrinkite stulpelinį variantą.
• Laikykite kandidatų žymes plonas ir vienodas. Per daug žymėjimo paslepia reikalingus sutapimus.

Kaip aiškina Emma Reyes, loginių galvosūkių redaktorė ir trenerė: „X-Wing yra sprendėjo metronomas — kai išmokstate dviejų per liniją ritmo ir tobulo sutapimo, eliminacijos atsiranda per kelias sekundes.“

Swordfish skenavimo metodas, kuris iš tiesų veikia masteliu

Swordfish be pasikartojančios rutinos gali atrodyti slidus.

• Suskaičiuokite kandidatus kiekvienoje eilutėje tiksliniam skaitmeniui; pažymėkite eilutes su 2–3 kandidatais.
• Sekite kandidatų stulpelių sąjungą bet kuriai trijulei iš šių eilučių.
• Jei sąjungos aibė yra tiksliai trys stulpeliai, turite galiojantį Swordfish.

Heuristikos paieškos laikui mažinti:

• Pirmenybę teikite skaitmenims, kurie jau telkiasi trijuose stulpeliuose.
• Praleiskite trijules, kuriose viena eilutė išsiskleidžia į keturis ar daugiau stulpelių.
• Jei eilutėmis paremtas variantas nieko nerodo, pakartokite tą pačią logiką su stulpeliais.

Greitas būdas treniruoti šį modelį – kaitalioti praktiką vidutinio ir sunkaus lygio lentose. Jei dar tik pradedate dirbti su kandidatų žymėjimu, pradėkite nuo Kaip žaisti Sudoku pradedantiesiems — galutinis gidas, o tada grįžkite prie Swordfish su tvarkingesniais užrašais.

Kodėl veikia žuvies raštai: eliminacijų logika

Žuvies raštai yra klasikinis apribojimų sklaidos taikymas stačiakampiuose vienetuose. Skaitmuo, apribotas iki k stulpelių per k eilutes, tampa užrakintas tose k sankirtose; bet koks kitas pasirodymas tuose stulpeliuose pažeistų eilučių aprėptį. Ir atvirkščiai, kai kalbama apie stulpelius ir eilutes.

• Jie įgyvendina tiesioginę dengimo ir bazės dvilypumo logiką: bazinės linijos saugo tikslias padėtis, o dengiančios linijos – eliminacijas.
• Tas pats principas naudojamas platesniuose apribojimų tenkinimo metoduose dirbtiniame intelekte ir operacijų tyrime. Dėl gilesnio konteksto apie apribojimus ir paiešką sudėtingose problemose žr. analitinę The Guardian medžiagą apie loginius galvosūkius ir problemų sprendimo kultūrą.

Pastaba: žuvies raštai yra paremti modeliais ir nereikalauja šakojimosi. Jie papildo, o ne pakeičia tokias technikas kaip spalvinimas ar grandinės.

Palyginimo lentelė: X-Wing, Swordfish, Jellyfish

Peržiūrėkite palyginimą iš pirmo žvilgsnio ir pasirinkite tinkamą įrankį, kai tankis didėja.

Praktikoje: vidutinio sunkumo sprendimas, kuris stringa, o paskui atsiveria

Dirbant su turnyrinio tipo galvosūkiais, dažniausias strigimas įvyksta po porų ir užrakintų kandidatų, kai dėžutės jau prisotintos. Štai sutrumpintas scenarijus.

• Tinklelio būsena: Po pagrindų skaitmuo 7 tinklelyje pasiskirstęs retai.
• X-Wing proveržis: 3 ir 7 eilutėse 7 matomas tik c1 ir c5. Tai X-Wing. Pašalinkite 7 iš kitų c1 ir c5 langelių.
• Grandininė reakcija: Tai atrakina paslėptą vienetą r3c5, tada pliką porą 6-oje dėžutėje.
• Swordfish tęsinys: Skaitmuo 5 1, 4 ir 8 eilutėse apsiriboja 2, 6 ir 9 stulpeliais. Taikykite Swordfish ir pašalinkite 5 kitur tuose stulpeliuose.
• Pabaiga: Tinklelis išsivalo, atsiranda kelios vienetų vietos ir paprasta pabaiga.

Pagal ilgalaikes analizes ir duomenų bazes, cituojamas Wikipedia Sudoku puslapyje, ši seka — X-Wing prieš Swordfish — atitinka tai, kaip kandidatų tankis paprastai mažėja, kai galvosūkiai pereina iš vidutinio į sunkų lygį.

Dažniausios klaidos ir kaip jų išvengti

• Netiksliai suskaičiuojamas kandidatų skaičius eilutėje:
  • Sprendimas: Skaičiuokite garsiai arba naudokite paprastą kiekvieno skaitmens kontrolinį sąrašą.
• Manoma, kad sutapimas yra teisingas, nors stulpeliai ar eilutės nesutampa tiksliai:
  • Sprendimas: X-Wing atveju stulpeliai arba eilutės turi sutapti idealiai; Swordfish atveju sąjungos aibė turi būti tiksliai trys.
• Viduryje modelio maišomas eilučių ir stulpelių mąstymas:
  • Sprendimas: Pirmiausia iki galo užbaikite vieną kryptį, tik tada pereikite prie kitos.
• Per klaidą šalinama bazinėse linijose:
  • Sprendimas: Šalinkite tik dengiančiose linijose, ne bazinėse eilutėse ar stulpeliuose, kurie apibrėžia žuvies raštą.
• Praleidžiami kandidatų užrašai:
  • Sprendimas: Tvarkingi užrašai yra pažangių Sudoku strategijų pagrindas.

Treniruočių planas automatiniam atpažinimui ugdyti

• Kasdienės 10 minučių pratybos su vienu skaitmeniu per visą tinklelį.
• Kaitaliokite savaites, kai pirmiausia skenuojate eilutes, ir savaites, kai pirmiausia skenuojate stulpelius, kad subalansuotumėte modelių atpažinimą.
• Ribokite laiką: 60 sekundžių vienam skaitmeniui X-Wing atveju; 2–3 minutės vienam skaitmeniui Swordfish atveju.
• Sekite vidutinį sprendimo laiką per 10 galvosūkių, kad įvertintumėte pažangą. Daugelis sprendėjų po dviejų savaičių tikslingų pratybų praneša apie 15–25 % greitesnį užbaigimą, o tai dera su platesniais problemų sprendimo laimėjimais, kuriuos pabrėžia analitiniai šaltiniai, tokie kaip arXiv.

Pažangios pastabos ekspertams ir sudarytojams

• Spalvinimo sinergija: Po Swordfish grįžkite prie dviejų spalvų grafų; eliminacijos dažnai sulaužo paritetą.
• Dėžučių sąveika: Žuvies raštai gali egzistuoti kartu su dėžutės–linijos redukcijomis — iš naujo peržiūrėkite dėžutes paveiktuose stulpeliuose ar eilutėse.
• Jellyfish riba: Jei trijų linijų sąjungos nuolat išsiplečia į keturis stulpelius, esate visai šalia Jellyfish — patikrinkite prieš pereidami prie grandinių.
• Kandidatų šalinimo disciplina: Visada pažymėkite, kurios eliminacijos priklauso kuriai technikai. Tai padeda išvengti grįžtamojo taisymo klaidų ir stiprina modelių atmintį.

Kaip praktikuotis internete ir matuoti pažangą

• Naudokite laikmatį ir klaidų skaitiklį neutralioje sąsajoje. Švari Žaisti Sudoku internete nemokamai aplinka palaiko kelis tipus ir lygius, todėl puikiai tinka modelių pratyboms.
• Pradėkite nuo struktūruotos pamokos, tada pereikite prie mišrios praktikos, kad X-Wing ir Swordfish atsirastų natūraliai. Pradedančiųjų gido paaiškinimai padeda išlaikyti nuoseklius kandidatų užrašus.
• Keiskite skaitmenis. Neieškokite tik 5 ir 7; skenuokite visus skaitmenis, kad atpažinimas taptų universalesnis.

Svarbiausios išvados

• X-Wing ir Swordfish Sudoku yra masto klausimas: 2 suderintos eilutės ar stulpeliai X-Wing atveju, 3 — Swordfish atveju.
• X-Wing atpažinkite radę dvi eilutes ar stulpelius su tiksliai dviem kandidatais, suderintais tuose pačiuose stulpeliuose ar eilutėse.
• Swordfish atpažinkite radę tris eilutes ar stulpelius, kuriuose visi kandidatai telpa į tiksliai tris bendrus stulpelius ar eilutes.
• Žuvies raštus taikykite po porų ir dėžutės–linijos ėjimų, bet prieš gilių grandinių technikas.
• Laikykitės griežtų kandidatų užrašų ir linijų skaičiavimo, kad išvengtumėte klaidingų eliminacijų ir greičiau atpažintumėte modelius.
• Praktikuokitės skenuodami po vieną skaitmenį laikomuose galvosūkiuose, kad šie modeliai taptų automatiniai.