ГОЛОВОЛОМКИ СУДОКУ | Наука і життя

ГОЛОВОЛОМКИ СУДОКУ Судоку більше-менше. Судоку в трикутниках. Чемпіонат Росії по судоку. Перший...
ГОЛОВОЛОМКИ СУДОКУ

ГОЛОВОЛОМКИ СУДОКУ
Судоку більше-менше.
Судоку в трикутниках.
Чемпіонат Росії по судоку. Перший тур. Мал. 1.
Чемпіонат Росії по судоку. Перший тур. Мал. 2.
Чемпіонат Росії по судоку. Перший тур. Мал. 3.
Чемпіонат Росії по судоку. Перший тур. Мал. 4.
Чемпіонат Росії по судоку. Перший тур. Мал. 5.
Чемпіонат Росії по судоку. Перший тур. Мал. 6.
Чемпіонат Росії по судоку. Перший тур. Мал. 7.
Чемпіонат Росії по судоку. Перший тур. Мал. 8.
Чемпіонат Росії по судоку. Перший тур. Мал. 9.
Чемпіонат Росії по судоку. Перший тур. Мал. 10.
Чемпіонат Росії по судоку. Другий тур. Судоку-1.
Чемпіонат Росії по судоку. Другий тур. Судоку-суми.
<
>
СУДОКУ - новомодна японська головоломка у вигляді латинської магічного квадрата. СУ по-японськи означає "цифра", а ДОК - "стоїть окремо". По суті - це цифровий пасьянс: потрібно заповнити клітини таблиці 9x9, поділеної на 9 квадратів 3x3, цифрами від 1 до 9 так, щоб в кожному рядку, в кожному стовпці і в кожному виділеному квадраті 3x3 кожна цифра зустрічалася б тільки один раз. наприклад:
Рис.1.
Прообраз судоку без поділу на окремі області зустрічається в роботах Леонарда Ейлера (1707-1783) про магічні квадратах (див. "Наука і життя" № 11, 1972 року і № 4, 1973 г.). Головоломка в її сучасному вигляді вперше була надрукована в американському журналі "Делл пенсл Пазлс" в 1979 році. Її автор - архітектор Ховард Гарнс. А після того як в минулому році британська газета "Таймс" опублікувала статтю "Судоку", почалася тріумфальна хода головоломки по всьому світу. Судоку почали друкувати не тільки спеціалізовані, а й масових газет і журналів.
Розглянемо сітку судоку з математичної точки зору. Виникає питання: скільки всіляких розстановок в ній цифр існує? За допомогою комп'ютера підрахували: 6 670 903 752 021 072 936 960 розстановок - в цьому незалежно переконалися Фразер Ярвіс з університету Шеффілда і Бертран Фелгенхауер з дрезденської Вищої технічної школи. У кожній з розстановок можна використовувати мільярди комбінацій, вибираючи набір задають цифр, тобто потенційна кількість різних завдань судоку неймовірно велике.
Професійно складені головоломки повинні мати поетапне рішення, коли в результаті кожного логічного ходу вписується чергова нова цифра. Якщо розглядати найпростіші ходи, то їх, по суті, тільки два. І кожен наступний крок рішення служить відповіддю на питання: "Яка цифра може стояти в цій клітці?" або "Де в цьому ряду (області) знаходиться така-то цифра?". Стосовно до сітки на рис.1 в якості відповіді на перше питання може бути відшукання числа на перетині верхнього рядка і четвертого ряду. Цифри 1, 2, 3, 4, 5, 6, 8 і 9 відпадають: вони вже є або в першій горизонталі, або в четвертій вертикалі. Значить, тут повинна стояти цифра 7. Приклад другого питання - де у верхньому ряду може перебувати 2? Чи не в першому і не в другому квадраті, тобто тільки в передостанній клітці. Як правило, цих двох питань і відповідей на них цілком достатньо для вирішення судоку. Правда, деколи наступний хід хоч і існує, але не впадає в очі - потрібен якийсь час, щоб його побачити. Тому можна говорити, що судоку бувають більш-менш складними. Зрозуміло, є і набагато хитріші міркування, що складаються з декількох припущень і ланцюжки висновків. Навіть є сайти для любителів судоку, де докладно класифікуються методи вирішення. Деякі радять просто дрібно записувати в кожну клітину всі цифри, які в ній можуть знаходитися, і поступово їх викреслювати.
Досвідчений програміст без праці зможе написати судоку-генератор - програму, яка виробляє головоломки, які мають логічне рішення. Саме такі судоку можна побачити в більшості газет і журналів. Однак серед знавців особливо цінуються судоку, зроблені вручну, - в їх вирішенні є певні краса і витонченість, які не може забезпечити жоден комп'ютер.
Часто задають цифри судоку утворюють деякий орнамент. У сітці на рис.2 ці цифри складаються в літери "Н і Ж" - ініціали журналу "Наука і життя".
Рис.2.
Вивчення головоломки дозволяє придумати безліч дослідницьких завдань на базі судоку.
завдання
Програміст перевіряє правильність заповнення сітки судоку. Для цього він переконується, що кожна з дев'яти цифр зустрічається в сітці рівно дев'ять разів і що в кожному стовпчику, кожному рядку і кожному виділеному квадраті сума цифр дорівнює 45. Чи достатньо такого алгоритму для гарантованої перевірки?
рекорди судоку
Можна спробувати скласти книгу рекордів судоку. Ось деякі можливі "номінації" в ній:
Судоку з єдиним рішенням і найменшим числом задають цифр.
Судоку з найменшою сумою задають цифр.
Судоку з найменшим числом задають цифр за умови, що на головних діагоналях все цифри теж повинні бути різні.
Судоку з максимальним числом рішень за умови, що додавання ще тільки однієї задає цифри робить рішення єдиним.
Слідом за що стали вже класичними судоку з'явилися десятки їх варіацій. У них використовуються сітки іншого розміру, області мають не квадратну форму, пропонуються додаткові умови.
Наведемо три варіації.
судоку 8x8
Заповніть клітини числами від 1 до 8, щоб в кожному рядку, кожному стовпчику і кожної виділеної жирним області все числа були різні.
Судоку більше-менше
У сітці не вказано жодної задає цифри. Зате розставлені знаки "більше" і "менше" між усіма сусідніми числами кожної області.
Судоку в трикутниках
Заповніть трикутні клітини цифрами від 1 до 9, щоб в кожному з шести великих трикутників і кожної лінії (навіть якщо лінія складається з двох окремих ділянок) за всіма трьома напрямками все цифри були різними.
Подібно чемпіонатів зі складання кубика Рубіка, стали проходити чемпіонати світу за рішенням судоку. Пройшов і перший чемпіонат Росії.
ЧЕМПІОНАТ РОСІЇ ПО СУДОКУ
Дванадцятого лютого 2006 року о Центрі позашкільної роботи в Митине пройшов перший очний чемпіонат Росії по судоку. Організував його російський клуб цінителів головоломок "Діоген". У чемпіонаті взяли участь двадцять найсильніших решателей головоломок. Любителі судоку, які не мали можливості приїхати в Москву, свої сили у змаганнях в реальному часі через Інтернет.
Змагання складалися з двох турів по одній годині. Вирішивши завдання, учасник повинен був виписати три ключові цифри в форму. Саме за цими ключам перевірялася правильність рішення.
У першому турі пропонувалися стандартні судоку в сітках різного розміру, всього - десять завдань. Кращий результат в першому турі - 290 балів з 300 - у Андрія Богданова з Підмосков'я. Наводимо завдання повністю, щоб кожен міг оцінити свій рівень.
У другому турі пропонувалися варіації судоку - завдання з додатковими умовами, всього - шість завдань. Наведемо два з них:
Судоку-1
Заповніть сітку за правилами судоку. Жирна риса стоїть між усіма парами сусідніх чисел, що відрізняються рівно на 1.
Судоку-суми
Заповніть сітку за правилами судоку. Числа поза сітки вказують суму перших трьох цифр у відповідному ряду.
Кілька учасників змогли вирішити п'ять завдань з шести.
Після двох турів між трьома переможцями - Андрієм Лемеш, Андрієм Богдановим і Ріад Ханмагомедовим - відбувся фінальний поєдинок з п'яти завдань. Час, відведений для вирішення кожного учасника, було пропорційно кількості набраних ним очок. Переходячи від рішення одного завдання до іншого, фіналісти пересувалися по партах до переможного фінішу, що представляло вельми азартне видовище.
Першим досяг "фінішної стрічки" москвич Ріад Ханмагомедов. Крім того, він єдиний з трьох вірно вирішив все п'ять завдань, і тому його перемога абсолютно заслужена і справедлива. Головним призом - тортом у вигляді судоку переможець пригостив усіх учасників під час подальшого чаювання.
Трохи докладніше про Інтернет-версії чемпіонату. Сайт клубу "Діоген" www.diogen.h1.ru користується популярністю не тільки у російських цінителів головоломок, але і у всьому світі, тому на інформацію про майбутній чемпіонат відгукнулися десятки любителів судоку. Географія учасників говорить сама за себе: Японія, Туреччина, Австралія, США, Чехія, Боснія і Герцоговина, Хорватія, Польща, зрозуміло, Росія, Білорусія, Україна і навіть Малайзія.
Технічно змагання відбувалися так: в момент початку кожного туру очного чемпіонату в мережі ставали доступними файли з умовами. Як і в очних змаганнях, кожен повинен був після закінчення години, відведеного на рішення, відправити заповнену форму з трьома ключовими цифрами.
Звичайно, оскільки є електронні програми за рішенням судоку і неможливо перевірити, вирішував учасник поодинці або на нього працювала ціла команда, результати он-лайн змагань можуть бути тільки неофіційними. Проте приємно відзначити, що четверо учасників: Shinichi Aoki, Taro Arimatsu, Daisuke Takei і Hideaki Jo (всі - з Японії) - впоралися з усіма завданнями обох турів.
Сайти любителів судоку:
http://www.play-sudoku.de/index.php?ru_index сайт з головоломками і форумом;
http://en.wikipedia.org/wiki/Sudoku багато інформації про судоку, завдання;
http://www.sudocu.com англійською мовою; є форум, спілкування решателей і програмістів судоку.

