Counting Solutions: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:Counting Solutions (n-Queens Problem)}} == Description == How many ways can one put $n$ queens on an $n \times n$ chessboard so that no two queens attack each other? In other words, how many points can be placed on an $n \times n$ grid so that no two are on the same row, column, or diagonal? == Related Problems == Related: Constructing Solutions, n-Queens Completion == Parameters == <pre>n: number of queens, size of chessboard</pre> == Tab...")
 
No edit summary
Line 10: Line 10:
== Parameters ==  
== Parameters ==  


<pre>n: number of queens, size of chessboard</pre>
n: number of queens, size of chessboard


== Table of Algorithms ==  
== Table of Algorithms ==  

Revision as of 12:03, 15 February 2023

Description

How many ways can one put $n$ queens on an $n \times n$ chessboard so that no two queens attack each other? In other words, how many points can be placed on an $n \times n$ grid so that no two are on the same row, column, or diagonal?

Related Problems

Related: Constructing Solutions, n-Queens Completion

Parameters

n: number of queens, size of chessboard

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Rivin, Zabih 1992 $O({8}^n*poly(n)$) $O({8}^n*n^{2})$ Exact Deterministic Time & Space

Time Complexity graph

N-Queens Problem - Counting Solutions - Time.png

Space Complexity graph

N-Queens Problem - Counting Solutions - Space.png

Pareto Decades graph

N-Queens Problem - Counting Solutions - Pareto Frontier.png

References/Citation

https://dl.acm.org/citation.cfm?id=1243380