Complete and Incomplete Algorithms for the Queen Graph Coloring Problem - IMT - Institut Mines-Télécom Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

Complete and Incomplete Algorithms for the Queen Graph Coloring Problem

Résumé

The queen graph coloring problem consists in covering a n x n chess board with n^2 queens in such a manner that two queens of the same color cannot attack each other. When the size, $n$, of the chess board is not a multiple of 2 or 3 it is difficult to color the queen graph with only n colors. We have developed an exact algorithm which is able to solve exhaustively this problem for dimension up to n=12 and finds a solution for n=14 in one week computing time. The 454 solutions of queen-12 show horizontal and vertical symmetries. Starting from this observation we design a new exact, but incomplete, algorithm which leads us to color queen-n problems with n colors for n=15,16,18,20,21,24 and 28 in less than one day computing time. In this paper we recall briefly the main characteristics of the first search tree algorithm then we describe the four kinds of geometric operations we have used to improve significantly our results.
Fichier principal
Vignette du fichier
complete-and-incomplete-algorithms.pdf (5.22 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00353904 , version 1 (24-10-2023)

Identifiants

  • HAL Id : hal-00353904 , version 1

Citer

Michel Vasquez, Djamal Habet. Complete and Incomplete Algorithms for the Queen Graph Coloring Problem. ECAI 2004: 16th European Conference on Artificial Intelligence, Aug 2004, Valencia, Spain. pp.226-230. ⟨hal-00353904⟩
244 Consultations
5 Téléchargements

Partager

Gmail Facebook X LinkedIn More