Что же такое?

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

   Прообразом и основой игры служит хорошо известный еще древним математикам латинский, или магический, квадрат. Изучению его замечательных свойств немало внимания уделил швейцарский математик Леонард Эйлер, долгое время живший и работавший в России. Он выяснил, что в матрице размером 9х9 каждый ряд и каждую колонку можно заполнить цифрами от 1 до 9 в определенном порядке и без повторения. Гарнс воплотил старую идею в новую форму – матрицу размером 9х9 квадратных ячеек. Он придумал первые простейшие алгоритмы, позволявшие решить задачу, отыскав недостающие числа.

   В 1979 году журнал Dell Pencil Puzzles and Word Games впервые представил игру под названием Number Place (позже ее стали также называть Nanpure). Необычные головоломки, для решения которых требовалось, следуя определенной логике, правильно расставить по местам недостающие цифры, далеко не сразу стали повальным увлечением, хотя и показались многим интересными.

    Что же касается Японии, то она сыграла ключевую роль в распространении игры по всему миру. Слово «судоку» является буквальным переводом на японский язык словосочетания «number place» («су» – число, цифра; «доку» – позиция, место). Американский журнал попался на глаза японским издателям, и головоломка поразила их воображение. В 1986 году журнал Nikoli впервые опубликовал задачи судоку в Японии. Новая забава не могла не понравиться японским читателям, известным своей врожденной любовью к числам. Игра в дальнейшем была значительно усовершенствована, и вскоре судокумания охватила всю страну. Потребовалось еще полтора десятка лет, чтобы достоинства этой игры признали европейцы. В 2004 Судоку начали печатать английские газеты, оттуда судоку-мания нахлынула на Европу и в Австралию. Наконец, в 2005 эта головоломка триумфально вернулась в США, завершив свой "кругосветный тур". В настоящее время выдается множество специализированных журналов и сборников, книг и инструкций по их решению, много газет печатают Судоку вместе с кроссвордами и заданиями по шахматам.

Правила судоку

    Правила игры судоку очень простые. Игровое поле состоит из квадрата, размером 9х9, разделенного на меньшие квадраты (регионы) со стороной 3х3 клеточки. Таким образом, все поле насчитывает 81 ячейку. В некоторых из них уже в начале игры расположены числа (от 1 до 9). В зависимости от того, сколько ячеек уже заполнено, конкретную судоку можно отнести к легким или сложным.

Цель игры судоку

    Цель головоломки – необходимо заполнить свободные ячейки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3х3, каждая цифра встречалась только один раз. Правильная головоломка имеет одно решение.
В последнее время появились и другие - более сложные модификации, чем 9х9 ячеек кроссвордов. Существуют судоку с размерами 15х15 или даже 16x16 предназначенные для опытных игроков. Для детей используются судоку меньших размеров, например, 2х2.

Алгоритмы решения головоломки

    Алгоритм решения судоки несложный - повторяйте следующие логические шаги вплоть до полного решения головоломки. Прогрессируйте к более тяжелым шагам лишь тогда, когда более простые уже не помогают открывать новые значения, или сокращать кандидаты в пустых ячейках.
   Перед тем как рассказать об алгоритме решения данной головоломки ознакомимся сначала с терминологией игры:
Ячейка – элементарная частица игры судоку. Ячейки объединены в регионы, а регионы образуют игровое поле головоломки. Стандартная головоломка судоку состоит из 81 ячейки.
Регион – квадрат 3х3 ячейки. Кроссворд Судоку состоит из девяти регионов, хотя существуют другие, менее популярные, варианты головоломки.
Кандидат – одно из чисел (от 1 до 9), что в зависимости от ситуации на игровом поле, может быть вставлено в ту или другую ячейку судоко.
Группа – одна строка, колонка или регион игрового поля судоки. Как легко удостовериться группа состоит из девяти ячеек.

Одиночный кандидат

    3
     
7 8 9

1 2 3
  5  
    9

1 2 3
  5  
7 8 9

1 2  
  5  
    9

1 2  
  5  
    9

1   3
  5  
7 8 9

Скрытый одиночный кандидат

1    
  5  
    9

 3 

1    
  5 6
    9

1 2  
 
    9

1    
  5  
    9

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

Закрытый кандидат

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

1    
    6
 

1    
  5  
7 8  

1    
  5  
  7  

1 2  
  5  
7 8  

1 2  
  5  
  8  

1    
5 6  
  8  

1  3
4   
 

1   3
4 5  
7 8  

1   
4 5  
7 8  

1   
  5  
  8  

 
  5  
  8  

1    
  5  
  8  

1    
4   6
 

1   
4 5  
 

  2  
4 5  
 

1 2  
4 5  
  8  

  2  
    6
  8  

 2  
 5 6
 8  

Так-как, хоть одна из „зеленых” ячеек должен иметь значение 2, никакие другие ячейки в этом ряду не могут содержать это число. Потому 2 следует удалить из выделенных желтым цветом ячеек.

Закрытый кандидат 2

1   
  5  
 

 2 3
 5  
  

1   3
  5  
  

1 2  
  5  
    9

1    
  5  
    9

 
  5  
7   9

1    
4 5  
    9

1    
4 5 6
    9

  2  
7    
 

1    

  8  

 2  
 5  
   9

  2  
  5  
    9

 5 6
 8 9

4 5 
7   9

    3
4 5  
    9

    3
  5  
7    

    3
4 5  
 

    
4 5 

Голая пара

    Если две ячейки в группе (строке, столбике или регионе) имеют идентичную пару кандидатов (и только эту пару кандидатов), то никакие другие ячейки в этой группе их иметь не могут.

 7 

  2  
4 5  
 

1 2  
4 5  
 

1    
4 5  
    

 9 

 
    6
  8  

 
    6
  8  

1    
    6
  8  

 3 

    Эти два кандидата должны быть исключенные из других ячеек группы. В примере приведенном выше, кандидаты 6 и 8 формируют в пределах ряда „голую пару” (выделено зеленым). Потому кандидаты 6 и 8 могут быть исключены из других ячеек этого ряда (желтая ячейка).

Голые тройки

1    
    6
     

1    
  5 
7 8 

1    
  5  
  7  

1   3
4    
 

1   3
4 5  
7 8  

1    
4   6
 

1   
4   
 

Голые четверки

  5  
7   9

1   
4 5 
7   

1    
4 5 6
  

  2  
     
7    

1    

  8  

  2  
  5  
    9

  2  
  5  
 

 
    6
  8  

Скрытые пары

  2 3

 

 2 3
 5  
 

1 2  
  5  
    9

1    
  5  
    9

    3
  5  
  

Скрытые тройки

    Если три ячейки в группе содержат трех кандидатов и эти кандидаты не входят в другие ячейки группы, то другие числа из этих трех клеток должны быть изъяты.

1 2  

 

1 2  
4    
  8  

1 2  

  8 9

  2 3
4   6
7    

  2  
4    
  8  

1 2  
    6
7   9

    3
    6
    9

 5 

4    
    9

    На рисунке вверху, кандидаты 3, 6 и 7 найдено только в ячейках выделенных зеленым цветом. Потому, все другие кандидаты могут быть изъяты из этих трех клеток. Скрытые тройки находить тяжело, но они к счастью, редко используются для решения головоломок.

Скрытые четверки

    Если четыре ячейки в группе содержат четырех кандидатов и эти кандидаты не входят в другие клетки группы, то другие числа из этих четырех ячеек должны быть изъяты.

1 2  

 

1   
   6
   9

  2  
     
7   9

    3

  8  

1   3
4 5  
  8  

    3
4 5  
 

1   3
4 5  
 

 
4 5  
  8  

  2  
  5  
7    

 
4   6
7 8  

    Скрытые четверки находить чрезвычайно сложно, даже когда точно извесно, что они есть. Попробуйте найти скрытые четверки на вышерасположенном рисунке.

Х-крыло

    "X-крыло" – позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны разделять две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (их в колонках должны разделять две строки) также формируют X-крыло. Эти четыре клетки - единственные возможные места расположения для "настоящих" кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного "настоящими" кандидатами, должны быть удалены. (Возможно эта позиция была названа X-крылом потому, что в конечном варианте "настоящие" кандидаты должны находиться по диагонали в противоположных углах прямоугольника.)

    Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки.
    Синие и ярко-зеленые ячейки формируют классическое "X-крыло" – первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. "Настоящих" кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены красным контуром).

Рыба-меч

    Позиция "рыба-меч" является одним из вариантов позиции "х-крыло" описанной выше.
    "Рыба-меч" – сложная позиция образованая тремя строчками. Все эти строчки должны иметь не больше чем три клеточки с одинаковыми кандидатами и использовать совместно три колонки. То же относится и к "рыбе-меч" образованной тремя колонками - колонки должны иметь не более трех ячеек с кандидатом и использовать совместно три строки. Эти колонки и строки формируют сетку, узлы которой являются единственно возможными для расположения "настоящих" кандидатов. Остальные кандидаты, находящиеся на линиях пересечения сетки должны быть удалены.
   Как всегда пример:

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

Решение с цветными метками

    В этой позиции нам интересны кандидаты, находящиеся только в одной или двух ячейках группы (ряда, колонки или региона 3х3). Одна из этих двух ячеек есть "верной", а другая соответственно "ложной", но мы еще не знаем какая. Как правило, в большинстве головоломок судоку есть много соединенных пар. Иногда они, соединяясь образуют целые сложные цепочки, предоставляя нам возможность обнаружить кандидатов, которых можно безопасно изъять.
    Для того, чтобы показать связь между этими ячейками используем два цвета - синий и ярко-зеленый:

   Если две ячейки в объединенной цепи имеют такой же цвет и разделяют ту же группу, то их цвет должен быть "ложным", потому что каждая группа может иметь только одно значение.
   Также, если какой-то кандидат за пределами сложной цепочки связан колонкой, рядом или регионом, с другими двумя ячейками выделеными альтернативными цветами, то этот "нецепочный" кандидат должен быть изъят.
   Чтобы понять все вышесказанное рассмотрим пример (рисунок вверху). Как видим, к головоломке был применен фильтр по кандидату 5. Ячейки отмеченные буквами A и B формируют соединенную пару, так-как они являются единственными кандидатами 5 в восьмой колонке. Ячейки B и C также образуют соединенную пару - они являются единственными кандидатами 5 в правом нижнем регионе. Наконец C и D является единственными кандидатами 5 в восьмой строке и потому также формируют соединенную пару. Эти три соединенных пары образуют цепочку и могут быть выделены альтернативными цветами, как показано на рисунке. Ячейка выделена красным контуром непосредсвенно относится к соединенным парам (A и D). Так-как одна из выделенных альтернативным цветом ячеек должен быть "верной" то этот отдаленный кандидат можно безопасно изъять.

P.S.

    Применяя шаги описанные выше можно решить большинство головоломок Судоку. Но есть также сложные пазлы, не подвластные логическому решению. Единственным методом их решения является "метод проб и ошибок" или, говоря иначе "метод научного тыка". Также встречаются Судоку, что имеют несколько решений - это как правило "битые" или неправильно составлены головоломки.