The N-Queens Problem

The formulation of the N-queens problem in the language of ccalc above is absolutely tight in the sense of "Tight logic programs," by E. Erdem and V. Lifschitz (in TPLP, Vol. 3, pp. 499-518, 2003.)

The formulation of the N-queens problem in the language of ccalc, with nested expressions, is equivalent to its formulation in the language of lparse, with cardinality constraints. This is due to equivalent transformations of "Weight constraints as nested expressions," by P. Ferraris and V. Lifschitz (to appear in TPLP).

The performances of smodels and ccalc on this problem, in terms of computation time, is discussed in [Erdem & Lifschitz, 2003] mentioned above. A comparison of smodels and cmodels on this problem is presented in the note comparison.ps prepared by Y. Lierler.