Язык решения проблем в среде судоку

Проблемы бывают большие и маленькие, но всегда есть в них то, чего требуется достигнуть при нехватке на момент существования проблемы достаточных и/или известных средств, позволяющих прийти к желаемому результату. Этот результат - поставленная цель.

 

Одним из средств достижения цели является язык, используемый при решении проблем. В большой науке, например в математике, разрабатывается свой особый специализированный язык, но не помешает иметь нам что-то подобное и для такой маленькой "науки", как судоку. Впрочем, и маленькая наука однажды может стать большой – такое случалось. Однако – ближе к теме.

 

Язык, если он адекватен решаемой проблеме, позволяет систематизировать знания в области решаемой проблемы оптимальным или наиболее рациональным путем. Язык, будучи хорошо усвоенным, оказывает полезное влияние на стиль мышления человека даже тогда, когда он решает проблемы уже иные, чем те, для которых разрабатывался специфический язык. Это, например, замечают программисты – язык, которым они пользуются при составлении программ, оказывает влияние на стиль их мышления во всех прочих ситуациях.

 

Внутренний язык, на котором человек решает свои проблемы, несколько, а порой существенно, отличается от языка, на котором он говорит. Внутренний язык, используемый при обработке информации, не содержит длинных слов – это ряды кратких символов, позволяющих их быстро внутренне обозреть. Если мы создадим для решения некоторых проблем свой символьный язык, то подсознание им воспользуется и будет применять его даже для решения иного вида проблем там, где новый язык окажется подходящим. А подходящим новый язык может оказаться потому, что так уж устроен наш интеллект – он абстрагируется от частностей, а затем применяет усвоенную абстрактную схему для других частностей, в чем-то сходных (по некоторому абстрактному, обобщенному смыслу) с задачами, что приходилось уже решать. Ну вот, таким примерно способом и достигается наполнение нашего сознательного, а также гораздо более обширного, подсознательного багажа, который мы беспрестанно эксплуатируем при решении своих текущих проблем.

 

Впрочем, я несколько заговорился. Хотя основная тема данного раздела связана с общей методологией решения проблем, но о судоку тоже ведь надо что-то сказать, иначе вы не станете читать данную статью, если задачи судоку вас интересуют больше, чем общие подходы к решению проблем.

 

Итак, что мы имеем вначале, когда смотрим на таблицу судоку? Мы имеем множество пустых клеток или ячеек и некоторое количество ячеек, содержащих какие-то цифры. Согласно условию задачи, такой эксклюзивной цифры, как в заполненной ячейке, не должно быть ни в блоке "квадратике", ни в строке, ни в столбце, содержащем подобную ячейку. Образно говоря, можно сказать, что заполненная ячейка перекрывает возможность для других ячеек иметь подобную эксклюзивную цифру. Если подобных перекрывающих ячеек несколько, то, в пределе, остается единственная ячейка, которая может содержать эту эксклюзивную цифру. Ну а далее нам остается только придумать как следует обозначить ячейки и их действия (воздействие на другие ячейки) символьным путем и – наш символьный язык будет готов! Здесь могут быть разные, удобные лично для вас варианты, но главное, чтобы записи на языке выглядели коротко и ясно. Тогда они примут удобный для сознания и подсознания алгоритмический вид.

 

Теперь перейдем для примера к конкретной таблице, взятой из списка экстремальных, т.е. очень сложных, судоку http://www.graycell.ru/sudoku.html.

 

 

Мы видим, что ячейки B4, C3 и G7, в каждой из которых есть цифра 3, перекрывают все строки и столбцы так, что остается единственная неперекрытая возможность, а именно: в ячейке A8 иметь цифру 3. Причем реализации полного перекрытия оказывает содействие уже заполненная ячейка A9, без чего трех перекрывающих ячеек оказалось бы маловато, чтобы ограничить единственную ячейку A8 с эксклюзивной, т.е. единственной, цифрой 3. Этот факт мы можем записать в символьном виде:

 

B4_C3_G7(3):P(A9)>A8-3

 

Символ "P", предваряемый двоеточием, означает действие перекрытия, "P(A9)" – перекрытие с помощью вспомогательного фактора A9, а символ ">" можно прочесть как "приводит к результату" или "обеспечивает результат", который в данном случае записывается A8-3, т.е. цифра 3 помещается в ячейку A8.

 

Поскольку в более общем случае адреса расположения объектов (в данном случае ячеек) и факторы перекрытия могут быть разные, то по мере решения задач, схема постепенно становится все более отработанной и абстрактной в нашем внутреннем (умозрительном) ее представлении и далее работает как общий алгоритм, подобный X+Y=Z, с которым справляется даже обычный калькулятор. А когда приведенная запись переходит на еще более высокий уровень абстракции, то она начинает работать применительно не только к судоку, но и даже ряда других задач, чему я мог бы привести примеры, но боюсь, что сие будет слишком громоздким для одной статьи. Ну а запись, по мере ее освоения можно сократить. Например, убрать не обязательные разделители "_", а также пояснения в скобках:

 

B4C3G7:P>A8-3

 

Ну а если ситуация представляется совсем уж простой, само собой разумеющейся, то достаточно ограничиться лишь записью, типа A8-3, что мы уже проделывали в предыдущих статьях, когда заполняли таблицы судоку. Кстати, и сейчас вы также заполняйте представленную выше таблицу после каждого описанного шага ее заполнения, иначе логика этого заполнения может оказаться непонятной.

 

Глядя на таблицу судоку, можно заметить некоторые особенности, которые желательно запомнить и держать в уме, чтобы оперировать с таблицей более осмысленно и эффективно. Обратите внимание на то, что ячейки B8, E8 и F8, содержащие цифры 8, 2, 1, находятся в одной строке и как бы вытесняют эти три цифры в три неперекрытые ячейки блока 9: H7, G9 и I9, а в перекрытых ячейках G8, H8, I8 могут, в результате, находиться лишь оставшиеся "незадействованными" цифры блока: 5, 6 и 9. Далее мы можем заметить, что ячейки I2 и I5 с цифрами 5 и 6 частично перекрывают ячейку I8, в которой до перекрытия могли потенциально находиться одна из трех цифр: 5, 6 или 9. Таким образом, цифры 5 и 6 как бы вытесняются или вычеркиваются из этой ячейки, оставляя в ней единственную цифру 9. Для большей точности нашего языка мы подобное несколько специфическое перекрытие обозначим не "P", как ранее, а "V" – "вытеснение", "вычеркивание", "удаление" и т.п. Тогда сей длинный абзац пояснений заменится записью:

 

B8_E8_F8=H7_G9_I9=821 G8_H8_I8=569 I2_I5:V(56)>I8(569)-9

 

"V(56)" – означает, что "вытеснение" производилось посредством цифр 5 и 6, а "I8(569)" информирует о том, что в ячейке I8 первоначально находились цифры 5, 6 и 9.

 

Эту запись, как и ранее, можно сократить несколькими способами. Например, так:

 

BEF8=H7GI9=821 GHI8=569 I2_I5:V(56)>I8(569)-9

 

Пояснения можно записать в ином месте, например I2_I5(56):V>I8(569)-9 вместо I2_I5:V(56), или вообще опустить, если таковые представляются излишними. Можно также записать пояснения отдельно от действий, например [C8_D8=47]. Здесь в квадратных скобках информация о том, что ячейки C8 и D8 содержат цифры 4 и 7 – то, что осталось после выяснения всех других цифр в 8-й строке. Конечно, мастер решения проблем должен подобные незначительные объемы информации держать в своей памяти, не отвлекаясь на подсказки, но можно, для начала, и записать эту подсказку. В результате получается такой достаточно очевидный в решении задачи фрагмент с эксклюзивным размещением цифр 4 и 7 в ячейках D8 и C8:

 

[C8_D8=47] D4(7):V>D8(47)-4 C8-7

 

Заполняя таким образом таблицу, мы, проделав записанные шаги, придем к следующему ее варианту:

 

 

Продолжить ее заполнение можно разными способами, но для разнообразия используем принцип вращения. Сначала обнаруживаем тот факт, что цифры 5_6_9, имеющиеся в трех нижних строках таблицы, не могут перемещаться по строкам тройками синхронно, так как 9 и 6 могут находиться лишь в разных строках 8-го блока. Таким образом, приходим к заключению, что вращение в трех нижних строках таблицы асинхронно, а это означает, что какие-то три пары цифр вращаются (перемещаются) синхронно, а отдельные три цифры – асинхронно этим трем парам. Иные варианты при асинхронном вращении не возможны.

 

Анализируя ситуацию таким образом, приходим к заключению, что 3_7 вращаются синхронно, а 8 – асинхронно. Эту информацию можно отобразить следующим образом:

 

[5_6_9 несинхронны; 3_7 синхронны; 8 асинхронна 3_7]

 

или несколько компактнее:

 

[5_6_9_ns; 3_7_s; 8_as_3_7]

 

Вследствие описанного вращения вариант H7=8 исключается и остаются варианты G9=8 и I9=8. Но вариант G9=8 перекрывается G5=8, так что приходим к результату I9-8. Что и запишем:

 

[5_6_9_ns; 3_7_s; 8_as_3_7]; 8_as_3_7+G5>I9-8

 

Сокращая дальнейшие записи (опуская квадратные скобки и т.п.) я привожу вариант окончания заполнения таблицы, который вы сможете разобрать самостоятельно, осмыслить его и даже переписать в более удачном для вашего восприятия виде:

 

G1>G9-1 H7-2 E9_F9=37 B9_C9=25 B9-2 C9-5

G1_H1+G9_H8>I4_I6=12>I1_I3=34 C3>I3-4 I1-3

CDEF1=6789+D459=796>D1-8 B3+C8=67>C1-9 E6>E-7 F-6

I1_B4_G7>H-3 F4_I3>G6-4 аналогично B6-9 A6-7 B2-7 G3-7

