3,000,000 Queens in less than one minute

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

3,000,000 Queens in less than one minute

Full text

Pdf (256 KB)

Source

ACM SIGART Bulletin archive
Volume 2 , Issue 2 (April 1991) table of contents

Pages: 22 - 24

Year of Publication: 1991

ISSN:0163-5719

Authors

Rok Sosic
Jun Gu

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 40, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/122319.122325 What is a DOI?

ABSTRACT

The n - queens problem is a classical combinatorial search problem. In this paper we give a linear time algorithm for this problem. The algorithm is an extension of one of our previous local search algorithms [3, 4, 6]. On an IBM RS 6000 computer, this algorithm is capable of solving problems with 3,000,000 queens in approximately 55 seconds.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John Gary Gaschnig, Performance measurement and analysis of certain search algorithms., 1979
	2	R. M. Haralick and G. Elliot. Increasing tree search efficiency for constraint satisfaction problems. <i>Artificial Intelligence,</i> 14:263--313, 1980.
	3	R. Sosic and J. Gu. Fast <i>n</i> - queen search on VAX and Bobcat machines. Unpublished CS 547 AI Class Student Project Report, Winter Quarter 1988.
	4	R. Sosic and J. Gu. How to search for million queens. Technical Report UUCS-TR-88--008, Dept. of Computer Science, Univ. of Utah, Feb. 1988 (also available from authors).
	5	Jun Gu, Parallel algorithms and architectures for very fast AI search, University of Utah, Salt Lake City, UT, 1991
	6	Rok Sosic , Jun Gu, A polynomial time algorithm for the N-Queens problem, ACM SIGART Bulletin, v.1 n.3, p.7-11, Oct. 1990 [doi>10.1145/101340.101343]
	7	S. Minton, M.D. Johnston, A.B. Philips, and P. Laird. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In <i>Proceedings of AAAI90,</i> pages 17--24, Aug. 1990.
	8	Harold S Stone , Paolo Sipala, The average complexity of depth-first search with backtracking and cutoff, IBM Journal of Research and Development, v.30 n.3, p.242-258, May 1986
	9	Harold S. Stone , Janice M. Stone, Efficient search techniques—an empirical study of the N-Queens problem, IBM Journal of Research and Development, v.31 n.4, p.464-474, July 1, 1987

CITED BY 7

	R. Sosic , J. Gu, Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.661-668, October 1994
	Marco Valtorta, Correspondence: Response to "Explicit Solutions to the N-Queens Problem for all N", ACM SIGART Bulletin, v.2 n.4, p.4-5, Aug. 1991
	Jun Gu, Efficient local search for very large-scale satisfiability problems, ACM SIGART Bulletin, v.3 n.1, p.8-12, Jan. 1992
	Jing-Chao Chen, An efficient non-probabilistic search algorithm for the N-queens problem, Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology, p.393-396, April 02-04, 2007, Phuket, Thailand
	Benjamin W. Wah , Yao-Jen Chang, Trace-Based Methods for Solving Nonlinear Global Optimization and Satisfiability Problems, Journal of Global Optimization, v.10 n.2, p.107-141, March 1997
	Yi Shang , Benjamin W. Wah, A Discrete Lagrangian-Based Global-SearchMethod for Solving Satisfiability Problems, Journal of Global Optimization, v.12 n.1, p.61-99, January 1998
	Oron Shagrir, Two Dogmas of Computationalism, Minds and Machines, v.7 n.3, p.321-344, 1997