NQueens package

Обзор

Проблема N-Queens-это классическая задача, часто встречающаяся в программных интервью и академических условиях. Задача состоит в том, чтобы поместить n Queens на шахматную доску N × N, так что ни одна две королевы не угрожают друг другу. Это означает, что ни один из двух королев не может разделить одну и ту же строку, столбец или диагональ.

Запись о проблеме

Учитывая целое число n, верните все различные решения головоломки N-Quozle. Вы можете вернуть ответы в любом порядке.

Каждое решение содержит отдельную конфигурацию платы N-Queens «размещение», где «Q» указывает королеву и «». Указывает пустое пространство.

Пример

Для n = 4 возможные решения:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Подход и алгоритмы

Алгоритм возврата

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

Шаги:

1. Initialize the Board : начните с пустой платы N × N.
2. Place the Queen : попробуйте поместить королеву в первый ряд и приступить к размещению последующих королев.
3. Check Validity : для каждого размещения королевы проверьте, противоречит ли оно с уже размещенными королевами.
4. Backtrack if Necessary : если размещение королевы приводит к отсутствию решения, удалите королеву (отступайте) и попробуйте следующую позицию.
5. Store the Solution : если найдена допустимая конфигурация (n Queens), храните конфигурацию платы.
6. Repeat : Продолжайте этот процесс, пока не будут опробованы все возможные конфигурации.

Проблемы

Представление совета директоров

Плата может быть представлена ​​с использованием 2D -списка, где каждая ячейка является либо «Q», либо '.

Проверка конфликтов

Эффективная проверка конфликтов имеет решающее значение:

1. Row Check : гарантирование никаких других королев не находится в одном и том же ряду.
2. Column Check : Обеспечение никаких других королев не находится в одном столбце.
3. Diagonal Check : гарантирование никаких других королев не находится на одной диагонали.

Оптимизация

Использование наборов для отслеживания занятых столбцов и диагонали может ускорить процесс проверки конфликтов.

Параллелизм с ThreadPoolexeCutor

Чтобы оптимизировать решение проблемы для более крупного N, решение использует параллелизм с помощью ThreadPoolexeCutor:

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

Наше решение

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

Установка

 pip install wolfsoftware.NQueens

Использование

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

Краткое содержание

Проблема n-Queens-это захватывающая и сложная проблема, которая требует глубокого понимания методов рекурсии, обратного отслеживания и оптимизации. Используя многопоточное, эта реализация эффективно находит все возможные решения для данного размера доски. Понимание и реализация проблемы N-Queens является ценным упражнением для улучшения навыков решения проблем и алгоритмического мышления.