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