๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A polynomial time algorithm for the N-Queens problem

โœ Scribed by Sosic, Rok; Gu, Jun

Book ID
120601923
Publisher
Association for Computing Machinery
Year
1990
Weight
405 KB
Volume
1
Category
Article
ISSN
0163-5719

No coin nor oath required. For personal study only.

โœฆ Synopsis

The
n
-queens problem is a classical combinatorial problem in the artificial intelligence (AI) area. Since the problem has a simple and regular structure, it has been widely used as a testbed to develop and benchmark new AI search problem-solving strategies. Recently, this problem has found practical applications in VLSI testing and traffic control. Due to its inherent complexity, currently even very efficient AI search algorithms developed so far can only find a solution for the
n
-queens problem with
n
up to about 100. In this paper we present a new, probabilistic local search algorithm which is based on a gradient-based heuristic. This efficient algorithm is capable of finding a solution for extremely large size
n
-queens problems. We give the execution statistics for this algorithm with
n
up to 500,000.

๐Ÿ“œ SIMILAR VOLUMES

A Polynomial-time Algorithm for the Bist
A Polynomial-time Algorithm for the Bistable Roommates Problem
โœ Jay Sethuraman; Chung-Piaw Teo ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 127 KB

In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) result