Қиын Судокуды болжаусыз шешу: кері іздеусіз әдіс

Мазмұны

• Қиын Судокуды болжаусыз қалай шешуге болады: қадамдық жүйе
• Неліктен кері іздеусіз Судоку әдісі жұмыс істейді (және ауқымданады)
• Қандай жетілдірілген үлгілер болжаусыз жояды?
• Салыстыру кестесі: әр тәсілді қашан қолдану керек
• Тәжірибеде: қиын басқатырғышта циклді қолдану
• Логика сияқты көрінетін, бірақ шын мәнінде болжам болатын жиі қателер
• Қателіксіз қалуға арналған құралдар мен үлгілер
• Дәлелдер мен контекст: дөрекі күштен гөрі логика
• Басып шығаруға болатын тексеру парағы: болжаусыз шешу реті
• Негізгі тұжырымдар

Қиын Судокуды болжаусыз шешу үшін, қарапайым жалғыз сандардан бастап үлгіге негізделген жоюларға дейінгі қатаң логикалық тәсілдер жиынтығын ретімен қолданыңыз. Қарындаш белгілерін пайдаланыңыз, шектеулер арқылы жойыңыз, содан кейін балық үлгілеріне, қанаттарға және бояуға өтіңіз — сынап көру мен қателесу қажет емес.

Мен жарыстық шешушілерге кері іздеуді тәртіпті, көзге көрінетін логикамен алмастыратын әдісті үйретемін. Қиын Судокуды болжаусыз шешкенде, сіз кандидаттарды үмітпен емес, дәлелмен ақиқатқа айналдыруды үйренесіз. Бұл тәртіп қиын күнделікті басқатырғыштардан чемпионат деңгейіндегі тапсырмаларға дейін ауқымданады және тығырыққа тірелу күйзелісін жояды.

Қиын Судокуды болжаусыз қалай шешуге болады: қадамдық жүйе

Тор толық шешілгенше осы детерминделген циклді қолданыңыз. Әр өтуде кемінде бір жою немесе орналастыру болуы керек.

1. Таза қарындаш белгілерін қойыңыз

• Әр бос ұяшыққа жол, баған және блок ережелерімен шектелген 1–9 кандидаттарын жазыңыз.
• Қателіктің «ығысуын» болдырмау үшін әр орналастырудан кейін белгілерді бірден жаңартыңыз.
• Егер сіз қарындаш белгілеріне жаңадан кіріссеңіз, осы бастаушыларға арналған Судоку нұсқаулығынан негіздерін қайталаңыз.

2. Алдымен жалғыз сандар мен негіздерді жинаңыз

• Жалаңаш жалғыз сан: ұяшықта бір ғана кандидат бар.
• Жасырын жалғыз сан: бір цифр жолда/бағанда/блокта тек бір рет қана кездеседі.
• Құлыпталған кандидаттар (көрсету/мәлімдеу): блок ішіндегі бір сызыққа шектелген цифр сол сызықтың қалған бөлігінен жойылады.

3. Орта деңгейлі жиынтық логиканы қолданыңыз

• Жалаңаш жұптар/үштіктер: екі/үш ұяшық бірдей екі/үш цифрды бөліседі — оларды көршілерінен алып тастаңыз.
• Жасырын жұптар/үштіктер: цифрлар жұбы/үштігі тек екі/үш ұяшықта ғана көрінеді — соларды бекітіп, басқаларын тазалаңыз.
• Блок–сызық қысқарту: егер кандидат блок ішінде тек бір жолда/бағанда ғана кездессе, сол цифрды басқа блоктардағы сол жолдан/бағаннан сызып тастаңыз.

4. Жетілдірілген Судоку тәсілдерін қолданыңыз (кері іздеусіз Судоку)

