Решение загадки n-queen

Question

Я только что решил проблему nqueen в python. Решение выводит общее число решений для размещения n ферзей на шахматной доске nXn, но попытка сделать это с n = 15 занимает больше часа, чтобы получить ответ Может кто-нибудь взглянуть на код и дать мне советы по ускорению этой программы ...... начинающий программист Python.

#!/usr/bin/env python2.7

##############################################################################
# a script to solve the n queen problem in which n queens are to be placed on
# an nxn chess board in a way that none of the n queens is in check by any other
#queen using backtracking'''
##############################################################################
import sys
import time
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:
                '''make a move on first legal move of next moves'''
                solution_list[current_row] = move
                queen(current_row, num_row, solution_list)
                '''undo move made'''
                solution_list[current_row] = 0
        else:
            return None

def gen_nextpos(a_row, solution_list, arr_size):
    '''function that takes a chess row number, a list of partially completed 
    placements and the number of rows of the chessboard. It returns a list of
    columns in the row which are not under attack from any previously placed
    queen.
    '''
    cand_moves = []
    '''check for each column of a_row which is not in check from a previously
    placed queen'''
    for column in range(1, arr_size):
        under_attack =  False
        for row in range(1, a_row):
            '''
            solution_list holds the column index for each row of which a 
            queen has been placed  and using the fact that the slope of 
            diagonals to which a previously placed queen can get to is 1 and
            that the vertical positions to which a queen can get to have same 
            column index, a position is checked for any threating queen
            '''
            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():
    '''
    main is the application which sets up the program for running. It takes an 
    integer input,N, from the user representing the size of the chessboard and 
    passes as input,0, N representing the chess board size and a solution list to
    hold solutions as they are created.It outputs the number of ways N queens
    can be placed on a board of size NxN.
    '''
    #board_size =  [int(x) for x in sys.stdin.readline().split()]
    board_size = [15]
    board_size = board_size[0]
    solution_list = array.array('i', [0]* (board_size + 1))
    #solution_list =  [0]* (board_size + 1)
    queen(0, board_size, solution_list)
    print(solution_count)


if __name__ == '__main__':
    start_time = time.time()
    main()
    print(time.time() 

Answer 1

Алгоритм возврата к проблеме N-Куинса - это наихудший алгоритм в худшем случае.Так что для N = 8, 8!число решений проверяется в худшем случае, N = 9 делает его равным 9 !, и т. д. Как видно, число возможных решений растет очень быстро и очень быстро.Если вы мне не верите, просто зайдите в калькулятор и начните умножать последовательные числа, начиная с 1. Дайте мне знать, как быстро калькулятору не хватает памяти.

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

Поскольку вам нужно найти все правильные решения, на самом деле мало что можно сделать для ускорения программы.Вы уже хорошо поработали, удалив невозможные ветви из дерева поиска.Я не думаю, что есть что-то еще, что будет иметь большое влияние.Это просто медленный алгоритм.

Answer 2

Только что увидел этот вопрос.Я хотел бы внести 2 решения.

1. Этот возвращает все различные решения

2. Этотвозвращает первое найденное правильное решение

Обратная связь приветствуется.Приветствия

Answer 3

Я бы посоветовал вам взглянуть на test_generators.py из источника Python для альтернативной реализации проблемы N-Queens.

Python 2.6.5 (release26-maint, Sep 12 2010, 21:32:47) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from test import test_generators as tg
>>> n= tg.Queens(15)
>>> s= n.solve()
>>> next(s)
[0, 2, 4, 1, 9, 11, 13, 3, 12, 8, 5, 14, 6, 10, 7]
>>> next(s)
[0, 2, 4, 6, 8, 13, 11, 1, 14, 7, 5, 3, 9, 12, 10]

Answer 4

Количество решений можно оценить, используя метод рандомизированной оценки Дональда Кнута.

Начиная с отсутствия королев, количество разрешенных позиций для следующей строки равно n.Произвольно выберите одну из позиций и рассчитайте количество разрешенных позиций (p) для следующей строки, умножьте ее на n и сохраните как общее количество решений (total = n * p), затем случайным образом выберите одну из разрешенных позиций..

Для этой строки рассчитайте количество разрешенных позиций (p) для следующей строки и умножьте на это общее количество решений (total * = p).Повторяйте это до тех пор, пока либо плата не может быть решена, в этом случае число решений равно нулю, либо пока плата не будет решена.

Повторите это много раз и рассчитайте среднее количество решений (включая любые нули).Это должно дать вам быструю и довольно точную аппроксимацию числа решений с помощью аппроксимации, улучшающей чем больше прогонов вы делаете.

Надеюсь, это имеет смысл;)

Answer 5

Мы также можем решить n-ферзей с помощью генетических алгоритмов.Это описано здесь https://youtu.be/l6qll5OldHQ, в одной из лекций курса edX ColumbiaX: CSMM.101x Искусственный интеллект (AI).

Целевая функция пытается оптимизировать количество неагрессивных пар королев.Анимация ниже показывает пример решения в R с n = 20.Более подробную информацию о том, как решить n-королевы с помощью генетических алгоритмов, можно найти здесь: https://sandipanweb.wordpress.com/2017/03/09/solving-the-n-queen-puzzle-with-genetic-algorithm-in-r/?frame-nonce=76cf9b156a.

Answer 6

Ниже моя реализация PYTHON. Возможно, вы захотите использовать PYPY для большей скорости.

Его скорости помогает использование метода времени O (1), чтобы проверить, атакованы ли уже следующие королевы теми, кто уже находится на доске.

Если предположить, что программа "nqueen.py", пример для ее запуска - "python nqueen.py 6", где 6 - это размер доски 6x6.

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, "N Queens" with an O(1) time method to check whether the next queen is attacked
#
import sys


board_size = int(sys.argv[1])
Attacked_H  = { i:0 for i in range(0, board_size) }
Attacked_DU = { i:0 for i in range(0, board_size*2) }
Attacked_DD = { i:0 for i in range(-board_size, board_size) }


def nqueen(B, N, row, col):
    if(row >= N):
        return 1
    if(col >= N):
        print "board:\n" + str.join("\n", ["_|"*q + "Q|" + "_|"*(board_size - q - 1) for q in B])
        return 0
    B[col] = row
    if(0==(Attacked_H[row] + Attacked_DU[row+col] + Attacked_DD[row-col])):
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 1,1,1 ]
        nqueen(B, N, 0, col + 1)
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 0,0,0 ]
    nqueen(B, N, row + 1, col)


nqueen(list(range(0, board_size)), board_size, 0, 0)