Потребителски вход

Запомни ме | Регистрация
Постинг
15.04.2012 19:05 - Судоку за напреднали – Как да решаваме судоку задачи за напреднали?
Автор: pitagorid Категория: Забавление   
Прочетен: 43458 Коментари: 3 Гласове:
3

Последна промяна: 15.04.2012 19:08

Постингът е бил сред най-популярни в категория в Blog.bg
Судоку за напреднали – Как да решаваме судоку задачи за напреднали?
В предишния мой постинг най-подробно описах една много силна техника за решаване на елементарни судоку задачи за начинаещи. С прост пример обясних стъпка по стъпка как се разкриват цифрите, които трябва да се поставят в празните клетки на пъзела с помощта на техниката „кръстосана щриховка”. Стана ясно, че почти 90% от судоку задачите публикувани във вестниците, могат да се решат само с прилагането на тази техника.
Поясних също, че техниките за решаване на судоку задачите се делят на два вида:
- техники с директно вписване на кандидата в празна клетка.
- техники с елиминиране на кандидат от клетка с няколко кандидата.
Има само две техники, чрез които може да става директно вписване на кандидата в празна клетка.
1. Скрит кандидат
2. Явен кандидат
За разкриване на скритите кандидати се използва именно техниката „кръстосана щриховка”. Това е фундаментална техника, с която трябва да се започне решаването на всеки судоку пъзел.
Разкриването на явен кандидат обаче, се оказва доста по-трудна задача. Впрочем има една категория явни кандидати, които се появяват „автоматически” при последователно прилагане на кръстосаната щриховка в няколко тура. Тези явни кандидати в някои ръководства за решаване на судоку дори са ги нарекли със специално име „пълна къща” (на английски full house). Става дума за тези случаи, когато в дадена пъзелна група осем от клетките вече са запълнени с цифри и има само една празна клетка. Чрез непосредствена проверка веднага се установява, коя цифра трябва да се постави в нея. Някъде може за срещнете тези явни кандидати да се наричат „Последна цифра” или „Последна клетка”, но във всички случаи трябва да знаете, че става въпрос за едно и също нещо.
И така ако един пъзел може да се реши само с прилагането на техниката „кръстосана щриховка” и автоматично съпровождащата я техника „явен кандидат – последна цифра”, то такъв судоку пъзел условно ще наричаме „лесен пъзел за начинаещи”.
Какво обаче трябва да се направи, ако прилагането само на тази техника не е достатъчна?
Много просто! Ще трябва да се приложат другите техники за решаване, които попадат в групата с елиминиране на кандидати от клетки с няколко кандидата.
Именно с това ще се занимаваме по-нататък тук.
Както казах и в предишния постинг това е съпроводено с една доста неприятна и отегчителна работа, която обаче е просто задължителна за да продължите по-нататък.
За какво става дума? Трябва задължително да попълните в празните клетки всички възможни цифри (кандидати) които съгласно правилата на играта могат да се поставят там.
Задачата не е трудна, но е отегчителна и изнервяща. Това е така, защото трябва клетка по клетка да проверите много внимателно всички възможности. Препоръчвам ви следния начин на работа.
1. Винаги започвайте решаването на пъзела с техниката „кръстосана щриховка” и автоматичното разкриване на явни кандидати до пълното изчерпване на всички възможности на тази техника. В огромното мнозинство от случаите, това ще е достатъчно да решите пъзела докрай. Но когато все пак това не е достатъчно ще намерите все пак доста клетки, в които директно да въведете цифри. С това осезателно ще намалите празните клетки, които ще трябва да анализирате за попълване с възможните кандидати.

image
Фиг.1
На горната фигура е показана началната базова конфигурация на един судоку пъзел за напреднали.
Започваме решаването с техниката „Кръстосана щриховка” докато стигнем до „задънена улица”. Ако правилно прилагате тази техника би трябвало да достигнете до позицията показана на Фиг.2.

image

Фиг.2
Ясно се вижда, че спрямо базовата конфигурация чрез кръстосаната щриховка добавихме 8 нови цифри в осем клетки, които са означени на фигурата със син цвят.

