Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток

@mxplusln · Регистрация: 15.12.2013

Студворк — интернет-сервис помощи студентам

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

Задача:
"Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток таким образом,
чтобы ни одна из ладей не била другую.
Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении."

@Catstail · 16.12.2013, 12:43

Здесь нужно использовать бэктрекинг...

@mxplusln · 16.12.2013, 16:30 **[ТС]**

Как раз в хаскель сложно это реализовать. С java я бы справился.

@Catstail · 16.12.2013, 16:47

Да и в Haskell, полагаю, можно.

@pycture · 16.12.2013, 20:25

Сообщение от Catstail

Здесь нужно использовать бэктрекинг...

Зачем? Просто надо найти все перестановки монжества 1..N

@Mysterious Light · 16.12.2013, 20:33

Сообщение от Catstail

Здесь нужно использовать бэктрекинг...

Для этого хорошо подходят списки.
По-хорошему, это задача на генерацию всех перестановок ряда [1..n], если последовательностью [x1,x2,..] обозначать расстановку, где на 1 строке находится на позиции x1, на 2 строке — на позиции x2 и т.д., по 1 ладье на строку.
Я предлагаю несколько общее решение с бэктрекингом, допускающая абстракцию от вида кодирования и спокобе взаимодействия фигур.

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
arrange :: ([a] -> a -> Bool) -> [[a]] -> [[a]]
arrange affect [] = return []
arrange affect (position:poss) = do
    disposition <- arrange affect poss
    pos <- filter (not . affect disposition) position
    return (pos : disposition)
 
tourAffect :: [Int] -> Int -> Bool
tourAffect = flip elem
 
tourDispos :: Int -> [[Int]]
tourDispos n = arrange tourAffect $ replicate n [1..n]

Не по теме:

Английский знаю плохо, поэтому поясняю слова, которыя я мог использовать неправильно:
«affect» = взаимодействовать
«arrange» = расставить
«disposition» = расстановка
«tour» = ладья

Можно в качестве аргумента ф-ции arrange передать любой способ взаимодействия, например, взаимодействие по диагонали учесть, тогда будет расстановка ферзей.

@Catstail · 16.12.2013, 22:07

Да, бэктрекинг - это я загнул...

@mxplusln · 16.12.2013, 23:22 **[ТС]**

спасибо за помощь))

а как бы вы написали таким же способом основную функцию, имеющею такую сигнатуру

Haskell
1
 roots::Int ->[[(Int,Int)]]

,которая выдает все возможные расстановки, для n-ладьей.

@Mysterious Light · 16.12.2013, 23:59

Перестановка permutation :: [Int] порождает такую расстановку

Haskell
1
zip [1..] permutation :: [(Int,Int)]

Соответственно, преобразовать моё решение tourDispos n :: [[Int]] или стандартную permutations [1..n] :: [[Int]] из пакета Data.List можно функцией

Haskell
1
2
map (zip [1..])
-- или так: map (zip [1..n])

Например, можно так написать:

Haskell
1
tourDispos' = map (zip [1..]) . tourDispos :: Int -> [[(Int,Int)]]

@mxplusln · 17.12.2013, 04:25 **[ТС]**

большое спасибо)) все легко и просто идёт, когда знаешь стандартные функции в Хаскель))

Добавлено через 3 часа 53 минуты
а как бы вы решили подобную задачу, только с игрой домино.

берется любое количество домино, где одна домино-косточка соответствует паре

Haskell
1
 Paar (Int, Int)

с номерами от 1 до 6, как список;

и из всех возможных "генераций рядов/строк", должно быть проверено, являются ли эти "домино-ряды/строки" ,
то есть должно быть проверено могут ли к друг другу присоединены

как бы функция domino должна потом выдать эти "домино-ряды"

@Mysterious Light · 17.12.2013, 05:10

Ну попробуйте сделать. Подсказки:
1. Можете создать "базу" всех домино, используя обычный map (дважды).
2. Перестановку ряда можно сделать стандартными средствами, используя "базу" в качестве аргумента.
3. Используйте filter над всем рядами, чтоб выделить подходящие. Предикат подходящего ряда сами можете описать.

@mxplusln · 18.12.2013, 02:33 **[ТС]**

я попробовал так решить задачу с домино

если у кого-то есть идеи, что можно улучшить или сделать эффективнее или сократить, покажите пожалуйста

Haskell
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
type Domino = (Int, Int)
 
--DOMINO-FUNKzIA
domino:: [Domino]->[[Domino]]
domino xs = [ys|ys<-perms xs, check ys == True]
 
--PROVERKA VSEH OTVETOV
check:: [Domino]->Bool
check [] = True
check (x:xs)
 | length xs ==0 = True
 | (((snd x) == (fst (head xs))) == False) = False
 | otherwise = check xs
 
