<!-- markdownlint-disable -->
<p align="center">
<a href="https://github.com/TheGrotShop/">
<img src="https://cdn.wolfsoftware.com/assets/images/github/organisations/thegrotshop/black-and-white-circle-256.png" alt="TheGrotShop logo" />
</a>
<br />
<a href="https://github.com/TheGrotShop/NQueens-package/actions/workflows/cicd.yml">
<img src="https://img.shields.io/github/actions/workflow/status/TheGrotShop/NQueens-package/cicd.yml?branch=master&label=build%20status&style=for-the-badge" alt="Github Build Status" />
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/blob/master/LICENSE.md">
<img src="https://img.shields.io/github/license/TheGrotShop/NQueens-package?color=blue&label=License&style=for-the-badge" alt="License">
</a>
<a href="https://github.com/TheGrotShop/NQueens-package">
<img src="https://img.shields.io/github/created-at/TheGrotShop/NQueens-package?color=blue&label=Created&style=for-the-badge" alt="Created">
</a>
<br />
<a href="https://github.com/TheGrotShop/NQueens-package/releases/latest">
<img src="https://img.shields.io/github/v/release/TheGrotShop/NQueens-package?color=blue&label=Latest%20Release&style=for-the-badge" alt="Release">
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/releases/latest">
<img src="https://img.shields.io/github/release-date/TheGrotShop/NQueens-package?color=blue&label=Released&style=for-the-badge" alt="Released">
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/releases/latest">
<img src="https://img.shields.io/github/commits-since/TheGrotShop/NQueens-package/latest.svg?color=blue&style=for-the-badge" alt="Commits since release">
</a>
<br />
<a href="https://github.com/TheGrotShop/NQueens-package/blob/master/.github/CODE_OF_CONDUCT.md">
<img src="https://img.shields.io/badge/Code%20of%20Conduct-blue?style=for-the-badge" />
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/blob/master/.github/CONTRIBUTING.md">
<img src="https://img.shields.io/badge/Contributing-blue?style=for-the-badge" />
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/blob/master/.github/SECURITY.md">
<img src="https://img.shields.io/badge/Report%20Security%20Concern-blue?style=for-the-badge" />
</a>
<a href="https://github.com/TheGrotShop/NQueens-package/issues">
<img src="https://img.shields.io/badge/Get%20Support-blue?style=for-the-badge" />
</a>
</p>
## 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.
<br />
<p align="right"><a href="https://wolfsoftware.com/"><img src="https://img.shields.io/badge/Created%20by%20Wolf%20on%20behalf%20of%20Wolf%20Software-blue?style=for-the-badge" /></a></p>
Raw data
{
"_id": null,
"home_page": "https://github.com/TheGrotShop/NQueens-package",
"name": "wolfsoftware.NQueens",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": null,
"author": "Wolf Software",
"author_email": "pypi@wolfsoftware.com",
"download_url": "https://files.pythonhosted.org/packages/be/37/2b23ffc27b2046214aa5799a7f425a876a006d29269f8d03673e2fe69626/wolfsoftware_nqueens-0.1.1.tar.gz",
"platform": null,
"description": "<!-- markdownlint-disable -->\n<p align=\"center\">\n <a href=\"https://github.com/TheGrotShop/\">\n <img src=\"https://cdn.wolfsoftware.com/assets/images/github/organisations/thegrotshop/black-and-white-circle-256.png\" alt=\"TheGrotShop logo\" />\n </a>\n <br />\n <a href=\"https://github.com/TheGrotShop/NQueens-package/actions/workflows/cicd.yml\">\n <img src=\"https://img.shields.io/github/actions/workflow/status/TheGrotShop/NQueens-package/cicd.yml?branch=master&label=build%20status&style=for-the-badge\" alt=\"Github Build Status\" />\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/blob/master/LICENSE.md\">\n <img src=\"https://img.shields.io/github/license/TheGrotShop/NQueens-package?color=blue&label=License&style=for-the-badge\" alt=\"License\">\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package\">\n <img src=\"https://img.shields.io/github/created-at/TheGrotShop/NQueens-package?color=blue&label=Created&style=for-the-badge\" alt=\"Created\">\n </a>\n <br />\n <a href=\"https://github.com/TheGrotShop/NQueens-package/releases/latest\">\n <img src=\"https://img.shields.io/github/v/release/TheGrotShop/NQueens-package?color=blue&label=Latest%20Release&style=for-the-badge\" alt=\"Release\">\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/releases/latest\">\n <img src=\"https://img.shields.io/github/release-date/TheGrotShop/NQueens-package?color=blue&label=Released&style=for-the-badge\" alt=\"Released\">\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/releases/latest\">\n <img src=\"https://img.shields.io/github/commits-since/TheGrotShop/NQueens-package/latest.svg?color=blue&style=for-the-badge\" alt=\"Commits since release\">\n </a>\n <br />\n <a href=\"https://github.com/TheGrotShop/NQueens-package/blob/master/.github/CODE_OF_CONDUCT.md\">\n <img src=\"https://img.shields.io/badge/Code%20of%20Conduct-blue?style=for-the-badge\" />\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/blob/master/.github/CONTRIBUTING.md\">\n <img src=\"https://img.shields.io/badge/Contributing-blue?style=for-the-badge\" />\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/blob/master/.github/SECURITY.md\">\n <img src=\"https://img.shields.io/badge/Report%20Security%20Concern-blue?style=for-the-badge\" />\n </a>\n <a href=\"https://github.com/TheGrotShop/NQueens-package/issues\">\n <img src=\"https://img.shields.io/badge/Get%20Support-blue?style=for-the-badge\" />\n </a>\n</p>\n\n## Overview\n\nThe N-Queens problem is a classic challenge often encountered in programming interviews and academic settings. The challenge is to place N\nqueens on an N\u00d7N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.\n\n## Problem Statement\nGiven an integer n, return all distinct solutions to the n-queens puzzle. You may return the answers in any order.\n\nEach solution contains a distinct board configuration of the n-queens' placement, where 'Q' indicates a queen and '.' indicates an empty space.\n\n## Example\nFor n = 4, the possible solutions are:\n\n```\n[\n [\".Q..\", // Solution 1\n \"...Q\",\n \"Q...\",\n \"..Q.\"],\n\n [\"..Q.\", // Solution 2\n \"Q...\",\n \"...Q\",\n \".Q..\"]\n]\n```\n## Approach and Algorithms\n\n### Backtracking Algorithm\n\nThe most common approach to solve the N-Queens problem is using backtracking. The backtracking algorithm incrementally builds candidates to the \nsolution and abandons a candidate as soon as it determines that the candidate cannot possibly lead to a valid solution.\n\nSteps:\n1. `Initialize the Board`: Start with an empty N\u00d7N board.\n2. `Place the Queen`: Try to place the queen in the first row and proceed to place subsequent queens.\n3. `Check Validity`: For each queen placement, check if it conflicts with already placed queens.\n4. `Backtrack if Necessary`: If placing a queen leads to no solution, remove the queen (backtrack) and try the next position.\n5. `Store the Solution`: If a valid configuration is found (N queens placed), store the board configuration.\n6. `Repeat`: Continue this process until all possible configurations have been tried.\n\n### Challenges\n\n#### Board Representation\n\nThe board can be represented using a 2D list where each cell is either 'Q' or '.'.\n\n#### Checking Conflicts\n\nEfficiently checking for conflicts is crucial:\n\n1. `Row Check`: Ensuring no other queens are in the same row.\n2. `Column Check`: Ensuring no other queens are in the same column.\n3. `Diagonal Check`: Ensuring no other queens are on the same diagonal.\n\n### Optimization\nUsing sets to track occupied columns and diagonals can speed up the conflict check process.\n\n### Concurrency with ThreadPoolExecutor\nTo optimize solving the problem for larger n, the solution leverages concurrency with ThreadPoolExecutor:\n\n* Each thread starts solving the problem for a different column in the first row.\n* This parallel approach can significantly reduce the time to find all solutions.\n\n## Our Solution\n\nThis solution came frome one of our *Free Friday Challenges*, where we pick random interview challenges during our downtime to write solutions to.\n\n### Installation\n\n```\npip install wolfsoftware.NQueens\n```\n\n### Usage\n\n```\nusage: nqueens [-h] [-v] [-V] [board_size]\n\nSee solutions to the NQueens problem.\n\npositional arguments:\n board_size Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)\n\nflags:\n -h, --help Show this help message and exit\n -v, --verbose Enable verbose output - show the actual boards (default: False)\n -V, --version Show program's version number and exit.\n\nThe N Queens puzzle is the problem of placing N chess queens on an N\u00d7N chessboard so that no two queens threaten each other.\n```\n\n## Summary\nThe N-Queens problem is a fascinating and complex challenge that requires a deep understanding of recursion, backtracking, and optimization techniques.\nBy leveraging multi-threading, this implementation efficiently finds all possible solutions for a given board size. Understanding and implementing the\nN-Queens problem is a valuable exercise for improving problem-solving skills and algorithmic thinking.\n\n<br />\n<p align=\"right\"><a href=\"https://wolfsoftware.com/\"><img src=\"https://img.shields.io/badge/Created%20by%20Wolf%20on%20behalf%20of%20Wolf%20Software-blue?style=for-the-badge\" /></a></p>\n",
"bugtrack_url": null,
"license": null,
"summary": "A simple solution for the N Queens problem.",
"version": "0.1.1",
"project_urls": {
"Documentation": "https://github.com/TheGrotShop/NQueens-package",
"Homepage": "https://github.com/TheGrotShop/NQueens-package",
"Source": "https://github.com/TheGrotShop/NQueens-package",
"Sponsor": "https://github.com/sponsors/WolfSoftware",
"Tracker": "https://github.com/TheGrotShop/NQueens-package/issues/"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "d9ac3f4398498fbfcc674dfba5a3ee099574ff1fd2d49c1e152102b2da4f2e3e",
"md5": "ada853c53eb28271c61735aafa8ab21c",
"sha256": "e8e41023b476d9769b0d182f841a9b41441b7f75e97b096d04c7b623dddd669d"
},
"downloads": -1,
"filename": "wolfsoftware.NQueens-0.1.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "ada853c53eb28271c61735aafa8ab21c",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 11306,
"upload_time": "2024-06-26T16:42:16",
"upload_time_iso_8601": "2024-06-26T16:42:16.616084Z",
"url": "https://files.pythonhosted.org/packages/d9/ac/3f4398498fbfcc674dfba5a3ee099574ff1fd2d49c1e152102b2da4f2e3e/wolfsoftware.NQueens-0.1.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "be372b23ffc27b2046214aa5799a7f425a876a006d29269f8d03673e2fe69626",
"md5": "c61374fa84109addc1d9290dd035fe42",
"sha256": "2362d5ded1144688f2ba145b5134ff73b4aec805366eb5028c361783e2159f5e"
},
"downloads": -1,
"filename": "wolfsoftware_nqueens-0.1.1.tar.gz",
"has_sig": false,
"md5_digest": "c61374fa84109addc1d9290dd035fe42",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 11676,
"upload_time": "2024-06-26T16:42:24",
"upload_time_iso_8601": "2024-06-26T16:42:24.717086Z",
"url": "https://files.pythonhosted.org/packages/be/37/2b23ffc27b2046214aa5799a7f425a876a006d29269f8d03673e2fe69626/wolfsoftware_nqueens-0.1.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-06-26 16:42:24",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "TheGrotShop",
"github_project": "NQueens-package",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "wolfsoftware.notify",
"specs": [
[
"==",
"0.1.0"
]
]
}
],
"lcname": "wolfsoftware.nqueens"
}
JSON