2. Сега трябва да попълним самата таблица с кандидатите.
Попълвайте празните клетки с молив, като записвате с малки цифри възможните кандидати по следния начин: Мислено разделете клетката на девет малки области в три реда по три области. В първия ред ще нанасяте само цифри 1,2 и 3. Във втория ред - цифрите 4,5 и 6, а в третия ред - цифрите 7,8 и 9. Това е просто за удобство и е много прегледно. Вижте Фиг.3

image
Фиг.3
Като пример нека да попълним "централната клетка" D5 с всички възможни цифри (кандидати). Като знаем правилата на играта проверяваме обкръжението на празната клетка, какви цифри са известни от трите пъзелни групи, в които участва клетката. Под обкръжение ще разбираме онези 20 клетки, които са в пряка връзка с празната клетка. На Фиг.3 тези клетки за оцветени в сиво. В обкръжението на клетката D5 има само шест клетки с попълнени цифри. Това са D3(5), D4(1), A5(1), E5(9), I5(8) и D9(9). Въпреки че попълнените клетки са шест, използвани са само 4 цифри - 1, 5, 8 и 9. Следователно клетката D5(2,3,4,6,7). От фигурата се вижда как трябва да запишем с молив малките цифрички в празната клетка.
По подобен начин постъпваме с всички празни клетки и записваме с молив възможните кандидати. В крайна сметка ще получим таблицата показана на Фиг.4

image
Фиг.4
Тези които не харесват този начин на нанасяне на цифрите, могат да си ги нанасят както желаят. А за по-практичните мога да предложа вместо цифри да слагат в областите на клетката малки кръгчета или точки. На желателно е това да става точно на мястото на цифрата и то задължително с молив, за да може лесно да се изтриват. Ето така както е показано на следващата Фиг.5

image

Фиг.5
След като свършихме тази черна работа нека да преминем към описанието на новите техники за решаване на судоку задачи за напреднали.
Ще започнем с техниките за елиминиране на кандидати от клетки с няколко кандидата:

3. Заключени кандидати в блок 3х3
Понякога, някоя цифра в даден блок 3х3 се явява като кандидат само в две или три клетки разположени в един ред или колона вътре в блока. Само една клетка обаче може да приеме и то задължително тази стойност. В такъв случай можем спокойно да елиминираме този кандидат в клетки извън блока, намиращи се на същия ред или колона.

image

Фиг.6
В примера на Фиг.6 сме избрали цифрата „3” за анализ. Всички клетки които съдържат в себе си като кандидат цифрата "3" са означени в сив цвят. В деветия блок 3х3 има две клетки съдържащи кандидат „3”, разположени само в долния ред (тези клетки са означени със зелен цвят). Следователно една от тези клетки ще приеме стойност „3” и никоя друга клетка в същия ред извън блока не може да приеме тази стойност. Можем веднага да елиминираме цифрата „3” съдържаща се в клетката на деветия ред - B9 (тази оцветена в синьо).

4. Заключени кандидати в ред или колона
Понякога някоя цифра вътре в ред или колона се явява като кандидат в две или три клетки разположени всички вътре в един блок 3х3. Една от тези клетки задължително ще приеме тази стойност. Следователно веднага можем да елиминираме този кандидат съдържащ се в останалите празни клетки в блока 3х3.
В примера на Фиг.7 отново сме избрали цифрата „3” за анализ. Всички клетки които съдържат в себе си като кандидат цифрата „3” са означени в сив цвят. В осмия ред има три клетки, които съдържат цифрата „3”, които са разположени с средния ред на блока. Следователно една от тези клетки в реда ще приеме стойност „3” и никоя друга клетка в същия блок 3х3 извън осмия ред не може да приеме тази стойност. Можем веднага да елиминираме цифрата „3” съдържаща се в останалите празни клетки на осмия блок 3х3 - D7 и E7 (тези оцветени в синьо).