--vspomogatelnaja funktizia dlja perstanovok
perms :: [Domino] -> [[Domino]]
perms [] = [[]]
perms (x:xs) = do 
  ys <- perms xs
  permsHelp x ys
 
permsHelp :: Domino -> [Domino] -> [[Domino]]
permsHelp x [] = [[x]]
permsHelp x zs@(y:ys) = (x:zs) : do
  s <- permsHelp x ys
  return (y:s)

@Mysterious Light · 27.02.2014, 04:07

Подыму старую тему в виду того, что она интересная.
Приведу свои результаты. Сравниваются стандартная функция permutations, вариант автора и мой вариант (три разные стратегии); также два варианта check, которые отличаются только организацией кода. Также приводится вариант с фильтрацией на этапе формирования перестановок domino'.

Код с тестами под GHC

Haskell
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
import Data.List(permutations)
 
type Domino = (Int, Int)
 
check:: [Domino] -> Bool
check [] = True
check (x:xs)
 | length xs == 0 = True
 | ((snd x) == (fst (head xs))) = check xs
 | otherwise = False
 
perms :: [Domino] -> [[Domino]]
perms [] = [[]]
perms (x:xs) = do 
  ys <- perms xs
  permsHelp x ys
 
permsHelp :: Domino -> [Domino] -> [[Domino]]
permsHelp x [] = [[x]]
permsHelp x zs@(y:ys) = (x:zs) : do
  s <- permsHelp x ys
  return (y:s)
 
dominoSet :: Int -> [Domino]
dominoSet n = [ (x,y) | x <- [1..n], y <- [1..n] ]
 
dominoSet3 = dominoSet 3
 
 
 
perms1 [] = [[]]
perms1 d  = (map.map) (d!!) $ p [0..pred n]
  where
    n = length d
    p :: [Int] -> [[Int]]
    p [x] = [[x]]
    p ns   = ns >>= \x -> map (x:) $ p $ filter (x/=) ns
 
perms2 = permutations
 
check' = \s -> case s of
  []     -> True
  (x:xs) -> case xs of
    []     -> True
    ~(y:_) -> (snd x == fst y) && check xs
 
