Dener Опубликовано 10 августа, 2007 Жалоба Share Опубликовано 10 августа, 2007 Судоку-прикольная игруха с цифрами на ломание мозгов.Сам познакомился где-то в начале года и до сих пор не отпустило... Короче-квадрат 9*9 клеток, даны несколько цифр.Задача проста-впиши остальные .Всё хорошо, но они должны быть разными в рядах и столбцах... Итак, кто играл, кто сломал мозг, кто продолжает ломать? Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
DupaVoz Опубликовано 10 августа, 2007 Жалоба Share Опубликовано 10 августа, 2007 Мммм, я вот сегодня как раз одну жахнул. А про что гутарить будем? Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
NortUS Опубликовано 11 августа, 2007 Жалоба Share Опубликовано 11 августа, 2007 Зевнул.... А я просто программку написал... Немного эвристики а если не поможет, то поросятами. Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Gil-Gellad Опубликовано 13 августа, 2007 Жалоба Share Опубликовано 13 августа, 2007 А я просто программку написал... Дай... Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Aeka Опубликовано 13 августа, 2007 Жалоба Share Опубликовано 13 августа, 2007 Есть еще вот такая штука: Sudoku Online. Там и для детсада, и для школьников, и для взрослых дяденек и тётенек есть. Причем, для тех, кому не терпится, - с ответами. Самые простые решаются вообще в уме. Без функционала заметок. Самые сложные мне приходилось по полчаса разрисовывать. Вопрос к аудитории: "А вы используете какую-нибудь систему для решения головомойки?" Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Dener Опубликовано 15 августа, 2007 Автор Жалоба Share Опубликовано 15 августа, 2007 Вопрос к аудитории: "А вы используете какую-нибудь систему для решения головомойки?" Я, да и мой отец тоже обычно пользуемся черновичками:перерисовываешь и... Правда время уходит и вообще... Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
NortUS Опубликовано 15 августа, 2007 Жалоба Share Опубликовано 15 августа, 2007 Аека, спасибо! на последних уровнях программка начала э-э-э... виснуть. пойду эвристики новые писать до поросят... Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
NortUS Опубликовано 15 августа, 2007 Жалоба Share Опубликовано 15 августа, 2007 А тактика... Ну для начала для каждой клетки обсчитываем ОДЗ. Если мощность множества ОДЗ = 1, то эту цифру вписываем (в итоге судоку решается в один проход - потому что каждая новая цифра только снижает ОДЗ) Если все ОДЗ имеют мощность более 1, то сортируем клетки в порядке возрастания числа вариантов и затем брутим с возвратом рекурсивно. В общем, аналогичным образом расставляют ферзей на шахматной доске. Вот доведу до ума, чтобы щелкала любую судоку и выложу Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Aeka Опубликовано 15 августа, 2007 Жалоба Share Опубликовано 15 августа, 2007 (изменено) 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;". Кто-то вечером получит лопатой по щеблу за такие игры. Восстановлю - выложу. Чтобы больше не пропадало. Изменено 16 августа, 2007 пользователем Aeka Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Aeka Опубликовано 16 августа, 2007 Жалоба Share Опубликовано 16 августа, 2007 Ых! Восстановила. Решает быстро. Удалось сократить решение со ста шагов до 10-40. В общем, решение головомойки "++" №5290 с сайта заняло 30 шагов. И 12 секунд. Секунды, конечно, фигня - тестовый сервер, вычислительные мощности на нуле практичкски. Желающим - rtf-ный файлик "как всё было". Как велся счет. 2007_08_16_sudoku_cube_solution__5290.rar Остается проблема с "забиванием" исходных данных - в базу их можно залить только набором insert-ов... что есть печально. В общем, вотъ. :) Цитата Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рекомендуемые сообщения
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.