Алгоритъм рибен меч с перка в судоку. Логически пъзели

Така че днес ще ви науча решаване на судоку.

За по-голяма яснота, нека вземем конкретен пример и разгледаме основните правила:

Правила за решаване на судоку:

Маркирах реда и колоната в жълто. Първо правиловсеки ред и всяка колона могат да съдържат числа от 1 до 9 и те не могат да се повтарят. Накратко - 9 клетки, 9 числа - следователно в 1-ва и същата колона не може да има 2 петици, осмици и т.н. По същия начин за струните.

Сега избрах квадратите - това е второ правило. Всеки квадрат може да съдържа числа от 1 до 9 и те не се повтарят. (Същото като в редове и колони). Квадратите са маркирани с удебелени линии.

Следователно имаме общо правилоза решаване на судоку: нито в линии, нито в колонинито в квадратичислата не трябва да се повтарят.

Е, нека се опитаме да го решим сега:

Маркирах единиците в зелено и показах посоката, в която гледаме. А именно, интересуваме се от последния горен квадрат. Може да забележите, че във 2-ри и 3-ти ред на този квадрат не може да има единици, в противен случай ще има повторение. И така - единица в горната част:

Лесно е да се намери двойка:

Сега нека използваме двете, които току-що намерихме:

Дано се е изяснил алгоритъмът за търсене, така че от тук нататък ще рисувам по-бързо.

Гледаме 1-ви квадрат на 3-ти ред (по-долу):

защото там имаме 2 свободни клетки, тогава всяка от тях може да има едно от две числа: (1 или 6):

Това означава, че в колоната, която подчертах, вече не може да има нито 1, нито 6 - затова поставяме 6 в горния квадрат.

Поради липса на време ще спра до тук. Силно се надявам да схванете логиката. Между другото, взех не най-простия пример, в който най-вероятно всички решения няма да бъдат незабавно видими недвусмислено и затова е по-добре да използвате молив. Все още не знаем за 1 и 6 в долния квадрат, затова ги рисуваме с молив - по същия начин 3 и 4 ще бъдат нарисувани с молив в горния квадрат.

Ако помислим още малко, използвайки правилата, ще се отървем от въпроса къде е 3 и къде е 4:

Да, между другото, ако някоя точка ви се стори неразбираема, пишете и аз ще обясня по-подробно. Успех със судоку.

Което ще ви помогне в развитието на един от най-важните органи – мозъка. Разбира се, добре познатите японски пъзели судоку са един от тях. С тяхна помощ можете доста да „напомпате мозъците“, защото в допълнение към необходимостта да изчислите огромен брой опции за подреждане на числата, вие също трябва да можете да направите това няколко десетки хода напред. С една дума, това е истински рай, ако искате да предпазите невроните си от изсъхване. И днес ще разгледаме основните трикове, които експертите по судоку използват. Ще бъде полезно както за начинаещи, така и за дългогодишни фенове на тези пъзели. В крайна сметка някой трябва да направи първите си стъпки в изкуството на судоку и някой трябва да подобри ефективността на своите решения!

правила

Ако все още не сте запознати, първо трябва да се запознаете с правилата. Повярвайте ми, те са много прости.

Игралното поле е квадрат с размери 9×9. В същото време той е разделен на по-малки квадрати с размери 3 × 3. Тоест цялото поле се състои от 81 клетки.

Условието на задачата са числата, които вече са поставени в тези клетки.

Блок (блок от клетки) - малък квадрат, линия или линия.

Какво трябва да направите: подредете всички останали числа, като следвате няколко правила. Първо, не трябва да има повторения във всеки от малките квадратчета. Второ, във всички колони и редове също не трябва да има повторения. Тоест всяко число трябва да се среща само веднъж във всеки от тези блокове. За да стане всичко още по-ясно, обърнете внимание на решеното судоку:

Основно решение

