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

Январь 01, 2006, 23:32

Здрав­ствуй­те до­ро­гие!

Во-пер­вых, раз­ре­ши­те всех по­здра­вить с на­сту­пив­шим Но­вым 2006 Го­дом! Сча­стья, уда­чи, успе­хов всем в но­вом году!

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

Это опять за­да­ча о рас­ста­нов­ке фер­зей, на сей раз за­ни­ма­ем­ся толь­ко под­счё­том ко­ли­че­ства воз­мож­ных рас­ста­но­вок:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
module Main
where

queens_rec _ 0 _ = 1
queens_rec board_size curr_vert test_func =
let correct_hor = filter (\x -> test_func curr_vert x) [1 .. board_size]
in sum (
map (\x -> queens_rec board_size (curr_vert-1) (
\vert horiz -> (vert /= curr_vert) &&
(horiz /= x) &&
(vert + horiz /= curr_vert + x) &&
(vert - horiz /= curr_vert - x) &&
(test_func vert horiz)
)) correct_hor
)

queens board_size = queens_rec board_size board_size (\x y -> True)

main = print (queens 8)

Ключ к по­ни­ма­нию:

Для про­вер­ки оче­ред­ной по­зи­ции мы ис­поль­зу­ем лямб­да-функ­цию от двух ар­гу­мен­тов: вер­ти­каль и го­ри­зон­таль. Для са­мой пер­вой по­зи­ции эта функ­ция все­гда бу­дет воз­вра­щать True для всех по­сле­ду­ю­щих эта функ­ция пре­вра­ща­ет­ся в ком­по­зи­цию про­вер­ки те­ку­щей рас­ста­нов­ки и всех преды­ду­щих:

\vert horiz -> (vert /= curr_vert) &&
(horiz /= x) &&
(vert + horiz /= curr_vert + x) &&
(vert - horiz /= curr_vert - x) && (test_func vert horiz)

Т.е. ин­фор­ма­цию о те­ку­щем со­сто­я­нии дос­ки мы хра­ним в виде од­ной длин­ной лямб­да-фук­ции.

blog comments powered by Disqus
Сергей Лымарь © 2005-2014, Все права защищены.