Sign in to follow this  
Dener

Судоку

Recommended Posts

Судоку-прикольная игруха с цифрами на ломание мозгов.Сам познакомился где-то в начале года и до сих пор не отпустило... :icon_biggrin:

Короче-квадрат 9*9 клеток, даны несколько цифр.Задача проста-впиши остальные .Всё хорошо, но они должны быть разными в рядах и столбцах...

Итак, кто играл, кто сломал мозг, кто продолжает ломать?

Share this post


Link to post
Share on other sites

Мммм, я вот сегодня как раз одну жахнул. А про что гутарить будем?

Share this post


Link to post
Share on other sites

Зевнул....

А я просто программку написал...

Немного эвристики а если не поможет, то поросятами.

Share this post


Link to post
Share on other sites

Есть еще вот такая штука:

Sudoku Online.

Там и для детсада, и для школьников, и для взрослых дяденек и тётенек есть.

Причем, для тех, кому не терпится, - с ответами.

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

Вопрос к аудитории: "А вы используете какую-нибудь систему для решения головомойки?"

Share this post


Link to post
Share on other sites
Вопрос к аудитории: "А вы используете какую-нибудь систему для решения головомойки?"

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

Правда время уходит и вообще...

Share this post


Link to post
Share on other sites

Аека, спасибо! на последних уровнях программка начала э-э-э... виснуть.

пойду эвристики новые писать до поросят...

Share this post


Link to post
Share on other sites

А тактика... Ну для начала для каждой клетки обсчитываем ОДЗ.

Если мощность множества ОДЗ = 1, то эту цифру вписываем

(в итоге судоку решается в один проход - потому что каждая новая цифра только снижает ОДЗ)

Если все ОДЗ имеют мощность более 1, то сортируем клетки в порядке возрастания числа вариантов и затем брутим с возвратом рекурсивно.

В общем, аналогичным образом расставляют ферзей на шахматной доске.

Вот доведу до ума, чтобы щелкала любую судоку и выложу

Share this post


Link to post
Share on other sites

NortUS, кажется я знаю, почему Ваш алгоритм виснет.

Расскажу немного про свои методы.

Рассматриваю доску с циферками как тесеракт со стороной "n".

Собственно, условие целостности тесеракта - любое параллельное сечение должно содержать уникальные числа.

Двигаюсь практически от обратного Вашего алгоритма. Определяю не ОДЗ, а "в точке с данными координатами может ли быть число i", i = [1,n].

Одно число - один проход.

После каждого прохода выясняю, появились ли точки внутри сечений, где может быть только число "i".

Если появились - заполняю точки числами, и заново (для скорости написания я пошла на такую неоптимальность) к i = 1. Нет - к следующему числу, i:=i+1.

Так вот, у простых головомоек такого подхода достаточно: доходя до n все числа расставляются по своим точкам. Соответственно, максимум проходов - n^2.

В сложных головоломках возникают ситуации, когда в, к примеру, трех точках одного сечения возникает неоднозначность. Вид: [x,a-b-c,x,x,x,a-b,x,x,a-b]. Здесь "x" - то, что нам неважно, а "a,b,c" - числа, выявленные в ОДЗ (Ваш алгоритм).

Логика подсказывает, что из последовательности в примере во втором сегменте можно смело удалить "a-b", оставив там только "c".

Собственно, Вам надо только научиться распознавать такие недонозначности - дело пойдет быстрее.

Наверное.

Свой алгоритм я реализовала на Оракловом PL/SQL. Очень удобно, когда за уникальностью следит кто-то другой.

В среднем решение находилось за десяток проходов.

Правда, сервер стонал. Но это - дело десятое.

Если интетесно, могу выложить исходники c DDL-ками своего чуда.

Кто-то за ночь успел мою схему на тестовом сервере грохнуть. Ушло всё. Исходники, таблички...

Работа двух дней умерла после одной команды "drop user ... cascade;". Кто-то вечером получит лопатой по щеблу за такие игры.

Восстановлю - выложу. Чтобы больше не пропадало.

Edited by Aeka

Share this post


Link to post
Share on other sites

Ых!

Восстановила.

Решает быстро.

Удалось сократить решение со ста шагов до 10-40.

В общем, решение головомойки "++" №5290 с сайта заняло 30 шагов. И 12 секунд.

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

Желающим - rtf-ный файлик "как всё было". Как велся счет.

2007_08_16_sudoku_cube_solution__5290.rar

Остается проблема с "забиванием" исходных данных - в базу их можно залить только набором insert-ов... что есть печально.

В общем, вотъ. :)

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.