Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.03.2009, 01:01   #1
С.М.С
Участник клуба
 
Аватар для С.М.С
 
Регистрация: 29.12.2008
Сообщений: 1,599
По умолчанию Логика для Кроссвордов Судоку.

Доброй ночи. Хотелось бы узнать кто - нибудь занимался созданием программ для решения судоку, если да, то насколько успешно. Пробовал разные варианты с логикой, получилось, что если код универсальный для всех степеней сложности, то обработка занимает большое время вплоть до нескольких часов.
С.М.С вне форума Ответить с цитированием
Старый 25.03.2009, 03:14   #2
Sasha_Smirnov
Особый статус
Участник клуба
 
Аватар для Sasha_Smirnov
 
Регистрация: 24.11.2008
Сообщений: 1,535
По умолчанию

Не может быть! Точнее, не должно. Попробуйте в квадрате 3 на 3.
Sasha_Smirnov вне форума Ответить с цитированием
Старый 26.03.2009, 01:03   #3
С.М.С
Участник клуба
 
Аватар для С.М.С
 
Регистрация: 29.12.2008
Сообщений: 1,599
По умолчанию

то, что квадрат 3 на 3 это так, и их там 9, плюс в некоторых случаях числа недолжны повторяться и по диагоналям. Дело не в этом, есть случаи, когда в одну ячейку подходит одна цифра на нескольких последовательных этапах обработки, тогда программа всё отлично и быстро расчитывает. А вот если создается ситуация, когда в ячейку подходит два, три и более значений, вот тогда и проблема. Сделал, чтобы в такой ситуаци программа брала число подставляла и производила проверку на совпадение, если числа не повторяются, то это число сохраняется и расчёт продолжается. При таком алгоритме может возникнуть ошибка вначале расчёта, что и происходит( к примеру если число взято неправельное для конечного результата, но в данный момен работы оно проходит все проверки). Так вот можно сделать полное заполнение нескольких квадратов, а дальше производить расчёт, если расчёт не верен изменять значение в последней ячейки, по достижению в ней числа 9, производить сброс в этой ячейки и увеличивать значение на еденицу больше в предыдущей в результате для одного квадрата получаем 9^9 комбинаций или 387 милин 420тыс 489 комбинации, а если брать несколько квадратов, при этом необходимо после каждого изменения значения проводить проверку на совпадение.!!!!
С.М.С вне форума Ответить с цитированием
Старый 01.04.2009, 16:12   #4
С.М.С
Участник клуба
 
Аватар для С.М.С
 
Регистрация: 29.12.2008
Сообщений: 1,599
По умолчанию

работает! восьмой уровень сложности в среднем 8 минут.
С.М.С вне форума Ответить с цитированием
Старый 01.04.2009, 16:36   #5
wall66
Участник клуба
 
Аватар для wall66
 
Регистрация: 04.10.2008
Сообщений: 1,485
По умолчанию

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

занимать будет много места, но производительность станет гораздо выше
свободен...
wall66 вне форума Ответить с цитированием
Старый 01.04.2009, 17:42   #6
Levsha100
Заблокирован
Старожил
 
Регистрация: 20.07.2008
Сообщений: 4,033
По умолчанию

Цитата:
Сообщение от wall66 Посмотреть сообщение
думаю легче было бы просчитать все возможные варианты расположения цифр вообще, и искать среди них подходящий для конкретного случая (с совпадающими клетками)

занимать будет много места, но производительность станет гораздо выше
Типа представить все состояния поля как вершины графа, а ходы как ребра, и искать выигравшую комбинацию!
Levsha100 вне форума Ответить с цитированием
Старый 01.04.2009, 18:05   #7
С.М.С
Участник клуба
 
Аватар для С.М.С
 
Регистрация: 29.12.2008
Сообщений: 1,599
По умолчанию

А вы пощитайте сколько это комбинаций, я примерно так тоже думал. Оказалось не проще, да и структура кросводов меняется, а переправить код проще чем переписывать заново, в любом случае попробуйте свой вариант если время есть и сравните, возможно Вы и правы.
С.М.С вне форума Ответить с цитированием
Старый 02.04.2009, 16:07   #8
wall66
Участник клуба
 
Аватар для wall66
 
Регистрация: 04.10.2008
Сообщений: 1,485
По умолчанию

сколько бы их ни было - это конечное число, которое можно рассчитать один единственный раз, чтобы потом в дальнейшем им пользоваться
свободен...
wall66 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Тетрис! Логика и возможности. Iceman Общие вопросы Delphi 4 04.01.2009 01:56
Логика монстра(ов) ChukCha Gamedev - cоздание игр: Unity, OpenGL, DirectX 15 19.08.2008 15:31
Метод перебора для нахождения решения "Судоку" ДЖО Помощь студентам 23 04.06.2008 22:29
USB логика на выходах StartMis Общие вопросы Delphi 2 26.05.2008 18:03