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

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

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

этот подход можно сформулировать рекурсивно: предположим, что мы уже породили последовательность из всех возможных способов разместить k − 1 ферзей на первых k − 1 вертикалях доски. Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k-й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k-й вертикали не бьется ни одним из остальных. Продолжая этот процесс, мы породим не просто одно решение, а все решения этой задачи.
pasted_image.png
Изменено: 16.09.2020, 21:56 - Дырокол
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
17.09.2020, 16:47
    #2662
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
начнем с простого
empty-board представляет пустое множество позиций
заодно определим и nil как пустой список
Код
1.
(define nil '())
Код
1.
(define empty-board nil)
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
17.09.2020, 16:48
    #2663
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
раскраска кода тут конечно говно
нужно будет подумать и сделать что-нибудь уже с этим, ато никакого эстетического удовольствия
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
17.09.2020, 21:45
    #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:47
    #2692
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
92 расстановки должно получиться, ну сами пересчитайте на всякий случай
одна голова хорошо, а гарын лучше
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
17.09.2020, 21:58
    #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, 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
        тут какая-то магия, которая даёт набор позиций)))
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
17.09.2020, 22:30
    #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:45
    #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:48
    #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:56
    #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, 23:01
    #2711
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
ну вы не долбоклюи, надеюсь поняли что используем везде префиксную нотацию
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
18.09.2020, 14:59
    #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, 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))
          расширенный набор позиций)))
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
18.09.2020, 15:41
    #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, 16:09
    #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
Ответить | Цитировать | Написать  
19.09.2020, 20:17
    #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:19
    #3042
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
интересно, почему игнор на соседство самому себе я реализовал как-то по дурацки
Цитата 
(not (and (= (car a) (car b)) (= (cadr a) (cadr b)))))))
сейчас не могу понять, почему
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
19.09.2020, 20:23
    #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:49
    #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, 21:04
    #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:15
    #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:25
    #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
Ответить | Цитировать | Написать  
20.09.2020, 17:12
    #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:17
    #3106
Лигафоны Рубацова
Лигафоны Рубацова
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 17:19
    #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:20
    #3108
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Лигафоны Рубацова  20.09.2020, 17:17
3106
На ПТ пишут что ты наркоман, но я считаю что это писк ужаса от зависти.
впереди такое время, что и мёртвые позавидуют живым
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 17:26
    #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:50
    #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:53
    #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, 18:04
    #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:12
    #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: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)))
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 18:22
    #3116
Лигафоны Рубацова
Лигафоны Рубацова
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Это на чём, на лиспе что-ли?
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 18:27
    #3117
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 20:41
    #3125
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 22:23
    #3172
краник
краник
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Дырокол  20.09.2020, 20:41
3125
завтра пойду погулять в места, где интернета не будет.
дня три-четыре погуляю
так что кому не терпится решать задачу дальше, могут саморедуцироваться
опасайся водяных вшей
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 22:30
    #3177
Лигафоны Рубацова
Лигафоны Рубацова
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Дырокол  20.09.2020, 18:27
3117
Лигафоны Рубацова  20.09.2020, 18:22
3116
Это на чём, на лиспе что-ли?
2533
OK
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
20.09.2020, 22:39
    #3182
black lives matter
black lives matter
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
фсе ферзи чорные, ОК
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
22.09.2020, 21:48
    #3316
Гопник с Вантового моста
Гопник с Вантового моста
Гость
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Каждый лиспер должен хоть раз написать свой лисп, воистину, братия!
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
24.09.2020, 21:39
    #3401
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
1.jpg
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
24.09.2020, 21:39
    #3402
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
погулял
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
24.09.2020, 21:45
    #3408
SQL
SQL
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
24.09.2020, 21:49
    #3411
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
SQL  24.09.2020, 21:45
3408
Дырокол  24.09.2020, 21:39
3402
погулял
Видел недавно на границе с абхазией вид подобный но ещё круче
круче в домбае
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
24.09.2020, 21:49
    #3412
Дырокол
Дырокол
Участник
Скрыть профиль Поместить в игнор-лист
Ну чо, будем решать задачу про расстановку ферзей. или чо
если про рф говорить
и эльбрус, но туда сложно гулять
 
Рейтинг: 0 / 0
Ответить | Цитировать | Написать  
25.09.2020, 07:50
    #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:57
    #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:59
    #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, 08:02
    #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:07
    #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:11
    #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:17
    #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
Ответить | Цитировать | Написать  
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо (Сообщения: 57, Страницы: 3)
Целевая тема:
Создать новую тему:
Автор:
Найденые участники ...
Найденые участники ...
Нов. | Избр.
Читают тему (0):
Читают форум (1): Bing
Участники онлайн (1): Bing
Пользовательское соглашение
созд. / загр.: 100ms (нв.: 1ms)
Закрыть
get settings:  2ms
get forum list:  2ms
check forum access:  0ms
check topic access:  0ms
get topic data:  2ms
get forum data:  1ms
get page posts:  83ms
track hit:  3ms
get tp. blocked users:  0ms
get online users:  3ms
check new:  1ms
others:  3ms
total:  100ms
x
x
Закрыть


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