| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > алгоритм проверки шахматного хода когда доска |
| Автор: integral 19.2.2009, 16:19 |
| Добрый день, столкнулся с такой задачей: есть шахматная доска, которая представляется в виде графа (клетка - узел графа). т.е. получается узел имеет от 3 до 8 связей; шахматная фигура делает ход, известна начальная и и конечная клетка. Как можно определить, может так походить фигура или нет. Например, давайте рассмотрим случай с ферзем   заранее спасибо UPD кроме класических шахмат, также хотелось бы иметь общее хранилище для Гексагональных шахмат и Шахмат на круглых досках |
| Автор: Akina 19.2.2009, 16:55 | ||
Что за бред? |
| Автор: integral 19.2.2009, 17:44 | ||
а что не нравится? Akina, попрошу аргументировать ваше заявление, а еще лучше - предложить замену такому варианту я вот подумал, может каждую ветку каким-то образом помечать (если хранить связи клетки в хеш-таблице, то можно использовать ключ). а каждая фигура "знает", по какой ветке ей можно перемещатся.... |
| Автор: Akina 19.2.2009, 18:21 | ||||
Очень хочется сказать что-то нехорошее... но ладно, ограничусь аргументацией. Итак, это граф. В котором рёбра соединяют соседствующие клетки. Соответственно единственная информация, добываемая из графа - это соседствуют клетки или нет, ну и при определённом просчёте - какова минимальная длина пути от одной клетки до другой. Направление в рамки графа не втискивается. Возьмём одну из фигур - коня. Он ходит на 2 клетки в каком-либо направлении, затем на одну - в перпендикулярном направлении. Однако у нас нет сведений о направлениях - то есть в рамках графа мы не можем построить ход коня. То есть граф для хранения шахматной доски неприменим.
Велосипед изобретён задолго до вас. Двумерный массив называется. |
| Автор: integral 19.2.2009, 18:31 | ||||
я тоже рассматривал этот вариант, но с ним как-то не вяжются Гексагональные шахматы и Шахматы на круглых досках, ну и еще кое-какие варианты есть... может можна поизощрятс над масивом, но как-то слишком изощрено
например, мы знаем что клетка имеет 6ть соседей, тогда каждый ее сосед хранится как Северный, южный и т.д. думаю, так можна будет сохранить направление при переходе с клетки в клетку... или всетаки другой вариант (мне вариант с графом очень не нравится из-за расхода памяти) |
| Автор: Akina 19.2.2009, 18:36 | ||||
Каждый из вариантов требует своего метода хранения. Определись, какой именно тебя интересует - тогда можно начинать думать. Или, скорее, гуглить.
Это не втискивается в граф. |
| Автор: integral 19.2.2009, 18:53 | ||||
интересуют как-раз несколько вариантов Но хотелось бы иметь единый способ описания доски, а определение возможности перехода фигуры переложить на саму фигуру
почему? например, переход по ветвям север дает прямую линию; если направления описать как перечисление enum {N = 1, NW=2, W=3}, то поворот на 90 градусов можно определить как изменение направлени на 2 ( |W-N|=2 ), на 45 на 1. но это ужастно неоптимально по скорости/памяти. что бы проверить переход ферзем из Е2 в С7 мне нужно найти Е2 и пройтись по всем возможным путям ищя клетку С7.... |
| Автор: Akina 19.2.2009, 21:22 | ||
В таком случае храни не граф, а таблицу в БД. Соответственно структура типа исходное поле, конечное поле, тип перехода. Правда, с типом перехода надо подумать немного (ведь есть двухфигурные ходы ака рокировка). |
| Автор: Silent 19.2.2009, 23:48 |
| Раз уж пошли извращения, то предложу вариант определения возможности хода: Будем хранить в качестве признака достижимости не булево значение, а набор битов. например бит 0 будет сообщать о возможности сходить пешкой, бит 1 - ладьей, бит 2 - слоном, 3 - конем, для ферзя - чтобы обязательно отсутствовал бит 3 тогда, например, для хода из а1 в а8 будет храниться 0b0010 (можно скакнуть только слоном), для а1 в с2 - 0b1000 (можно только конем), а вариант а1-а2 есть 0b0011 (или пешка, или ладья) P.S. Извиняюсь за слон-ладью, все время путаю которая фигура какая есть :-[. Здесь считаю что ладья ходит по вертикали-горизонтали, а слон по диагоналям |
| Автор: Akina 20.2.2009, 00:18 | ||||
ферзь, ладья
король, ферзь, ладья Добавлено через 1 минуту и 52 секунды Но формально возможный ход может быть реально невозможным - ладья не может пойти с а1 на а3, если на а2 стоИт фигура... для учёта этого потребуется четырёхмерная матрица, а это перебор. |
| Автор: integral 20.2.2009, 17:00 | ||||
это понятно, но в памяти то ведь эту структуру надо как-то отображать
это вариант, хранить с каждым направлением возможность перехода по нем фигуры с этой клетки, тогда для проверки возможности достижения конечной клетки перебирать клетки на этом пути и проверять их на отсутствие в них препядствий... как-то так |
| Автор: Earnest 20.2.2009, 18:50 | ||
Это двадцать пятый вопрос - как хранить в памяти. Если ты хочешь иметь обобщенное описание доски - разработай абстрактный интерфейс, который для каждого типа будет реализовываться по своему. Для обычной доски - матрица самое то. Для гексогональной - извращайся по другому. Главное, чтобы интерфейс был ясным. Типа "Хто в этой клетке сидит?", "Хто у нас сосед по грани X", "Может данная фигура совершить ход из клетки А в B?". Главное, чтобы алгоритм был отдельно, а мухи, т.е. имплементация - отдельно. Добавлено через 1 минуту и 4 секунды Хочешь использовать граф - используй, но интерфейс должен формулироваться на языке задачи, а не имплементации. |
| Автор: Lomir 20.2.2009, 23:46 |
| Кстати, 6-ти гранная доска тоже очень хорошо описывается матрицей. Тока там ось Y повернута не на 90 градусов относительно Х, а на 120. Что то похожее на это:  |
| Автор: aram90 27.2.2009, 20:49 |
| Что ж, предложу свой вариант, можни хранить пары чисел для каждой фигуры, (dx,dy), например для коня (-1,-2) (1,-2) (2,-1) (2,1) (1,2) (-1,2) (-2,1) (-2,-1) Это значит что если конь стоит в клетке (x,y), то она может ходить в клетку (x+dx,y+dy), если она, конечно, существует. Только надо хранить еще флажок для каждой фигуры - может ли она сделать несколько шагов, или только одну. Если может делать несколько шагов, значит она может перемещаться в клетку (x+dx*k,y+dy*k) для фиксированной (dx,dy), но еще надо проверять путь на наличие других фигуров. |