dominoPC   = {-# SCC "dominoPC" #-}   \xs -> [ ys | ys <- perms  xs,  check  ys ]
dominoP1C  = {-# SCC "dominoP1C" #-}  \xs -> [ ys | ys <- perms1 xs, check  ys ]
dominoP2C  = {-# SCC "dominoP2C" #-}  \xs -> [ ys | ys <- perms2 xs, check  ys ]
dominoPC'  = {-# SCC "dominoPC'" #-}  \xs -> [ ys | ys <- perms  xs, check' ys ]
dominoP1C' = {-# SCC "dominoP1C'" #-} \xs -> [ ys | ys <- perms1 xs, check' ys ]
dominoP2C' = {-# SCC "dominoP2C'" #-} \xs -> [ ys | ys <- perms2 xs, check' ys ]
 
dominoGen :: [Domino] -> Int -> [[Domino]]
dominoGen [] _ = [[]]
dominoGen xs last = do
  x@(_,t) <- filter (\ ~(f,_) -> f == last) xs
  ys <- dominoGen (filter (x/=) xs) t
  return (x:ys)
 
domino' = {-# SCC "domino'" #-} \xs -> do
  x@(_,t) <- xs
  map (x:) $ dominoGen (filter (/=x) xs) t
  
    
 
 
cs = sum . map (sum . map (uncurry (+)))
 
main = do
    print "domino set"
    print $ ds3
    print "PC"
    print $ cs $ dominoPC ds3
    print "P1C"
    print $ cs $ dominoP1C ds3
    print "P2C"
    print $ cs $ dominoP2C ds3
    print "PC'"
    print $ cs $ dominoPC' ds3
    print "P1C'"
    print $ cs $ dominoP1C' ds3
    print "P2C'"
    print $ cs $ dominoP2C' ds3
    print "domino'"
    print $ cs $ domino' ds3
  where ds3 = dominoSet3

Bash
1
2
$ ghc --make Main.hs -o Main -O2 -prof
$ ./Main +RTS -p -sstderr

Вывод на экран:

Bash
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
"domino set"
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
"PC"
7776
"P1C"
7776
"P2C"
7776
"PC'"
7776
"P1C'"
7776
"P2C'"
7776
"domino'"
7776
   1,664,190,924 bytes allocated in the heap
     138,176,192 bytes copied during GC
          30,576 bytes maximum residency (129 sample(s))
          51,456 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)
 
  Generation 0:  3046 collections,     0 parallel,  0.44s,  0.37s elapsed
  Generation 1:   129 collections,     0 parallel,  0.02s,  0.02s elapsed
 
  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.97s  (  2.07s elapsed)
  GC    time    0.46s  (  0.39s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.42s  (  2.45s elapsed)
 
  %GC time      18.8%  (15.7% elapsed)
 
  Alloc rate    845,572,191 bytes per MUT second
 
  Productivity  81.2% of total user, 80.2% of total elapsed

Файл Main.prof

Bash
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
    Thu Feb 27 03:59 2014 Time and Allocation Profiling Report  (Final)
 
       Main +RTS -p -sstderr -RTS
 
    total time  =        2.00 secs   (100 ticks @ 20 ms)
    total alloc = 1,042,424,092 bytes  (excludes profiling overheads)
 
COST CENTRE                    MODULE               %time %alloc
 
dominoP1C                      Main                  35.0   32.3
dominoP1C'                     Main                  24.0   25.1
dominoPC                       Main                  14.0   13.6
dominoP2C                      Main                  10.0    7.6
dominoPC'                      Main                   9.0   13.6
dominoP2C'                     Main                   8.0    7.6
 
 
                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc
 
MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 CAF                     Main                                                 208          48   0.0    0.1   100.0  100.0
  domino'                Main                                                 220           1   0.0    0.0     0.0    0.0
  dominoP2C'             Main                                                 219           1   8.0    7.6     8.0    7.6
  dominoP1C'             Main                                                 218           1  24.0   25.1    24.0   25.1
  dominoPC'              Main                                                 217           1   9.0   13.6     9.0   13.6
  dominoP2C              Main                                                 216           1  10.0    7.6    10.0    7.6
  dominoP1C              Main                                                 215           1  35.0   32.3    35.0   32.3
  dominoPC               Main                                                 214           1  14.0   13.6    14.0   13.6
 CAF                     GHC.IO.Handle.FD                                     145           2   0.0    0.0     0.0    0.0
 CAF                     System.Posix.Internals                               144           1   0.0    0.0     0.0    0.0
 CAF                     GHC.Conc                                             128           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.Internals                              119           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Encoding.Iconv                                113           5   0.0    0.0     0.0    0.0

Что сразу бросается в глаза, глядя на самую последнюю таблицу (колонка %time)
1. простое переписывание check в check' без изменения логики улучшает производительность.
2. стандартная permutations работает быстрее любой частной реализации, концепция mxplusln последовательного размещения каждого элемента на каждой возможной позиции работает быстрее моей концепции о последовательном размещении на каждой позиции всех возможных элементов.
3. фильтр во время генерации перестановок рулит ))

@Qazan · 09.03.2014, 16:06

А может определитель по строке разложить .

каждый моном - это произведение чисел которые лежат одиночно и в строке и в столбце.
всего мономов факториал штук .
А каждый элемент монома содержит координату .

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@mxplusln 1 / 1 / 0 Регистрация: 15.12.2013 Сообщений: 5

	Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток 15.12.2013, 21:39. Показов 2383. Ответов 13 Метки нет (Все метки) Добрый вечер, я в хаскелле новичок помогите пожалуйста решить задачу о расстановке ладьей на шахматной доске. Для кого-то может быть будет очень интересно ее решить, но у меня мало времени, чтобы с этой задачей быстро справится. Задача: "Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении." 0

@Catstail Супер-модератор 38164 / 21099 / 4306 Регистрация: 12.02.2012 Сообщений: 34,687 Записей в блоге: 14
	16.12.2013, 12:43
	Здесь нужно использовать бэктрекинг... 0

@mxplusln 1 / 1 / 0 Регистрация: 15.12.2013 Сообщений: 5
	16.12.2013, 16:30 [ТС]
	Как раз в хаскель сложно это реализовать. С java я бы справился. 0

@Catstail Супер-модератор 38164 / 21099 / 4306 Регистрация: 12.02.2012 Сообщений: 34,687 Записей в блоге: 14
	16.12.2013, 16:47
	Да и в Haskell, полагаю, можно. 0

@Catstail Супер-модератор 38164 / 21099 / 4306 Регистрация: 12.02.2012 Сообщений: 34,687 Записей в блоге: 14
	16.12.2013, 22:07
	Да, бэктрекинг - это я загнул... 0

@Mysterious Light $Эксперт по математике/физике$ 4312 / 2104 / 431 Регистрация: 19.07.2009 Сообщений: 3,202 Записей в блоге: 24
	17.12.2013, 05:10
	Ну попробуйте сделать. Подсказки: 1. Можете создать "базу" всех домино, используя обычный map (дважды). 2. Перестановку ряда можно сделать стандартными средствами, используя "базу" в качестве аргумента. 3. Используйте filter над всем рядами, чтоб выделить подходящие. Предикат подходящего ряда сами можете описать. 1

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	09.03.2014, 16:06
	А может определитель по строке разложить . каждый моном - это произведение чисел которые лежат одиночно и в строке и в столбце. всего мономов факториал штук . А каждый элемент монома содержит координату . 0