An analytical evidence for Kalé's heuristic for the N queens problem

DOI10.1016/0020-0190(93)90196-GMaRDI QIDQ1210322zbMATH OpenOpenAlexFDO

Authors Sang-Bong Oh

Publication date 23 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90196-g

zbMATH Keywords

\(N\) queens problembacktrackscombinatorial problemsKalé's heuristicsearch techniques

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

The \(N\) queens problem has been one of the most popular testbeds for investigating many search techniques for combinatorial problems. Recently, \textit{L. V. Kalé} [Inf. Process. Lett. 34, No. 4, 173-178 (1990; Zbl 0696.68097)] presented an almost perfect heuristic for this problem in the sense that it finds a first solution without any backtracks in most cases. Although it is based on the empirical solution densities, it is not justified to be sound in the analytical point of view. This paper provides an analytical evidence for Kalé's value- ordering heuristic which follows middle-out instantiation of the first 1/3 and the last 1/3 rows and out-middle instantiation for the middle 1/3 rows.

Recommendations

• An almost perfect heuristic for the N nonattacking queens problem
• Fast search algorithms for the n-queens problem
• Landscape analysis and efficient metaheuristics for solving the \(n\)-queens problem
• New decision rules for exact search in \(N\)-queens
• scientific article; zbMATH DE number 1743978

Cites work

• An almost perfect heuristic for the N nonattacking queens problem

Cited in

(2)

• New decision rules for exact search in \(N\)-queens
• An almost perfect heuristic for the N nonattacking queens problem

This page was built for publication: An analytical evidence for Kalé's heuristic for the \(N\) queens problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210322)