Задача про N королев

Задача про N королев формулюється наступним чином. Потрібно розставити на шахматній досці Nкоролев таким чином , щоб ніякі дві королеви не змогли побити одна одну згідно правил гри в шахи. Тому, ніякі дві королеви не можуть бути розміщені в одному ряду: по вертикалі , горизонталі , діагоналі.

Для вирішення задачі, пронумеруємо вертикальні та горизонтальні рядки шахматної доски від 1 до N. Для нумерації діагоналі , розділимо їх на два типи таким чином , щоб діагональ специфицифікувалась типом і номером, які обчислюються із її вертикальних і горизонтальних рядів:

Diagonal = N + Column - Row (type 1)

Diagonal = Row + Column - 1 (type 2)

Якщо ви дивитесь на шахматну доску на ряд 1 по горизонталі та колонку 1 по вертикалі з лівої сторони , тоді Tun1розділяє діагоналлю клітку як символ похилої риски вліво (\), а Tun2- вправо (/). Малюнок9.5. демонструє нумерацію діагоналей Tunу2 на досці 4х4.

| 1 | 2 | 3 | 4 |

1 | 1 | 2 | 3 | 4 |

2 | 2 | 3 | 4 | 5 |

3 | 3 | 4 | 5 | 6 |

4 | 4 | 5 | 6 | 7 |

Мал. 9.5. Нумерація діагоналей Типу2 на шахматній досці.

Для вирішення задачі про N королев на Пролозі, ми повинні вміти встановлювати який рядок, колонка і діагональ ще не зайняті , а також вміти відмічати де вже розміщені королеви.

Позицію королеви можна описати за допомогою зазначення номера рядка та колонки:

queen = q(integer, integer) .

Такий опис задає позицію одної королеви. Для фіксації більшої кількості позицій, можемо використать список:

queens = queen* .

Нам, також, будуть потрібні декілька списків чисел, які будуть визначати ще не зайняті королевами ряди , колонки та діагоналі. Ці списки опишемо наступним чином:

freelist = integer* .

Шахматну дошку зможемо обробляти як єдиний об'єкт, якщо зробимо наступний опис:

board = board(queens, freelist,freelist,freelist,freelist)

де чотири аргументи типу freelistзадають відповідно ряди, колонки та діагоналі Типу1і Типу2.

Наприклад, шахматну доску 4х4 без королев можна задать:

board([],[1,2,3,4],[1,2,3,4],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7]),

а шахматну доску з однією королевою в самому лівому верхньому кутку опише предикат:

board([q(1,1)],[2,3,4],[2,3,4],[1,2,3,4,5,6,7],[2,3,4,5,6,7])

Накінець, ми можемо вирішити поставлену задачу, описуючи відношення між пустою доскою і доскою з N королевами. Визначимо предикат placeN(integer, board, board) з двома фразами. Королеви розташовуються одна за одною, поки кожний рядок і кожна колонка не будуть зайняті. Тому в першій фразі два списки freerows і freecols - пусті:

placeN(_, board(D,[],[],X,Y), board(D,[],[],X,Y)):- !.

placeN(_, Board1, Rеsult):-