Като правило, ако решавате просто судоку, тогава всичко, което трябва да направите, е да запишете всичко. възможни вариантиза всяка от 81 клетки и постепенно зачеркнете неподходящите опции. Много е просто.

Но ако отидете ниво нагоре, до по-сложно судоку, тогава нещата стават по-интересни. Често ще се случва, че няма начин да поставите нови числа и ще трябва да преминете през предположенията: „Нека това число е тук“, след което ще трябва да разгледате тази хипотеза и или да стигнете до решение на проблема , или до противоречие на вашето предположение.

Но разбира се, има специални трикове, които ще ви помогнат да направите всичко това по-ефективно.

трикове

1. Голи двойки/тройки/четворки

Ако имате две клетки в един блок (квадрат, ред или колона), в които можете да поставите само 2 числа, тогава е очевидно, че тези числа могат да бъдат премахнати от опциите за други клетки в този блок.

Нещо повече, този трик може лесно да се направи както с тройки, така и с четворки:

2. Скрити двойки

Много полезна техника, в известен смисъл противоположна на голите двойки. Ако в някои две клетки на един квадрат във „възможни опции“ имате числа, които не се повтарят никъде другаде (в рамките на този квадрат), тогава всички останали числа от тези две клетки могат да бъдат премахнати.

За да стане още по-ясно, обърнете внимание на примери (един прост и по-сложен):

За щастие, това работи както за тройки, така и за четворки, но си струва да споменем една много важна и много готина функция. Не е необходимо три/четири клетки да съдържат еднакви 3 цифри от формата (a;b;c) (a;b;c) (a;b;c). Тази опция ще ви бъде достатъчна: (a;b) (b;c) (a;c).

3. Безименно правило

Ако имате чифт или тройка в една колона/ред, които се намират в същия квадрат, можете спокойно да премахнете тези числа от други клетки даден квадрат.

4. Посочване на двойки

Ако има две еднакви цифри в един ред/колона от „възможни опции“, тогава тези цифри могат да бъдат премахнати от съответната колона/ред.

Това може да бъде много полезно понякога, особено ако намерите няколко от тези двойки:

Разбира се, в този случай тези числа трябва да отсъстват в други клетки на квадрата, но според неназованото правило това не се изисква.

Обичате судоку и други гатанки, игри, пъзели и тестове, насочени към развиване на различни аспекти на мисленето? Получете достъп до всички интерактивни материали на сайта, за да се развивате по-ефективно.

Заключение

Разгледахме основните техники, които се използват при решаването на судоку. Отбелязвам, че това е само началото и в следващите статии ще разгледаме по-сложни и по-интересни функции, благодарение на които решаването на подобни проблеми ще стане още по-интересно и по-лесно.

Като обучение, изданието 4brain ви кани да се запознаете с файла, който съдържа судоку с различни нива на трудност. Отделете време за практика, защото ако отделите достатъчно време на този урок, тогава в края на този курс от статии, повярвайте ми, ще станете истински ас в решаването на японски пъзели.

Ако имате въпроси относно тези техники или судоку, които прикачваме към статията, не се колебайте да ги зададете в коментарите!

Судоку е много интересен пъзел. Необходимо е да подредите числата от 1 до 9 в полето по такъв начин, че всеки ред, колона и блок от 3 х 3 клетки да съдържа всички числа, като в същото време те не трябва да се повтарят. Обмисли инструкции стъпка по стъпкакак се играе судоку, основни методи и стратегия за решение.

Алгоритъм за решение: от просто към сложно

Алгоритъмът за решаване на умствената игра судоку е доста прост: трябва да повторите следните стъпки, докато цялостно решениезадачи. Постепенно преминете от най-простите стъпки към по-сложни, когато първите вече не ви позволяват да отворите клетка или да изключите кандидат.

Единични кандидати

Първо, за по-нагледно обяснение как се играе судоку, нека въведем система за номериране на блокове и клетки на полето. Както клетките, така и блоковете са номерирани отгоре надолу и отляво надясно.

