VPF::Задача о восьми ферзях - Форум программистов

rafan99

Дата 23.5.2012, 07:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 23.5.2012

Репутация: нет
Всего: нет

Всем привет!
Этот код находит кол-во всех возможных расположений N-ферзей на доске NxN.Wikipedia.
Используеться backtracking+рекурсия.
Мог бы ктонибудь переделать этот рекурсивный алгоритм в нерекурсивный использущий стэк(stack).

Код


from array import array

solution_count = 0

def queen(current_row, num_row, solution_list):
    if current_row == num_row:
        global solution_count 
        solution_count = solution_count + 1
    else:
        current_row += 1
        next_moves = gen_nextpos(current_row, solution_list, num_row + 1)
        if next_moves:
            for move in next_moves:
                solution_list[current_row] = move
                queen(current_row, num_row, solution_list)
                solution_list[current_row] = 0
        else:
            return None

def gen_nextpos(a_row, solution_list, arr_size):
    cand_moves = []
    for column in range(1, arr_size):
        under_attack =  False
        for row in range(1, a_row):
            if (abs(a_row - row) == abs(column - solution_list[row]) 
                    or solution_list[row] == column):
                under_attack = True
                break
        if not under_attack:
            cand_moves.append(column)
    return cand_moves

def main():
    size=input('Ukazite razmeri stola:') 
    solution_list = array('i', [0]* (size + 1))
    queen(0, size, solution_list)
    print("Kol-vo vozmoznix raspolozenij: "+str(solution_count))


main()

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Python: Общие вопросы \| Следующая тема »