ГОЛОВОЛОМКИ СУДОКУ

Судоку більше-менше.

Судоку в трикутниках.

Чемпіонат Росії по судоку. Перший тур. Рис. 1.

Чемпіонат Росії по судоку. Перший тур. Рис. 2.

Чемпіонат Росії по судоку. Перший тур. Рис. 3.

Чемпіонат Росії по судоку. Перший тур. Рис. 4.

Чемпіонат Росії по судоку. Перший тур. Рис. 5.

Чемпіонат Росії по судоку. Перший тур. Рис. 6.

Чемпіонат Росії по судоку. Перший тур. Рис. 7.

Чемпіонат Росії по судоку. Перший тур. Рис. 8.

Чемпіонат Росії по судоку. Перший тур. Рис. 9.

Чемпіонат Росії по судоку. Перший тур. Рис. 10.

Чемпіонат Росії по судоку. Другий тур. Судоку-1.

Чемпіонат Росії по судоку. Другий тур. Судоку-суми.

СУДОКУ - новомодна японська головоломка у вигляді латинської магічного квадрата. СУ по-японськи означає "цифра", а ДОК - "стоїть окремо". По суті - це цифровий пасьянс: потрібно заповнити клітини таблиці 9x9, поділеної на 9 квадратів 3x3, цифрами від 1 до 9 так, щоб в кожному рядку, в кожному стовпці і в кожному виділеному квадраті 3x3 кожна цифра зустрічалася б тільки один раз. наприклад:

Рис.1.

Прообраз судоку без поділу на окремі області зустрічається в роботах Леонарда Ейлера (1707-1783) про магічні квадратах (див. "Наука і життя" № 11, 1972 року і № 4, 1973 г.). Головоломка в її сучасному вигляді вперше була надрукована в американському журналі "Делл пенсл Пазлс" в 1979 році. Її автор - архітектор Ховард Гарнс. А після того як в минулому році британська газета "Таймс" опублікувала статтю "Судоку", почалася тріумфальна хода головоломки по всьому світу. Судоку почали друкувати не тільки спеціалізовані, а й масових газет і журналів.

Розглянемо сітку судоку з математичної точки зору. Виникає питання: скільки всіляких розстановок в ній цифр існує? За допомогою комп'ютера підрахували: 6 670 903 752 021 072 936 960 розстановок - в цьому незалежно переконалися Фразер Ярвіс з університету Шеффілда і Бертран Фелгенхауер з дрезденської Вищої технічної школи. У кожній з розстановок можна використовувати мільярди комбінацій, вибираючи набір задають цифр, тобто потенційна кількість різних завдань судоку неймовірно велике.

Професійно складені головоломки повинні мати поетапне рішення, коли в результаті кожного логічного ходу вписується чергова нова цифра. Якщо розглядати найпростіші ходи, то їх, по суті, тільки два. І кожен наступний крок рішення служить відповіддю на питання: "Яка цифра може стояти в цій клітці?" або "Де в цьому ряду (області) знаходиться така-то цифра?". Стосовно до сітки на рис.1 в якості відповіді на перше питання може бути відшукання числа на перетині верхнього рядка і четвертого ряду. Цифри 1, 2, 3, 4, 5, 6, 8 і 9 відпадають: вони вже є або в першій горизонталі, або в четвертій вертикалі. Значить, тут повинна стояти цифра 7. Приклад другого питання - де у верхньому ряду може перебувати 2? Чи не в першому і не в другому квадраті, тобто тільки в передостанній клітці. Як правило, цих двох питань і відповідей на них цілком достатньо для вирішення судоку. Правда, деколи наступний хід хоч і існує, але не впадає в очі - потрібен якийсь час, щоб його побачити. Тому можна говорити, що судоку бувають більш-менш складними. Зрозуміло, є і набагато хитріші міркування, що складаються з декількох припущень і ланцюжки висновків. Навіть є сайти для любителів судоку, де докладно класифікуються методи вирішення. Деякі радять просто дрібно записувати в кожну клітину всі цифри, які в ній можуть знаходитися, і поступово їх викреслювати.

