Записки начинающего функциональщика: восемь ферзей

Клас­си­че­ская фор­му­ли­ров­ка этой за­да­чи зву­чит так: най­ти все ва­ри­ан­ты рас­ста­нов­ки фер­зей на дос­ке 8 на 8 та­ких, что фер­зи не бьют друг дру­га. Обоб­щим её для дос­ки N на N.

Дос­ка бу­дет хра­нит­ся в виде спис­ка го­ри­зон­таль­ных по­зи­ций фер­зей.

Для на­ча­ла вве­дём функ­цию про­вер­ки при­над­леж­но­сти неко­то­ро­го чис­ла спис­ку:

is_in _ []          = False
is_in a (x:xs)
    | a == x        = True
    | xs == []      = False
    | True          = is_in a (xs)

Два фер­зя сто­ят на од­ной диа­го­на­ли, если вы­пол­ня­ет­ся одно из сле­ду­ю­щих усло­вий (x – вер­ти­каль, y – го­ри­зон­таль):

Вве­дём функ­цию, ко­то­рая бу­дет транс­фор­ми­ро­вать неко­то­рую те­ку­щую рас­ста­нов­ку фер­зей в сум­му или раз­ность вер­ти­ка­ли и го­ри­зон­та­ли:

diag_transform board func = [func x y | (x, y) <- zip board [0..]]

Те­перь мо­жем на­пи­сать функ­цию про­вер­ки кор­рект­но­сти до­бав­ле­ния но­во­го фер­зя к те­ку­щей рас­ста­нов­ке:

valid_pos p g board
    | is_in p board                                = False
    | is_in (p+g) (diag_transform board (+))       = False
    | is_in (p-g) (diag_transform board (-))       = False
    | True                                         = True

p и g – го­ри­зон­таль и вер­ти­каль кан­ди­да­та со­от­вет­ствен­но.

Вво­дим функ­цию ге­не­ра­ции всех кор­рект­ных по­ло­же­ний фер­зя для неко­то­рой пред­ва­ри­тель­но за­дан­ной рас­ста­нов­ки:

new_board g size board = [board ++ [x] | x <- [0..(size-1)], valid_pos x g board]

g – вер­ти­каль на ко­то­рую мы ста­вим но­во­го фер­зя, size – раз­мер дос­ки, board – те­ку­щая рас­ста­нов­ка. Не от­хо­дя от кас­сы, про­те­сти­ру­ем эту функ­цию:

> new_board 2 8 [0,2]
[[0,2,4],[0,2,5],[0,2,6],[0,2,7]]

Нам по­на­до­бить­ся вспо­мо­га­тель­ная функ­ция, объ­еди­ня­ю­щая вло­жен­ные спис­ки, т.е. [[0],[1]] => [0,1]. Вот она:

add_board [] = []
add_board (x:xs) = x ++ add_board xs

Функ­ция, на­хо­дя­щая все пе­ре­ста­нов­ки для кон­крет­ной вер­ти­ка­ли, т.е. на вход по­сту­па­ет мно­же­ство всех пе­ре­ста­но­вок для N фер­зей, на вы­хо­де спи­сок всех пе­ре­ста­но­вок для N+1 фер­зей:

trans_board g size boards_list = add_board [new_board g size x | x <- boards_list]

Про­те­сти­ру­ем её:

> trans_board 1 4 [[0],[1],[2],[3]]
[[0,2],[0,3],[1,3],[2,0],[3,0],[3,1]]

И, на­ко­нец, функ­ция де­ла­ю­щая этот про­цесс в цик­ле:

queens_rec g size pos_list =
    if g == size then pos_list
    else queens_rec (g+1) size (trans_board g size pos_list)

Ма­лень­кая обёрт­ка, ко­то­рую и бу­дем в по­след­ствии вы­зы­вать для по­ис­ка всех рас­ста­но­вок (в т.ч. она ге­не­ри­ру­ет са­мый пер­вый спи­сок рас­ста­но­вок):

queens board_size = queens_rec 1 board_size (new_board 0 board_size [])

На­сла­жда­ем­ся!

> queens 4
[[1,3,0,2],[2,0,3,1]]
> length (queens 8)
92

Та­ким об­ра­зом, ал­го­ритм для каж­до­го шага ге­не­ри­ру­ет спи­сок всех пе­ре­ста­но­вок фер­зей до кон­крет­ной вер­ти­ка­ли. При­мер для дос­ки 4x4:

1 - [[0],[1],[2],[3]]
2 - [[0,2],[0,3],[1,3],[2,0],[3,0],[3,1]]
3 - [[0,3,1],[1,3,0],[2,0,3],[3,0,2]]
4 - [[1,3,0,2],[2,0,3,1]]

Учи­ты­ваю что Haskell язык ле­ни­вый, эти спис­ки ни­ко­гда в чи­стом виде у нас в па­мя­ти не по­яв­ля­ют­ся.

Те­перь неко­то­рые за­ме­ча­ния по про­из­во­ди­тель­но­сти. На­пи­шем C++ про­грам­му для по­ис­ка пе­ре­ста­но­вок:

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

#include <iostream>
#include <vector>

unsigned num = 0;
unsigned board_size = 8;

void next_pos(std::vector& board, int dep)
{
    if ( dep == board_size )
    {
        num++;
        return;
    }

    int i;
    for ( board[dep] = 0; board[dep] < (int)board_size; ++board[dep] )
    {
        bool is_correct = true;

        for ( i = 0; i < dep; ++i )
        {
            if ( (board[i] == board[dep]) ||
                 (board[i] + i == board[dep] + dep) ||
                 (board[i] - i == board[dep] - dep) )
            {
                is_correct = false;
                break;
            }
        }

        if ( is_correct )
            next_pos(board, dep+1);
    }
}

void main()
{
    std::vector board(board_size,0);
    next_pos(board,0);
    std::cout << num << std::endl;
}

И срав­ним её ско­рость со ско­ро­стью на­шей Haskell про­грам­мы. Что­бы ско­рость вы­во­да най­ден­ных по­зи­ций не вли­я­ла на про­грам­мы, бу­дем ис­кать толь­ко ко­ли­че­ство всех пе­ре­ста­но­вок. C++ про­грам­ма ком­пи­ли­ро­ва­лась Vi­su­al Stu­dio 2005 с оп­ти­ми­за­ци­ей по ско­ро­сти. Haskell про­грам­ма ком­пи­ли­ро­ва­лась GHC 6.4.1 с оп­ци­ей -O. Ре­зуль­та­ты для дос­ки 14x14:

Haskell: 274.75 сек.
C++: 36.09 сек.

Итак, Haskell про­грам­ма по­лу­чи­лась в 7 раза мед­лен­нее, учи­ты­вая, ка­ки­ми аб­страк­ци­я­ми мы поль­зо­ва­лись (ле­ни­вые спис­ки), ка­че­ство оп­ти­ми­за­ции в GHC опре­де­лён­но вы­зы­ва­ет ува­же­ние.