Нека започнем да разглеждаме нашата област. Първо трябва да намерите единични кандидати за място в клетката. Те могат да бъдат скрити или явни. Помислете за възможните кандидати за шестия блок: виждаме, че само една от петте свободни клетки съдържа уникален номер, следователно четирите могат безопасно да бъдат въведени в четвъртата клетка. Разглеждайки този блок по-нататък, можем да заключим: втората клетка трябва да съдържа числото 8, тъй като след изключването на четирите осемте в блока не се срещат никъде другаде. Със същата обосновка поставяме числото 5.

Внимателно прегледайте всички възможни опции. Разглеждайки централната клетка на петия блок, откриваме, че не може да има други опции освен числото 9 - това е ясен единствен кандидат за тази клетка. Деветте могат да бъдат зачеркнати от останалите клетки на този блок, след което останалите числа могат лесно да бъдат записани. Използвайки същия метод, преминаваме през клетките на други блокове.

Как да открием скрити и явно "голи двойки"

След като въведохме необходимите числа в четвъртия блок, нека се върнем към празните клетки на шестия блок: очевидно е, че числото 6 трябва да бъде в третата клетка и 9 в деветата.

Концепцията за "гола двойка" присъства само в играта на судоку. Правилата за тяхното откриване са следните: ако две клетки от един и същи блок, ред или колона съдържат идентична двойка кандидати (и само тази двойка!), то другите клетки от групата не могат да ги имат. Нека обясним това на примера на осмия блок. Поставяйки възможни кандидати във всяка клетка, намираме очевидна "гола двойка". Числата 1 и 3 присъстват във втората и петата клетка на този блок и там и там има само по 2 кандидата, следователно те могат безопасно да бъдат изключени от останалите клетки.

Завършване на пъзела

Ако сте научили урока как да играете судоку и сте следвали горните инструкции стъпка по стъпка, тогава трябва да получите нещо като тази снимка:

Тук можете да намерите единични кандидати: единица в седмата клетка на деветия блок и двойка в четвъртата клетка на третия блок. Опитайте се да разрешите пъзела до края. Сега сравнете вашия резултат с правилното решение.

Се случи? Поздравления, това означава, че успешно сте усвоили уроците как да играете судоку и сте се научили как да решавате най-простите пъзели. Има много разновидности на тази игра: судоку с различни размери, судоку с допълнителни зони и допълнителни условия. Игралното поле може да варира от 4 x 4 до 25 x 25 клетки. Може да попаднете на пъзел, в който числата не могат да се повтарят в допълнителна област, например диагонално.

Започни с прости опциии постепенно преминавайте към по-трудни, защото с обучението идва и опитът.

Судоку е математически пъзел, чиято родина се счита за изгряващо слънце- Япония. Времето за невероятно вълнуващ и развиващ се пъзел лети незабелязано. Статията ще предостави начини, методи и стратегии за решаване на судоку.

История на имената на играта

Колкото и да е странно, но Япония не е родното място на играта. Всъщност известният математик Леонхард Ойлер е изобретил пъзела през 18 век. От курса на висшата математика мнозина трябва да си спомнят известните "кръгове на Ойлер". Ученият бил запленен от областите на комбинаториката и пропозиционалната логика, той нарекъл своите квадрати от различни редове „латински“ и „гръко-латински“, тъй като използвал букви, за да композира предимно. Но пъзелът придоби истинска популярност след редовни публикации в японското списание Nikoli, където получи името Sudoku през 1986 г.

Как изглежда загадката?

Пъзелът представлява квадратно поле с размери 9 на 9 клетки. В зависимост от сложността и вида на пъзела, компютърът оставя даден брой квадратни клетки запълнени. Понякога начинаещите се интересуват от въпроса: "Колко варианта на пъзела могат да бъдат направени?".

