Всё таки решить эту головоломку сможет почти каждый. Главное выбрать себе уровень сложности по плечу. Судоку интересная головоломка, хорошо занимающая сонный мозг и свободное время. В целом любой, кто пытался её решить, уже сумел выделить некоторые закономерности. Чем больше её решаешь, тем лучше начинаешь понимать принципы игры, но и тем больше хочется как-то улучшить свой способ решения. Со времени возникновения судоку люди разработали уже множество различных способов решения, какие-то проще, какие-то сложнее. Ниже приведён примерный набор базовых подсказок и несколько из наиболее простых методов решения судоку. Для начала определимся с терминологией.
Искушённые любители могут купить настольную версию судоку на ozon.ru
Синглы (единственные варианты) могут быть определены исключением цифр, уже присутствующих в рядах, колонках или областях. Следующие методы позволяют решить большинство «простых» вариантов судоку.
Поскольку эти пары обе находятся в третьей области (правой верхней), мы также можем исключить числа 1 и 4 из остальных клеток этой области.
Когда три клетки в одной группе не содержат иных кандидатов кроме трех, эти числа могут быть исключены из остальных клеток группы.
Обратите внимание: не обязательно, чтобы эти три клетки содержали все числа трио! Необходимо только чтобы эти клетки не содержали других кандидатов.
В этом ряду мы имеем трио 1,4,6 в клетках A, С и G, или двух кандидатов из этого трио. Эти три клетки будут обязательно содержать всех трех кандидатов. Поэтому они не могут быть в другом месте в этом рядом, и поэтому могут быть исключены из других клеток (E и F).
Аналогично для квартета, если четыре клетки не содержат иных кандидатов кроме как из одного квартета, эти числа могут быть исключены из других клеток этой группы. Как и для трио, клетки, содержащие квартет не обязаны содержать всех четырех кандидатов квартета.
Для очевидных групп кандидатов (предыдущий метод: 3.1) пары, трио и квартреты позволяли исключить кандидатов из других клеток группы.
В этом методе, скрытые группы кандидатов позволяют исключить других кандидатов из содержащих их клеток.
Если есть N клеток (2,3 или 4), содержащие N общих чисел (и они не встречаются в других клетках группы), тогда остальные кандидаты для этих клеток могут быть исключены.
В этом ряду пара (4,6) встречается только в клетках A и C.
Остальные кандидаты, таким образом, могут быть исключены из этих двух клеток, поскольку они должны содержать либо 4 либо 6 и никаких других.
Как и в случае очевидных трио и квартетов, клетки не обязаны содержать все числа из трио или квартера. Скрытые трио очень сложно рассмотреть. К счастью, они не часто используются для решения судоку.
Скрытые квартеты разглядеть практически невозможно!
Следующие методы не обязательно более сложные для понимания чем вышеописанные, но не так просто определить когда они должны применяться.
Этот метод может применяться к областям:
Как и в предыдущем примере, две колонки (B и C), где 9 может быть только в двух ячейках (B3 и B9, C2 и C8).
Поскольку B3 и C2, как и B9 и C8 находятся внутри одной области (а не в одном ряду, как в предыдущем примере), 9 может быть исключена из остальных клеток этих двух областей.
Этот метод является более сложным вариантом предыдущего (4.1 Связанные пары).
Вы можете применить его когда один из кандидатов присутствует не более чем в трех рядах и во всех рядах они находятся в одних и тех же трех колонках.
Первое, с чем следовало бы определиться в методологии решения проблем, это вопрос собственно понимания того, чего мы достигаем и можем достигнуть в вопросах решения проблем. Понимание обычно мыслится как нечто само собой разумеющееся, и мы упускаем из виду тот момент, что понимание имеет определенную начальную точку отсчета понимания, лишь относительно которой мы можем говорить о том, что понимание действительно имеет место с определенного нами конкретного момента. Судоку здесь, в нашем рассмотрении, удобна тем, что позволяет на ее примере в некоторой мере смоделировать вопросы понимания и решения проблем. Однако начнем мы с несколько иных и не менее важных, чем судоку, примеров.
Физик, изучающий специальную теорию относительности, может говорить о "кристально ясных" положениях Эйнштейна. Такое словосочетание мне встретилось на одном из сайтов в интернете. Но с чего начинается это понимание "кристальной ясности". Оно начинается с усвоение математической записи постулатов, из которых могут строиться по известным и понятным правилам все многоэтажные математические конструкции СТО. Но чего не понимает физик, как и я, это почему работают постулаты СТО именно так, а не иначе.
Прежде всего, подавляющее большинство обсуждающих это учение не понимают, что именно заключается в постулате постоянства скорости света в переложении из математического его применения на реальность. А этот постулат подразумевает постоянство скорости света во всех мыслимых и не мыслимых смыслах. Скорость света постоянна относительно любых покоящихся и движущих объектов разом. Скорость луча света, согласно постулату, постоянна даже относительно встречного, поперечного и удаляющегося луча света. А, при этом, реально мы имеем лишь замеры, косвенно связанные со скоростью света, интерпретируемые как ее постоянство.
Законы Ньютона для физика и даже для просто изучающих физику столь привычны, что представляются настолько понятными, как нечто само собой разумеющееся и иного быть не может. Но, скажем, применение закона всемирного тяготения начинается с его математической записи, по которой можно рассчитать даже траектории космических объектов и характеристики орбит. Но почему эти законы работают именно так, а не иначе – такого понимания у нас нет.
Аналогично и судоку. В интернете можно найти многократно повторяющиеся описания "базовых" способов решения задач судоку. Если запомнить эти правила, то можно понимать как решается та или иная задача судоку посредством применения "базовых" правил. Но у меня вопрос: а понимаем ли мы, почему эти "базовые" способы срабатывают именно так, а не иначе.
Итак, мы переходим к следующему ключевому положению в методологии решения проблем. Понимание возможно только на основе какой-то модели, предоставляющей базу для этого понимания и возможность произвести некоторый натурный или мысленный эксперимент. Без этого мы можем иметь лишь правила применения заученных исходных положений: постулатов СТО, законов Ньютона или "базовых" способов в судоку.
У нас нет и в принципе не может быть моделей, удовлетворяющих постулату ничем не ограничиваемого постоянства скорости света. У нас нет, но могут быть придуманы недоказуемые модели, согласующиеся с законами Ньютона. И такие "ньютоновские" модели есть, но они как-то не впечатляют продуктивными возможностями для проведения натурного или мысленного эксперимента. Зато судоку предоставляет нам такие возможности, которые мы можем использовать и для понимания собственно задач судоку, и для иллюстрации моделирования, как общего подхода в решении проблем.
Одна из возможных моделей задач судоку – это рабочая таблица. Создается она простым заполнением всех пустых клеток (ячеек) заданной в задаче таблицы числами 123456789. Далее задача сводится к последовательному удалению всех лишних цифр из ячеек до тех пор, пока все клетки таблицы будут заполнены единичными (эксклюзивными) цифрами, удовлетворяющими условию задачи.
Я создаю такую рабочую таблицу в Excel. Сначала выделяю все пустые ячейки (клетки) таблицы. Нажимаю F5-"Выделить"-"Пустые ячейки"-"OK". Более общий способ выделения нужных ячеек: удерживаю Ctrl и кликом мышки выделяю эти ячейки. Затем для выделенных ячеек устанавливаю синий цвет, размер 10 (исходный – 12) и шрифт Arial Narrow. Это все для того, чтобы хорошо просматривались последующие изменения в таблице. Далее я ввожу в пустые клетки числа 123456789. Делаю это следующим образом: записываю и сохраняю это число в отдельной ячейке. Затем нажимаю на F2, выделяю и копирую это число операцией Ctrl+C. Далее перехожу к ячейкам таблицы и, последовательно обходя все пустые ячейки, ввожу в них число 123456789 операцией Ctrl+V, и рабочая таблица готова.
Лишние цифры, о которых будет речь далее, я удаляю следующим образом. Операцией Ctrl+клик мышкой - выделяю ячейки с лишней цифрой. Затем нажимаю Ctrl+H и в верхнее поле открывшегося окошка ввожу удаляемую цифру, а нижнее поле должно быть совершенно пустым. Далее остается щелкнуть по опции "Заменить все" и лишняя цифра удалена.
Судя по тому, что мне обычно удается сделать более продвинутую обработку таблиц обычными "базовыми" способами, чем в примерах, приводимых в интернете, рабочая таблица является наиболее простым инструментом в решении задач судоку. Более того, многие ситуации, касающиеся применения наиболее сложных из так называемых "базовых" правил, у меня в рабочей таблице попросту не возникали.
В то же время, рабочая таблица – это и модель, на которой можно провести эксперименты с последующим выявлением всех "базовых" правил и разных нюансов их применения, вытекающего из экспериментов.
Итак, перед вами фрагмент рабочей таблицы с девятью блоками, нумеруемыми слева-направо и сверху-вниз. В данном случае у нас заполнен цифрами 123456789 четвертый блок. Это и есть наша модель. Вне блока красным цветом мы выделили "активированные" (окончательно определенные) цифры, в данном случае четверки, которые намерены подставить в оформляемую таблицу. Голубые пятерки – это пока не определенные относительно их дальнейшей роли цифры, о которых после поговорим. Назначенные нами активированные цифры как бы вычеркивают, выталкивают, удаляют – в общем, вытесняют одноименные цифры в блоке, поэтому там они представлены бледным цветом, символизирующим тот факт, что эти бледные цифры удалены. Хотел было сделать этот цвет еще бледнее, но тогда они могли бы стать вообще не заметными при просмотре в интернете.
В итоге в четвертом блоке в ячейке E5 оказалась одна, тоже активированная, но скрытая четверка. "Активированная" потому, что она, в свою очередь тоже может удалять лишние цифры, если таковые окажутся на ее пути, а "скрытая" потому, что она находится среди других цифр. Если ячейку E5 атаковать остальными, кроме 4, активированными цифрами 12356789, то в E5 возникнет "голая" одиночка – 4.
Теперь уберем одну активированную четверку, например из F7. Тогда четверка в заполненном блоке может оказаться уже и только в ячейке E5 или F5, оставаясь при этом активированной в строке 5. Если к этой ситуации привлечь активированные пятерки, без F7=4 и F8=5, то в ячейках E5 и F5 возникнет голая или скрытая активированная пара 45.
После того как вы в достаточной мере отработаете и осмыслите разные варианты с голыми и скрытыми одиночками, двойками, тройками и т.д. не только в блоках, но и в строках и столбцах, мы можем перейти к еще одному эксперименту. Создадим голую пару 45, как было сделано раньше, а потом подключим активированные F7=4 и F8=5. В результате возникнет ситуация E5=45. Подобные ситуация очень часто возникает в процессе обработки рабочей таблицы. Такая ситуация означает, что одна из этих цифр, в данном случае 4 или 5, обязательно должна находиться в блоке, строке и столбце, включающих в себя ячейку E5, потому что во всех этих случаях должны присутствовать две цифры, а не одна из них.
А главное, мы теперь уже знаем, каким образом возникают часто встречающиеся ситуации, подобные E5=45. Подобным же образом определимся с ситуациями, когда в одной ячейке возникает тройка цифр и т.п. И когда мы доведем степень осмысления и восприятия этих ситуаций до состояния самоочевидности и простоты, тогда следующий шаг – это уже, так сказать, научное осмысление ситуаций: мы тогда сможем делать статистический анализ таблиц судоку, выявлять закономерности и использовать наработанный материал для решения самых сложнейших задач.
Таким образом, экспериментируя на модели, мы получаем наглядное и даже "научное" представление относительно скрытых или открытых одиночек, пар, троек и т.д. Если вы ограничитесь только операциями с описанной простой моделью, то некоторые ваши представления окажутся неточными или даже ошибочными. Однако как только вы перейдете к решению конкретных задач, то неточности первоначальных представлений быстро выявятся, ну а модели, на которых проводились эксперименты, придется переосмыслить и уточнить. Таков неизбежный путь гипотез и уточнений в решении любых проблем.
Надо сказать, что скрытые и открытые одиночки, а также открытые пары, тройки и даже четверки, – это обычные ситуации, возникающие при решении задач судоку с рабочей таблицей. Скрытые пары случались редко. А вот скрытые тройки, четверки и т.д. мне при обработке рабочих таблиц как-то не попадались, так же, как и многократно описанные в интернете методы обхода контуров "x-wing" и "рыба-меч", при которых возникают "кандидаты" на удаление при любом из двух альтернативных способов обхода контуров. Смысл этих способов: если уничтожаем "кандидата" х1, то остается эксклюзивный кандидат х2 и при этом удаляется кандидат х3, а если уничтожаем х2, то остается эксклюзивный х1, но и в этом случае удаляется кандидат х3, так что в любом случае следует удалить х3, не затрагивая пока кандидатов х1 и х2. В более общем плане, это частный случай ситуации: если два альтернативных способа приводят к одному и тому же результату, то этот результат может использоваться для решения задачи судоку. В таком, более общем, плане ситуации мне встречались, но не в варианте "x-wing" и "рыба-меч" и не при решении задач судоку, для которых достаточно знания лишь "базовых" подходов.
Особенности применения рабочей таблицы можно показать на следующем нетривиальном примере. На одном из форумов решателей судоку http://zforum.net/index.php?topic=3955.25;wap2 мне встретилась задача, представленная как одна из сложнейших задач судоку, не решаемая обычными способами, без применения перебора с допущениями относительно подставляемых в ячейки цифр. Покажем, что с рабочей таблицей можно решить эту задачу без подобного перебора:
Справа исходная задача, слева рабочая таблица после "вычеркивания", т.е. рутинной операции удаления лишних цифр.
Сначала договоримся об обозначениях. ABC4=689 означает, что в ячейках A4, B4 и C4 находятся цифры 6, 8 и 9 – по одной или по несколько цифр на ячейку. Со строками аналогично. Так, B56=24 означает, что в ячейках В5 и В6 находятся цифры 2 и 4. Знак ">" – это знак обусловленного действия. Так, D4=5>I4-37 означает, что вследствие сообщения D4=5 следует поместить число 37 в ячейку I4. Сообщение может быть явным – "голым" – и скрытым, которое следует выявить. Воздействие сообщения может быть последовательным (передаваться опосредованно) по цепочке и параллельным (воздействовать непосредственно на другие ячейки). Например:
D3=2; D8=1>A9-1>A2-2>A3-4,G9-3; (D8=1)+(G9=3)>G8-7>G7-1>G5-5
Эта запись означает, что D3=2, но этот факт нужно выявить. D8=1 передает A3 свое воздействие по цепочке и в A3 следует записать 4; одновременно D3=2 воздействует непосредственно на G9, что приводит к результату G9-3. (D8=1)+(G9=3)>G8-7 – совместное воздействие факторов (D8=1) и (G9=3) приводит к результату G8-7. И т.п.
В записях может также встретиться сочетание типа H56/68. Оно означает, что в ячейках H5 и H6 запрещены цифры 6 и 8, т.е. их следует из этих ячеек удалить.
Итак, начинаем работу с таблицей и для начала применяем хорошо проявленное, заметное условие ABC4=689. Это означает, что во всех остальных (кроме A4, B4 и C4) ячейках блока 4 (средний, левый) и 4-й строки должны быть удалены цифры 6, 8 и 9:
Аналогичным образом применяем B56=24. В совокупности имеем D4=5 и (после D4=5>I4-37) HI4=37, а также (после B56=24>C6-1) C6=1. Применим это к рабочей таблице:
В I89=68скрытая>I56/68>H56-68: т.е. в ячейках I8 и I9 находится скрытая пара цифр 5 и 6, которая запрещает нахождение этих цифр в I56, что приводит к результату H56-68. Этот фрагмент мы можем рассмотреть по другому, подобно тому, как это делали в экспериментах на модели рабочей таблицы: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. То есть, двусторонняя "атака" (G23=68) и (AD7=68) приводит к тому, что в I8 и I9 могут находиться только цифры 6 и 8. Далее (I89=68) подключается к "атаке" на H56 совместно с предыдущими условиями, что и приводит к H56-68. Дополнительно к этой "атаке" подключается (ABC4=689), что в данном примере выглядит излишним, однако если бы мы работали без рабочей таблицы, то фактор воздействия (ABC4=689) оказался бы скрытым, и вполне уместным было бы обратить на него внимание специально.
Следующее действие: I5=2>G1-2,G6-9,B6-4,B5-2.
Надеюсь, оно уже понятно без комментариев: подставляйте цифры, которые стоят после тире, не ошибетесь:
H7=9>I7-4; D6=8>D1-4,H6-6>H5-8:
Следующая серия действий:
D3=2; D8=1>A9-1>A2-2>A3-4,G9-3;
(D8=1)+(G9=3)>G8-7>G7-1>G5-5;
D5=9>E5-6>F5-4:
I=4>C9-4>C7-2>E9-2>EF7-35>B7-7,F89-89,
то есть, в результате "вычеркивания" – удаления лишних цифр – в ячейках F8 и F9 возникает открытая, "голая" пара 89, которую, вместе с другими результатами, указанными в записи, применяем к таблице:
H2=4>H3-1>F2-1>F1-6>A1-3>B8-3,C8-5,H1-7>I2-5>I3-3>I4-7>H4-3
Их результат:
Затем следуют довольно рутинные, очевидные действия:
H1=7>C1-8>E1-5>F3-7>E2-9>E3-8,C3-9>B3-5>B2-6>C2-7>C4-6>A4-9>B4-8;
B2=6>B9-9>A8-6>I8-8>F8-9>F9-8>I9-6;
E7=3>F7-5,E6-7>F6-3
Их результат: окончательное решение задачи:
Так или иначе, будем считать, что с "базовыми" способами в судоку или в иных областях интеллектуального приложения мы разобрались на основе подходящей для этого модели и даже научились их применять. Но это лишь часть нашего продвижения в методологии решения проблем. Далее, повторюсь, следует не всегда учитываемый, но непременный этап доведения предварительно усвоенных способов до состояния простоты их применения. Решение примеров, осмысливание результатов и способов этого решения, переосмысливание этого материала на основе принятой модели, снова продумывание всех вариантов с доведением степени их понимания до автоматизма, когда решение с применением "базовых" положений становится рутинных и исчезает как проблема. Что это дает: это каждый должен прочувствовать на своем опыте. А суть в том, что когда проблемная ситуация становится рутинной, то поисковый механизм интеллекта направляется к освоению все более сложных положений в области решаемых проблем.
А что такое "более сложные положения"? Это всего лишь новые "базовые" положения в решении проблемы, понимание которых, в свою очередь, тоже можно довести до состояния простоты, если найти для этой цели подходящую модель.
В статье Василенко С.Л. "Числовая гармония Судоку" я нахожу пример задачи с 18 симметричными ключами:
Относительно этой задачи утверждается, что она может быть решена с применением "базовых" приемов только до некоторого состояния, после достижения которого остается лишь применить простой перебор с пробной подстановкой в ячейки некоторых предполагаемых эксклюзивных (единичных, одиночных) цифр. Это состояние (продвинутое чуть далее, чем в примере Василенко) имеет вид:
Такая модель есть. Это своеобразный механизм вращения выявленных и не выявленных эксклюзивных (единичных) цифр. В простейшем случае, некоторая тройка эксклюзивных цифр вращается в правом или левом направлении, переходя этой группой от строки к строке или от столбца к столбцу. В целом же, при этом вращаются в каком-то одном направлении три группы троек цифр. В более сложных случаях, три пары эксклюзивных цифр вращается в одном направлении, а тройка одиночек вращается в противоположном направлении. Так, например, происходит вращение эксклюзивных цифр в первых трех строках рассматриваемой задачи. И, что самое здесь важное, это своеобразное вращение можно заметить, рассматривая расположение цифр в обработанной рабочей таблице. Этих сведений пока достаточно, а другие нюансы модели вращения мы поймем в процессе решения задачи.
Итак, в первых (верхних) трех строках (1, 2 и3) мы можем заметить вращение пар (3+8) и (7+9), а также (2+х1) с неизвестным х1 и тройка одиночек (х2+4+1) с неизвестным х2. При этом, мы можем обнаружить, что каждое из х1 и х2 могут быть либо 5, либо 6.
В строках 4, 5 и 6 просматриваются пары (2+4) и (1+3). Должна быть также 3-я неизвестная пара и тройка одиночек из которых известна лишь одна цифра 5.
Аналогичным образом просматриваем строки 789, затем тройки столбцов ABC, DEF и GHI. Собранную информацию мы запишем в символическом и, надеюсь, достаточно понятном виде:
Пока нам эта информация нужна только для понимания общей ситуации. Тщательно продумайте ее и тогда мы сможем далее продвинуться вперед к следующей специально подготовленной для этого таблице:
Цветами я выделил альтернативные варианты. Голубой цвет означает "разрешено", а желтый – "запрещено". Если, скажем, разрешено в A2=79 разрешено A2=7, то C2=7 – запрещено. Или наоборот – разрешено A2=9, запрещено C2=9. А далее разрешения и запрещения передаются по логической цепочке. Такая расцветка сделана для того, чтобы было проще просматривать разные альтернативные варианты. В общем, это некоторая аналогия упомянутым ранее способов "x-wing" и "рыба-меч" при обработке таблиц.
Просматривая вариант B6=7 и, соответственно, B7=9, мы можем обнаружить сразу два момента, несовместимых с этим вариантом. Если B7=9, то в строках 789 возникает синхронно вращающаяся тройка, что недопустимо, так как синхронно (в одном направлении) могут вращаться либо только три пары (и три одиночки асинхронно им), либо три тройки (без одиночек). Кроме этого, если B7=9, то через несколько шагов обработки рабочей таблицы в 7-й строке обнаружим несовместимость: B7=D7=9. Так что подставляем единственно приемлемый из двух альтернативных вариант B6=9, и далее задача решается простыми средствами обычной обработки без всякого слепого перебора:
Далее, у меня есть готовый пример с применением модели вращения для решения задачи из чемпионата мира по судоку, но этот пример я опускаю, чтобы слишком уж не растягивать данную статью. К тому же, как оказалось, эта задача имеет три варианта решения, что плохо подходит для первоначального освоения модели вращения цифр. Еще я изрядно "попыхтел" над вытащенной из интернета задачей Гэри МакГайра с 17 ключами для решения его головоломки, пока с еще более изрядным раздражением не выяснил, что эта "головоломка" имеет более 9 тысяч вариантов решения.
Итак, волей-неволей, приходится переходить к разработанной Арто Инкала "самой сложной в мире" задаче судоку, имеющей, как известно, единственное решение.
После внесения двух вполне очевидных эксклюзивных цифр и обработки рабочей таблицы, задача имеет следующий вид:
Черным и более крупным шрифтом выделены ключи, заданные исходной задаче. Чтобы продвинуться в решении этой задачи, мы снова должны опереться на адекватную, подходящую для этой цели модель. Модель эта – своеобразный механизм вращения цифр. Она уже не однажды обсуждалась в этой и предыдущих статьях, но чтобы понять дальнейший материал статьи, этот механизм следует продумать и проработать в деталях. Примерно так, как если бы вы поработали с таким механизмом эдак с десяток лет. Но вы все равно сможете понять этот материал если не с первого чтения, то со второго или третьего и т.д. Более того, если проявите настойчивость, то и этот "сложный для понимания" материал вы доведете до состояния его рутинности и простоты. Нового в этом плане здесь ничего нет: то, что сначала очень сложно, постепенно становится не так уж сложным, а при дальнейшей непрекращающейся проработке все самым очевидным и не требующих умственных усилий становится на свои подобающие места, после чего вы можете освободить свой умственный потенциал для дальнейшего продвижения вперед по данной решаемой проблеме или относительно других проблем.
При внимательном анализе структуры задачи Арто Инкала можно заметить, что вся она построена по принципу трех синхронно вращающихся пар и тройки вращающихся асинхронно парам одиночек: (х1+х2)+(х3+х4)+(х5+х6)+(х7+х8+х9). Порядок вращения может быть, например, такой: в первых трех строках 123 первая пара (х1+х2) переходит из первой строки первого блока во вторую строку второго блока, затем в третью строку третьего блока. Вторая пара переходит из второй строки первого блока в третью строку второго блока, затем, в этом вращении, перепрыгивает в первую строку третьего блока. Третья пара из третьей строки первого блока перепрыгивает в первую строку второго блока и далее в этом же направлении вращения переходит во вторую строку третьего блока. Тройка одиночек движется в подобном режиме вращения, но в противоположном вращению пар. Ситуация со столбцами выглядит аналогично: если таблицу мысленно (или реально) повернуть на 90 градусов, то строки станут столбцами, с тем же, как ранее для строк, характером движения одиночек и пар.
Проворачивая в уме эти вращения применительно к задаче Арто Инкала, мы постепенно доходим до понимания очевидных ограничений на выбор вариантов этого вращения для выбранной тройки строк или столбцов:
Не должно быть синхронно (в одном направлении) вращающихся троек и пар – такие тройки, в отличие от тройки одиночек, будем в дальнейшем называть триплетами;
Не должно быть асинхронных между собой пар или асинхронных между собой одиночек;
Не должно быть вращающихся в одном (например, в правом) направлении и пар и одиночек – это повторение предыдущих ограничений, но может быть оно покажется более понятным.
Кроме этого есть и другие ограничения:
Не должно быть ни одной пары в 9-ти строках, совпадающей с парой в каком-либо из столбцов и то же самое относительно столбцов и строк. Это должно быть очевидным: потому что сам факт расположения двух цифр в одной строке свидетельствует о том, что они находятся в разных столбцах.
Еще можно сказать, что очень редко бывают совпадения пар в разных тройках строк или подобное совпадение в тройках столбцов, а также редко бывают совпадения троек одиночек в строках и/или столбцах, но это уже, так сказать, вероятностные закономерности.
Исследование блоков 4,5,6.
В блоках 4-6 возможны пары (3+7) и (3+9). Если принять (3+9), то получится недопустимое синхронное вращение триплета (3+7+9), так что имеем пару (7+3). После подстановки этой пары и последующей обработки таблицы обычными средствами получим:
При этом мы можем сказать, что 5 в B6=5 может быть лишь одиночкой, асинхронной (7+3), а 6 в I5=6 является параобразующей, так как она находится в одной строке H5=5 в шестом блоке и, следовательно, она не может быть одиночкой и может двигаться лишь синхронно с (7+3.
и расположил кандидатов на одиночки по количеству появления их в этой роли в данной таблице:
Если принять, что наиболее частотные 2, 4 и 5 и есть одиночки, то по правилам вращения с ними могут сочетаться только пары: (7+3), (9+6) и (1+8) - пара (1+9) отброшена, так как она отрицает пару (9+6). Далее после подстановки этих пар и одиночек и дальнейшей обработки таблицы обычными методами получим:
Вот такая непокорная таблица оказалась – не желает обрабатываться до конца.
Придется поднапрячься и заметить, что в столбцах ABC есть пара (7+4) и что 6 перемещается синхронно 7 в этих столбцах, поэтому 6 – параобразующая, так что в столбце "C" 4-го блока возможно лишь сочетания (6+3)+8 либо (6+8)+3. Первое из этих сочетаний не проходит, так как тогда в 7-м блоке в столбце "B" возникнет недопустимая синхронная тройка – триплет (6+3+8). Ну а далее, после подстановки варианта (6+8)+3 и обработки таблицы обычным способом приходим к благополучному завершению задачи.
Второй вариант: вернемся к таблице, полученной после выявления сочетания (7+3)+5 в строках 456 и перейдем к исследованию столбцов ABC.
Здесь мы можем заметить, что пара (2+9) не может иметь место в ABC. Другие комбинации (2+4), (2+7), (9+4) и (9+7) дают синхронную тройку - триплет в A4+A5+A6 и B1+B2+B3, что неприемлемо. Остается одна приемлемая пара (7+4). Причем 6 и 5 двигаются синхронно 7, значит они параобразующие, т.е. образуют какие-то пары, но не 5+6.
Составим список возможных пар и их сочетаний с одиночками:
Сочетание (6+3)+8 не проходит, т.к. иначе образуется недопустимая тройка-триплет в одном столбце (6+3+8), о чем уже говорили и в чем можем убедиться еще раз, проверив все варианты. Из кандидатов на одиночки больше всех очков набирает цифра 3, а наиболее вероятное из всех приведенных сочетаний: (6+8)+3, т.е. (С4=6 + C5=8) + C6=3, что дает:
Далее самый вероятный кандидат на одиночку либо 2, либо 9 (по 6 баллов), однако в любом из этих случаев остается в силе кандидат 1 (4 балла). Начнем с (5+29)+1, где 1 асинхронно 5, т.е. поставим 1 из В5=1 в качестве асинхронной одиночки во все столбцы ABC:
В блоке 7, столбец A, возможны лишь варианты (5+9)+3 и (5+2)+3. Но мы лучше обратим внимание на то, что в строках 1-3 теперь проявились пары (4+5) и (8+9). Их подстановка приводит к быстрому результату, т.е. к завершению задачи после обработки таблицы обычными средствами.
Ну а теперь, потренировавшись на предыдущих вариантах, мы можем попробовать решить задачу Арто Инкала без привлечения статистических оценок.
Снова возвращаемся в исходное положение:
В блоках 4-6 возможны пары (3+7) и (3+9). Если принять (3+9), то получится недопустимое синхронное вращение триплета (3+7+9), так что для подстановки в таблицу имеем только вариант (7+3):
5 здесь, как мы видим, одиночка, 6 – параобразующая. Допустимые варианты в ABC5: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. Но (2+1) асинхронна (7+3), поэтому остаются (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. В любом случае 1 является синхронной (7+3) и, следовательно, параобразующей. Подставим 1 в этом качестве в таблицу:
Цифра 6 здесь является параобразующей в бл. 4-6, но бросающейся в глаза пары (6+4) нет в списке допустимых пар. Следовательно четверка в A4=4 асинхронна 6:
Так как D4+E4=(8+1) и согласно анализу вращения образует эту пару, то получаем:
Если ячейки C456=(6+3)+8, то B789=683, т.е. получится синхронная тройка-триплет, так что остается вариант (6+8)+3 и результат его подстановки:
B2=3 здесь одиночка, С1=5 (асинхронная 3) - параобразующая, A2=8 - также параобразующая. В3=7 может быть и синхронной и асинхронной. Теперь мы можем проявить себя и на более сложных приемах. Натренированным взглядом (или хотя бы при проверке на компьютере) мы видим, что при любом статусе В3=7 – синхронном или асинхронном – мы получаем один и тот же результат A1=1. Следовательно, мы можем подставить это значение в A1 и далее уже более обычными простыми средствами завершить нашу, вернее Арто Инкала, задачу:
Так или иначе, мы смогли рассмотреть и даже проиллюстрировать три общих подхода на пути решения проблем: определить точку понимания проблемы (не предположительный или слепо декларируемый, а реальный момент, начиная с которого мы можем говорить о понимании проблемы), выбрать модель, позволяющую реализовать понимание посредством натурного или мысленного эксперимента и – это в-третьих – довести степень понимания и восприятия достигнутых при этом результатов до состояния самоочевидности и простоты. Есть еще и четвертый подход, который применяю лично я.
У каждого человека случаются состояния, когда стоящие перед ним интеллектуальные задачи и проблемы решаются более легко, чем это бывает обычно. Эти состояния вполне можно воспроизводить. Для этого надо овладеть техникой отключения мыслей. Сначала хотя бы на доли секунды, затем, все более растягивая этот отключающий момент. Далее рассказывать, вернее рекомендовать, что-то в этом отношении не могу, потому что продолжительность применения этого метода дело сугубо личное. Но я прибегаю к этому способу порой надолго, когда передо мной встает проблема, к которой я не вижу вариантов того, как к ней можно подступиться и решить. В результате, раньше или позже из кладовых памяти выплывает подходящий прообраз модели, которая проясняет суть того, что требуется разрешить.
Задачу Инкала я решил несколькими способами, в том числе описанными в предыдущих статьях. И всегда в той или иной мере использовал этот четвертый подход с отключением и последующей концентрацией умственных усилий. Самое быстрое решение задачи я получил простым перебором – что называется "методом тыка" – правда, с использованием лишь "длинных" вариантов: тех, что могли быстро привести к выходу на положительный или отрицательный результат. Другие варианты отымали у меня больше времени, потому что основное время уходило на хотя бы черновую отработку технологии применения этих вариантов.
Хороший также вариант в духе четвертого подхода: настраиваться на решение задач судоку, подставляя лишь по единственной цифре в ячейку в процессе решения задачи. То есть, большая часть задачи и ее данных "прокручиваются" в уме. Именно так и происходит основная часть процесса решения интеллектуальных проблем, и этот навык следует тренировать ради расширения своих возможностей в решении проблем. Я, например, не профессиональный решатель судоку. У меня иные задачи. Но, тем не менее, хочу поставить перед собой такую цель: обрести умение решать задачи судоку повышенной сложности, без рабочей таблицы и не прибегая к подстановке более одной цифры в одну пустую клетку. При этом допускается любой способ решения судоку, включая и простой перебор вариантов.
О переборе вариантов я вспоминаю здесь не случайно. Любой подход к решению задач судоку предполагает в своем арсенале набор определенных способов, включая тот или иной вид перебора. При этом любой из способов, применяемых в судоку в частности или при решении любых других проблем, имеет свою область его эффективного применения. Так, при решении относительно простых задач судоку наиболее эффективны простые "базовые" способы, описанные в многочисленных статьях по этой теме в интернете, а более сложный "метод вращения" оказывается здесь зачастую бесполезным, потому что он лишь усложняет ход простого решения и при этом какой-то новой информации, проявляющейся в ходе решения задачи, не дает. Но в наиболее сложных случаях, как задача Арто Инкала, "метод вращения" может играть ключевую роль.
Судоку в моих статьях – лишь иллюстративный пример подходов к решению проблем. Среди решенных мною задач есть и на порядок посложнее, чем судоку. Например, расположенные на нашем сайте компьютерные модели работы котлов и турбин. О них я тоже был бы не против рассказать. Но пока я выбрал именно судоку, чтобы достаточно наглядным образом показать своим молодым согражданам возможные пути и этапы продвижения к конечной цели решаемых проблем.
На сегодня пока все.
Поле судоку представляет собой таблицу 9х9 клеток. В каждую клетку заносится цифра от 1 до 9. Цель игры: расположить цифры таким образом, чтобы в каждой строке, в каждом столбце и в каждом блоке 3х3 не было повторений. Другими словами, в каждом столбце, строке и блоке должны быть все цифры от 1 до 9.
Для решения задачи в пустые клетки можно записывать кандидатов. Например, рассмотрим клетку 2-го столбца 4-ой строки: в столбце, в котором она находится, уже имеются цифры 7 и 8, в строке - цифры 1, 6, 9 и 4, в блоке - 1, 2, 8 и 9. Следовательно, из кандидатов в данной ячейке вычеркиваем 1, 2, 4, 6, 7, 8, 9, и у нас остается только два возможных кандидата – 3 и 5.
Аналогично, рассматриваем возможных кандидатов для других ячеек и получаем следующую таблицу:
С кандидатами решать интереснее и можно применять различные логические методы. Далее мы рассмотрим некоторые из них.
Метод заключается в отыскании в таблице одиночек, т.е. ячеек, в которых возможна только одна цифра и никакая другая. Записываем эту цифру в данную ячейку и исключаем ее из других клеток этой строки, столбца и блока. Например: в данной таблице имеются три «одиночки» (они выделены желтым цветом).
Если в ячейке стоит несколько кандидатов, но один из них не встречается больше ни в одной другой ячейке данной строки (столбца или блока), то такой кандидат называется «скрытой одиночкой». В следующем примере кандидат «4» в зеленом блоке найден только в центральной ячейке. Значит, в этой ячейке обязательно будет «4». Заносим «4» в данную ячейку и вычеркиваем из других ячеек 2-го столбца и 5-ой строки. Аналогично, в желтом столбце кандидат «2» встречается один раз, следовательно, в данную ячейку заносим «2» и исключаем «2» из ячеек 7-ой строки и соответствующего блока.
Предыдущие два метода – это единственные методы, которые однозначно определяют содержимое ячейки. Следующие методы позволяют только уменьшать количество кандидатов в ячейках, что рано или поздно приведет к одиночкам или скрытым одиночкам.
Бывают случаи, когда кандидат в пределах блока находится только в одном строке (или в одном столбце). В силу того, что одна из этих ячеек обязательно будет содержать этого кандидата, из всех остальных ячеек данной строки (столбца) этого кандидата можно исключить.
В примере ниже, центральный блок содержит кандидата «2» только в центральном столбце (желтые ячейки). Значит, одна из этих двух ячеек точно должна быть «2», и никакие другие ячейки в том ряду вне этого блока не могут быть «2». Поэтому «2» может быть исключен как кандидат из других ячеек этого столбца (ячейки зеленого цвета).
Если две ячейки в группе (строке, столбце, блоке) содержат идентичную пару кандидатов и ничего более, то никакие другие ячейки этой группы не могут иметь значения этой пары. Эти 2 кандидата могут быть исключены из других ячеек в группе. В примере ниже, кандидаты «1» и «5» в колонках восемь и девять формируют Открытую Пару в пределах блока (желтые ячейки). Поэтому, так как одна из этих ячеек должна быть «1», а другая должны быть «5», кандидаты «1» и «5» исключаем из всех других ячеек этого блока (зеленые ячейки).
Тоже самое можно сформулировать для 3 и 4-х кандидатов, только участвует уже 3 и 4 ячейки, соответственно. Открытые тройки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета.
Открытые четверки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета.
Если в двух ячейках в группе (строке, столбце, блоке) содержат кандидаты, среди которых идентичная пара, не встречающаяся ни в одной другой ячейке данного блока, то никакие другие ячейки этой группы не могут иметь значения этой пары. Следовательно, все другие кандидаты этих двух ячеек могут быть исключены. В примере ниже, кандидаты «7» и «5» в центральной колонке находятся только в ячейках желтого цвета, значит, всех остальных кандидатов из этих ячеек можно исключить.
Аналогично, можно искать скрытые тройки и четверки.
Если значение имеет только два возможных местоположения в какой-то строке (столбце), то оно обязательно должно быть назначено в одну из этих ячеек. Если же существует еще одна строка (столбец), где этот же кандидат также может быть только в двух ячейках и столбцы (строки) этих ячеек совпадают, то ни одна другая ячейка этих столбцов (строк) не может содержать данную цифру. Рассмотрим пример:
В 4-ой и 5-ой строках цифра «2» может быть только в двух ячейка желтого цвета, при чем эти ячейки находятся в одинаковых столбцах. Следовательно, цифра «2» может быть записана только двумя способами: 1) если «2» записать в 5-ый столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 7-ым столбцом.
2) если «2» записать в 7-ой столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 5-ым столбцом.
Следовательно, 5-ый и 7-ой столбец обязательно будут иметь цифру «2» либо в 4-ой строке, либо в 5-ой. Тогда из других ячеек данных столбцов цифру «2» можно исключить (зеленые клетки).
Этот метод является вариацией метода .
Из правил головоломки следует, что если кандидат находится в трех строках и только в трех столбцах, то в других строках этого кандидата в этих столбцах можно исключить.
Алгоритм:
Эта же логика применима и в случае трех колонок, где кандидат ограничивается тремя строками.
Рассмотрим пример. В трех строчках (3, 5 и 7-ая) кандидат «5» встречается не более трех раз (ячейки выделены желтым цветом). При этом они принадлежат только трем столбцам: 3, 4 и 7-ому. Согласно методу «Рыба меч» из других ячеек этих столбцов кандидата «5» можно исключить (зеленые ячейки).
В примере, приведенном ниже, так же применяется метод «Рыба меч», но уже для случая трех колонок. Исключаем кандидата «1» из ячеек зеленого цвета.
«X-wing» и «Рыба меч» можно обобщить на случай четырех строк и четырех столбцов. Данный метод будет называться «Медуза».
Бывают ситуации, когда кандидат встречается только два раза в группе (в строке, столбце или блоке). Тогда искомая цифра обязательно будет в одном из них. Стратегия метода «Цвета» заключается в том, чтобы просматривать эту взаимосвязь с использованием двух цветов, например, желтого и зеленого. При этом решение может быть в клеточках только какого-то одного цвета.
Выделяем все взаимосвязанные цепочки и принимаем решение:
В следующем примере применим метод «Цвета» для ячеек с кандидатом «9». Начинаем раскрашивать с ячейки в левом верхнем блоке (2 строка, 2 столбец), закрасим ее в желтый цвет. В своем блоке она имеет только одного соседа с «9», закрасим его в зеленый цвет. Также у нее только один сосед в столбце, закрашиваем и его в зеленый цвет.
Аналогичным образом работаем с остальными ячейками, содержащими цифру «9». Получаем:
Кандидат «9» может быть либо только во всех желтых ячейках, либо во всех зеленых. В правом среднем блоке встретились две ячейки одинакового цвета, следовательно, зеленый цвет неверный, так как в данном блоке получается две «9», что недопустимо. Исключаем, «9» из всех зеленых клеток.
Еще один пример на метод «Цвета». Пометим парные ячейки для кандидата «6».
Клетка с «6» в верхнем центральном блоке (выделим сиреневым цветом) имеет двух разноцветных кандидатов:
«6» обязательно будет или в желтой или в зеленой клетке, следовательно, из этой сиреневой клетки «6» можно исключить.
История игры
Числовую структуру придумали в Швейцарии еще в XVIII веке, на ее основе в XX веке был разработан числовой кроссворд. Однако в США, где непосредственно была придумана игра, она не получила большого распространения, в отличие от Японии, где головоломка не только прижилась, но и получила большую популярность. Именно в Японии она и приобрела привычное название «Судоку», и затем распространилась по миру.
Правила игры
Кроссворд имеет простую структуру: задается матрица из 9 квадратов, называемых секторами. Эти квадраты располагаются по три в ряду и имеют размер 3х3 клетки. Матрица Судоку выглядит как квадрат, состоящий из 3 строк и 3 столбцов, которые делят его на 9 секторов, содержащих по 9 клеток каждый. Часть клеток заполнена цифрами – чем больше цифр известно, тем проще головоломка.
Цель игры
Нужно заполнить все пустые клетки, при этом есть всего 1 правило: цифры не должны повторяться. Каждый сектор, строка и столбец должны содержать цифры от 1 до 9 без повторений. Лучше заполнять пустые клетки карандашом: так будет проще внести изменения в случае ошибки или начать заново.
Методы решения
Рассмотрим простой вариант судоку. Например, в секторе или строке осталась всего 1 пустая клетка, – логично, что в нее надо вписать то число, которого нет в числовом ряду.
Далее стоит изучить строки и столбцы, в которых есть одинаковые цифры в 2 секторах. Поскольку числа не должны повторяться, то можно проверить, в каких клетках может располагаться та же цифра в 3 секторе. Зачастую там остается только 1 клетка, в которую как раз и нужно вписать цифру.
Таким образом, часть поля кроссворда заполнится. Затем можно приступать к изучению строк. Допустим, в строке есть 3 свободных клетки, вам понятно, какие цифры должны быть туда вписаны, но неизвестно, куда конкретно. Нужно попробовать подстановку. Часто бывают варианты, когда в 2 других клетках цифра не может располагаться, потому что либо она есть в соответствующем столбце, либо в секторе.
Сложные судоку
В сложных судоку эти методы работают только наполовину, наступает момент, когда совершенно невозможно определить, в какую клетку вписывать число. Тогда нужно сделать предположение и проверить его. Если в строке, столбце или секторе есть 2 клетки, в которые одинаково возможно вписать цифру, то нужно вписать ее карандашом и следовать логике заполнения дальше. Если ваше допущение неверно, то в какой-то момент кроссворд покажет ошибку, и возникнет повтор цифр. Тогда становится очевидным, что цифра должна находиться во второй клетке, нужно вернуться назад и исправить ошибку. Лучше в таком случае использовать цветной карандаш, чтобы было проще найти момент, с которого нужно решать кроссворд заново.
Маленький секрет
Проще и быстрее решать судоку, если первоначально наметить карандашом, какие цифры могут быть в каждой клетке. Тогда не придется каждый раз проверять все секторы, и в процессе заполнения сразу будут очевидны те клетки, в которых остался только 1 вариант допустимой цифры.
Судоку – это не только увлекательная игра, которая позволяет скоротать время, это головоломка, которая развивает логическое мышление, способность удерживать большой объем информации и внимательность к деталям.
СУДОКУ - это популярная игра - пазл, которая представляет собой головоломку с цифрами, одолеть которую можно только строя логические умозаключения. В названии Судоку в переводе с японского «су»— «цифра», а doku «доку»— «стоящая отдельно». Следовательно, «СУДОКУ» в приблизительном переводе означает «одиночная цифра».
Название "Sudoku" дало этой головоломке японское издательство Nicoli в 1984 году. Sudoku - это сокращение от "Suuji wa dokushin ni kagiru", что в переводе с японского означает "число должно быть единственным". Издательство Nikoli не только придумало звучное имя, но и впервые ввело симметрию в заданиях для своих головоломок. Название головоломке дал руководитель Nicoli - Кaji Maki. Весь мир принял это новое японское название, но в самой Японии головоломку называют "Nanpure". Nicoli зарегистрировало в своей стране слово "Sudoku" как торговую марку.
Родиной шахмат считается Индия, родиной футбола - Англия. У игры судоку (sudoku), быстро распространившейся по всему миру, родины как таковой нет. Прообразом судоку можно считать головоломку “Магический квадрат”, которая появилась Китае 2000 лет назад.
История судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707 - 1783).
В бумагах его архива, датированных 17 октября 1776 года, содержатся записи о том, как образовать магический квадрат с определенным числом ячеек, особенно 9, 16, 25 и 36. В другом документе, озаглавленном «Научное исследование новых разновидностей магического квадрата» Эйлер помещал в клетки латинские буквы (Латинский квадрат), позже он заполнил клетки греческими буквами и называл квадрат греко-латинским. Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов таким образом, чтобы не один из них не повторялся ни в одной строке и ни в одном столбце.
В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine. Автором головоломки был Гарвард Гарис из Индианы. Головоломку «Number Place» (в переводе на русский - "место числа") - это можно считать одним из первых выпусков современных судоку. В ней были добавлены блоки размером 3х3 клетки, что было важным усовершенствованием, так как позволило сделать головоломку более интересной. Он использовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 9х9 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 3х3.
Таким, образом, идея судоку пришла не из Японии, как думают многие, однако название игры действительно японское.
В Японии эта головоломка была опубликована компанией Nicoly Inc., крупным издателем сборников различных головоломок, в газете Monthly Nicolist в апреле 1984 года под заголовком «Число может использоваться только один раз». 12 ноября 2004 года газета The Times впервые на своих страницах опубликовала головоломку судоку. Эта публикация стала сенсацией, головоломка быстро распространилась по всей Британии, Австралии, Новой Зеландии; приобрела популярность и в США.
Итак, что же собой представляет судоку? В настоящее время появилось множество модернизаций для этого популярного вида головоломок, но классическая судоку представляет собой квадрат 9х9 клеток, разбитый на подквадраты со сторонами по 3 клетки каждый. Таким образом, общее игровое поле составляет 81 клетку. В приложении к моей работе я помещу разные виды судоку и варианты решений (их мне помогали решить родители).
Судоку различаются по уровню сложности в зависимости от размера квадрата:
Судоку бывают разных уровней:
У головоломок судоку всего одно правило. Необходимо заполнить свободные клетки так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3Х3 каждая цифра от 1 до 9 встречалась бы только 1 раз. Часть клеток в судоку уже заполнена цифрами, и вам остается заполнить остальные. Чем больше цифр стоит изначально, тем проще решить головоломку. Кстати, правильно составленная судоку имеет только одно решение.
Стратегия решения судоку включает в себя три этапа:
Лучший способ решения — записывать числа-кандидаты в вершине левого угла ячейки. После этого можно увидеть именно те числа, которые должны занимать данную ячейку. Играть в судоку нужно медленно, так как это расслабляющая игра. Некоторые головоломки можно решить за несколько минут, но на другие можно потратить часы или, в отдельных случаях, даже дни.
Математическая основа. Количество возможных комбинаций в судоку 9x9 составляет по расчётам Бертхама Фельгенхауэра 6 670 903 752 021 072 936 960.