• X-Wing Судоку: екі жолды (немесе бағанды) туралаңыз, онда бір цифр дәл екі сәйкес бағанда (немесе жолда) кездеседі; сол цифрды басқа жерлердегі осы бағандардан (немесе жолдардан) жойыңыз.
• Swordfish Судоку: X-Wing-ті үш жолға/бағанға кеңейтеді.
• Y-Wing стратегиясы (XY-Wing): XY ілмекті ұяшық XZ және YZ ұяшықтарымен байланысады; қай pivot шын болса да, олардың қиылысындағы Z жойылады.
• Судоку бояу (қарапайым/екі түсті): тор бойынша екілік кандидатқа түс беріңіз; бір түстегі қайшылықтар сол түстің бәрін жоюға мүмкіндік береді.
• Бірегей тікбұрыштар (UR): өлімге әкелетін үлгілерді орналастыруды мәжбүрлеу немесе жою арқылы болдырмаңыз.
• Шамамен құлыпталған кандидаттар (ALC/ALS): толыққа жуық жиындар қабаттасқанда, ортақ кандидат жойылуы мүмкін.

5. Қайта белгілеңіз, қайта шолыңыз, қайталаңыз

• Әр сәтті қадамнан кейін кандидат жазбаларын жаңартыңыз.
• 2–4-қадамдарды шешілгенше қайталаңыз. Тұрып қалсаңыз, негіздерді қайта тексеріңіз; жетілдірілген қадамдар көбіне жаңа жалғыз сандарды ашады.

Wikipedia растайтындай, Судоку толықтай логика арқылы шешіледі — болжау қажет емес — және жарамды басқатырғыш үшін ең аз берілген сан саны 2012 жылы дәлелденген 17 (дереккөз).

Неліктен кері іздеусіз Судоку әдісі жұмыс істейді (және ауқымданады)

Кері іздеусіз әдіс ашық: әр қадам жергілікті немесе жаһандық үлгімен негізделеді. Бұл қателерді азайтып, түзетуді жылдамдатады.

• Сенімділік: Сіз ешқашан цифрды дәлелсіз қоймайсыз, сондықтан болжау әкелетін тізбекті қателерден аулақ боласыз.
• Оқу қисығы: Тәсілдер бір-біріне сүйенеді; X-Wing-ті меңгеру Swordfish-ті интуитивті етеді.
• Тасымалданғыштық: Сол логика қағазда шешсеңіз де, Sudoku Pro онлайн басқатырғыштары сияқты цифрлық торды қолдансаңыз да бірдей жұмыс істейді.

Тәуелсіз Судоку құрастырушысы Алекс Ромеро былай түсіндіреді: «Үлгіге негізделген жоюларға берілгенде, сіз “Егер ше?” дегенді “Демек” дегенге ауыстырасыз. Дәл осы ауысым ең қиын торларды ешқашан болжаусыз ашып береді».

Қандай жетілдірілген үлгілер болжаусыз жояды?

Төменде мен қиын Судокуды болжаусыз шешу үшін қолданатын тәжірибеде дәлелденген үлгілер берілген. Әрқайсысы кандидаттарды сынақ арқылы емес, қайшылық немесе қамту арқылы жояды.

X-Wing: екі сызықты туралау

• d цифрын табыңыз: ол екі түрлі жолда дәл екі рет, бірдей бағандарда кездеседі.
• Әр жолда сол екі орынның бірі шын болуы тиіс болғандықтан, d бұл бағандардың басқа жерлерінде бола алмайды.
• Мысал: Егер R2 және R7-дегі 5 сандары C3 пен C8-мен шектелсе, басқа барлық жолдардағы C3 пен C8-ден 5-ті жойыңыз.

Swordfish: үш сызықты жалпылау

• Үш жолдың (немесе бағанның) әрқайсысында үш кандидат орны бар цифрды іздеңіз, және олар бірдей үш бағанды (немесе жолды) бөліседі.
• Сол цифрды үлгіден тыс осы бағандардан (немесе жолдардан) жойыңыз.

Y-Wing (XY-Wing): ілмек пен қанаттар логикасы

• Ілмекті ұяшық AB; оны көретін қанат ұяшықтары AC және BC.
• Бір қанатта A шын болса немесе екінші қанатта B шын болса — демек, қанаттардың қиылысындағы C жалған.