image
Фиг.7
Аналогичен е случая и с колона В на същата фигура. В четвъртия блок 3х3 има две клетки с кандидат цифрата „3” разположени само в колона В (тези оцветени в зелено). Следователно една от тези клетки в колоната ще при¬еме стойност „3” и никоя друга клетка в същия блок 3х3 извън колона В не може да приеме тази стойност. Можем веднага да елиминираме цифрата „3” съдържаща се в останалата празна клетка на четвъртия блок 3х3 - C5 (тази оцветена в синьо).
Описаните по-горе две техники на заключени кандидати в блок 3х3, в ред или колона са сравнително лесни за приложение, но за съжаление доста трудни за откриване. Трудността идва от това, че трябва да се работи с точно определен кандидат и трябва по някакъв начин цялата плетеница от цифри в таблицата да се „филтрира” и клетките които съдържат избрания кандидат да изпъкнат.
Ако разгледаме попълнената таблица с кандидати на фигура 3 ще ни бъде трудно за открием всички клетки които съдържат примерно цифрата „3”, която избрахме в примерите. За щастие има начин това да стане по-лесно. И отново на помощ идва техниката „кръстосана щриховка”. Този път ние няма да я използваме за откриване на скрити кандидати, а за „филтриране” на таблицата за да открием по-лесно къде има търсения от нас кандидат. Вижте Фиг.8
Използваме техниката „кръстосана щриховка”, но този път на фигурата не сме прекарали реално хоризонтални и вертикални линии през съществуващите клетки с цифрата „3”, а това сме направили „мислено”, както става с действителност, когато решавате задачата директно върху печатното издание. Ред трети и четвърти са „задраскани”. Колона А и колона G също са „задраскани”. Всички празни полета в първи и шести блок 3х3 също са „задраскани”. Това което остана незадраскано са филтрираните празни клетки които съдържат в себе си цифрата „3”. Тези клетки на фигурата са оцветени в светло синьо и изпъкват между останалите. На практика в печатното издание те няма да са оцветени, но все пак много ще ни улеснят да открием сред плетеницата точно тези клетки които ни интересуват.

image
Фиг.8
Гледайки фигурата много лесно откриваме за цифрата „3” прилагането на техниките „заключени кандидати”. В резултат елиминираме цифрата „3” от четири клетки с няколко кандидата. Това вече го направихме в примерите по-горе. Вижте Фиг.9

image

Фиг.9
На новата фигура съгласно техниката „кръстосана щриховка” веднага откриваме нов скрит кандидат за цифрата „3”. Това е клетката C7(3) и директно вписваме в ние „3”.
По подобен начин можем да приложим техниките „затворен кандидат” и за всички останали цифри от 1 до 9 за този пример.
Цифрата „1” е изцяло нанесена в таблицата и с нея няма да се занимаваме.
За цифрите „2”, „4”, „5”, „6”, „7” и „8” след непосредствена проверка установяваме, че тази техника не може да се приложи.
За цифрата”9” обаче може. Вижте Фиг.10

image

Фиг.10
В последната колонка но шести блок 3х3 има заключен кандидат „9” в колона I. Това ни дава право за елиминираме цифрата „9” в клетките I1, I2 и I3. След елиминацията в клетката I3 остава явен кандидат - цифрата „6” и можем директно да я въведем в тази клетка I3(6). Вижте Фиг.11.
Това е крайния резултат от прилагането на техниката „заключени кандидати” за избрания от нас пример. Понеже добавихме две нови цифри в клетките C7(3) и I3(6) имаме право да направим един допълнителен тур с техниката „кръстосана щриховка”. Възможно е да открием още скрити кандидати и дори да решим пъзела.
Еврика!! Има такъв в клетката A2(6). После се открива още един B9(6). След това още един C5(6). След това още един A1(7). След това пък можем да приложим „заключен кандидат” в колона G и трети блок 3х3 и можем да елиминираме цифрата”7” от клетката G5. След това намираме още един скрит кандидат в клетката A7(9), а от там пък чрез „заключени кандидати” ще елиминираме цифрата „9” от клетките B1и B3. В крайна сметка получаваме резултата показан на Фиг.12.

image
Фиг.11
image

Фиг.12
Сега можем отново да направим един нов тур с техниката „кръстосана щриховка” и вероятно можем да решим пъзела до край (което е наистина така), но ще спра дотук, за да покажа с пример нови техники за елиминиране на кандидати.

5. “Явна двойка” или така наречените още “Близнаци”
Ако две клетки в пъзелна група съдържат еднаква двойка от кандидати и в същите клетки няма други кандидати, казваме, че това са “близнаци”. В този случай не е възможно друга клетка от същата пъзелна група да съдържа който и да е един от тези “близнаци”. Тези кандидати могат веднага да се елиминират от останалите клет¬ки на групата.

