Перейти к содержанию

Судоку


Dener

Рекомендуемые сообщения

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

  • Ответов 28
  • Created
  • Последний ответ

Top Posters In This Topic

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

Sudoku Online.

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

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

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

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

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;". Кто-то вечером получит лопатой по щеблу за такие игры.

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

Изменено пользователем Aeka
Ссылка на комментарий
Поделиться на другие сайты

Ых!

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

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

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

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

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

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

2007_08_16_sudoku_cube_solution__5290.rar

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

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

Ссылка на комментарий
Поделиться на другие сайты

Join the conversation

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 смайлов.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу

Объявления


×
×
  • Создать...