Според правилата на комбинаториката броят на пермутациите може да се намери чрез изчисляване на факториела на броя на елементите. И така, судоку използва числа от 1 до 9, така че трябва да изчислите факториела на 9. Чрез прости изчисления получаваме 9! = 1*2*3*4*5*6*7*7*9 = 362 880 - опции за различни комбинации от низове. След това трябва да използвате формулата за пермутация на матрицата и да изчислите броя на възможните позиции на редове и колони. Формулата за изчисление е доста сложна, просто отбележете, че когато замените само една тройка колони / редове, можете да увеличите общия брой опции с 6 пъти. Умножавайки стойностите, получаваме 46 656 - начина на пермутации в матрицата на загадката само за 1 комбинация. Лесно е да се досетите, че крайното число ще бъде равно на 362 880 * 46 656 = 16 930 529 280 опции за игра - решите да не отменяте.

Според изчисленията на Бертам Фелгенхауер обаче пъзелът има много повече решения. Формулите на Бертам са много сложни, но дават общ брой пермутации от 6 670 903 752 021 072 936 960 - варианта.

Правила на играта

Правилата на судоку варират в зависимост от вида на пъзела. Но за всички варианти изискването на класическото судоку е общо: числата от 1 до 9 да не се повтарят вертикално и хоризонтално в полето, както и във всеки избран раздел "три по три".

Има и други видове игри, като четно-нечетно судоку, диагонал, виндоку, жирандол, зони и латино. На латиница вместо цифри се използват букви от латинската азбука. Вариантът четно-нечетно трябва да се решава като обикновено судоку, само че трябва да се вземат предвид многоцветните области. В клетките от един цвят трябва да има четни числа, а вторият - нечетни. В диагонална гатанка до класически правила"вертикално, хоризонтално, три по три" се добавят още два диагонала на полето, в които също не трябва да има повторения. Разновидност на зоната е вид цветно судоку, което няма разделение три по три. класически видигри. Вместо това с помощта на цветни или удебелени граници се избират произволни области от 9 клетки, в които трябва да се поставят числа.

Как да решите судоку правилно?

Основното правило на загадката гласи: има само една правилна версия на числото за всяка клетка от полето. Ако изберете грешен номер на даден етап, следващото решение ще стане невъзможно. Числата вертикално и хоризонтално ще започнат да се повтарят.

Най-простият пример за твърдение е ситуация с 8 известни числа хоризонтално, вертикално или в областта "три по три". Начините за решаване на судоку в този случай са очевидни - въведете липсващата цифра от редицата от 1 до 9 в необходимия квадрат.В примера на изображението по-горе това ще бъде числото 4.

Понякога две клетки от областта "три на три" остават незапълнени. В този случай всяка клетка има две възможни опции за попълване, но само една е правилна. Можете да направите правилния избор, като разглеждате празните площи не само като част от площта, но и като част от вертикалата и хоризонталата. Например в квадрата "три по три" липсват 2 и 3. Трябва да изберете една клетка и да вземете предвид вертикалните и хоризонталните пресечки, което е. Да предположим, че вече има една 3 по вертикалата, но и в двете последователности липсва 2. Тогава изборът е очевиден.

Пъзелите за начално ниво са трудни, като правило предоставят възможност за незабавно попълване на няколко клетки с единствените правилни стойности. Просто трябва внимателно да обмислите игралното поле. Но не винаги изборът на начини / методи, как да решите судоку, е толкова прост.

Какво означава "предварително определен избор" в судоку?

Понякога изборът не е единствен, но въпреки това е предопределен. Нека наречем това число "уникален кандидат". Намирането на такова подреждане на числа в полето на пъзела не е трудно, но ще изисква известен опит в решаването на пъзела. Пример за правилно решаване на судоку с уникален кандидат е описан подробно за варианта на игралното поле на изображението по-долу.

