![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы
![]() |
Поиск в этой теме
![]() |
![]() |
#1 |
Форумчанин
Регистрация: 30.06.2012
Сообщений: 145
|
![]()
Доброго времени суток, уважаемые эксперты.
Есть головоломка где нужно расставить шарики (аналог однопалубных кораблей в морском бое). Снизу и справа пишется как в японском кроссворде количество шариков в столбце или строке. Так же на поле помимо шариков есть стрелочки, которые указывают в каком направлении есть шарик дальше по строке или столбцу или диагонали. Прикасаться шарики не могут. Задание картинкой прикладываю ниже. Не могу придумать алгоритм решения. Если делать через бектрекинг - это очень долго и сложно. Может есть варианты попроще? Не приходит ничего на ум, к сожалению. Если же только бектрекинг, то может есть варианты его упрощения? Вариант с подставлением сразу правильного ответа - не подходит по заданию. Саму головоломку уже реализовал, а вот над авто решением думаю. Заранее спасибо за советы. Последний раз редактировалось Armageddets; 08.05.2020 в 17:13. |
![]() |
![]() |
![]() |
#2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,429
|
![]()
Тоже ничего особо годного не пришло в голову. Если делать так, как сказано в тексте? Сначала вычеркнуть все клеточки, где шарика точно быть не может. Для всех строк, в которых по одному шарику и стоят горизонтальные стрелки, вычеркнуть клеточки за стрелкой. Тоже самое для столбцов. Затем второй случай, когда у стрелочки возможны два варианта расположения шарика, то вычеркнуть заведомо неподходящие соседние клетки. Затем начинать поиск решения через бектрекинг. Выбрать ту стрелочку, у которой осталось минимальное количество вариантов расстановки шарика. Продолжать поиск, пока не будут выбраны шарики для всех стрелок. Думаю, что на этот момент останется мало свободных клеток для расстановки оставшихся шариков.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись
![]() |
![]() |
![]() |
![]() |
#3 |
фрилансер, препод.
Участник клуба
Регистрация: 11.10.2019
Сообщений: 1,041
|
![]()
можно попробовать методом в лоб: имеется 49 переменных (клеток)
для них составляется 14 уравнений (7 для строк + 7 для столбцов). Уравнения решаются каким-нибудь методом. Имеются также уточняющие условия (стрелки, соприкосновения) - для выбора из нескольких решений нужного Последний раз редактировалось Алексей1153; 09.05.2020 в 20:55. |
![]() |
![]() |
![]() |
#4 |
Форумчанин
Регистрация: 30.06.2012
Сообщений: 145
|
![]()
Спасибо за советы. Начал делать алгоритм бек трекинга. Начинают шарики расставляться. Первые 3 становятся, а на четвертом нет места для него подходящего и он возвращает алгоритм на шаг назад, после чего третий шарик стает почему-то на то же место и четвертый опять не может никуда стать.
Помогите найти ошибку, если есть время. У меня подозрение на: 1) либо я когда делаю доступным ход для первых шариков при нахождении стрелок где-то напартачил 2) либо в самом алгоритме бек трекинга беда. Может мне дополнительная проверка нужна для скачка не на 1 шаг назад, а на целых 2 и более. То есть с логикой алгоритма натупил. Вот алгоритм бек трекинга (весь проект тоже прилагаю): Код:
|
![]() |
![]() |
![]() |
#5 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,429
|
![]()
Чуть-чуть изменил код. Теперь первые 4 шарика ставятся на поле. Удалил таймер и сделал отрисовку по требованию. Чуть-чуть изменил графику. Вместо цифр используется свой тип, чтобы код легче читался. Закомментированный код не менял. Баги конечно же могли остаться.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись
![]() |
![]() |
![]() |
![]() |
#6 |
Форумчанин
Регистрация: 30.06.2012
Сообщений: 145
|
![]()
Спасибо огромное!
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм решения головоломки Акари (Akari LightUp Фонари) | Armageddets | Общие вопросы Delphi | 4 | 18.06.2017 10:51 |
Подскажите алгоритм решения | Nickolay0512 | Общие вопросы C/C++ | 12 | 07.10.2014 23:26 |
Алгоритм решения задачи | Amet13 | Помощь студентам | 1 | 21.04.2012 13:16 |
Алгоритм решения сравнений | outaccess | Помощь студентам | 0 | 02.05.2011 14:55 |
Алгоритм решения | Naruto63 | Помощь студентам | 6 | 20.09.2009 22:47 |