КОМПЬЮТЕРРА


"Магический квадрат" (HELP) 

Автор: Константин Кноп, Konstantin@Knop.com
Дата публикации:09.09.2000


Магический квадрат,
или
Числа на плацу

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

Кажется еще более удивительным, но все вышесказанное относится также и к сфере интеллектуальных развлечений. Шахматы, шашки, нарды, а также многие карточные игры известны с глубокой древности, причем интерес к ним практически не ослабевает. "Пятнашки" были изобретены Сэмом Лойдом более века назад и сохраняют популярность до сих пор. Примерно столько же известна головоломка Эдуарда Люка "Ханойская башня". А вот кубику Рубика - всего чуть более двадцати лет, причем ныне, после бешеного успеха начала 80-х годов, его популярность почти угасла. И, между прочим, кроссворды также изобретены в начале 20-го века, но первые лет 10 о них практически никто не знал, а сейчас разгадывание кроссвордов - любимый досуг миллионов людей, причем в последнее время появляются все новые и новые виды кроссвордных головоломок - сканворды, филворды и т.п

Я не оставляю надежды, что когда-нибудь наряду с кроссвордами и чайнвордами свое заслуженное "место под солнцем" отвоюют и разнообразные числовые головоломки, в которых нужно делать примерно то же, что и в кроссвордах - заполнять пустые клетки цифрами. Рассказ о таких задачах-головоломках мы начнем с японского изобретения - игры "магический квадрат". Другое ее (английское) название - "Number Place" ("Числовая площадка" или, говоря, военным языком, "Числовой плац") .

Плац имеет форму квадрата 9x9, разбитого на единичные клетки. Некоторые из этих клеток уже заполнены, а остальные еще только предстоит заполнить, используя для этого цифры от 1 до 9. Основное условие такое: в каждой строке, в какждом столбце и в любом из девяти "выделенных" квадратиков 3x3 все цифры должны быть различными. Понятно, что при этом каждая цифра может встретиться (быть использована) в строке, столбце и квадрате 3x3 только один раз.

Две задачи, которые я здесь комментирую, придуманы в 1997 году японцем Хирофуми Фудзивара, а мною взяты с сайта http://www.pro.or.jp/~fuji/java/puzzle/numplace/book1/index-eng.html

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

1386.gif (4275 bytes)

Посмотрите на рисунок с условием задачи 1. Чтобы расставить недостающие цифры, необходимо найти какую-то "зацепочку". Как это сделать? Инструкций, гарантирующих успех на 100%, я дать не могу, но несколько полезных рекомендаций все-таки выдам.

1. Постарайтесь найти место, на котором допустима только какая-то одна цифра (то есть такое место, для которого все цифры, кроме одной, уже использованы либо в той же строке, либо в том же столбце, либо в том же квадратике 3x3).

Постарайтесь отыскать такие места самостоятельно, а если не получится - поглядите на следующий рисунок.

1387.gif (4507 bytes)

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

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

1388.gif (4546 bytes)

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

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

Посмотрите на верхнюю строку (на любом из рисунков, начиная с условия). Где именно в ней может стоять двойка? Легко убедиться, что только в третьем столбце - во всех остальных свободных столбцах этой строки двойки с самого начала стоят в других строках. Если сформулировать эту мысль аккуратнее, то получится вот что:

1389.gif (4976 bytes)

3. Для каждой строки, столбца, квадрата 3x3 постарайтесь найти цифру, которая может в этой строке (столбце или квадратике) стоять только в единственном месте. Если бы мы с самого начала воспользовались этим рецептом, то смогли бы сразу же поставить единицу в четвертый столбец, двойку - в четвертую строку, седьмой столбец и правый средний квадратик 3x3, а цифру 9 - в первый столбец и левый средний квадратик. Рецепт-то, оказывается, очень мощный! (Увы, зато его гораздо тяжелее применять на практике: для выполнения первого рецепта достаточно было посмотреть на одно конкретное место "плаца", а здесь приходится внимательнейшим образом просматривать весь "плац" и анализировать, какие цифры не могут находиться на тех или иных местах.)

1390.gif (4801 bytes)

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

1391.gif (4120 bytes)

Так или иначе, а решение первой задачи можно довести до конца, ни разу не применяя этой "тяжелой артиллерии". А чтобы все-таки читатели смогли ее освоить, я приведу еще одну задачу. Попробуйте в этой задаче сразу применить оба рецепта. Сколько цифр при этом вам удастся поставить на первом же шаге решения?

1392.gif (5230 bytes)

Мне с первого шага поддались 20 цифр - см. рисунок. (Кстати, постарайтесь внимательно проанализировать, исходя из каких соображений поставлена та или иная цифра).

Ваш Константин Кноп