Algoritmos para el problema de las n-reinas

Alfredo Candia Véjar (1), Cesar Astudillo Hernández (1)

e-mails: acandia@utalca.cl, castudillo@utalca.cl

(1) Universidad de Talca - Dpto. de Ingeniería de Sistemas, Curicó Chile

Abstract

The n-queens problem is to find the different ways to assign n non-attacking queens in a nxn chessborad. This work analizes the application of an algorithm based on Local Search for the resolution of the n-queens problem. Empirical results show that large size instances of the problem are well solved by the Local Search algorithm in comparison to more sofisticated algorithms like Genetic algorithms.

Resumen/Resumo

El problema computacional de las n-reinas consiste en encontrar las diferentes formas de asignar n reinas a un tablero n x n, de tal manera que éstas no se ataquen. ESte trabajo analiza la aplicación de algoritmos basados en Busqueda Local para la solución del problema de las n-reinas. La experimentación computacional efectuada con instancias de gran tamaño muestran que se obtienen interesantes resultados con el algoritmo de Búsqueda Local en comparación con algoritmos más sofisticados tal como Algoritmos Genéticos

Keywords:N-queens problem, local search

Palabras Clave/Palavras Chave: Problema de las n-reinas, Búsqueda local


BibTex 

@INPROCEEDINGS{candia-vejar04:59,
                  AUTHOR       = {Alfredo Candia Véjar and Cesar Astudillo Hernández},
                  TITLE        = {Algoritmos para el problema de las n-reinas},
                  BOOKTITLE    = {30ma Conferencia Latinoamericana de Informática (CLEI2004)},
                  YEAR         = {2004},
                  editor       = {Mauricio Solar and David Fernández-Baca and Ernesto Cuadros-Vargas},
                  pages        = {160--167},
                  address      = {},
                  month        = Sep,
                  organization = {Sociedad Peruana de Computación},
                  note         = {ISBN 9972-9876-2-0},
                  file         = {http://clei2004.spc.org.pe/es/html/pdfs/59.pdf}
}

pdficon.gif PDF de este artículo
PDF de CLEI2004 (incluye todos los artículos)
Página principal CLEI 2004
Generado por Sociedad Peruana de Computación