![]() |
|
![]() ![]() ![]() |
|
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
Здрасти, нужно написать прогу, которая на шахматной доске раставит 12 коней так, чтобы все клетки доски были "битые" (под ударом).
Надо использовать двухмерный массив! Результат должен быть примерно таким: | 0 | 0 | * | * | k | 0 | * | k | k | * | * | * | k | k | * | 0 | * | 0 | * | k | * | * | * | * | 0 | * | k | * | * | * | * | 0 | * | 0 | * | * | * | 0 | k | * | 0 | * | 0 | * | * | k | 0 | * | * | 0 | * | * | * | * | 0 | * | k | 0 | k | 0 | * | 0 | k | 0 Где * - поле под ударом, k - конь, 0 - не битое поле (их не должно быть!) Спасибо! |
|||
|
||||
III.nfo |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 18.10.2004 Репутация: 2 Всего: 2 |
По-моему, надо сначала составить схему удара одним конём и "протаскивать" её по полю. Насчёт расположения: кони не должны быть рядом с краем доски (тк бьют на расстояние в клетку от себя) и, скорее всего, должны быть группами. Наверняка будет симметрия, т.е. можно сделать только часть работы и отразить через плоскость симметрии.
Вы уверены, что это возможно? Вот "заливка" одним конём:
Это сообщение отредактировал(а) III.nfo - 25.2.2006, 19:18 |
|||
|
||||
SoWa |
|
|||
![]() Харекришна ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
А потом перебором коней по всей доске проставь.
-------------------- Всем добра ![]() |
|||
|
||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
на, например, перебором...
правда, придется перебирать 64^12 (ну чуть меньше из-за того, что два коня на одной клетке стоять не могут), а отсечений тут пока не видно... ... ага... можно попробовать разделить задачу на две: растановка коней, которые бьют черные клетки, и тех, которые - белые... тогда будет что-то вроде 2*(32^6), что уже обозримо... -------------------- qqq |
|||
|
||||
ДобренькийПапаша |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1278 Регистрация: 14.1.2006 Где: г.Москва Репутация: нет Всего: 7 |
Модератор: пользуемся кнопкой Код - тогда и подсветка будет, и отступы сохранятся...
Добавлено @ 20:51 Довольно эффективный алгоритм.Предполагается, что расположение коней в квадратах одинаково с точностью до поворота на 90 градусов по часовой стрелке. Значения заносятся в двумерный массив. Находим все сочетания из 16 по 3 и для каждого ставим сразу 4 коня, т.е. всего 560 комбинаций. Доска разбивается на четыре части. Это сообщение отредактировал(а) maxim1000 - 25.2.2006, 22:49 -------------------- Меня зовут Себастьян Парейра, торговец чёрным деревом. |
|||
|
||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
и как, находит? (не запускал, под рукой Паскаля нету) вообще-то из симметрии доски совсем не следует, что расположение коней будет симметричным из этого следует, что если какое-торешение есть, то будутеще три решения - повороты на 90 градусов а то, что все они совпадут, т.е. оно будетсимметричным относительно такого поворота, может быть, а может и не быть если какое-то решение так находится - прекрасно просто могут быть пропущены асимметричные решения... -------------------- qqq |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Ну во-первых просто 32*31*30*29*28*27 = 652 458 240 (что уже сносно) - потому как потом любой вариант расстановки по черным полям комбинируется с любым вариантом расстановки по белым полям (которые получаем любым способом, например отразить относительно любой оси). Во-вторых, отсечения все-таки будут (например обработка проверки что осталось полей менее чем 8 * число оставшихся к расстановке коней, и еще кой-какие мелочи) - проверять программно быстрее, чем считать заведомо тухлые варианты (при условии что надо найти все расстановки). -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
maxim1000,
Вот сделал клетки какие бьет конь! |
|||
|
||||
ДобренькийПапаша |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1278 Регистрация: 14.1.2006 Где: г.Москва Репутация: нет Всего: 7 |
Моя прога работает. Не парьте мозги. Вычисляет расположение коней.
Кстати, я кандидат в мастера спорта по шахматам. Про поворачивание доски всё у меня правильно, maxim1000. Забейте, задача решена. -------------------- Меня зовут Себастьян Парейра, торговец чёрным деревом. |
|||
|
||||
mes |
|
|||
любитель ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: нет Всего: 250 |
пойдем от конца. Нам надо чтоб все клетки были битые. Начнем с cамых трудных - ето угловые клетки(a1,а2,b1,b2 и симетричные им)
Так как нельзя поставить коня так чтоб он бил сразу две угловые клетки, мы вынуждены разделить коней (для каждого угла). Теперь у нас получилось три коня на угол. чтоб перекрыть 4 клетки 3-мя конями, надо чтоб как минимум две клетки были в битой зоне одного коня. Такая позиция только одна(а3) на каждый угол. т.е 4 коня из 8 имеют однозначно единственое положение. Oсталось по два на угол и по две клетки(такие как а1,b2) Для каждой из етих клеток существует три позиции коня (например для клетки а1 ето а1,c2,b3). т.е. когда поле занято конём или когда оно битое. можно расмотреть следующее поле.(а3) Тогда мы узнаем что возможных позиций только 2 для каждого коня. Осталось перебрать в каких из етих позиций перекрываются все остальные клетки. ![]() |
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
ДобренькийПапаша,
А у тебя в углах не битые клетки остались и у тебя не видно где кони стоят! МОжешь помочь исправить это? |
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
mes,
Нарисуй визуально если тебе не трудно! |
|||
|
||||
esperant0 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
задача не решаема это не сложно доказать.
для того чтобы закрыть четыре четверки, состоящии из четырех угловых клеток нужно 16 коней -------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: нет Всего: 88 |
esperant0, это ты сказал не подумавши. Погорячился. -------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
esperant0 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
нужно 12 коней, но как их не ставь остануться свободные клетки. среди не угловых -------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: нет Всего: 88 |
B3, C3, C4, C6, C7, D6, E3, F2, F3, F5, F6, G6
-------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
mes |
|
|||
любитель ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: нет Всего: 250 |
[QUOTE=Dov,27.2.2006, 23:42]
Решение у этой задачи есть. Если расставить три коня так что они бьют все четыре угловые клетки, то из 3х возможных вариантов,два (зеркальных) являются решением. При заполнение трех оставшихся углов нужно учитывая правило поворота, расставить коней в те же позиции. Сейчас нет времени для более подробного обяснения. ![]() Попозже постараюсь более подробно. |
|||
|
||||
esperant0 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
да промазал я.
![]() -------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
Dov,
Вот теперь прогу надо написать, которая так раставит! Добавлено @ 08:58 Dov, У тебя не все клетки под ударом! |
|||
|
||||
mes |
|
|||
любитель ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: нет Всего: 250 |
||||
|
||||
mes |
|
|||
любитель ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: нет Всего: 250 |
Алгоритм программы такой:
1. Раставляешь коней (любое кол-во) так, чтобы 4 угловые клетки во всех 4-х углах были биты. Получится следуещее: Потом убираешь последователно в каждом углу одного "лишнего" ( того, при убирании которого, все клетки всего поля будут биты)
В конце концов получится "рисунок" как у Dova При таком алгоритме кол-во проверок минимально (в удачном случае находит решение после 8 хода, при неудачном с 20 хода) |
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: нет Всего: 88 |
Конечно, не все. На некоторых 'лошади' стоят(8 штук). Если хочешь поставить их под бой тоже, прийдётся добавить ущё 2 коника. Ну, так дерзай, proger. Видишь, и ник у тебя подходящий. ![]() -------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
ДобренькийПапаша |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1278 Регистрация: 14.1.2006 Где: г.Москва Репутация: нет Всего: 7 |
Proger, я написал прогу, там на первой странице. Если немного не так, тогда подправь.
-------------------- Меня зовут Себастьян Парейра, торговец чёрным деревом. |
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: нет Всего: 88 |
ДобренькийПапаша, плагиатом занимаешься, нехорошо. А может быть тебя зовут А.К.Сахаров из Барнаула? -------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
Dov, Спасибо за помощь!
|
|||
|
||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
mes, А прогу нАПИСАТЬ МОЖЕШЬ, А ТО У МЕНЯ НЕ ПОЛУЧАЕТСЯ!
|
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: нет Всего: 88 |
proger, вот, тупо перевёл на С++ ту прогу, которая на паскале.
Видок у неё ещё тот, но зато работает. А красоту сам наведёш, если захочешь.
-------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
mes |
|
||||
любитель ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: нет Всего: 250 |
Вариантов для написания проги очень много. В зависимости от того что тебе надо. Думаю, что тебе важно, чтоб компьютер перебрал все возможные варианты независимо от того являются ли они симметричными. Чтоб проверять только те позиции, которые имеет смысл, я разбил задачу на две части. Первая: Как известно конь не может бить угловые клетки в разных углах. Таких клеток 16. (4*4) Вопрос: Могут ли бить 12 коней ети 16 клеток? Каждая клетка может бить "бита" не более чем с девяти позиций: (8 битых +1 когда клетка занята конём) Конь может бить две соседние клетки, только если они рассположены по диагонали
По результату программы видно, что минимальное кол-во коней для перекрытия угловых клеток нужно 12 (нас это устраивает) 4 Коня имеют 5 позиций, другие 4 - 3позиции, и еше 4 Коня могут находится только в 1 положении, значит расставлять нужно только 8 коней. На основе етих данных я создал, список позиций, и методом перебора проверил есть ли среди вариантов такие, которые бы били бы все клетки.
В результате два варианта (зеркальных) где группа из трех коней, симметрична относительно поворота. При проверке во второй части перебираются 50625 позиций. Если учитывать симметрию относительно поворота, (т.е для одного угла) , то сократится приблизительно до 15 позиций. Надеюсь тебе ето поможет. ![]() P.S. Прошу прощение за малое кол-во комментариев и неформатированный код. ![]() Это сообщение отредактировал(а) mes - 9.3.2006, 18:37 Присоединённый файл ( Кол-во скачиваний: 29 ) ![]() |
||||
|
|||||
proger |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 400 Регистрация: 10.10.2004 Репутация: нет Всего: 1 |
Спасибо!
|
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |