чОткий форум
20.03.21 © 2024 Программизд 02
 
Мобильная версия    Контакт    Правила    FAQ    Помощь
Гость
Войти | Регистрация | Профиль | Очистить
Новые сообщения | Избранное
Форумы | Участники | Статистика | Поиск
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо
Сообщения: 57 / Страницы: 1  2  3  все  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2285
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Будем. но позже
 
Рейтинг: 0 / 0
15.09.2020, 15:13
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2289
блохастые утки Скрыть профиль Поместить в игнор-лист
блохастые утки
Гость
Дырокол  15.09.2020, 15:13
2285
Будем. но позже
Фпезду всякую очкарийную поеботу.
 
Рейтинг: 0 / 0
15.09.2020, 15:14
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2299
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
блохастые утки  15.09.2020, 15:14
2289
Дырокол  15.09.2020, 15:13
2285
Будем. но позже
Фпезду всякую очкарийную поеботу.
мы будем делоть робота, который будет делоть за нас
 
Рейтинг: 0 / 0
15.09.2020, 15:18
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2300
блохастые утки Скрыть профиль Поместить в игнор-лист
блохастые утки
Гость
Дырокол  15.09.2020, 15:18
2299
блохастые утки  15.09.2020, 15:14
2289
Дырокол  15.09.2020, 15:13
2285
...
Фпезду всякую очкарийную поеботу.
мы будем делоть робота, который будет делоть за нас
ну незнаю, робот может спиться как бендор в футураме
 
Рейтинг: 0 / 0
15.09.2020, 15:19
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2307
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
блохастые утки  15.09.2020, 15:19
2300
Дырокол  15.09.2020, 15:18
2299
блохастые утки  15.09.2020, 15:14
2289
...
мы будем делоть робота, который будет делоть за нас
ну незнаю, робот может спиться как бендор в футураме
бендора заменит кисо воробьянинов
 
Рейтинг: 0 / 0
15.09.2020, 15:22
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2533
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
задачу будем решать на scheme с чистого листа, т.е. не пользуясь никакими эдванс-фичами языка. весь инструментарий будем создавать себе по ходу дела сами
за основу мы возьмем формулировку задачи 2.42 и шаблон решения из книжки SICP, дополнив недостающие там звенья

итак, В «задаче о восьми ферзях» спрашивается, как расставить на шахматной доске восемь ферзей так, чтобы ни один из них не бил другого (то есть никакие два ферзя не должны находиться на одной вертикали, горизонтали или диагонали).
одно из возможных решений показано на рисунке

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

этот подход можно сформулировать рекурсивно: предположим, что мы уже породили последовательность из всех возможных способов разместить k − 1 ферзей на первых k − 1 вертикалях доски. Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k-й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k-й вертикали не бьется ни одним из остальных. Продолжая этот процесс, мы породим не просто одно решение, а все решения этой задачи.
pasted_image.png
Изменено: 16.09.2020, 21:56 - Дырокол
Рейтинг: 0 / 0
16.09.2020, 21:55
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2662
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
начнем с простого
empty-board представляет пустое множество позиций
заодно определим и nil как пустой список
Код
1.
(define nil '())
Код
1.
(define empty-board nil)
 
Рейтинг: 0 / 0
17.09.2020, 16:47
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2663
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
раскраска кода тут конечно говно
нужно будет подумать и сделать что-нибудь уже с этим, ато никакого эстетического удовольствия
 
Рейтинг: 0 / 0
17.09.2020, 16:48
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2690
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
да фиг знает что дальше.
ну давайте пойдем с конца, от тестирования.

для доски 8 на 8 в итоге будут такие расстановки:
Спойлер
'(((1 1) (5 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8))
  ((1 1) (6 2) (8 3) (3 4) (7 5) (4 6) (2 7) (5 8))
  ((1 1) (7 2) (4 3) (6 4) (8 5) (2 6) (5 7) (3 8))
  ((1 1) (7 2) (5 3) (8 4) (2 5) (4 6) (6 7) (3 8))
  ((2 1) (4 2) (6 3) (8 4) (3 5) (1 6) (7 7) (5 8))
  ((2 1) (5 2) (7 3) (1 4) (3 5) (8 6) (6 7) (4 8))
  ((2 1) (5 2) (7 3) (4 4) (1 5) (8 6) (6 7) (3 8))
  ((2 1) (6 2) (1 3) (7 4) (4 5) (8 6) (3 7) (5 8))
  ((2 1) (6 2) (8 3) (3 4) (1 5) (4 6) (7 7) (5 8))
  ((2 1) (7 2) (3 3) (6 4) (8 5) (5 6) (1 7) (4 8))
  ((2 1) (7 2) (5 3) (8 4) (1 5) (4 6) (6 7) (3 8))
  ((2 1) (8 2) (6 3) (1 4) (3 5) (5 6) (7 7) (4 8))
  ((3 1) (1 2) (7 3) (5 4) (8 5) (2 6) (4 7) (6 8))
  ((3 1) (5 2) (2 3) (8 4) (1 5) (7 6) (4 7) (6 8))
  ((3 1) (5 2) (2 3) (8 4) (6 5) (4 6) (7 7) (1 8))
  ((3 1) (5 2) (7 3) (1 4) (4 5) (2 6) (8 7) (6 8))
  ((3 1) (5 2) (8 3) (4 4) (1 5) (7 6) (2 7) (6 8))
  ((3 1) (6 2) (2 3) (5 4) (8 5) (1 6) (7 7) (4 8))
  ((3 1) (6 2) (2 3) (7 4) (1 5) (4 6) (8 7) (5 8))
  ((3 1) (6 2) (2 3) (7 4) (5 5) (1 6) (8 7) (4 8))
  ((3 1) (6 2) (4 3) (1 4) (8 5) (5 6) (7 7) (2 8))
  ((3 1) (6 2) (4 3) (2 4) (8 5) (5 6) (7 7) (1 8))
  ((3 1) (6 2) (8 3) (1 4) (4 5) (7 6) (5 7) (2 8))
  ((3 1) (6 2) (8 3) (1 4) (5 5) (7 6) (2 7) (4 8))
  ((3 1) (6 2) (8 3) (2 4) (4 5) (1 6) (7 7) (5 8))
  ((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (6 8))
  ((3 1) (7 2) (2 3) (8 4) (6 5) (4 6) (1 7) (5 8))
  ((3 1) (8 2) (4 3) (7 4) (1 5) (6 6) (2 7) (5 8))
  ((4 1) (1 2) (5 3) (8 4) (2 5) (7 6) (3 7) (6 8))
  ((4 1) (1 2) (5 3) (8 4) (6 5) (3 6) (7 7) (2 8))
  ((4 1) (2 2) (5 3) (8 4) (6 5) (1 6) (3 7) (7 8))
  ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (1 7) (5 8))
  ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (5 7) (1 8))
  ((4 1) (2 2) (7 3) (5 4) (1 5) (8 6) (6 7) (3 8))
  ((4 1) (2 2) (8 3) (5 4) (7 5) (1 6) (3 7) (6 8))
  ((4 1) (2 2) (8 3) (6 4) (1 5) (3 6) (5 7) (7 8))
  ((4 1) (6 2) (1 3) (5 4) (2 5) (8 6) (3 7) (7 8))
  ((4 1) (6 2) (8 3) (2 4) (7 5) (1 6) (3 7) (5 8))
  ((4 1) (6 2) (8 3) (3 4) (1 5) (7 6) (5 7) (2 8))
  ((4 1) (7 2) (1 3) (8 4) (5 5) (2 6) (6 7) (3 8))
  ((4 1) (7 2) (3 3) (8 4) (2 5) (5 6) (1 7) (6 8))
  ((4 1) (7 2) (5 3) (2 4) (6 5) (1 6) (3 7) (8 8))
  ((4 1) (7 2) (5 3) (3 4) (1 5) (6 6) (8 7) (2 8))
  ((4 1) (8 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8))
  ((4 1) (8 2) (1 3) (5 4) (7 5) (2 6) (6 7) (3 8))
  ((4 1) (8 2) (5 3) (3 4) (1 5) (7 6) (2 7) (6 8))
  ((5 1) (1 2) (4 3) (6 4) (8 5) (2 6) (7 7) (3 8))
  ((5 1) (1 2) (8 3) (4 4) (2 5) (7 6) (3 7) (6 8))
  ((5 1) (1 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8))
  ((5 1) (2 2) (4 3) (6 4) (8 5) (3 6) (1 7) (7 8))
  ((5 1) (2 2) (4 3) (7 4) (3 5) (8 6) (6 7) (1 8))
  ((5 1) (2 2) (6 3) (1 4) (7 5) (4 6) (8 7) (3 8))
  ((5 1) (2 2) (8 3) (1 4) (4 5) (7 6) (3 7) (6 8))
  ((5 1) (3 2) (1 3) (6 4) (8 5) (2 6) (4 7) (7 8))
  ((5 1) (3 2) (1 3) (7 4) (2 5) (8 6) (6 7) (4 8))
  ((5 1) (3 2) (8 3) (4 4) (7 5) (1 6) (6 7) (2 8))
  ((5 1) (7 2) (1 3) (3 4) (8 5) (6 6) (4 7) (2 8))
  ((5 1) (7 2) (1 3) (4 4) (2 5) (8 6) (6 7) (3 8))
  ((5 1) (7 2) (2 3) (4 4) (8 5) (1 6) (3 7) (6 8))
  ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (4 7) (8 8))
  ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (8 7) (4 8))
  ((5 1) (7 2) (4 3) (1 4) (3 5) (8 6) (6 7) (2 8))
  ((5 1) (8 2) (4 3) (1 4) (3 5) (6 6) (2 7) (7 8))
  ((5 1) (8 2) (4 3) (1 4) (7 5) (2 6) (6 7) (3 8))
  ((6 1) (1 2) (5 3) (2 4) (8 5) (3 6) (7 7) (4 8))
  ((6 1) (2 2) (7 3) (1 4) (3 5) (5 6) (8 7) (4 8))
  ((6 1) (2 2) (7 3) (1 4) (4 5) (8 6) (5 7) (3 8))
  ((6 1) (3 2) (1 3) (7 4) (5 5) (8 6) (2 7) (4 8))
  ((6 1) (3 2) (1 3) (8 4) (4 5) (2 6) (7 7) (5 8))
  ((6 1) (3 2) (1 3) (8 4) (5 5) (2 6) (4 7) (7 8))
  ((6 1) (3 2) (5 3) (7 4) (1 5) (4 6) (2 7) (8 8))
  ((6 1) (3 2) (5 3) (8 4) (1 5) (4 6) (2 7) (7 8))
  ((6 1) (3 2) (7 3) (2 4) (4 5) (8 6) (1 7) (5 8))
  ((6 1) (3 2) (7 3) (2 4) (8 5) (5 6) (1 7) (4 8))
  ((6 1) (3 2) (7 3) (4 4) (1 5) (8 6) (2 7) (5 8))
  ((6 1) (4 2) (1 3) (5 4) (8 5) (2 6) (7 7) (3 8))
  ((6 1) (4 2) (2 3) (8 4) (5 5) (7 6) (1 7) (3 8))
  ((6 1) (4 2) (7 3) (1 4) (3 5) (5 6) (2 7) (8 8))
  ((6 1) (4 2) (7 3) (1 4) (8 5) (2 6) (5 7) (3 8))
  ((6 1) (8 2) (2 3) (4 4) (1 5) (7 6) (5 7) (3 8))
  ((7 1) (1 2) (3 3) (8 4) (6 5) (4 6) (2 7) (5 8))
  ((7 1) (2 2) (4 3) (1 4) (8 5) (5 6) (3 7) (6 8))
  ((7 1) (2 2) (6 3) (3 4) (1 5) (4 6) (8 7) (5 8))
  ((7 1) (3 2) (1 3) (6 4) (8 5) (5 6) (2 7) (4 8))
  ((7 1) (3 2) (8 3) (2 4) (5 5) (1 6) (6 7) (4 8))
  ((7 1) (4 2) (2 3) (5 4) (8 5) (1 6) (3 7) (6 8))
  ((7 1) (4 2) (2 3) (8 4) (6 5) (1 6) (3 7) (5 8))
  ((7 1) (5 2) (3 3) (1 4) (6 5) (8 6) (2 7) (4 8))
  ((8 1) (2 2) (4 3) (1 4) (7 5) (5 6) (3 7) (6 8))
  ((8 1) (2 2) (5 3) (3 4) (1 5) (7 6) (4 7) (6 8))
  ((8 1) (3 2) (1 3) (6 4) (2 5) (5 6) (7 7) (4 8))
  ((8 1) (4 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8)))
мы не лыком шиты, поэтому сгенерим для них себе сразу подходящий список этих расстановок
Спойлер
(define result (list
 (list
  (list 1 1)
  (list 5 2)
  (list 8 3)
  (list 6 4)
  (list 3 5)
  (list 7 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 1 1)
  (list 6 2)
  (list 8 3)
  (list 3 4)
  (list 7 5)
  (list 4 6)
  (list 2 7)
  (list 5 8))
 (list
  (list 1 1)
  (list 7 2)
  (list 4 3)
  (list 6 4)
  (list 8 5)
  (list 2 6)
  (list 5 7)
  (list 3 8))
 (list
  (list 1 1)
  (list 7 2)
  (list 5 3)
  (list 8 4)
  (list 2 5)
  (list 4 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 2 1)
  (list 4 2)
  (list 6 3)
  (list 8 4)
  (list 3 5)
  (list 1 6)
  (list 7 7)
  (list 5 8))
 (list
  (list 2 1)
  (list 5 2)
  (list 7 3)
  (list 1 4)
  (list 3 5)
  (list 8 6)
  (list 6 7)
  (list 4 8))
 (list
  (list 2 1)
  (list 5 2)
  (list 7 3)
  (list 4 4)
  (list 1 5)
  (list 8 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 2 1)
  (list 6 2)
  (list 1 3)
  (list 7 4)
  (list 4 5)
  (list 8 6)
  (list 3 7)
  (list 5 8))
 (list
  (list 2 1)
  (list 6 2)
  (list 8 3)
  (list 3 4)
  (list 1 5)
  (list 4 6)
  (list 7 7)
  (list 5 8))
 (list
  (list 2 1)
  (list 7 2)
  (list 3 3)
  (list 6 4)
  (list 8 5)
  (list 5 6)
  (list 1 7)
  (list 4 8))
 (list
  (list 2 1)
  (list 7 2)
  (list 5 3)
  (list 8 4)
  (list 1 5)
  (list 4 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 2 1)
  (list 8 2)
  (list 6 3)
  (list 1 4)
  (list 3 5)
  (list 5 6)
  (list 7 7)
  (list 4 8))
 (list
  (list 3 1)
  (list 1 2)
  (list 7 3)
  (list 5 4)
  (list 8 5)
  (list 2 6)
  (list 4 7)
  (list 6 8))
 (list
  (list 3 1)
  (list 5 2)
  (list 2 3)
  (list 8 4)
  (list 1 5)
  (list 7 6)
  (list 4 7)
  (list 6 8))
 (list
  (list 3 1)
  (list 5 2)
  (list 2 3)
  (list 8 4)
  (list 6 5)
  (list 4 6)
  (list 7 7)
  (list 1 8))
 (list
  (list 3 1)
  (list 5 2)
  (list 7 3)
  (list 1 4)
  (list 4 5)
  (list 2 6)
  (list 8 7)
  (list 6 8))
 (list
  (list 3 1)
  (list 5 2)
  (list 8 3)
  (list 4 4)
  (list 1 5)
  (list 7 6)
  (list 2 7)
  (list 6 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 2 3)
  (list 5 4)
  (list 8 5)
  (list 1 6)
  (list 7 7)
  (list 4 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 2 3)
  (list 7 4)
  (list 1 5)
  (list 4 6)
  (list 8 7)
  (list 5 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 2 3)
  (list 7 4)
  (list 5 5)
  (list 1 6)
  (list 8 7)
  (list 4 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 4 3)
  (list 1 4)
  (list 8 5)
  (list 5 6)
  (list 7 7)
  (list 2 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 4 3)
  (list 2 4)
  (list 8 5)
  (list 5 6)
  (list 7 7)
  (list 1 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 8 3)
  (list 1 4)
  (list 4 5)
  (list 7 6)
  (list 5 7)
  (list 2 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 8 3)
  (list 1 4)
  (list 5 5)
  (list 7 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 3 1)
  (list 6 2)
  (list 8 3)
  (list 2 4)
  (list 4 5)
  (list 1 6)
  (list 7 7)
  (list 5 8))
 (list
  (list 3 1)
  (list 7 2)
  (list 2 3)
  (list 8 4)
  (list 5 5)
  (list 1 6)
  (list 4 7)
  (list 6 8))
 (list
  (list 3 1)
  (list 7 2)
  (list 2 3)
  (list 8 4)
  (list 6 5)
  (list 4 6)
  (list 1 7)
  (list 5 8))
 (list
  (list 3 1)
  (list 8 2)
  (list 4 3)
  (list 7 4)
  (list 1 5)
  (list 6 6)
  (list 2 7)
  (list 5 8))
 (list
  (list 4 1)
  (list 1 2)
  (list 5 3)
  (list 8 4)
  (list 2 5)
  (list 7 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 4 1)
  (list 1 2)
  (list 5 3)
  (list 8 4)
  (list 6 5)
  (list 3 6)
  (list 7 7)
  (list 2 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 5 3)
  (list 8 4)
  (list 6 5)
  (list 1 6)
  (list 3 7)
  (list 7 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 7 3)
  (list 3 4)
  (list 6 5)
  (list 8 6)
  (list 1 7)
  (list 5 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 7 3)
  (list 3 4)
  (list 6 5)
  (list 8 6)
  (list 5 7)
  (list 1 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 7 3)
  (list 5 4)
  (list 1 5)
  (list 8 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 8 3)
  (list 5 4)
  (list 7 5)
  (list 1 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 4 1)
  (list 2 2)
  (list 8 3)
  (list 6 4)
  (list 1 5)
  (list 3 6)
  (list 5 7)
  (list 7 8))
 (list
  (list 4 1)
  (list 6 2)
  (list 1 3)
  (list 5 4)
  (list 2 5)
  (list 8 6)
  (list 3 7)
  (list 7 8))
 (list
  (list 4 1)
  (list 6 2)
  (list 8 3)
  (list 2 4)
  (list 7 5)
  (list 1 6)
  (list 3 7)
  (list 5 8))
 (list
  (list 4 1)
  (list 6 2)
  (list 8 3)
  (list 3 4)
  (list 1 5)
  (list 7 6)
  (list 5 7)
  (list 2 8))
 (list
  (list 4 1)
  (list 7 2)
  (list 1 3)
  (list 8 4)
  (list 5 5)
  (list 2 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 4 1)
  (list 7 2)
  (list 3 3)
  (list 8 4)
  (list 2 5)
  (list 5 6)
  (list 1 7)
  (list 6 8))
 (list
  (list 4 1)
  (list 7 2)
  (list 5 3)
  (list 2 4)
  (list 6 5)
  (list 1 6)
  (list 3 7)
  (list 8 8))
 (list
  (list 4 1)
  (list 7 2)
  (list 5 3)
  (list 3 4)
  (list 1 5)
  (list 6 6)
  (list 8 7)
  (list 2 8))
 (list
  (list 4 1)
  (list 8 2)
  (list 1 3)
  (list 3 4)
  (list 6 5)
  (list 2 6)
  (list 7 7)
  (list 5 8))
 (list
  (list 4 1)
  (list 8 2)
  (list 1 3)
  (list 5 4)
  (list 7 5)
  (list 2 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 4 1)
  (list 8 2)
  (list 5 3)
  (list 3 4)
  (list 1 5)
  (list 7 6)
  (list 2 7)
  (list 6 8))
 (list
  (list 5 1)
  (list 1 2)
  (list 4 3)
  (list 6 4)
  (list 8 5)
  (list 2 6)
  (list 7 7)
  (list 3 8))
 (list
  (list 5 1)
  (list 1 2)
  (list 8 3)
  (list 4 4)
  (list 2 5)
  (list 7 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 5 1)
  (list 1 2)
  (list 8 3)
  (list 6 4)
  (list 3 5)
  (list 7 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 5 1)
  (list 2 2)
  (list 4 3)
  (list 6 4)
  (list 8 5)
  (list 3 6)
  (list 1 7)
  (list 7 8))
 (list
  (list 5 1)
  (list 2 2)
  (list 4 3)
  (list 7 4)
  (list 3 5)
  (list 8 6)
  (list 6 7)
  (list 1 8))
 (list
  (list 5 1)
  (list 2 2)
  (list 6 3)
  (list 1 4)
  (list 7 5)
  (list 4 6)
  (list 8 7)
  (list 3 8))
 (list
  (list 5 1)
  (list 2 2)
  (list 8 3)
  (list 1 4)
  (list 4 5)
  (list 7 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 5 1)
  (list 3 2)
  (list 1 3)
  (list 6 4)
  (list 8 5)
  (list 2 6)
  (list 4 7)
  (list 7 8))
 (list
  (list 5 1)
  (list 3 2)
  (list 1 3)
  (list 7 4)
  (list 2 5)
  (list 8 6)
  (list 6 7)
  (list 4 8))
 (list
  (list 5 1)
  (list 3 2)
  (list 8 3)
  (list 4 4)
  (list 7 5)
  (list 1 6)
  (list 6 7)
  (list 2 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 1 3)
  (list 3 4)
  (list 8 5)
  (list 6 6)
  (list 4 7)
  (list 2 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 1 3)
  (list 4 4)
  (list 2 5)
  (list 8 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 2 3)
  (list 4 4)
  (list 8 5)
  (list 1 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 2 3)
  (list 6 4)
  (list 3 5)
  (list 1 6)
  (list 4 7)
  (list 8 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 2 3)
  (list 6 4)
  (list 3 5)
  (list 1 6)
  (list 8 7)
  (list 4 8))
 (list
  (list 5 1)
  (list 7 2)
  (list 4 3)
  (list 1 4)
  (list 3 5)
  (list 8 6)
  (list 6 7)
  (list 2 8))
 (list
  (list 5 1)
  (list 8 2)
  (list 4 3)
  (list 1 4)
  (list 3 5)
  (list 6 6)
  (list 2 7)
  (list 7 8))
 (list
  (list 5 1)
  (list 8 2)
  (list 4 3)
  (list 1 4)
  (list 7 5)
  (list 2 6)
  (list 6 7)
  (list 3 8))
 (list
  (list 6 1)
  (list 1 2)
  (list 5 3)
  (list 2 4)
  (list 8 5)
  (list 3 6)
  (list 7 7)
  (list 4 8))
 (list
  (list 6 1)
  (list 2 2)
  (list 7 3)
  (list 1 4)
  (list 3 5)
  (list 5 6)
  (list 8 7)
  (list 4 8))
 (list
  (list 6 1)
  (list 2 2)
  (list 7 3)
  (list 1 4)
  (list 4 5)
  (list 8 6)
  (list 5 7)
  (list 3 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 1 3)
  (list 7 4)
  (list 5 5)
  (list 8 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 1 3)
  (list 8 4)
  (list 4 5)
  (list 2 6)
  (list 7 7)
  (list 5 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 1 3)
  (list 8 4)
  (list 5 5)
  (list 2 6)
  (list 4 7)
  (list 7 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 5 3)
  (list 7 4)
  (list 1 5)
  (list 4 6)
  (list 2 7)
  (list 8 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 5 3)
  (list 8 4)
  (list 1 5)
  (list 4 6)
  (list 2 7)
  (list 7 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 7 3)
  (list 2 4)
  (list 4 5)
  (list 8 6)
  (list 1 7)
  (list 5 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 7 3)
  (list 2 4)
  (list 8 5)
  (list 5 6)
  (list 1 7)
  (list 4 8))
 (list
  (list 6 1)
  (list 3 2)
  (list 7 3)
  (list 4 4)
  (list 1 5)
  (list 8 6)
  (list 2 7)
  (list 5 8))
 (list
  (list 6 1)
  (list 4 2)
  (list 1 3)
  (list 5 4)
  (list 8 5)
  (list 2 6)
  (list 7 7)
  (list 3 8))
 (list
  (list 6 1)
  (list 4 2)
  (list 2 3)
  (list 8 4)
  (list 5 5)
  (list 7 6)
  (list 1 7)
  (list 3 8))
 (list
  (list 6 1)
  (list 4 2)
  (list 7 3)
  (list 1 4)
  (list 3 5)
  (list 5 6)
  (list 2 7)
  (list 8 8))
 (list
  (list 6 1)
  (list 4 2)
  (list 7 3)
  (list 1 4)
  (list 8 5)
  (list 2 6)
  (list 5 7)
  (list 3 8))
 (list
  (list 6 1)
  (list 8 2)
  (list 2 3)
  (list 4 4)
  (list 1 5)
  (list 7 6)
  (list 5 7)
  (list 3 8))
 (list
  (list 7 1)
  (list 1 2)
  (list 3 3)
  (list 8 4)
  (list 6 5)
  (list 4 6)
  (list 2 7)
  (list 5 8))
 (list
  (list 7 1)
  (list 2 2)
  (list 4 3)
  (list 1 4)
  (list 8 5)
  (list 5 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 7 1)
  (list 2 2)
  (list 6 3)
  (list 3 4)
  (list 1 5)
  (list 4 6)
  (list 8 7)
  (list 5 8))
 (list
  (list 7 1)
  (list 3 2)
  (list 1 3)
  (list 6 4)
  (list 8 5)
  (list 5 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 7 1)
  (list 3 2)
  (list 8 3)
  (list 2 4)
  (list 5 5)
  (list 1 6)
  (list 6 7)
  (list 4 8))
 (list
  (list 7 1)
  (list 4 2)
  (list 2 3)
  (list 5 4)
  (list 8 5)
  (list 1 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 7 1)
  (list 4 2)
  (list 2 3)
  (list 8 4)
  (list 6 5)
  (list 1 6)
  (list 3 7)
  (list 5 8))
 (list
  (list 7 1)
  (list 5 2)
  (list 3 3)
  (list 1 4)
  (list 6 5)
  (list 8 6)
  (list 2 7)
  (list 4 8))
 (list
  (list 8 1)
  (list 2 2)
  (list 4 3)
  (list 1 4)
  (list 7 5)
  (list 5 6)
  (list 3 7)
  (list 6 8))
 (list
  (list 8 1)
  (list 2 2)
  (list 5 3)
  (list 3 4)
  (list 1 5)
  (list 7 6)
  (list 4 7)
  (list 6 8))
 (list
  (list 8 1)
  (list 3 2)
  (list 1 3)
  (list 6 4)
  (list 2 5)
  (list 5 6)
  (list 7 7)
  (list 4 8))
 (list
  (list 8 1)
  (list 4 2)
  (list 1 3)
  (list 3 4)
  (list 6 5)
  (list 2 6)
  (list 7 7)
  (list 5 8))))
 
Рейтинг: 0 / 0
17.09.2020, 21:45
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2692
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
92 расстановки должно получиться, ну сами пересчитайте на всякий случай
одна голова хорошо, а гарын лучше
 
Рейтинг: 0 / 0
17.09.2020, 21:47
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2696
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
реализуем-ка процедурку queen-cols, которая возвращает последовательность
всех способов разместить ферзей на первых k вертикалях доски
Код
1.
2.
3.
  (define (queen-cols k)
    если k = 0, то сорян, возвращаем пустое размещение (список из одного пустого размещения)
    иначе чё-то делаем)
ну по типу такого:
Код
1.
2.
3.
4.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       чё-то делаем))
 
Рейтинг: 0 / 0
17.09.2020, 21:58
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2700
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дальше вспоминаем, что делать-то хотели

Предположили, что мы уже породили последовательность из всех возможных способов разместить k − 1 ферзей на первых k − 1 вертикалях доски.
Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k-й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k-й вертикали не бьется ни одним из остальных.

Иными словами у нас будет некий фильтр, которому на вход будет подаваться вышеуказанный расширенный набор позиций, т.е.
Код
1.
2.
3.
4.
5.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
        тут какая-то магия, которая даёт набор позиций)))
 
Рейтинг: 0 / 0
17.09.2020, 22:05
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2703
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
фильтр напишем универсальный в том смысле, что у него будет два параметра предикат и просеиваимая последовательность (в виде списка)
Т.е. фильтр будет просеивать последовательность, выбирая из неё только те элементы, которые удовлетворяют данному предикату
Код
1.
2.
3.
4.
5.
6.
7.
8.
(define (filter predicate sequence)
  (условия:
   ((если sequence null, то вернуть пустой список)
    (если первый элемент последовательности удовлетворяет предикату, то
         (сконструировать результирующий список из этого первого элемента
          и результата вызова фильтра уже для хвоста последовательности
          (т.е от второго элемента до последнего)
    (иначе первый элемент пропускаем и работаем дальше рекурсивно с хвостом (вызываем filter для хвоста)))))
Изменено: 17.09.2020, 22:30 - Дырокол
Рейтинг: 0 / 0
17.09.2020, 22:30
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2706
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
для того, чтобы написать фильтр, нам понадобятся примитивы языка:

null? - проверка списка на пустоту
Код
1.
2.
3.
4.
> (null? '(a b c))
#f
> (null? '())
#t
Для реализации конкретного уровня абстракции данных в нашем языке имеется
составная структура, называемая парой, и она создается с помощью элементарной
процедуры cons. Эта процедура принимает два аргумента и возвращает объект данных,
который содержит эти два аргумента в качестве частей. Имея пару, мы можем получить
ее части с помощью элементарных процедур car и cdr. Таким образом, использовать
cons, car и cdr можно так:
Код
1.
2.
3.
4.
5.
6.
7.
8.
> (define x (cons 1 2))
> x
'(1 . 2)
> (car x)
1
> (cdr x)
2
>
Также понадобится общая форма условного выражения :
(cond (p1 e1)
(p2 e2)
.
.
.
(pn en ))
Она состоит из символа cond, за которым следуют заключенные в скобки пары
выражений (pi ei), называемых ветвями. В каждой из этих пар первое
выражение — предикат (predicate), то есть выражение, значение которого интерпрети-
руется как истина или ложь. Второй элемент пары - выражение, вычисляемое если предикат истинный.

Условные выражения вычисляются так: сначала вычисляется первый предикат. Если его
значением является ложь, вычисляется второй предикат. Этот процесс продолжается до тех пор,
пока не найдется предикат, значением которого будет истина, и в этом случае интерпретатор
возвращает значение соответствующего выражения-следствия в качестве значения всего
условного выражения. Если ни один из предикатов не окажется истинным, значение условного
выражения будет неопределённым.

к примеру, модуль числа определяется так:
Код
1.
2.
3.
4.
   (define (abs x)
     (cond ((> x 0) x)
           ((= x 0) 0)
           ((< x 0) (- x))))
Изменено: 17.09.2020, 22:46 - Дырокол
Рейтинг: 0 / 0
17.09.2020, 22:45
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2707
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
с этими примитивами сам фильтр реализуется так:
Код
1.
2.
3.
4.
5.
6.
(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
Изменено: 17.09.2020, 22:56 - Дырокол
Рейтинг: 0 / 0
17.09.2020, 22:48
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2709
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
проверим
Код
1.
2.
3.
4.
5.
> (filter odd? (list 1 2 3 4 5))
'(1 3 5)

> (filter (λ (x) (> x 3)) (list 1 2 3 4 5))
'(4 5)
работает
 
Рейтинг: 0 / 0
17.09.2020, 22:56
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2711
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
ну вы не долбоклюи, надеюсь поняли что используем везде префиксную нотацию
 
Рейтинг: 0 / 0
17.09.2020, 23:01
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2865
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дырокол  17.09.2020, 22:05
2700
Дальше вспоминаем, что делать-то хотели

Предположили, что мы уже породили последовательность из всех возможных способов разместить k − 1 ферзей на первых k − 1 вертикалях доски.
Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k-й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k-й вертикали не бьется ни одним из остальных.

Иными словами у нас будет некий фильтр, которому на вход будет подаваться вышеуказанный расширенный набор позиций, т.е.
Код
1.
2.
3.
4.
5.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
        тут какая-то магия, которая даёт набор позиций)))
итак, фильтр мы написали, и алгоритм приобретает такой вид:
Код
1.
2.
3.
4.
5.
6.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
          предикат
          расширенный набор позиций)))
Изменено: 18.09.2020, 14:59 - Дырокол
Рейтинг: 0 / 0
18.09.2020, 14:59
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2866
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
разберёмся с предикатом

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

т.е. предикат должен на вход брать множество позиций и возвращать результат работы
некоторой функции сравнения, которая для этого множества позиций определяет,
находится ли ферзь с k-й вертикали в безопасности от остальных.
назовём эту функцию сравнения safe?
Код
1.
2.
3.
4.
5.
6.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
          (λ (positions) (safe? k positions))
          расширенный набор позиций)))
 
Рейтинг: 0 / 0
18.09.2020, 15:10
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2867
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
напишем эту safe?-функцию:
Код
1.
(define (safe? k positions) ...)
и заодно будем её тестировать
пусть мы расставили 7 ферзей и осталось поставить 8-го.

картинка несколькими постами ранее у нас соответствует такой расстановке:
Код
1.
(define good-positions '((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (6 8)))
для этой расстановки наша функция должна возвращать true

а для расстановки, например, где восьмой ферзь на одну клетку выше (бьётся ферзём с седьмой вертикали)
Код
1.
(define bad-positions '((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (5 8)))
наша функция должна возвращать false.
 
Рейтинг: 0 / 0
18.09.2020, 15:41
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #2871
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
для этого
1) нам нужно взять последний k-й элемент из позиции.
2) проверить его на пересечение с соседями по строкам и столбцам
3) проверить его на пересечение с соседями по диагоналям
если и 2) и 3) возвращают пустое множество, то возвращаем истину, иначе ложь.

вообще говоря, один и тот же сосед не может попасть и 2) и в 3) одновременно (напоминаю, что мы считаем, что (k-1)-я расстановка правильная), поэтому достаточно просто проверить равенство 2) и 3), т.к. они равны только в случае пустоты.

все три пункта удобно решать с помощью реализованной нами выше абстракции фильтра.
т.е.

1) отфильтровать k-й элемент из positions
Код
1.
2.
> (filter (lambda (x) (= (cadr x) 8)) good-positions)
'((6 8))
где cadr - это сокращение для комбинации (car (cdr ...))

поскольку возвращается список из одного элемента - списка координат искомого ферзя, то удобно сделать ему car дополнительно чтоб избавиться от лишних скобок
Код
1.
2.
3.
4.
5.
>  (car (filter (lambda (x) (= (cadr x) 8)) good-positions))
'(6 8)
>  (car (filter (lambda (x) (= (cadr x) 8)) bad-positions))
'(5 8)
далее обозначим найденный таким образом k-й элемент за item

2) это проверить item на соседство с помощью фильтра
Код
1.
(filter (λ (x) (row-column-neighborhood?  item x)) positions)
где row-column-neighborhood? - предикат, отвечающий нам на вопрос являются ли item и x соседями по строкам или столбцам

3) это проверить item на соседство с помощью фильтра
Код
1.
(filter (λ (x) (diagonal-neighborhoods?  item x)) positions)
где diagonal-neighborhoods? - предикат, отвечающий нам на вопрос являются ли item и x соседями по диагоналям

предикаты row-column-neighborhood? и diagonal-neighborhoods? нам ещё предстоит написать позже, а пока взяв за основу всё вышесказанное, зафиксируем тело функции safe?
Код
1.
2.
3.
4.
(define (safe? k positions)
  (let ((item (car (filter (λ (x) (= (cadr x) k)) positions))))
    (equal? (filter (λ (x) (row-column-neighborhood?  item x)) positions)
           (filter (λ (x) (diagonal-neighborhoods?  item x)) positions))))
Изменено: 18.09.2020, 16:10 - Дырокол
Рейтинг: 0 / 0
18.09.2020, 16:09
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3041
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
предикат row-column-neighborhood? - очевидно возвращает true, если у сравниваемых элементов либо совпадают либо номер строки, либо номер столбца и при этом один и тот же элемент сам себе не сосед и пустой тоже не сосед.
т.е.:
Код
1.
2.
3.
4.
5.
6.
(define row-column-neighborhood?
  (λ (a b)
    (and
     (not (equal? a nil))
     (or (= (car a) (car b)) (= (cadr a) (cadr b)))
     (not (and (= (car a) (car b)) (= (cadr a) (cadr b)))))))
проверяем:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
> (row-column-neighborhood? '(6 8) '(5 8))
#t
> (row-column-neighborhood? '(6 7) '(5 8))
#f
> (row-column-neighborhood? '(5 7) '(5 8))
#t
> (row-column-neighborhood? '() '(5 8))
#f
> (row-column-neighborhood? '(5 8) '(5 8))
#f
 
Рейтинг: 0 / 0
19.09.2020, 20:17
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3042
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
интересно, почему игнор на соседство самому себе я реализовал как-то по дурацки
Цитата 
(not (and (= (car a) (car b)) (= (cadr a) (cadr b)))))))
сейчас не могу понять, почему
 
Рейтинг: 0 / 0
19.09.2020, 20:19
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3043
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
вроде так проще и понятней
Код
1.
2.
3.
4.
5.
6.
(define row-column-neighborhood?
  (λ (a b)
      (and
       (not (equal? a nil))
       (or (= (car a) (car b)) (= (cadr a) (cadr b)))
       (not (equal? a b)))))
 
Рейтинг: 0 / 0
19.09.2020, 20:23
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3044
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
чтобы написать проверку диагональных соседей,
еще раз посмотрим на картинку
и соответвующую ей расстановку

((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (6 8))
pasted_image.png
 
Рейтинг: 0 / 0
19.09.2020, 20:49
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3046
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
на первом месте в записи фигуры у нас номер строки, на втором номер столбца.
т.е. если запись фигуры (x, y)
то ось X идёт с севера на юг, а Y c запада на восток

например, item = (5, 4)
чтобы найти его диагональных соседей, надо рассмотреть все элементы, полученные от item :
1) уменьшением x и y на единицу одновременно (пройтись на северо-восток): (4, 3) (3, 2) (2, 1)
2) увеличением x на единицу и уменьшением y на единицу одновременно (пройтись на юго-запад): (6, 3) (7, 2) (8, 1)
3) аналогично пройтись на северо-запад и юго-восток

если нигде не столкнемся с существущими ферзями, то возвращаем false, иначе true.
в данном случае во втором пункте мы столкнёмся с ферзём - найдем соседа (7,2)

"нигде не столкнёмся" мы реализуем так: в процессе поиска соседей будем добавлять их в список и если в конце он окажется пустым, то вернём false

на данном этапе напишем генератор всех возможных соседей для данного item, процедура построения списка соседей будет выглядеть так:
Код
1.
2.
3.
4.
5.
6.
7.
8.
(define (neighborhoods item min max direction)
    (let ((x (car item))
          (y (cadr item))
          (x-operation (if (or (equal? direction "SE") (equal? direction "SW")) + -))
          (y-operation (if (or (equal? direction "SE") (equal? direction "NE")) + -)))
      (if (and (>= x min) (<= x max) (>= y min) (<= y max))
         (cons item (neighborhoods (list (x-operation x 1) (y-operation y 1)) min max direction))
         '())))
Изменено: 19.09.2020, 21:11 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:04
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3047
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
заметим, что в это реализации сам item тоже попадает в соседи самому себе:
Код
1.
2.
3.
4.
> (neighborhoods '(5 4) 1 8 "NW")
'((5 4) (4 3) (3 2) (2 1))
> (neighborhoods '(5 4) 1 8 "SW")
'((5 4) (6 3) (7 2) (8 1))
поэтому подкрутим немного, удаляя его из каждого списка:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
(define (diagonal-neighborhoods item)
  (define (neighborhoods item min max direction)
    (let ((x (car item))
          (y (cadr item))
          (x-operation (if (or (equal? direction "SE") (equal? direction "SW")) + -))
          (y-operation (if (or (equal? direction "SE") (equal? direction "NE")) + -)))
      (if (and (>= x min) (<= x max) (>= y min) (<= y max))
         (cons item (neighborhoods (list (x-operation x 1) (y-operation y 1)) min max direction))
         '())))
  (append
   (remove item (neighborhoods item 1 8 "NE"))
   (remove item (neighborhoods item 1 8 "NW"))
   (remove item (neighborhoods item 1 8 "SE"))
   (remove item (neighborhoods item 1 8 "SW"))))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
> (diagonal-neighborhoods '(5 4))
'((4 5)
  (3 6)
  (2 7)
  (1 8)
  (4 3)
  (3 2)
  (2 1)
  (6 5)
  (7 6)
  (8 7)
  (6 3)
  (7 2)
  (8 1))
Изменено: 19.09.2020, 21:16 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:15
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3050
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
теперь, наконец, мы можем написать то, ради чего всё это затевалось - предикат diagonal-neighborhoods?

в его реализации воспользуемся абстракцией фильтра
логика следующая
предикат - это некая функция от пары сравниваемых элементов, которая пытается установить являются ли они соседями.
чтобы это сделать, она берет один из элементов, генерит для него всех возможных соседей, а потом проходит по ним фильтром, пытаясь установить, есть ли среди них другой элемент.
Код
1.
2.
3.
4.
5.
(define diagonal-neighborhoods?
  (λ (a b)
    (not (equal? nil
                (filter (λ (x) (equal? a x))
                       (diagonal-neighborhoods b))))))
проверяем:
Код
1.
2.
3.
4.
> (diagonal-neighborhoods? '(5 4) '(4 3))
#t
> (diagonal-neighborhoods? '(5 4) '(3 3))
#f
Изменено: 19.09.2020, 21:28 - Дырокол
Рейтинг: 0 / 0
19.09.2020, 21:25
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3103
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
дальше нужно написать процедуру adjoin-position, которая добавляет нового ферзя
на определенных горизонтали и вертикали к заданному множеству позиций
Код
1.
2.
(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list (list new-row k))))
 
Рейтинг: 0 / 0
20.09.2020, 17:12
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3106
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
 
Рейтинг: 0 / 0
20.09.2020, 17:17
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3107
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
выше были использованы примитивные процедуры
append и remove

append берет в качестве аргументов два списка и составляет из их элементов один общий список:
Код
1.
2.
> (append '(1 4 9 16 25) '(1 3 5 7))
(1 4 9 16 25 1 3 5 7)
remove возвращает все элементы исходной последовательности, за исключением данного.

в принципе, если в языке их нет, то их можно реализовать так:
Код
1.
2.
3.
4.
(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2))))
remove можно выразить как простой фильтр:
Код
1.
2.
(define (remove item sequence)
  (filter (λ (x) (not (= x item))) sequence))
Изменено: 20.09.2020, 17:22 - Дырокол
Рейтинг: 0 / 0
20.09.2020, 17:19
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3108
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Лигафоны Рубацова  20.09.2020, 17:17
3106
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
впереди такое время, что и мёртвые позавидуют живым
 
Рейтинг: 0 / 0
20.09.2020, 17:20
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3109
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дырокол  18.09.2020, 15:10
2866
разберёмся с предикатом

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

т.е. предикат должен на вход брать множество позиций и возвращать результат работы
некоторой функции сравнения, которая для этого множества позиций определяет,
находится ли ферзь с k-й вертикали в безопасности от остальных.
назовём эту функцию сравнения safe?
Код
1.
2.
3.
4.
5.
6.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
          (λ (positions) (safe? k positions))
          расширенный набор позиций)))
так, safe? мы реализовали
осталась генерация расширенного набора позиций
 
Рейтинг: 0 / 0
20.09.2020, 17:26
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3110
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
идея следующая:

надо сначала сгенерить расстановку для первого столбца:
Код
1.
(((1 1)) ((2 1)) ((3 1)) ((4 1)) ((5 1)) ((6 1)) ((7 1)) ((8 1)))
потом для каждого элемента добавить расстановку для второго столбца:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
'(((1 1) (1 2))
  ((1 1) (2 2))
  ((1 1) (3 2))
  ((1 1) (4 2))
  ((1 1) (5 2))
  ((1 1) (6 2))
  ((1 1) (7 2))
  ((1 1) (8 2)))

'(((2 1) (1 2))
  ((2 1) (2 2))
  ((2 1) (3 2))
  ((2 1) (4 2))
  ((2 1) (5 2))
  ((2 1) (6 2))
  ((2 1) (7 2))
  ((2 1) (8 2)))
...

'(((8 1) (1 2))
  ((8 1) (2 2))
  ((8 1) (3 2))
  ((8 1) (4 2))
  ((8 1) (5 2))
  ((8 1) (6 2))
  ((8 1) (7 2))
  ((8 1) (8 2)))
и так далее
Изменено: 20.09.2020, 17:51 - Дырокол
Рейтинг: 0 / 0
20.09.2020, 17:50
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3111
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
в общем, пишем генератор.

сначала напишем генератор для последовательности целых чисел от min до max:
Код
1.
2.
3.
4.
(define (enumerate-interval low high)
  (if (> low high)
    nil
    (cons low (enumerate-interval (+ low 1) high))))
Код
1.
2.
> (enumerate-interval 1 8)
(1 2 3 4 5 6 7 8)
 
Рейтинг: 0 / 0
20.09.2020, 17:53
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3112
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
потом мы можем взять эти числа за номера строк и для каждого k-го стобца генерить пары c помощью
adjoin-position, которая, напомню добавляет нового ферзя на определенных горизонтали и
вертикали к заданному множеству позиций

т.е. мы можем начать с пустого множества позиций так:
Код
1.
2.
3.
4.
> (adjoin-position 1 1 '())
'((1 1))
> (adjoin-position 2 1 '())
'((2 1))
потом применить эту функцию к предыдущему результату:
Код
1.
2.
3.
4.
5.
6.
7.
8.
> (adjoin-position 1 2 '(1 1))
'(1 1 (1 2))
> (adjoin-position 1 2 '((1 1)))
'((1 1) (1 2))
> (adjoin-position 2 2 '((1 1)))
'((1 1) (2 2))
> (adjoin-position 3 2 '((1 1)))
'((1 1) (3 2))
и так далее
 
Рейтинг: 0 / 0
20.09.2020, 18:04
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3113
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
задумаемся, что по сути при фиксированном стобце k это отображение номеров строк из множества от 1 до 8 в пары (1 k), (2 k) и так далее, причем приписанных (добавленных) к предыдущей расстановке. т.е. это отображение с параметром "номер строки", которое вызывает для каждого номера строки функцию преобразования adjoin-position.

перед тем, как продолжить, реализуем абстракцию "отображение" в общем виде.

Это процедура высшего порядка (в миру называется map).
Map берет в качестве аргументов процедуру от одного аргумента и список,
а возвращает список результатов, полученных применением процедуры к каждому элементу списка:
Код
1.
2.
3.
4.
5.
6.
(define (map proc items)
  (if (null? items)
  nil
  (cons
     (proc (car items))
     (map proc (cdr items)))))
Код
1.
2.
3.
4.
5.
(map abs (list -10 2.5 -11.6 17))
> (10 2.5 11.6 17)

(map (lambda (x) (* x x)) (list 1 2 3 4))
> (1 4 9 16)
 
Рейтинг: 0 / 0
20.09.2020, 18:12
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3115
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
т.е. наше отображение будет выглядеть так:
Код
1.
2.
3.
4.
(map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size))
теперь можно приступить к генерации:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((1 1))))
                 (enumerate-interval 1 8))
'(((1 1) (1 2))
  ((1 1) (2 2))
  ((1 1) (3 2))
  ((1 1) (4 2))
  ((1 1) (5 2))
  ((1 1) (6 2))
  ((1 1) (7 2))
  ((1 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((2 1))))
                 (enumerate-interval 1 8))
'(((2 1) (1 2))
  ((2 1) (2 2))
  ((2 1) (3 2))
  ((2 1) (4 2))
  ((2 1) (5 2))
  ((2 1) (6 2))
  ((2 1) (7 2))
  ((2 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((3 1))))
                 (enumerate-interval 1 8))
'(((3 1) (1 2))
  ((3 1) (2 2))
  ((3 1) (3 2))
  ((3 1) (4 2))
  ((3 1) (5 2))
  ((3 1) (6 2))
  ((3 1) (7 2))
  ((3 1) (8 2)))
 
Рейтинг: 0 / 0
20.09.2020, 18:16
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3116
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
Это на чём, на лиспе что-ли?
 
Рейтинг: 0 / 0
20.09.2020, 18:22
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3117
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
 
Рейтинг: 0 / 0
20.09.2020, 18:27
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3125
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
 
Рейтинг: 0 / 0
20.09.2020, 20:41
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3172
краник Скрыть профиль Поместить в игнор-лист
краник
Гость
Дырокол  20.09.2020, 20:41
3125
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
опасайся водяных вшей
 
Рейтинг: 0 / 0
20.09.2020, 22:23
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3177
Лигафоны Рубацова Скрыть профиль Поместить в игнор-лист
Лигафоны Рубацова
Гость
Дырокол  20.09.2020, 18:27
3117
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
OK
 
Рейтинг: 0 / 0
20.09.2020, 22:30
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3182
black lives matter Скрыть профиль Поместить в игнор-лист
black lives matter
Гость
фсе ферзи чорные, ОК
 
Рейтинг: 0 / 0
20.09.2020, 22:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3316
Гопник с Вантового моста Скрыть профиль Поместить в игнор-лист
Гопник с Вантового моста
Гость
Каждый лиспер должен хоть раз написать свой лисп, воистину, братия!
 
Рейтинг: 0 / 0
22.09.2020, 21:48
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3401
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
1.jpg
 
Рейтинг: 0 / 0
24.09.2020, 21:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3402
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
погулял
 
Рейтинг: 0 / 0
24.09.2020, 21:39
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3408
SQL
Скрыть профиль Поместить в игнор-лист
SQL
Участник
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
 
Рейтинг: 0 / 0
24.09.2020, 21:45
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3411
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
SQL  24.09.2020, 21:45
3408
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
круче в домбае
 
Рейтинг: 0 / 0
24.09.2020, 21:49
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3412
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
если про рф говорить
и эльбрус, но туда сложно гулять
 
Рейтинг: 0 / 0
24.09.2020, 21:49
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3448
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дырокол  20.09.2020, 18:16
3115
т.е. наше отображение будет выглядеть так:
Код
1.
2.
3.
4.
(map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size))
теперь можно приступить к генерации:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((1 1))))
                 (enumerate-interval 1 8))
'(((1 1) (1 2))
  ((1 1) (2 2))
  ((1 1) (3 2))
  ((1 1) (4 2))
  ((1 1) (5 2))
  ((1 1) (6 2))
  ((1 1) (7 2))
  ((1 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((2 1))))
                 (enumerate-interval 1 8))
'(((2 1) (1 2))
  ((2 1) (2 2))
  ((2 1) (3 2))
  ((2 1) (4 2))
  ((2 1) (5 2))
  ((2 1) (6 2))
  ((2 1) (7 2))
  ((2 1) (8 2)))
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
> (map (lambda (new-row)
                    (adjoin-position
                     new-row 2 '((3 1))))
                 (enumerate-interval 1 8))
'(((3 1) (1 2))
  ((3 1) (2 2))
  ((3 1) (3 2))
  ((3 1) (4 2))
  ((3 1) (5 2))
  ((3 1) (6 2))
  ((3 1) (7 2))
  ((3 1) (8 2)))
выше приведены отдельные map-ы, генерирующие нужные списки в зависимости от параметров - предыдущего сгенерённого списка, номера строки, номера столбца.

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

поэтому нам нужна некая процедура вида
Код
1.
2.
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
т.е. у нас есть некая процедура proc - в нашем случае это процедура вида
Код
1.
2.
3.
(lambda (new-row)
                    (adjoin-position
                     new-row 2 '((3 1))))
есть последовательность seq - в нашем случае это
Код
1.
(enumerate-interval 1 8)
мы хотем аккумулировать результаты этих map-ов, начав с пустого nil.

то-есть нам нужна некоторая функция аккумулирования accumulate, которую мы запускаем с параметрами
Код
1.
(accumulate append nil (map proc seq))
Изменено: 25.09.2020, 07:51 - Дырокол
Рейтинг: 0 / 0
25.09.2020, 07:50
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3449
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
ничего не мешает нам реализовать подобное накопление в самом общем виде, когда на вход функции накопления мы подаём
1) операцию накопления
2) начальное значение
3) последовательность, элементы которой и нужно накопить, применив к ним операцию накопления:
Код
1.
2.
3.
4.
5.
(define (accumulate op initial sequence)
  (if (null? sequence)
    initial
    (op (car sequence)
       (accumulate op initial (cdr sequence)))))
Код
1.
2.
(accumulate + 0 (list 1 2 3 4 5))
15
Код
1.
2.
(accumulate * 1 (list 1 2 3 4 5))
120
Код
1.
2.
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)
 
Рейтинг: 0 / 0
25.09.2020, 07:57
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3450
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
Дырокол  18.09.2020, 15:10
2866
разберёмся с предикатом

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

т.е. предикат должен на вход брать множество позиций и возвращать результат работы
некоторой функции сравнения, которая для этого множества позиций определяет,
находится ли ферзь с k-й вертикали в безопасности от остальных.
назовём эту функцию сравнения safe?
Код
1.
2.
3.
4.
5.
6.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
          (λ (positions) (safe? k positions))
          расширенный набор позиций)))
после всех этих приготовлений счастье наконец пришло в наш дом
и мы можем написать алгоритм целиком:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
        (λ (positions) (safe? k positions))
        (flatmap
         (λ (rest-of-queens)
           (map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size)))
         (queen-cols (- k 1))))))
 
Рейтинг: 0 / 0
25.09.2020, 07:59
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3451
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
исходная задача формулируется в терминах нахождения расстановки в зависимости от размера доски, поэтому обернём нашу функцию так:
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
        (λ (positions) (safe? k positions))
        (flatmap
         (λ (rest-of-queens)
           (map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size)))
         (queen-cols (- k 1))))))
  (queen-cols board-size))
 
Рейтинг: 0 / 0
25.09.2020, 08:02
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3452
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
весь код выглядит так (map я не стал выписывать ещё раз, потому что он реализован в стандартной библиотеке и любой интерпретатор его понимает)
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
       (list empty-board)
       (filter
        (λ (positions) (safe? k positions))
        (flatmap
         (λ (rest-of-queens)
           (map (lambda (new-row)
                  (adjoin-position
                   new-row k rest-of-queens))
               (enumerate-interval 1 board-size)))
         (queen-cols (- k 1))))))
  (queen-cols board-size))

; nil
(define nil '())

; enumerate integers
(define (enumerate-interval low high)
  (if (> low high)
     nil
     (cons low (enumerate-interval (+ low 1) high))))

; filter
(define (filter predicate sequence)
  (if (null? sequence)
     sequence
     (if (predicate (car sequence))
        (cons (car sequence) (filter predicate (cdr sequence)))
        (filter predicate (cdr sequence)))))

; accumulate
(define (accumulate op init sequence)
  (cond ((null? sequence) init)
       (else (op (car sequence) (accumulate op init (cdr sequence))))))

; flatmap
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

(define empty-board nil)

(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list (list new-row k))))

(define row-column-neighborhood?
  (λ (a b)
    (and
     (not (equal? a nil))
     (or (= (car a) (car b)) (= (cadr a) (cadr b)))
     ;(not (and (= (car a) (car b)) (= (cadr a) (cadr b)))))))
     (not (equal? a b)))))

(define (diagonal-neighborhoods item)
  (define (neighborhoods item min max direction)
    (let ((x (car item))
          (y (cadr item))
          (x-operation (if (or (equal? direction "SE") (equal? direction "SW")) + -))
          (y-operation (if (or (equal? direction "SE") (equal? direction "NE")) + -)))
      (if (and (>= x min) (<= x max) (>= y min) (<= y max))
         (cons item (neighborhoods (list (x-operation x 1) (y-operation y 1)) min max direction))
         '())))
  (append
   (remove item (neighborhoods item 1 8 "NE"))
   (remove item (neighborhoods item 1 8 "NW"))
   (remove item (neighborhoods item 1 8 "SE"))
   (remove item (neighborhoods item 1 8 "SW"))))

(define (safe? k positions)
  (let ((item (car (filter (λ (x) (= (cadr x) k)) positions))))
    (equal? (filter (λ (x) (row-column-neighborhood?  item x)) positions)
           (filter (λ (x) (diagonal-neighborhoods?  item x)) positions))))

(define diagonal-neighborhoods?
  (λ (a b)
    (not (equal? nil
                (filter (λ (x) (equal? a x))
                       (diagonal-neighborhoods b))))))
 
Рейтинг: 0 / 0
25.09.2020, 08:07
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3453
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
проверяем
Код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
> (queens 8)
'(((1 1) (5 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8))
  ((1 1) (6 2) (8 3) (3 4) (7 5) (4 6) (2 7) (5 8))
  ((1 1) (7 2) (4 3) (6 4) (8 5) (2 6) (5 7) (3 8))
  ((1 1) (7 2) (5 3) (8 4) (2 5) (4 6) (6 7) (3 8))
  ((2 1) (4 2) (6 3) (8 4) (3 5) (1 6) (7 7) (5 8))
  ((2 1) (5 2) (7 3) (1 4) (3 5) (8 6) (6 7) (4 8))
  ((2 1) (5 2) (7 3) (4 4) (1 5) (8 6) (6 7) (3 8))
  ((2 1) (6 2) (1 3) (7 4) (4 5) (8 6) (3 7) (5 8))
  ((2 1) (6 2) (8 3) (3 4) (1 5) (4 6) (7 7) (5 8))
  ((2 1) (7 2) (3 3) (6 4) (8 5) (5 6) (1 7) (4 8))
  ((2 1) (7 2) (5 3) (8 4) (1 5) (4 6) (6 7) (3 8))
  ((2 1) (8 2) (6 3) (1 4) (3 5) (5 6) (7 7) (4 8))
  ((3 1) (1 2) (7 3) (5 4) (8 5) (2 6) (4 7) (6 8))
  ((3 1) (5 2) (2 3) (8 4) (1 5) (7 6) (4 7) (6 8))
  ((3 1) (5 2) (2 3) (8 4) (6 5) (4 6) (7 7) (1 8))
  ((3 1) (5 2) (7 3) (1 4) (4 5) (2 6) (8 7) (6 8))
  ((3 1) (5 2) (8 3) (4 4) (1 5) (7 6) (2 7) (6 8))
  ((3 1) (6 2) (2 3) (5 4) (8 5) (1 6) (7 7) (4 8))
  ((3 1) (6 2) (2 3) (7 4) (1 5) (4 6) (8 7) (5 8))
  ((3 1) (6 2) (2 3) (7 4) (5 5) (1 6) (8 7) (4 8))
  ((3 1) (6 2) (4 3) (1 4) (8 5) (5 6) (7 7) (2 8))
  ((3 1) (6 2) (4 3) (2 4) (8 5) (5 6) (7 7) (1 8))
  ((3 1) (6 2) (8 3) (1 4) (4 5) (7 6) (5 7) (2 8))
  ((3 1) (6 2) (8 3) (1 4) (5 5) (7 6) (2 7) (4 8))
  ((3 1) (6 2) (8 3) (2 4) (4 5) (1 6) (7 7) (5 8))
  ((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (6 8))
  ((3 1) (7 2) (2 3) (8 4) (6 5) (4 6) (1 7) (5 8))
  ((3 1) (8 2) (4 3) (7 4) (1 5) (6 6) (2 7) (5 8))
  ((4 1) (1 2) (5 3) (8 4) (2 5) (7 6) (3 7) (6 8))
  ((4 1) (1 2) (5 3) (8 4) (6 5) (3 6) (7 7) (2 8))
  ((4 1) (2 2) (5 3) (8 4) (6 5) (1 6) (3 7) (7 8))
  ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (1 7) (5 8))
  ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (5 7) (1 8))
  ((4 1) (2 2) (7 3) (5 4) (1 5) (8 6) (6 7) (3 8))
  ((4 1) (2 2) (8 3) (5 4) (7 5) (1 6) (3 7) (6 8))
  ((4 1) (2 2) (8 3) (6 4) (1 5) (3 6) (5 7) (7 8))
  ((4 1) (6 2) (1 3) (5 4) (2 5) (8 6) (3 7) (7 8))
  ((4 1) (6 2) (8 3) (2 4) (7 5) (1 6) (3 7) (5 8))
  ((4 1) (6 2) (8 3) (3 4) (1 5) (7 6) (5 7) (2 8))
  ((4 1) (7 2) (1 3) (8 4) (5 5) (2 6) (6 7) (3 8))
  ((4 1) (7 2) (3 3) (8 4) (2 5) (5 6) (1 7) (6 8))
  ((4 1) (7 2) (5 3) (2 4) (6 5) (1 6) (3 7) (8 8))
  ((4 1) (7 2) (5 3) (3 4) (1 5) (6 6) (8 7) (2 8))
  ((4 1) (8 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8))
  ((4 1) (8 2) (1 3) (5 4) (7 5) (2 6) (6 7) (3 8))
  ((4 1) (8 2) (5 3) (3 4) (1 5) (7 6) (2 7) (6 8))
  ((5 1) (1 2) (4 3) (6 4) (8 5) (2 6) (7 7) (3 8))
  ((5 1) (1 2) (8 3) (4 4) (2 5) (7 6) (3 7) (6 8))
  ((5 1) (1 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8))
  ((5 1) (2 2) (4 3) (6 4) (8 5) (3 6) (1 7) (7 8))
  ((5 1) (2 2) (4 3) (7 4) (3 5) (8 6) (6 7) (1 8))
  ((5 1) (2 2) (6 3) (1 4) (7 5) (4 6) (8 7) (3 8))
  ((5 1) (2 2) (8 3) (1 4) (4 5) (7 6) (3 7) (6 8))
  ((5 1) (3 2) (1 3) (6 4) (8 5) (2 6) (4 7) (7 8))
  ((5 1) (3 2) (1 3) (7 4) (2 5) (8 6) (6 7) (4 8))
  ((5 1) (3 2) (8 3) (4 4) (7 5) (1 6) (6 7) (2 8))
  ((5 1) (7 2) (1 3) (3 4) (8 5) (6 6) (4 7) (2 8))
  ((5 1) (7 2) (1 3) (4 4) (2 5) (8 6) (6 7) (3 8))
  ((5 1) (7 2) (2 3) (4 4) (8 5) (1 6) (3 7) (6 8))
  ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (4 7) (8 8))
  ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (8 7) (4 8))
  ((5 1) (7 2) (4 3) (1 4) (3 5) (8 6) (6 7) (2 8))
  ((5 1) (8 2) (4 3) (1 4) (3 5) (6 6) (2 7) (7 8))
  ((5 1) (8 2) (4 3) (1 4) (7 5) (2 6) (6 7) (3 8))
  ((6 1) (1 2) (5 3) (2 4) (8 5) (3 6) (7 7) (4 8))
  ((6 1) (2 2) (7 3) (1 4) (3 5) (5 6) (8 7) (4 8))
  ((6 1) (2 2) (7 3) (1 4) (4 5) (8 6) (5 7) (3 8))
  ((6 1) (3 2) (1 3) (7 4) (5 5) (8 6) (2 7) (4 8))
  ((6 1) (3 2) (1 3) (8 4) (4 5) (2 6) (7 7) (5 8))
  ((6 1) (3 2) (1 3) (8 4) (5 5) (2 6) (4 7) (7 8))
  ((6 1) (3 2) (5 3) (7 4) (1 5) (4 6) (2 7) (8 8))
  ((6 1) (3 2) (5 3) (8 4) (1 5) (4 6) (2 7) (7 8))
  ((6 1) (3 2) (7 3) (2 4) (4 5) (8 6) (1 7) (5 8))
  ((6 1) (3 2) (7 3) (2 4) (8 5) (5 6) (1 7) (4 8))
  ((6 1) (3 2) (7 3) (4 4) (1 5) (8 6) (2 7) (5 8))
  ((6 1) (4 2) (1 3) (5 4) (8 5) (2 6) (7 7) (3 8))
  ((6 1) (4 2) (2 3) (8 4) (5 5) (7 6) (1 7) (3 8))
  ((6 1) (4 2) (7 3) (1 4) (3 5) (5 6) (2 7) (8 8))
  ((6 1) (4 2) (7 3) (1 4) (8 5) (2 6) (5 7) (3 8))
  ((6 1) (8 2) (2 3) (4 4) (1 5) (7 6) (5 7) (3 8))
  ((7 1) (1 2) (3 3) (8 4) (6 5) (4 6) (2 7) (5 8))
  ((7 1) (2 2) (4 3) (1 4) (8 5) (5 6) (3 7) (6 8))
  ((7 1) (2 2) (6 3) (3 4) (1 5) (4 6) (8 7) (5 8))
  ((7 1) (3 2) (1 3) (6 4) (8 5) (5 6) (2 7) (4 8))
  ((7 1) (3 2) (8 3) (2 4) (5 5) (1 6) (6 7) (4 8))
  ((7 1) (4 2) (2 3) (5 4) (8 5) (1 6) (3 7) (6 8))
  ((7 1) (4 2) (2 3) (8 4) (6 5) (1 6) (3 7) (5 8))
  ((7 1) (5 2) (3 3) (1 4) (6 5) (8 6) (2 7) (4 8))
  ((8 1) (2 2) (4 3) (1 4) (7 5) (5 6) (3 7) (6 8))
  ((8 1) (2 2) (5 3) (3 4) (1 5) (7 6) (4 7) (6 8))
  ((8 1) (3 2) (1 3) (6 4) (2 5) (5 6) (7 7) (4 8))
  ((8 1) (4 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8)))
расстановка с картинки здесь вроде попала на 27-ю строку.

число расстановок:
Код
1.
2.
> (length (queens 8))
92
Изменено: 25.09.2020, 08:19 - Дырокол
Рейтинг: 0 / 0
25.09.2020, 08:11
Ответить | Цитировать | Написать  
Ну чо, будем решать задачу про расстановку ферзей. или чо
    #3454
Дырокол
Скрыть профиль Поместить в игнор-лист
Дырокол
Участник
должно работать на любом интерпретаторе

я использую racket
Код
1.
2.
sudo add-apt-repository ppa:plt/racket
sudo apt install racket
консольные интерпретаторы рубят юникод, поэтому красивую лямбду (λ (a b)) зарубят. в этом случае пишем топорно (lambda (a b))

если запускать не racket, а gui-шный drracket, то будет норм.
 
Рейтинг: 0 / 0
25.09.2020, 08:17
Ответить | Цитировать | Написать  
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо
Сообщения: 57 / Страницы: 1  2  3  все  
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые участники ...
Найденые участники ...
Читают тему (0):
Читают форум (0):
Участники онлайн (0):
Пользовательское соглашение
...
Закрыть
get settings:  1ms
get forum list:  1ms
check forum access:  0ms
check topic access:  0ms
get topic data:  1ms
get forum data:  0ms
get page posts:  77ms
track hit:  3ms
get tp. blocked users:  0ms
get online users:  2ms
check new:  3ms
others:  6ms
total:  94ms
созд. / загр.: 94ms (нв.: 3ms)
x
x
Закрыть


Просмотр
Close
Debug Console [Select Text]