28 февраля 2013

Задача о восьми ферзях -- одним оператором SQL

Вот, наткнулся на статью "Задача о восьми Ферзях на Oracle SQL"
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;


 

 

 
 

Комментариев нет:

Отправить комментарий