Разгадывание судоку

Попу­ляр­ные в XX веке кросс­ворды в веке XXI сме­нило новое увле­че­ние — при­шед­шая из Япо­нии игра судоку. Суще­ствуют раз­лич­ные вари­анты игры и множе­ство «патен­то­ван­ных» рекомен­даций игро­кам. Уди­ви­тельно, но зна­ние матема­ти­че­ских терми­нов, даже только по назва­ниям, поз­во­ляет созда­вать эффек­тив­ные при­ёмы раз­га­ды­ва­ния судоку.

Зада­ние в клас­си­че­ском вари­анте судоку — запол­нить циф­рами от 1 до 9 клетки квад­рат­ной таб­лицы $9\times 9$, кото­рая раз­де­лена на девять квад­ра­тов $3\times 3$. В каж­дой строке и в каж­дом столбце таб­лицы, в каж­дом квад­рате $3\times 3$ цифры должны быть раз­лич­ными.

Ряд вари­ан­тов игры полу­ча­ется из клас­си­че­ского про­стым добав­ле­нием усло­вий, напри­мер: «диаго­нали» — в каж­дой из двух диаго­на­лей таб­лицы цифры также не должны повто­ряться; «нера­вен­ства» — сосед­ние клетки таб­лицы свя­заны зна­ками «больше» и «меньше», кото­рые отно­сятся к «оби­та­те­лям» этих кле­ток; «суммы» — вся таб­лица раз­де­лена не только на девять квад­ра­тов $3\times 3$, но и на обла­сти, для каж­дой из кото­рых при­ве­дена сумма всех её цифр.

Началь­ные усло­вия могут отли­чаться чис­лом зара­нее «про­пи­сан­ных» цифр. Как пра­вило, уменьше­ние числа началь­ных цифр услож­няет задачу, но для «cумм» и иногда для «нера­венств» их нет вообще.

Игро­вое пове­де­ние начи­нающего люби­теля судоку можно срав­нить с мето­ди­кой начи­нающего шахма­ти­ста, быстро тонущего в оке­ане рас­чё­тов по принципу «он — туда, я — сюда…». Уме­ние отбра­сы­вать лиш­ние, ненуж­ные вари­анты в рас­чё­тах — про­во­дить пере­бор с огра­ни­че­ни­ями — одно из глав­ных пре­имуществ «обу­чен­ного» игрока и в шахма­тах, и в судоку.

Пере­би­рать вари­анты всё равно при­дётся, без этого не обойтись, но с помощью ряда при­ёмов можно сокра­тить объём работы во много раз. Раз­бе­рём несколько таких при­ёмов на при­ме­рах.

Метод край­него элемента. Это сло­во­со­че­та­ние известно каж­дому, кто посещал заня­тия в матема­ти­че­ском кружке. В нашем слу­чае слово «край­ний» будет озна­чать «экс­тремаль­ный» (т. е. наименьший или наи­больший).

Напри­мер, при раз­га­ды­ва­нии судоку «суммы» огра­ни­че­ния в пере­боре можно полу­чить, отме­тив в таб­лице все блоки из двух кле­ток, суммы в кото­рых равны 3, 4, 16, 17. Это и есть «край­ние» элементы, наименьшие и наи­большие. Каж­дое из этих чисел един­ствен­ным обра­зом пред­став­ля­ется в виде суммы двух раз­ных цифр (отлич­ных от нуля): $$ 3=1+2,\quad 4=1+3,\quad 16=7+9,\quad 17=8+9. $$

А для других чисел вари­ан­тов было бы больше, напри­мер, $7=1+6=2+5=3+4$.

Разгадывание судоку // Математическая составляющая

На рисунке, иллю­стри­рующем подоб­ный при­мер, две такие «край­ние» обла­сти, в соот­вет­ствующих клет­ках будут нахо­диться (в неиз­вест­ном нам пока порядке) цифры 1, 3 и 8, 9. Это сразу даёт «огра­ни­че­ние» для выде­лен­ного квад­рата — числа 7 и 10 из неисполь­зо­ван­ных цифр можно сложить един­ствен­ным обра­зом: $7=2+5$, $10=4+6$. Теперь в этом квад­рате $3 \times 3$ оста­лась неисполь­зо­ван­ной только цифра 7, кото­рая и отправ­ля­ется в пра­вый ниж­ний угол. После этого опре­де­ля­ется и сосед цифры 7 по выде­лен­ной обла­сти — цифра 6.

Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая

Пере­ход к допол­не­нию. Идея состоит в том, что для изу­че­ния части дан­ного множе­ства может быть полез­ным изу­че­ние допол­няющей части. Вот пояс­няющий при­мер, наве­ян­ный знаме­ни­той исто­рией про Архимеда. Даны мер­ный ста­кан­чик и шарик, объём кото­рого надо быстро опре­де­лить. Кла­дём шарик в ста­кан, зали­ваем водой с вер­хом, запоми­наем отметку на шкале, вынимаем шарик, смот­рим на новую отметку. Раз­ность объёмов, опре­де­ля­емых пер­вой и вто­рой мет­ками, равна объёму шарика.

Разгадывание судоку // Математическая составляющая

Вер­нёмся к разо­бран­ному ранее при­меру. Цифру 7 в пра­вом ниж­нем углу квад­рата $3\times 3$ можно «поста­вить на место» и с помощью при­ёма «пере­ход к допол­не­нию».

Пра­вая ниж­няя клетка квад­рата явля­ется частью «языка», ухо­дящего в сосед­ний квад­рат, а все осталь­ные обла­сти с обо­зна­чен­ными суммами за пре­делы квад­рата $3\times 3$ не выхо­дят. Cумма цифр по всем клет­кам любого квад­рата раз­би­е­ния $3\times 3$ равна $$1+2+…+9=45,$$ а сумма цифр во «внут­рен­них» обла­стях с суммами дан­ного квад­рата равна $10+4+17+7=38$. Эти цифры «допол­няют» цифру в пра­вом ниж­нем углу квад­рата, она равна $45-38=7$.

Блоч­ный метод. В нашем слу­чае блоки — это оди­на­ко­вые наборы цифр.

В сле­дующем при­мере из клас­си­че­ского вари­анта судоку блок (2, 3) встре­ча­ется в пер­вой строке и в чет­вёр­том столбце. В пра­вом верх­нем квад­рате $3\times 3$ упомя­ну­тые строка и стол­бец «закры­вают» для цифр блока $(2, 3)$ все клетки, кроме двух. Затем, в этом квад­рате после­до­ва­тельно опре­де­ляем место 1, место блока $(6, 7)$, место 9.

Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая

Можно счи­тать, что место для 9 было най­дено мето­дом пере­хода к допол­не­нию — другими циф­рами были заняты восемь из девяти мест в квад­рате $3\times 3$.

Связ­ность. В матема­тике линей­ная связ­ность множе­ства — свойство, озна­чающее, что любые две его точки можно свя­зать непре­рыв­ной кри­вой, не выхо­дящей за гра­ницы множе­ства.

В судоку «нера­вен­ства» такой линией можно счи­тать цепочку нера­венств, свя­зы­вающую группу под­ряд идущих цифр. Идею метода иллю­стри­рует при­ве­дён­ный при­мер. Такая ситу­ация в рас­чё­тах должна быть исклю­чена, так как между 3 и 4 цифр нет, связ­ность наруша­ется.

Разгадывание судоку // Математическая составляющая

В судоку «нера­вен­ства» важен и метод край­него элемента, в част­но­сти 1 и 9 играют осо­бую роль. Ком­би­ни­руя эти методы, можно решать задачи, в кото­рых в началь­ной позиции нет ни одной цифры!

Сна­чала опре­де­лим край­ние элементы. Един­ствен­ная клетка, из кото­рой выхо­дят только знаки «больше», — левая ниж­няя клетка, зна­чит, в ней нахо­дится цифра 9. Это свое­об­раз­ный источ­ник, вершина горы. Ана­логично, сред­няя клетка — един­ствен­ная, оби­та­тель кото­рой меньше сосе­дей, — в ней нахо­дится 1. Теперь ста­но­вится оче­вид­ным то, что клетки с 9 и с 1 свя­зы­вает «ручей», кото­рый запол­няют цифры 8, 7, …, 2.

Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая
Разгадывание судоку // Математическая составляющая

Конечно, в реаль­ных зада­чах вида «нера­вен­ства» (как, впро­чем, и во всех других видах) учи­ты­ваются и сооб­раже­ния, свя­зан­ные с непо­вто­ря­емо­стью цифр в стро­ках и столб­цах таб­лицы $9\times 9$.

При­ве­дён­ные при­меры пре­враще­ний матема­ти­че­ских терми­нов в игро­вые при­ёмы судоку под­твер­ждают спра­вед­ли­вость латин­ского изре­че­ния nomen est omen: имя — уже зна­че­ние.

Разворот книги

Книга «Математическая составляющая»
Книга «Математическая составляющая»