Skip to main content

A simple solution for the N Queens problem.

Project description

TheGrotShop logo
Github Build Status License Created
Release Released Commits since release

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:

  1. Initialize the Board: Start with an empty N×N board.
  2. Place the Queen: Try to place the queen in the first row and proceed to place subsequent queens.
  3. Check Validity: For each queen placement, check if it conflicts with already placed queens.
  4. Backtrack if Necessary: If placing a queen leads to no solution, remove the queen (backtrack) and try the next position.
  5. Store the Solution: If a valid configuration is found (N queens placed), store the board configuration.
  6. 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:

  1. Row Check: Ensuring no other queens are in the same row.
  2. Column Check: Ensuring no other queens are in the same column.
  3. 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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

wolfsoftware_nqueens-0.1.1.tar.gz (11.7 kB view details)

Uploaded Source

Built Distribution

wolfsoftware.NQueens-0.1.1-py3-none-any.whl (11.3 kB view details)

Uploaded Python 3

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

Hashes for wolfsoftware_nqueens-0.1.1.tar.gz
Algorithm Hash digest
SHA256 2362d5ded1144688f2ba145b5134ff73b4aec805366eb5028c361783e2159f5e
MD5 c61374fa84109addc1d9290dd035fe42
BLAKE2b-256 be372b23ffc27b2046214aa5799a7f425a876a006d29269f8d03673e2fe69626

See more details on using hashes here.

File details

Details for the file wolfsoftware.NQueens-0.1.1-py3-none-any.whl.

File metadata

File hashes

Hashes for wolfsoftware.NQueens-0.1.1-py3-none-any.whl
Algorithm Hash digest
SHA256 e8e41023b476d9769b0d182f841a9b41441b7f75e97b096d04c7b623dddd669d
MD5 ada853c53eb28271c61735aafa8ab21c
BLAKE2b-256 d9ac3f4398498fbfcc674dfba5a3ee099574ff1fd2d49c1e152102b2da4f2e3e

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page