Каков наилучший способ хранения доски проблемы 8 ферзя в Python

Question

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

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

Я начал с pandas.DataFrame , потому что мои данные были приведены в CSV.Затем я заметил, что должен проверить одинаковые платы, и переключился на numpy.array () для простого сравнения плат.Другой способ - использовать простой список кортежей Python:

[(q1_x, q1_y), (q2_x, q2_y), ....(q8_x, q8_y)]

Но я не знаю, какое это лучшее решение для этого.

Спасибо за любую помощь.

Answer 1

Для представления допустимых состояний:

Быстрый и компактный способ хранения позиций ферзя на шахматной доске - это простой массив (или список), где индекс представляет номер столбца, а значение - номер строки, гдекоролева находится.Вы можете использовать -1 для отметки, если в столбце нет ферзя:

Например: queens = [0, 1, 2, 3, 4, 5, 6, 7] представляет следующую конфигурацию:

  0 1 2 3 4 5 6 7
0 Q
1   Q
2     Q
3       Q
4         Q
5           Q
6             Q
7               Q

Вы также можете использоватьnumpy массив 8-битных целых чисел

[править] для представления всех состояний:

вы можете компактно использовать массив из 8 двоичных чисел от 0 до 255, где они представляютпозиция столбца ферзя:

import random

class Queens:
    def __init__(self):
        self.config = [bin(random.randrange(0, 256))[2:].zfill(8) for _ in range(8)]

    def __repr__(self):
        return'\n'.join(self.config)

    def __str__(self):
        result = ['  ' + ' '.join(str(idx) for idx in range(8))]
        for rdx, elt in enumerate(self.config):
            a = elt.replace('1', 'Q ')
            a = a.replace('0', '  ')
            a = str(rdx) + ' ' + a
            result.append(a)
        return'\n'.join(result)

q = Queens()
print(repr(q), end='\n\n')
print(q)

вывод:

01010001
10000010
01000010
10100001
01011110
10001110
01010110
11000000

  0 1 2 3 4 5 6 7
0   Q   Q       Q 
1 Q           Q   
2   Q         Q   
3 Q   Q         Q 
4   Q   Q Q Q Q   
5 Q       Q Q Q   
6   Q   Q   Q Q   
7 Q Q             

Answer 2

Альтернативой является Numba: http://numba.pydata.org/. Позволяет кодировать наивные for циклы, которые медленны в чистом питоне и все еще получают хорошую производительность.