An analytical evidence for Kalé's heuristic for the \(N\) queens problem (Q1210322)

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.