Бояу (екі түсті)

• Кандидат цифр жұптар тізбегінде көрінсе, кезектесіп бояңыз (A түсі және B түсі).
• Егер A түсі бір бірлікте өз-өзіне қайшы келсе, A түсін барлық жерден жойыңыз; әйтпесе екі түсті де көретін кез келген кандидат жойылады.

Бірегей тікбұрыштар (UR)

• Төрт ұяшықтан тұратын тікбұрышта бірдей екі цифр болса, бұл екі шешімге әкеледі, ал бұл заңсыз.
• Бірегейлікті сақтау үшін UR пішінін пайдаланып қосымша кандидатқа мәжбүрлеңіз немесе біреуін жойыңыз.

Healthline дерегінше, логикалық басқатырғыштар назар мен жұмыс жадын жаттықтыра алады — сіз осы үлгілерді шолуда қолданатын дағдылар (дереккөз). Әдейі жаттығу — кері байланысы бар мақсатты жаттығулар — дағдыны меңгеруді жеделдетеді, бұл ұғым менеджмент зерттеулерінде жақсы құжатталған (HBR).

Салыстыру кестесі: әр тәсілді қашан қолдану керек

Келесі матрица сізге келесі логикалық құралды таңдауға көмектеседі. Егер жылдам анықтама керек болса, шешу кезінде осы кестеге өтіңіз.

Салыстыру кестесі

Тәжірибеде: қиын басқатырғышта циклді қолдану

Міне, мен жақында 26 берілгені бар басқатырғышта қиын Судокуды болжаусыз қалай шешкенім.

• Бастапқы күй: Толық қарындаш белгілері ешқандай жалғыз сан бермеді; екі блокта 7 үшін құлыпталған кандидаттар көрінді.
• Негіздер кезеңі: Блок–сызық тазалаудан кейін R5C2-де 9 санының жасырын жалғыз орны пайда болды; бұл 5-жолдағы жалаңаш жұпты ашты.
• Орта деңгей кезеңі: 7-блоктағы (2,8) жасырын жұп 3-бағанды тазалап, R2C3-те 2 жалаңаш жалғыз санын тудырды.
• Жетілдірілген кезең: 1 және 9-жолдардағы 6 сандары бойынша C2 және C7 бағандарында X-Wing пайда болып, басқа жерлердегі C2 және C7-ден 6 жойылды да, 6-блокта жасырын жалғыз 6 ашылды.
• Қанат сәті: Y-Wing (R3C4=27 ілмек; R1C4=29; R3C6=79) R1C6-дағы 9-ды жойды.
• Тізбекті әсер: Тағы екі жалғыз сан шықты; 4 сандары бойынша қарапайым бояу тізбегі 8-бағанда бір түсті қайшылыққа ұшырап, қалғанын тазалады. Тор кері іздеусіз аяқталды.

Әр қадам құжатталды; ешқандай «сынап көру» қадамы болған жоқ. Негізгі нәрсе — циклді қайталау және шағын жоюлардың үлкендерін ашуына мүмкіндік беру.

Логика сияқты көрінетін, бірақ шын мәнінде болжам болатын жиі қателер

Қиын Судокуды болжаусыз тұрақты шешкіңіз келсе, мына тұзақтардан аулақ болыңыз.

• Кандидатты «дұрыс көрінеді» деп қабылдау. Егер ережені айта алмасаңыз (мысалы, «4-блоктағы құлыпталған кандидат ... мәжбүрлейді»), бұл — болжам.
• Қайта белгілемеуді өткізіп жіберу. Ескірген қарындаш белгілері жалғыз сандарды жасырады және бояу сияқты тізбек үлгілерін бұзады.
• Ерекше әдістерді тым ерте қолдану. Әрқашан алдымен негіздерді тазалаңыз; көптеген қиын басқатырғыштар ALS немесе тізбекке бай желілерсіз-ақ шешіледі.

Қателіксіз қалуға арналған құралдар мен үлгілер

Тұрақтылық — қиын Судокуды жылдам болжаусыз шешуге мүмкіндік беретін нәрсе.

• Белгілеу: Айқындық үшін rNcM (жол/баған) жазуын қолданыңыз. Жалғыз сандарды шеңберге алыңыз, жұптарды/үштіктерді астын сызыңыз, ал екілік кандидаттарды түспен белгілеңіз.
• Тексеру парақтары: Цикл қадамдарының басып шығарылған тізімін тордың жанына қойыңыз.
• Жаттығу ортасы: Sudoku Pro сайтындағы таза, шешілетін жинақты пайдаланыңыз және, егер жаңадан бастасаңыз, X-Wing Судоку немесе Swordfish Судоку қоспас бұрын бастаушыларға арналған Судоку оқулығымен ұғымдарды қайталаңыз.

Дәлелдер мен контекст: дөрекі күштен гөрі логика

Компьютерлік шешушілер басқатырғыштарды кері іздеу және exact cover (мысалы, Algorithm X) арқылы шеше алады, бірақ адамға ыңғайлы әдістер әлі де үлгіге негізделген және көрнекі болып қала береді (Wikipedia on Sudoku). Ірі газеттер ұсынатын редакциялық басқатырғыш ортада күтілетіні — болжаммен емес, логикалық қадамдармен шешілу (The New York Times).

• Логикалық шешілгіштік: Жарияланған қиын басқатырғыштар кездейсоқ тармақталуды емес, ой қорытуын марапаттауға арналған.
• Дағдыны дамыту: Жетілдірілген Судоку тәсілдері үлгілердің ойша каталогын қалыптастырып, іздеу еңбегін азайтады.
• Сенімділік: Болжамсыз аяқтау сенімді тексеру ізін береді — әдісіңізді қайта қарап, үйрете аласыз.

Басып шығаруға болатын тексеру парағы: болжаусыз шешу реті

Мұны үстеліңіздің жанына жапсырып қойыңыз да, қиын Судокуды болжаусыз шешу үшін оны блок-схема сияқты қолданыңыз.

1. Тор бойына толық қарындаш белгілерін қойыңыз
2. Жалаңаш жалғыз сандар, содан кейін жасырын жалғыз сандар
3. Құлыпталған кандидаттар (көрсету және мәлімдеу)
4. Жалаңаш жұптар/үштіктер, содан кейін жасырын жұптар/үштіктер
5. Блок–сызық қысқартуларын қайта қарау
6. X-Wing Судоку (алдымен жолдар, содан кейін бағандар)
7. Swordfish Судоку (қажет болса)
8. Y-Wing стратегиясының мүмкіндіктері
9. Екілік кандидаттардағы Судоку бояуы
10. Бірегей тікбұрыштар; мәжбүрлі орналастыруларды іздеңіз
11. Тығыз аймақтардағы ALS/ALC шолулары
12. Қайта белгілеңіз де, 2-қадамға оралыңыз

Осы циклді ұстана отырып, сіз қиын Судокуды қайта-қайта болжаусыз шешесіз, қорқынышты торларды шағын, дәлелденетін қадамдар тізбегіне айналдырасыз.

Негізгі тұжырымдар

• Қиын Судокуды болжаусыз шешу үшін қатаң тәсілдер циклін қолданыңыз — жалғыз сандар, жұптар/үштіктер, құлыпталған кандидаттар, содан кейін балықтар, қанаттар және бояу.
• Әр орналастырудан кейін кандидаттарды қайта белгілеңіз; ескірген жазбалар қателер мен өткізіп алуларға әкеледі.
• Сирек тізбектерге жүгінбей тұрып, X-Wing, Swordfish, Y-Wing стратегиясы, бояу және Бірегей тікбұрыштарға басымдық беріңіз.
• Логикаңызды өткір ұстау үшін Sudoku Pro-дағы іріктелген торларда жаттығып, негіздерді қайталаңыз.
• Қадамдарыңызды құжаттаңыз; егер орналастыруды түсіндіре алмасаңыз, сіз шешіп жатқан жоқсыз — болжап отырсыз.