В подчертания червен квадрат, на пръв поглед, може да стои всяка цифра, с изключение на 5. Но всъщност уникален кандидат за мястото е цифрата 4. Необходимо е да се вземат предвид всички вертикали и хоризонтали на тройката - три разглеждани области. И така, във вертикали 2 и 3 има четворки, което означава, че 4 малки полета могат да бъдат разположени в едно от трите квадрата на първата колона. Горният квадрат вече е зает от числото 5, броят на местата за символа 4 е намален. Също така не е трудно да се намери четири в долния хоризонтал на региона, следователно от 3 варианта за местоположението на номера остана само един.

Намиране на уникален кандидат на игралното поле

Разглежданият пример беше очевиден, тъй като на полето просто нямаше други числа. Намирането на уникален кандидат в определен пъзел не е лесно. Игралното поле на изображението по-долу ще служи като добър пример за обяснение на метода за решаване на судоку чрез търсене на уникален кандидат.

Въпреки че описанието на решението не изглежда просто, приложението му на практика не създава трудности. Винаги се търси уникален кандидат в определена област три на три. В това отношение играчът се интересува само от три вертикали и три хоризонтали на игралното поле. Всички останали се считат за незначителни и просто се изхвърлят. В примера е необходимо да се намери мястото на уникалния кандидат номер 7 за централен регион. Ъгловите квадрати на разглежданото поле са заети с числа, а числото 7 вече присъства в централния вертикал. Това означава, че единствените възможни квадратчета за поставяне на уникалния кандидат 7 са 1-ва и 3-та клетка от средния ред на " площ три по три".

Как да решите трудно судоку?

Всяка игра има 4 нива на трудност. Те се различават по броя на цифрите в първоначалната версия на полето. Колкото повече от тях, толкова по-лесно е да решите судоку. Както и в други игри, феновете организират състезания и цели шампионати по судоку.

Най-трудните опции за игра включват голям брой опции за попълване на всяка клетка. Понякога може да има максимално възможен брой - 8 или 9. В такива ситуации се препоръчва да запишете всички опции с молив по ръбовете и ъглите на клетката. Изброяването на всички комбинации с подробно проучване вече може да помогне за премахване на припокриващите се числа и намаляване на броя на вариациите за една клетка.

Стратегии за решаване на цветни пъзели

По-сложна версия на играта са судоку пъзели с цвят. Такива пъзели се считат за трудни поради въвеждането на допълнителни условия. Всъщност цветът е не само елемент на усложнение, но и вид намек, който не трябва да се пренебрегва при решаването. Това важи и за играта четно-нечетно.

Но цветът може да се използва и при решаване на обикновено судоку, отбелязвайки по-вероятните случаи на заместване. В горната снимка на пъзела числото 4 може да бъде поставено само в сини и оранжеви клетки, всички други опции очевидно са грешни. Изборът на тези области ще ви позволи да се отклоните от числото 4 и да преминете към търсене на други стойности, докато забравянето на клетките няма да работи напълно.

Судоку за деца

Може да звучи странно, но децата обичат да решават судоку. Играта развива много добре логиката и креативно мислене. Учените вече са доказали, че играта предотвратява смъртта на мозъчни клетки. Хората, които редовно решават пъзела, имат повече високо ниво I.Q.

За много малки деца, все още не познаване на числата, Разработени са варианти на судоку със символи. Гатанката е напълно семантично независима. Родителите определено трябва да научат децата си как да играят судоку, ако искат да развият логиката, концентрацията и мисленето на децата. Играта е полезна за поддържане на умствените способности на всяка възраст. Изследователите сравняват ефекта на пъзела върху човешкия мозък с ефекта упражнениеза развитие на мускулите. Психолозите твърдят, че судоку облекчава депресията и помага при лечението на деменция.

Добър ден на вас, скъпи любители на логическите игри. В тази статия искам да очертая основните методи, методи и принципи за решаване на судоку. Има много видове от този пъзел на нашия сайт и в бъдеще несъмнено ще бъдат представени още повече! Но тук ще разгледаме само класическата версия на судоку, като основна за всички останали. И всички трикове, описани в тази статия, ще бъдат приложими и за всички други видове судоку.

Самотник или последният герой.

