|
Логическая задача
|
|
| snaper1993 | Дата: Понедельник, 10.11.2008, 22:40 | Сообщение # 1 |
 Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Поле для игры в судоку имеет размер 9хх.9 клеточек и условно разбитое на 9 квадратов размером 3хх.3.
Каждая клеточка есть или пустой, или содержит число от 1 до 9.
Пример:
389|7..|2..
672|.5.|.1.
.14|6.9|..3
------------
23.|5..|871
85.|.37|.49
497|81.|3.5
------------
.65|482|13.
1.3|.7.| 46.
74.|1.3|59.
Вам необходимо расставить в пустые клеточки числа от 1 до 9 так, чтобы
1) в каждой строке числа не повторялись
2) в каждом столбике числа не повторялись
3) в каждом с 9- ты условных квадратов числа не повторялись
Для вышеприведенного примера ответ следующий:
389|741|256
672|358|914
514|629|783
------------
236|594|871
851|237|649
497|816|325
------------
965|482|137
123|975|4 68
748|163|592
Входные данные:
В стандартном входном потоке записанные 9 строк по 9 чисел. (числа разделены пропусками). Пустая клеточка обозначена числом 0. Нулей (пустых клеточек) будет не больше чем 29
Исходные данные:
в стандартный исходный поток запишите ответ к заданному судоку - 9 строк по 9 чисел в каждом (разделенные пропусками!!!)
Пример входных данных:
3 8 9 7 0 0 2 0 0
6 7 2 0 5 0 0 1 0
0 1 4 6 0 9 0 0 3
2 3 0 5 0 0 8 7 1
8 5 0 0 3 7 0 4 9
4 9 7 8 1 0 3 0 5
0 6 5 4 8 2 1 3 0
1 0 3 0 7 0 4 6 0
7 4 0 1 0 3 5 9 0
Пример исходных данных:
3 8 9 7 4 1 2 5 6
6 7 2 3 5 8 9 1 4
5 1 4 6 2 9 7 8 3
2 3 6 5 9 4 8 7 1
8 5 1 2 3 7 6 4 9
4 9 7 8 1 6 3 2 5
9 6 5 4 8 2 1 3 7
1 2 3 9 7 5 4 6 8
7 4 8 1 6 3 5 9 2
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Alexander | Дата: Вторник, 11.11.2008, 02:49 | Сообщение # 2 |
|
Всевышний
Группа: Модераторы
Сообщений: 475
Статус: Offline
| Если нужно самое простое(и разумеется плохое) решение, то считаем число пустых клеток и подставляем туда поочерёдно все возможные варианты(ссылка на комбинаторные задачи лежит в соседней теме). Если нужен самый оптимальный вариант, то нужно использовать предложенный Д. Кнутом "Dancing Links", но где он описан на русском языке я не в курсе.
Скажем дружно- нафиг нужно!
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 04:00 | Сообщение # 3 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Quote
Д. Кнутом "Dancing Links",
а где ето можно найти!Добавлено (10.11.2008, 21:00)
---------------------------------------------
Quote
ссылка на комбинаторные задачи лежит в соседней теме
чото я не могу найти, подскажы точно где!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Alexander | Дата: Вторник, 11.11.2008, 05:12 | Сообщение # 4 |
|
Всевышний
Группа: Модераторы
Сообщений: 475
Статус: Offline
| http://www.vekua42.edu.ge/Computer/Tasks/perebortasks.htm
http://www.google.ru/search?....refox-a
Скажем дружно- нафиг нужно!
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 05:49 | Сообщение # 5 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Quote
http://www.vekua42.edu.ge/Computer/Tasks/perebortasks.htm
http://www.google.ru/search?....refox-a
чото я ничево там не нашол!
А ты знаеш как зделать ету задачку!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| PROTOSS | Дата: Вторник, 11.11.2008, 06:08 | Сообщение # 6 |
 Старый знакомый
Группа: Пользователи
Сообщений: 42
Статус: Offline
| любопытно а на каком языке сама судоку сделана
Излил душу - Вытри за собой!
|
| |
| |
| Seqular | Дата: Вторник, 11.11.2008, 06:36 | Сообщение # 7 |
 Хранитель
Группа: Администраторы
Сообщений: 859
Статус: Offline
| PROTOSS, Сама судоку не может быть сделана на каком-то языке. Это настольная игра. А вот реализации ее есть и на JAVA и на в принципе любом языке... Мы же не знаем, на каком языке написаны Шахматы. А вообще, правильно было сказано. Нужно подставлять все варианты, возможно рекурсивно. И проверять каждый раз все поле на предмет противоречий.
Поддерживаю также проект сообщество молодых сисадминов
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 06:38 | Сообщение # 8 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Seqular, ти моеш помоч с етой задачкой!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Seqular | Дата: Вторник, 11.11.2008, 06:38 | Сообщение # 9 |
|
Хранитель
Группа: Администраторы
Сообщений: 859
Статус: Offline
| snaper1993, Что именно вызывает затруднения?
Поддерживаю также проект сообщество молодых сисадминов
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 06:39 | Сообщение # 10 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Извеняюсь будем придерыватся норм русского языка:
Seqular, ты можеш помоч с етой задачкой!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Seqular | Дата: Вторник, 11.11.2008, 06:40 | Сообщение # 11 |
|
Хранитель
Группа: Администраторы
Сообщений: 859
Статус: Offline
| snaper1993, правильно будет "Можешь помочь с этой задачкой" =))) Ну неважно
Поддерживаю также проект сообщество молодых сисадминов
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 06:40 | Сообщение # 12 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| Скласть таблицу и подставлять в пропуски числа!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Seqular | Дата: Вторник, 11.11.2008, 06:42 | Сообщение # 13 |
|
Хранитель
Группа: Администраторы
Сообщений: 859
Статус: Offline
| Скласть в таблицу - проще простого. Считал строку из файла, занес в матрицу по цифрам (строкам). А насчет проверки условий - тут целый блок данных надо придумать. Есть идея, но не оптимальная наверное
Поддерживаю также проект сообщество молодых сисадминов
|
| |
| |
| snaper1993 | Дата: Вторник, 11.11.2008, 06:42 | Сообщение # 14 |
|
Бывалый
Группа: Пользователи
Сообщений: 121
Статус: Offline
| я просто с украины и не очень орошо знаю русский!
Извеняйте!
Я - желанный гость Сайта взаимопомощи программистам Pascal А ты?
|
| |
| |
| Alexander | Дата: Вторник, 11.11.2008, 06:43 | Сообщение # 15 |
|
Всевышний
Группа: Модераторы
Сообщений: 475
Статус: Offline
| Quote (PROTOSS) любопытно а на каком языке сама судоку сделана
там только цифры. Игра придумана в англии, а популярность получила в японии.
Quote (snaper1993) А ты знаеш как зделать ету задачку!
snaper1993, насколько я понял, ты из украины. Это объясняет твой русский, который мы принимаем за "албанский", но постарайся пожалуйста ставить в конце предложений нужный знак, а то вопрос от утверждения у тебя трудно отличить. Это очень популярная задача и в англоязычном интернете полно статей на эту тему, странно что в рунете только исходники. Вот пример такой статьи.
Помнится, когда я только учил СИ, я писал такой алгоритм. Провозился с ним 2 дня, а производительность так и осталась низкой. Если найду его, то обязательно выложу. Вот блин, пока писал вы тут уже нафлудили=)
Скажем дружно- нафиг нужно!
Сообщение отредактировал Alexander - Вторник, 11.11.2008, 06:45 |
| |
| |
