Задача про 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):-