A simple solution for the N Queens problem.
Project description
Overview
The N-Queens problem is a classic challenge often encountered in programming interviews and academic settings. The challenge is to place N queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.
Problem Statement
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answers in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' indicates a queen and '.' indicates an empty space.
Example
For n = 4, the possible solutions are:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Approach and Algorithms
Backtracking Algorithm
The most common approach to solve the N-Queens problem is using backtracking. The backtracking algorithm incrementally builds candidates to the solution and abandons a candidate as soon as it determines that the candidate cannot possibly lead to a valid solution.
Steps:
Initialize the Board
: Start with an empty N×N board.Place the Queen
: Try to place the queen in the first row and proceed to place subsequent queens.Check Validity
: For each queen placement, check if it conflicts with already placed queens.Backtrack if Necessary
: If placing a queen leads to no solution, remove the queen (backtrack) and try the next position.Store the Solution
: If a valid configuration is found (N queens placed), store the board configuration.Repeat
: Continue this process until all possible configurations have been tried.
Challenges
Board Representation
The board can be represented using a 2D list where each cell is either 'Q' or '.'.
Checking Conflicts
Efficiently checking for conflicts is crucial:
Row Check
: Ensuring no other queens are in the same row.Column Check
: Ensuring no other queens are in the same column.Diagonal Check
: Ensuring no other queens are on the same diagonal.
Optimization
Using sets to track occupied columns and diagonals can speed up the conflict check process.
Concurrency with ThreadPoolExecutor
To optimize solving the problem for larger n, the solution leverages concurrency with ThreadPoolExecutor:
- Each thread starts solving the problem for a different column in the first row.
- This parallel approach can significantly reduce the time to find all solutions.
Our Solution
This solution came frome one of our Free Friday Challenges, where we pick random interview challenges during our downtime to write solutions to.
Installation
pip install wolfsoftware.NQueens
Usage
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.
Summary
The N-Queens problem is a fascinating and complex challenge that requires a deep understanding of recursion, backtracking, and optimization techniques. By leveraging multi-threading, this implementation efficiently finds all possible solutions for a given board size. Understanding and implementing the N-Queens problem is a valuable exercise for improving problem-solving skills and algorithmic thinking.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file wolfsoftware_nqueens-0.1.1.tar.gz
.
File metadata
- Download URL: wolfsoftware_nqueens-0.1.1.tar.gz
- Upload date:
- Size: 11.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.1 CPython/3.12.4
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2362d5ded1144688f2ba145b5134ff73b4aec805366eb5028c361783e2159f5e |
|
MD5 | c61374fa84109addc1d9290dd035fe42 |
|
BLAKE2b-256 | be372b23ffc27b2046214aa5799a7f425a876a006d29269f8d03673e2fe69626 |
File details
Details for the file wolfsoftware.NQueens-0.1.1-py3-none-any.whl
.
File metadata
- Download URL: wolfsoftware.NQueens-0.1.1-py3-none-any.whl
- Upload date:
- Size: 11.3 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.1 CPython/3.12.4
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8e41023b476d9769b0d182f841a9b41441b7f75e97b096d04c7b623dddd669d |
|
MD5 | ada853c53eb28271c61735aafa8ab21c |
|
BLAKE2b-256 | d9ac3f4398498fbfcc674dfba5a3ee099574ff1fd2d49c1e152102b2da4f2e3e |