?

Log in

No account? Create an account

Previous Entry | Next Entry

Питоническое

Увидел сегодня такое элегантное решение проблемы 8 ферзей на питоне, что просто обомлел:






def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0, nextY-i):
            return True
    return False

def queens(num=8, state=()):
    for pos in range(num):
        if not conflict(state, pos):
            if len(state) == num-1:
                yield (pos,)
            else:
                for result in queens(num, state + (pos,)):
                    yield (pos,) + result

list(queens())

Comments

( 3 comments — Leave a comment )
papa_lyosha
Feb. 12th, 2016 07:06 am (UTC)
Здорово. А вот решение в хаскелле:

conflict [] _ = False
conflict (x:xs) x' = abs(x-x') `elem` [0,length xs + 1] || conflict xs x'
queens 0 = [[]]
queens n = [xs++[x] | xs<-queens (n-1), x<-filter (not . conflict xs) [1..8] ]
answer = queens 8
solomon2
Feb. 12th, 2016 07:10 am (UTC)
Мне кажется это все-таки too cryptic :)
papa_lyosha
Feb. 12th, 2016 07:24 am (UTC)
А если 4-ую строчку заменить на
queens n = [xs++[x] | xs<-queens (n-1), x<-[1..8], not (conflict xs x) ]
Тогда она дословно переводится на русский:
"Что бы поставить n ферзей, надо поставит n-1 ферзя и добавить еще одного, который не конфликтует с остальными"

Edited at 2016-02-12 07:26 am (UTC)
( 3 comments — Leave a comment )