Досвідчений програміст без праці зможе написати судоку-генератор - програму, яка виробляє головоломки, які мають логічне рішення. Саме такі судоку можна побачити в більшості газет і журналів. Однак серед знавців особливо цінуються судоку, зроблені вручну, - в їх вирішенні є певні краса і витонченість, які не може забезпечити жоден комп'ютер.

Часто задають цифри судоку утворюють деякий орнамент. У сітці на рис.2 ці цифри складаються в літери "Н і Ж" - ініціали журналу "Наука і життя".

Рис.2.

Вивчення головоломки дозволяє придумати безліч дослідницьких завдань на базі судоку.

завдання

Програміст перевіряє правильність заповнення сітки судоку. Для цього він переконується, що кожна з дев'яти цифр зустрічається в сітці рівно дев'ять разів і що в кожному стовпчику, кожному рядку і кожному виділеному квадраті сума цифр дорівнює 45. Чи достатньо такого алгоритму для гарантованої перевірки?

рекорди судоку

Можна спробувати скласти книгу рекордів судоку. Ось деякі можливі "номінації" в ній:

Судоку з єдиним рішенням і найменшим числом задають цифр.

Судоку з найменшою сумою задають цифр.

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

Судоку з максимальним числом рішень за умови, що додавання ще тільки однієї задає цифри робить рішення єдиним.

Слідом за що стали вже класичними судоку з'явилися десятки їх варіацій. У них використовуються сітки іншого розміру, області мають не квадратну форму, пропонуються додаткові умови.

Наведемо три варіації.

судоку 8x8

