чОткий форум
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
Ответить | Цитировать | Написать  
Форумы / Общение / Ну чо, будем решать задачу про расстановку ферзей. или чо
Сообщения: 57 / Страницы: 1  2  3  все  
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые участники ...
Найденые участники ...
Читают тему (0):
Читают форум (1): Google
Участники онлайн (1): Google
Пользовательское соглашение
...
Закрыть
get settings:  1ms
get forum list:  1ms
check forum access:  0ms
check topic access:  0ms
get msg page:  0ms
>>> redirection >>>:  210ms
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:  33ms
track hit:  4ms
get tp. blocked users:  0ms
get online users:  5ms
check new:  5ms
others:  8ms
total:  270ms
созд. / загр.: 270ms (нв.: 5ms)
x
x
Закрыть


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