6.“Явна тройка”, “Явна четворка”, "Явна петица" и т.н.
Същия принцип на “близнаците” може да се приложи и за 3,4 и т.н кандидата в три, четири и т.н клетки на пъзелна група. Можем условно да ги наречем “явна тройка”, “явна четворка”, “явна петица” и т.н..
“Явна тройка” е налице когато три клетки от групата съдържат само три различни кандидата, независимо как са разпределени те в тези клетки. В този случай веднага можем да изключим кандидатите от тройката, съдържащи се в други клетки на групата.
Важно! Клетките образуваща “явна тройка”, не трябва да съдържат други кандидати освен тези в тройката”.
“Явна четворка” е налице когато четири клетки от групата съдържат само четири различни кандидата, независимо как са разпределени те в тези клетки. В този случай веднага можем да изключим кандидатите от четворката, съдържащи се в други клетки на групата.
Важно! Клетките образуваща “явна четворка”, не трябва да съдържат други кандидати освен тези в четворката”.
Нека да се върнем отново към Фиг.12, но без да филтрираме никоя цифра. Виж Фиг.13

image

Фиг.13
Ако разгледаме внимателно таблицата с кандидатите ще забележим, че клетките I1(3,5) и I2(3,5) съдържат по два еднакви кандидата - цифрите 3 и 5. Казваме, че това е „явна двойка” или както често я наричат още - „близнаци”. Смисълът на тази техника е този, че ако в едната клетка се постави цифрата „3”, то задължително в другата трябва да се постави цифрата „5”. Следователно от останалите три клетки на третия блок 3х3 и трите клетки от колона I можем да изключим цифрите „3” и „5”.
Също така в колона H в шести блок 3х3 се съдържат три клетки в които се съдържат като кандидати цифрите „5”, „6” и „7”. Тези три клетки - H4(5,6), H5(7,5) и H6(7,6) образуват „явна тройка”. Следователно от клетките G5(2,5), H9(3,5,8), H1(3,5,8) и I4(2,4,5,9) трябва да елиминираме цифрата „5”.
Забележете че в третия ред също има „явна тройка” - клетките B3(4,2), C3(2,9) и F3(4,2,9). Вижте Фиг.14.

image
Фиг.14
Запазваме всички цифри оцветени в зелен цвят, а елиминираме (изтриваме с гумичката) всички цифри оцветени в синьо и получаваме като краен резултат следната таблица показана на Фиг.15

image
Фиг.15
Виждаме че се появиха 3 „явни кандидата” в клетките H1(8), G5(2) и I9(2). Това е достатъчно пъзелът да бъде решен докрай. Виж Фиг.16

image
Фиг.16

Това е за днес.
В следващия постинг ще продължа с описанието на нови две важни техники за решаване на судоку пъзели за напреднали и дори за майстори.
До нови срещи
 



Гласувай:
3
0



1. анонимен - Не помня от колко години вече всеки ...
17.04.2012 22:29
Не помня от колко години вече всеки ден решавам поне по едно много сложно. Най-трудното съм го решавал шект дена, но без проби и грешки. Търся логиката до края. Методите, които използвам са около десетина, не повече.
цитирай
2. chetivo - Благодаря Ви за труда! Дотук ...
18.02.2013 03:07
Благодаря Ви за труда!

Дотук съм стигнала сама до показаните техники, но ще се надявам да мога да прочета и следващите Ви наставления, защото ударих сериозно на камък с един пъзел...
Знам, че вероятно ако го започна отначало, по друг път, ще го реша, но искам по този ;)
цитирай
3. andrey40 - судоку за напреднали-нови техники
23.01.2017 21:29
Здравейте,завършвайки постинга от 15.04.2012,Вие казвате ,че ще покажете две нови техники.
Къде мога да намеря това?Благодарност за труда!
цитирай
Търсене

За този блог
Автор: pitagorid
Категория: Други
Прочетен: 2951377
Постинги: 158
Коментари: 1058
Гласове: 3829
Календар
«  Май, 2021  
ПВСЧПСН
12
3456789
10111213141516
17181920212223
24252627282930
31