Заповніть клітини числами від 1 до 8, щоб в кожному рядку, кожному стовпчику і кожної виділеної жирним області все числа були різні.

Судоку більше-менше

У сітці не вказано жодної задає цифри. Зате розставлені знаки "більше" і "менше" між усіма сусідніми числами кожної області.

Судоку в трикутниках

Заповніть трикутні клітини цифрами від 1 до 9, щоб в кожному з шести великих трикутників і кожної лінії (навіть якщо лінія складається з двох окремих ділянок) за всіма трьома напрямками все цифри були різними.

Подібно чемпіонатів зі складання кубика Рубіка, стали проходити чемпіонати світу за рішенням судоку. Пройшов і перший чемпіонат Росії.

ЧЕМПІОНАТ РОСІЇ ПО СУДОКУ

Дванадцятого лютого 2006 року о Центрі позашкільної роботи в Митине пройшов перший очний чемпіонат Росії по судоку. Організував його російський клуб цінителів головоломок "Діоген". У чемпіонаті взяли участь двадцять найсильніших решателей головоломок. Любителі судоку, які не мали можливості приїхати в Москву, свої сили у змаганнях в реальному часі через Інтернет.

Змагання складалися з двох турів по одній годині. Вирішивши завдання, учасник повинен був виписати три ключові цифри в форму. Саме за цими ключам перевірялася правильність рішення.

У першому турі пропонувалися стандартні судоку в сітках різного розміру, всього - десять завдань. Кращий результат в першому турі - 290 балів з 300 - у Андрія Богданова з Підмосков'я. Наводимо завдання повністю, щоб кожен міг оцінити свій рівень.

У другому турі пропонувалися варіації судоку - завдання з додатковими умовами, всього - шість завдань. Наведемо два з них:

Судоку-1

Заповніть сітку за правилами судоку. Жирна риса стоїть між усіма парами сусідніх чисел, що відрізняються рівно на 1.

Судоку-суми

Заповніть сітку за правилами судоку. Числа поза сітки вказують суму перших трьох цифр у відповідному ряду.

Кілька учасників змогли вирішити п'ять завдань з шести.

Після двох турів між трьома переможцями - Андрієм Лемеш, Андрієм Богдановим і Ріад Ханмагомедовим - відбувся фінальний поєдинок з п'яти завдань. Час, відведений для вирішення кожного учасника, було пропорційно кількості набраних ним очок. Переходячи від рішення одного завдання до іншого, фіналісти пересувалися по партах до переможного фінішу, що представляло вельми азартне видовище.

Першим досяг "фінішної стрічки" москвич Ріад Ханмагомедов. Крім того, він єдиний з трьох вірно вирішив все п'ять завдань, і тому його перемога абсолютно заслужена і справедлива. Головним призом - тортом у вигляді судоку переможець пригостив усіх учасників під час подальшого чаювання.

Трохи докладніше про Інтернет-версії чемпіонату. Сайт клубу "Діоген" www.diogen.h1.ru користується популярністю не тільки у російських цінителів головоломок, але і у всьому світі, тому на інформацію про майбутній чемпіонат відгукнулися десятки любителів судоку. Географія учасників говорить сама за себе: Японія, Туреччина, Австралія, США, Чехія, Боснія і Герцоговина, Хорватія, Польща, зрозуміло, Росія, Білорусія, Україна і навіть Малайзія.

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

Звичайно, оскільки є електронні програми за рішенням судоку і неможливо перевірити, вирішував учасник поодинці або на нього працювала ціла команда, результати он-лайн змагань можуть бути тільки неофіційними. Проте приємно відзначити, що четверо учасників: Shinichi Aoki, Taro Arimatsu, Daisuke Takei і Hideaki Jo (всі - з Японії) - впоралися з усіма завданнями обох турів.

Сайти любителів судоку:

http://www.play-sudoku.de/index.php?ru_index сайт з головоломками і форумом;

http://en.wikipedia.org/wiki/Sudoku багато інформації про судоку, завдання;

http://www.sudocu.com англійською мовою; є форум, спілкування решателей і програмістів судоку.