Skip to content

Research at St Andrews

Models and symmetry breaking for 'peaceable armies of queens'

Research output: Book/ReportBook

Author(s)

B M Smith, K E Petrie, I P Gent

School/Research organisations

Abstract

We discuss a difficult optimization problem on a chess-board, requiring equal numbers of black and white queens to be placed on the board so that the white queens cannot attack the black queens. We show how the symmetry of the problem can be straightforwardly eliminated using SBDS, allowing a set of non-isomorphic optimal solutions to be found. We present three different ways of modelling the problem in constraint programming, starting from a basic model. An improvement on this model reduces the number of constraints in the problem by introducing ancillary variables representing the lines on the board. The third model is based on the insight that only the white queens need be placed, so long as there are sufficient unattacked squares to accommodate the black queens. We also discuss variable ordering heuristics: we present a heuristic which finds optimal solutions very quickly but is poor at proving optimality, and the opposite heuristic for which the reverse is true. We suggest that in designing heuristics for optimization problems, the different requirements of the two tasks (finding an optimal solution and proving optimality) should be taken into account.

Close

Details

Original languageEnglish
PublisherUnknown Publisher
Number of pages16
Publication statusPublished - 2004

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Solving computational problems in the theory of word-representable graphs

    Akgün, Ö., Gent, I. P., Kitaev, S. & Zantema, H., 24 Feb 2019, In : Journal of Integer Sequences. 22, 2, 17 p., 19.2.5.

    Research output: Contribution to journalArticle

  2. A review of literature on parallel constraint solving

    Gent, I. P., Miguel, I. J., Nightingale, P. W., McCreesh, C., Prosser, P., Moore, N. & Unsworth, C., Sep 2018, In : Theory and Practice of Logic Programming. 18, 5-6, p. 725-758 34 p.

    Research output: Contribution to journalArticle

  3. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Complexity of n-Queens completion (extended abstract)

    Gent, I. P., Jefferson, C. A. & Nightingale, P. W., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 5608-5611 4 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

ID: 728202

Top