E1>F9-7 E9-3 F5-3 D2-3 D367=125+EF8=12>D7-5

DI6=12>CF8=58+C9=5>C6-8 F6-5 A3-8 C2-1 D6-2 D3-1

I6-1 I4-2 F3-2 C5-2 E6-5 B5-4 C7-4 B7-1 C4-6 A7-6

E2-4 F2-9 H3-9 G4-9 H4-5 A5-5 A4-1 E5-1 E4-8

E7-9 F7-8 G7-5 H8-6 H2-8 G2-6

 

Если что и не очень ясно в этой задаче, то следующий фрагмент ее решения поможет все понять.

 

В первой статье о судоку мы говорили о модели решения на основе рабочей таблицы. Суть, вкратце, заключается в том, что в пустые клетки таблицы первоначально вписываются числа 123456789, затем, используя исходно заполненные ячейки, вычеркиваем лишние цифры во всех блоках "квадратиках", строках и столбцах. Применительно к задаче, которую мы только что разбирали, рабочая таблица будет иметь следующий вид:

 

 

Здесь, в новой модели задачи, все оказывается столь просто для ее решения, что даже не удобно приводить такой пример, хотя и взят он из списка экстремальных судоку. Но приступим.

 

Первое действие, которое мы представим в символьном виде: "I8(9)", означает, что мы нашли эксклюзивную цифру 9 в ячейке I8 и далее должны вычеркнуть эту цифру из чисел в других ячейках, расположенных в блоке, строке и столбце, где находится ячейка с эксклюзивной цифрой. В данном случае единственная ячейка, имеющая эксклюзивную цифру 9, находится в блоке, что можно отобразить записью I8(9b). В более сложном, чем в данном примере, случае ячейка с эксклюзивной цифрой оказывается заполненной числом с несколькими цифрами, среди которых и скрыта эксклюзивная цифра, что выясняется лишь в результате внимательного просмотра таблицы, когда обнаруживается, что есть только единственная подобная ячейка в блоке, строке или в столбце. Итак: "I8(9b)" – нашли 9 в блоке и вычеркнули ее всюду в содержащих I8 блоке, строке и столбце. Если бы это нахождение случилось в строке или столбце, то записали бы "I8(9str)" или "I8(9stl)". Символы "b", "str" и stl"" не являются обязательными и используются лишь в качестве дополнительного ориентира, когда понимание того как произошло обнаружение эксклюзивной цифры представляет некоторую сложность.

 

Следующее действие GH8(56) или G8_H8(56str) понимается аналогично действию, описанному для случая с единственной эксклюзивной цифрой: нашли две ячейки с цифрами 5 и 6 в 8-й строке и вычеркнули их из этой строки – вы проделывайте у себя в таблице все описанные вычеркивания, иначе трудно будет уследить за смыслом описываемых действий. Далее следует простое действие G9(1), затем EF9(3):V>D8(34)-4, требующее некоторых пояснений: цифра 3 содержится лишь в ячейках E9 и F9, поэтому она "вычеркивает" 3 из D8, где до этого находились цифры 3 и 4. Действие "вычеркивания" отображается так же, как и было описано ранее в этой статье, т.е. сочетанием символов ":V>". Далее вы сможете разобраться самостоятельно, вычеркивая лишние цифры в ячейках, а я привожу весь алгоритм решения данной задачи на основе модели рабочей таблицы:

 

I8(9b) GH(56) G9(1) EF9(3):V>D8(34)-4 D8(4) DEF7(589) C8(7)

A8(3) B9(2) C9(5) G9(1) H7(2) I9(8) I3(4) I1(3) D1(8) C1(9)

E1(7) F1(6) D7(5) E9(3) GH4(59) G6(4) H6(3) E2(4b) F5(3b)

D2(3b) F2(9) F7(8) E4(8b) B6(9b) AE5(15) B5(4) C5(2) C26(18)

C4(6) A4(1) A5(5) C6(8) C2(1) B2(7) A3(8) G2(6) H3(9) H4(5)

I4(2) I6(1) D6(2) D3(1) E3(5)

 

Итак, мы теперь имеем два языка и два подхода в решении задач судоку. Первый подход, как и его язык, следует осваивать, заполняя (например, следуя моим записям) пустые клетки таблицы, а второй – напротив, удаляя лишние цифры из первоначально заполненных избыточным количеством цифр рабочих таблиц. Второй вариант проще первого, если эта рабочая таблица находится перед глазами, а первый вариант проще второго, когда такой таблицы перед вами нет. Два подхода позволяют посмотреть на решение задач в среде судоку с двух сторон. Аналогичным образом, подобный принцип рассмотрения ситуации с разных сторон, проиллюстрированный в среде судоку, ускоряет достижение желаемого результата при решении любых проблем.

 

Список и краткий обзор статей, касающихся судоку

Copyright © 2009 - 2022 Алгоритмист | Правовая информация
Сделано в JustCreative | Карта сайта
Яндекс.Метрика