http://habrahabr.ru/post/128137/
Решение может и верное, но выглядит кошмарно
Захотел решить её попроще.
В лучших традициях Оракла -- одним оператором SQL.
Получилось.. Не сразу, но все же получилось. Долго не был уверен, что её вообще можно решить _одним_оператором
Сама задача полностью описана на Википедии
http://ru.wikipedia.org/wiki/%C7%E0%E4%E0%F7%E0_%EE_%E2%EE%F1%FC%EC%E8_%F4%E5%F0%E7%FF%F5
Решено в общем случае -- для доски любого размера. Для доски 8*8 время выполнения 2 секунды, для 9*9 -- 40 секунд. Дальше -- растёт лавинообразно, но так и должно быть.
Я решал принципиальный вопрос -- можно ли это сделать компактно и в общем случае.
Детали реализации оператора SQL:
Клетки внутри оператора адресуются не по именам (a1, b2), а по номерам, начиная с 0.
Для доски 8 на 8 -- от 0 до 63.
Использован алгоритм поиска с возвратом
http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D1%81_%D0%B2%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BE%D0%BC
Но этот алгоритм был усовершенствован, я назвал такой алгоритм "Метод ограниченных ресурсов". Суть его такова:
На доске есть четыре типа ресурсов: вертикали, горизонтали, левые и правые диагонали.
Каждая поставленная фигура на доску "потребляет" одну горизонталь, одну вертикаль, и две диагонали.
Соответственно, следующего ферзя мы будем пробовать ставить на ту клетку, для которого есть оставшиеся незанятые горизонталь, вертикаль и диагонали.
Этим существенно сокращаем время перебора.
Оператор возвращает все возможные решения этой задачи. Для доски 8*8 это 92 решения.
with
T2 (N, L, X, Y, D1, D2, NL)
as (select level - 1, 0
, power (2, trunc ((level - 1) / &&D)), power (2, mod ((level - 1), &D))
, power (2, &D - 1 + trunc ((level - 1) / &D) - mod ((level - 1), &D))
, power (2, trunc ((level - 1) / &D) + mod ((level - 1), &D))
, chr (trunc ((level - 1) / &D) + 97) || to_char (mod ((level - 1), &D) + 1)
from dual connect by level <= power (&D, 2))
, T3 (RN, RL, RX, RY, RD1, RD2, RNL)
as (select * from T2 union all
select N, RL + 1, RX + X, RY + Y, RD1 + D1, RD2 + D2, RNL || ' ' || NL
from T2, T3
where bitand (RX , X ) = 0 and bitand (RY , Y) = 0
and bitand (RD1, D1) = 0 and bitand (RD2, D2) = 0 and N > RN
)
select RNL from T3 where RL = &D - 1;
Комментариев нет:
Отправить комментарий