И така, откъде започва решението за судоку? Няма значение дали е лесно или не. Но винаги в началото има търсене на очевидни клетки за запълване.

Фигурата показва пример за самотник - това е числото 4, което може безопасно да бъде поставено в клетка 2 8. Тъй като шестият и осмият хоризонтал, както и първият и третият вертикал, вече са заети от четири. Те са показани със стрелки. Зелен цвят. А в долния ляв малък квадрат имаме само една незаета позиция. Фигурата е маркирана в зелено на снимката. Останалите самотници също са поставени, но без стрели. Оцветени са в синьо. Може да има доста такива единични, особено ако има много цифри в първоначалното състояние.

Има три начина за търсене на необвързани:

• Самотник в квадрат 3 на 3.
• Хоризонтално
• Вертикално

Разбира се, можете произволно да преглеждате и идентифицирате сингли. Но е по-добре да се придържате към конкретна система. Най-очевидното би било да започнете с номер 1.

• 1.1 Проверете квадратите, където няма никой, проверете хоризонталите и вертикалите, които пресичат този квадрат. И ако вече има такива в тях, тогава напълно изключваме линията. Така търсим единственото възможно място.
• 1.2 След това проверете хоризонталните линии. В кое има единство и къде не. Проверяваме малки квадратчета, които включват тази хоризонтална линия. И ако в тях има единица, тогава изключваме празните клетки на този квадрат от възможните кандидати за желаното число. Ще проверим и всички вертикали и ще изключим тези, в които също има единство. Ако остане единственото възможно празно място, тогава поставяме желания номер. Ако останат два или повече празни кандидата, тогава напускаме тази хоризонтална линия и преминаваме към следващата.
• 1.3 Подобно на предишния параграф, проверяваме всички хоризонтални линии.

"Скрити единици"

Друга подобна техника се нарича "и кой, ако не аз ?!" Погледнете фигура 2. Нека работим с горния ляв малък квадрат. Нека първо преминем през първия алгоритъм. След това успяхме да разберем, че в клетка 3 1 има самотник - числото шест. Поставяме го, а във всички останали празни клетки поставяме с дребен шрифт всички възможни варианти, спрямо малкия квадрат.

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

гола двойка

Под тази концепция комбинирах няколко вида решения на судоку: гол чифт, три и четири. Това е направено във връзка с тяхната еднаквост и разлики само в броя на участващите числа и клетки.

И така, нека да разгледаме. Погледнете фигура 3. Тук записваме всички възможни опции по обичайния начин с дребен шрифт. И нека разгледаме по-отблизо горния среден малък квадрат. Тук в клетки 4 1, 5 1, 6 1 получихме поредица от еднакви числа - 1, 5, 7. Това е гола тройка в истинския й вид! Какво ни дава? И фактът, че тези три числа 1, 5, 7 ще бъдат разположени само в тези клетки.Така можем да изключим тези числа в средния горен квадрат на втория и третия хоризонтален ред. Също така в клетка 1 1 ще изключим седемте и веднага ще поставим четири. Тъй като няма други кандидати. И в клетка 8 1 ще изключим единицата, трябва да помислим допълнително за четирите и шестиците. Но това е друга история.

Трябва да се каже, че по-горе беше разгледан само частен случай на гола тройка. Всъщност може да има много комбинации от числа

• // три числа в три клетки.
• // всякакви комбинации.
• // всякакви комбинации.

скрита двойка

Този начин за решаване на судоку ще намали броя на кандидатите и ще даде живот на други стратегии. Вижте фигура 4. Горният среден квадрат е пълен с кандидати, както обикновено. Цифрите са изписани с дребен шрифт. в зеленомаркирани са две клетки - 4 1 и 7 1. Защо са забележителни за нас? Само в тези две клетки има кандидати 4 и 9. Това е нашата скрита двойка. от общо взетотова е същата двойка като в параграф три. Само в клетки има други кандидати. Тези други могат безопасно да бъдат изтрити от тези клетки.