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


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