Добрый день,
столкнулся с такой задачей: есть шахматная доска, которая представляется в виде графа (клетка - узел графа). т.е. получается узел имеет от 3 до 8 связей; шахматная фигура делает ход, известна начальная и и конечная клетка.  Как можно определить, может так походить фигура или нет. Например, давайте рассмотрим случай с ферзем   
заранее спасибо

UPD кроме класических шахмат, также хотелось бы иметь общее хранилище для Гексагональных шахмат и Шахмат на круглых досках

Это сообщение отредактировал(а) integral - 19.2.2009, 18:55

Что за бред?

а что не нравится?
Akina, попрошу аргументировать ваше заявление, а еще лучше - предложить замену такому варианту

я вот подумал, может каждую ветку каким-то образом помечать (если хранить связи клетки в хеш-таблице, то можно использовать ключ). а каждая фигура "знает", по какой ветке ей можно перемещатся.... 

Это сообщение отредактировал(а) integral - 19.2.2009, 17:45

Очень хочется сказать что-то нехорошее... но ладно, ограничусь аргументацией.

Итак, это граф. В котором рёбра соединяют соседствующие клетки. Соответственно единственная информация, добываемая из графа - это соседствуют клетки или нет, ну и при определённом просчёте - какова минимальная длина пути от одной клетки до другой. Направление в рамки графа не втискивается. Возьмём одну из фигур - коня. Он ходит на 2 клетки в каком-либо направлении, затем на одну - в перпендикулярном направлении. Однако у нас нет сведений о направлениях - то есть в рамках графа мы не можем построить ход коня. То есть граф для хранения шахматной доски неприменим.


Велосипед изобретён задолго до вас. Двумерный массив называется.

я тоже рассматривал этот вариант, но с ним как-то не вяжются Гексагональные шахматы и Шахматы на круглых досках, ну и еще кое-какие варианты есть... может можна поизощрятс над масивом, но как-то слишком изощрено


например, мы знаем что клетка имеет 6ть соседей, тогда каждый ее сосед хранится как Северный, южный и т.д. думаю, так можна будет сохранить направление при переходе с клетки в клетку...
 или всетаки другой вариант (мне вариант с графом очень не нравится из-за расхода памяти)


Это сообщение отредактировал(а) integral - 19.2.2009, 18:34

Каждый из вариантов требует своего метода хранения. Определись, какой именно тебя интересует - тогда можно начинать думать. Или, скорее, гуглить.


Это не втискивается в граф.

интересуют как-раз несколько вариантов Но хотелось бы иметь единый способ описания доски, а определение возможности перехода фигуры переложить на саму фигуру


почему? например, переход по ветвям север дает прямую линию; если направления описать как перечисление enum {N = 1, NW=2, W=3}, то поворот на 90 градусов можно определить как изменение направлени на 2 ( |W-N|=2 ), на 45 на 1. но это ужастно неоптимально по скорости/памяти. что бы проверить переход ферзем из Е2 в С7 мне нужно найти Е2 и пройтись по всем возможным путям ищя клетку С7....

Это сообщение отредактировал(а) integral - 19.2.2009, 18:56

В таком случае храни не граф, а таблицу в БД.
Соответственно структура типа исходное поле, конечное поле, тип перехода. Правда, с типом перехода надо подумать немного (ведь есть двухфигурные ходы ака рокировка).

Раз уж пошли извращения, то предложу вариант определения возможности хода:
Будем хранить в качестве признака достижимости не булево значение, а набор битов.
например бит 0 будет сообщать о возможности сходить пешкой, бит 1 - ладьей, бит 2 - слоном, 3 - конем, для ферзя - чтобы обязательно отсутствовал бит 3
тогда, например, для хода из а1 в а8 будет храниться 0b0010 (можно скакнуть только слоном), для а1 в с2 - 0b1000 (можно только конем), а вариант а1-а2 есть 0b0011 (или пешка, или ладья)

P.S. Извиняюсь за слон-ладью, все время путаю которая фигура какая есть :-[. Здесь считаю что ладья ходит по вертикали-горизонтали, а слон по диагоналям

ферзь, ладья


король, ферзь, ладья

Добавлено через 1 минуту и 52 секунды
Но формально возможный ход может быть реально невозможным - ладья не может пойти с а1 на а3, если на а2 стоИт фигура... для учёта этого потребуется четырёхмерная матрица, а это перебор.

это понятно, но в памяти то ведь эту структуру надо как-то отображать



это вариант, хранить с каждым направлением возможность перехода по нем фигуры с этой клетки, тогда для проверки возможности достижения конечной клетки перебирать клетки на этом пути и проверять их на отсутствие в них препядствий... как-то так

Это двадцать пятый вопрос - как хранить в памяти. Если ты хочешь иметь обобщенное описание доски - разработай абстрактный интерфейс, который для каждого типа будет реализовываться по своему. Для обычной доски - матрица самое то. Для гексогональной - извращайся по другому. Главное, чтобы интерфейс был ясным. Типа "Хто в этой клетке сидит?", "Хто у нас сосед по грани X", "Может данная фигура совершить ход из клетки А в B?". Главное, чтобы алгоритм был отдельно, а мухи, т.е. имплементация - отдельно.

Добавлено через 1 минуту и 4 секунды
Хочешь использовать граф - используй, но интерфейс должен формулироваться на языке задачи, а не имплементации.

Кстати, 6-ти гранная доска тоже очень хорошо описывается матрицей.
Тока там ось Y повернута не на 90 градусов относительно Х, а на 120.

Что то похожее на это:



Это сообщение отредактировал(а) Lomir - 20.2.2009, 23:47

Что ж, предложу свой вариант, можни хранить пары чисел для каждой фигуры, (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), но еще надо проверять путь
на наличие других фигуров.