Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Непростая шахматная задачка
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию Непростая шахматная задачка - 17.02.2005, 07:53

Я еще ученик, по этому участвую на олимпиадах, на одной области попалась задача: На доске задано расположение пешек, может ли оно получиться в процессе игры?
1. Решение этой задачи не рискнуло выложить даже жюри.
2. Чисто с точки зрения математики эта задача (писать на Pas please) просто не МОЖЕТ уложиться в 2 секунды, но можетя я где-то ошибся в расчетах.
3. В этой задаче очень много крайних случаев (возможно ли их все рассмотреть)
4. Пожалуйста, помогите ее решить, я на нее уже не одни сутки убил как на Паскале, так и на листочке, и все равно сам же придумываю случаи, на которых мое решение слетает. Должно быть общее решение!
Помогите!
Ответить с цитированием
  (#2 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию Непростая шахматная задачка - 17.02.2005, 07:53

Я еще ученик, по этому участвую на олимпиадах, на одной области попалась задача: На доске задано расположение пешек, может ли оно получиться в процессе игры?
1. Решение этой задачи не рискнуло выложить даже жюри.
2. Чисто с точки зрения математики эта задача (писать на Pas please) просто не МОЖЕТ уложиться в 2 секунды, но можетя я где-то ошибся в расчетах.
3. В этой задаче очень много крайних случаев (возможно ли их все рассмотреть)
4. Пожалуйста, помогите ее решить, я на нее уже не одни сутки убил как на Паскале, так и на листочке, и все равно сам же придумываю случаи, на которых мое решение слетает. Должно быть общее решение!
Помогите!
Ответить с цитированием
  (#3 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 17.02.2005, 23:02

Уточнение: помимо пешек на поле находятся и остальные фигуры? Т.е. они участвуют в игре?
Ответить с цитированием
  (#4 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 17.02.2005, 23:02

Уточнение: помимо пешек на поле находятся и остальные фигуры? Т.е. они участвуют в игре?
Ответить с цитированием
  (#5 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 18.02.2005, 05:22

Во входном файле лишь положение пешек (подразумевается, что остальные фигуры есть, но не показаны)
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 18.02.2005, 05:22

Во входном файле лишь положение пешек (подразумевается, что остальные фигуры есть, но не показаны)
Ответить с цитированием
  (#7 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 18.02.2005, 08:12

Если остальные фигуры "подразумеваются", то общего решения нет, потому что невозможно в этом случае отследить перемещение пешек по диагонали... На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам (т.е. пешки не стоят на первом и последнем полях, количество пешек одного цвета меньше или равно восьми). Решать задачу имеет смысл, если:
1. В игре участвуют только пешки.
2. Указано положение всех фигур.
Но в последнем случае, решение гарантировано не уложится в 2 секунды (слишком много возможных ходов)...
PS. И вообще, приведи полный текст условия.
Ответить с цитированием
  (#8 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 18.02.2005, 08:12

Если остальные фигуры "подразумеваются", то общего решения нет, потому что невозможно в этом случае отследить перемещение пешек по диагонали... На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам (т.е. пешки не стоят на первом и последнем полях, количество пешек одного цвета меньше или равно восьми). Решать задачу имеет смысл, если:
1. В игре участвуют только пешки.
2. Указано положение всех фигур.
Но в последнем случае, решение гарантировано не уложится в 2 секунды (слишком много возможных ходов)...
PS. И вообще, приведи полный текст условия.
Ответить с цитированием
  (#9 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 18.02.2005, 10:07

1. Условие я рассказал как есть, Положение фигур не дано, но никто не сказал, что оба игрока играют разумно (т.е. не подставляют фигуры под удар)
2. Насчет невозможности решения ты не прав.. У меня только вчера пришла мощная идея, которую я почти реализовал..
3. На области в большинстве тестов предполагался критерий мобильности (т.е. кол-во возможных поеданий) 7 а я говорю как раз о крайних случаях с неполной мобильностью фигур..
4. Уфф... она решилась (УРРА уложилась во время!) там не надо перебирать все ходы. Идея моего решения (может кто-то лучше найдет?): считаем критерий мобильности (максимальный за игру) по ходам (т.е. ищем ходы, которые не уменьшают мобильность), а потом уже с конкретным критерием мобильности считаем рекурсивно взятия, на всех извращенных тестах пробовал

Цитата:
На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам
Это неправда.. подумай сам почему..

Цитата:
Если остальные фигуры "подразумеваются", то общего решения нет, потому что невозможно в этом случае отследить перемещение пешек по диагонали
Это тоже неправда (хотя код вышел немаленький...) [/quote]
Ответить с цитированием
  (#10 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 18.02.2005, 10:07

1. Условие я рассказал как есть, Положение фигур не дано, но никто не сказал, что оба игрока играют разумно (т.е. не подставляют фигуры под удар)
2. Насчет невозможности решения ты не прав.. У меня только вчера пришла мощная идея, которую я почти реализовал..
3. На области в большинстве тестов предполагался критерий мобильности (т.е. кол-во возможных поеданий) 7 а я говорю как раз о крайних случаях с неполной мобильностью фигур..
4. Уфф... она решилась (УРРА уложилась во время!) там не надо перебирать все ходы. Идея моего решения (может кто-то лучше найдет?): считаем критерий мобильности (максимальный за игру) по ходам (т.е. ищем ходы, которые не уменьшают мобильность), а потом уже с конкретным критерием мобильности считаем рекурсивно взятия, на всех извращенных тестах пробовал

Цитата:
На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам
Это неправда.. подумай сам почему..

Цитата:
Если остальные фигуры "подразумеваются", то общего решения нет, потому что невозможно в этом случае отследить перемещение пешек по диагонали
Это тоже неправда (хотя код вышел немаленький...) [/quote]
Ответить с цитированием
  (#11 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 19.02.2005, 00:05

Цитата:
<div class='quotetop'>Цитата
Цитата:
На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам
Это неправда.. подумай сам почему..[/quote]
Согласен, не учёл, что количество фигур (и перемещений по диагонали) ограничено. В принципе, от этого можно оттолкнуться.
Ответить с цитированием
  (#12 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 19.02.2005, 00:05

Цитата:
<div class='quotetop'>Цитата
Цитата:
На самом деле, я думаю, в таком случае возможна любая ситуация, которая не противоречит правилам
Это неправда.. подумай сам почему..[/quote]
Согласен, не учёл, что количество фигур (и перемещений по диагонали) ограничено. В принципе, от этого можно оттолкнуться.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 20.02.2005, 00:04

Ну... если я правильно понимаю условие задачи от этого и нужно отталкиваться. Т.Е. основная сложность задачи состоит не в получении рекурсирвного положения из пешек (и проверка хватит ли им ходов (критерия мобильности) на то чтобы вернуться в исходное положение), а собственно в вычислении критерия мобильности (иначе эту задачу на олимпиаде хоть кто-нить да решил, потому что она получилась бы сильно простой...)
Просто случай например
00000000 2-черная пешка,1 -белая
22222222 очевидно невозможен из-за критерия мобильности
00000000 т.е белые сделали как минимум 3 взятия, а черные
00000000 могли ходить лишь 2 конями, хотя вроде бы
00100000 данная ситуация соответствует правилам передвижения
00101000
10101011
00000000
Кроме того возможны случаи, когда на возвращение в исходное положение не хватит "времени" (т.е. опять же минимальное число ходов больше критерия мобильности)
Ответить с цитированием
  (#14 (permalink)) Старый
Knight of Shadows Knight of Shadows вне форума
Новичок
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.02.2005
По умолчанию 20.02.2005, 00:04

Ну... если я правильно понимаю условие задачи от этого и нужно отталкиваться. Т.Е. основная сложность задачи состоит не в получении рекурсирвного положения из пешек (и проверка хватит ли им ходов (критерия мобильности) на то чтобы вернуться в исходное положение), а собственно в вычислении критерия мобильности (иначе эту задачу на олимпиаде хоть кто-нить да решил, потому что она получилась бы сильно простой...)
Просто случай например
00000000 2-черная пешка,1 -белая
22222222 очевидно невозможен из-за критерия мобильности
00000000 т.е белые сделали как минимум 3 взятия, а черные
00000000 могли ходить лишь 2 конями, хотя вроде бы
00100000 данная ситуация соответствует правилам передвижения
00101000
10101011
00000000
Кроме того возможны случаи, когда на возвращение в исходное положение не хватит "времени" (т.е. опять же минимальное число ходов больше критерия мобильности)
Ответить с цитированием
  (#15 (permalink)) Старый
ChronicK06 ChronicK06 вне форума
Member
 
Сообщений: 16
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2005
По умолчанию 06.02.2006, 01:56

Я думаю проверку на количество взятий можно сделать так:
проверить сколько фигур соперника могут сделать ход с их начальных позиций + сколько пешек "исчезло" у соперника = количество возможных взятий (конечно король не в счёт)
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
шахматная доска Andrew2012 Visual C++ 2 13.02.2012 11:59
задачка C++ ltony Вопросы начинающих программистов 1 04.02.2012 05:11
шахматная задача (2 ладьи) ilyas_sam Prolog 0 12.06.2010 17:57
задачка Tina Prolog 2 06.04.2010 09:50
Непростая задачка на логику Sliderz Prolog 3 29.11.2009 00:02
Задачка Julijanna Задания за деньги 8 30.09.2009 21:21
Задачка Шахматная доска 4х4, на ней 4 коня Gizbo Prolog 0 10.05.2009 12:55
задачка на PHP Alexandr_14 PHP 4 06.02.2008 02:22
Шахматная задача определение хода Knight of Shadows Pascal 6 27.02.2005 04:20
Задачка про чай MiHanick Prolog 1 12.12.2004 12:23



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов