Generalized Graph Product and its Application on Generating Solutions of the Millennium n-Queens Problem

Autores/as

  • Oliver Kolossoski Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0003-2543-9346
  • Luiz Carlos Matioli Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Curitiba, PR, Brasil https://orcid.org/0000-0002-6506-3550
  • Elvis Manuel Rodriguez Torrealba Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0001-7161-4083
  • Juliana Gomes da Silva Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0002-8715-914X

DOI:

https://doi.org/10.35819/remat2022v8i1id5379

Palabras clave:

n-Queens Problem, Graphs, Graph Theory, Graph Product

Resumen

The generalized Kronecker graph product was introduced by Figueroa-Centeno et al. (2008). Later, Baca et al. (2018) used it for obtaining solutions of the n-queens problem on larger boards from solutions on smaller boards. In this paper, we generalize the graph product and the recent results by Baca et al. (2018), obtaining a larger class of solutions by knowing solutions on lower size boards in advance. We finalize the paper stating a couple of conjectures regarding conditions for obtaining composite solutions via graph product.

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Oliver Kolossoski, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

http://lattes.cnpq.br/9946871277029782

Luiz Carlos Matioli, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Curitiba, PR, Brasil

http://lattes.cnpq.br/6084324625677114

Elvis Manuel Rodriguez Torrealba, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

http://lattes.cnpq.br/8201440943194955

Juliana Gomes da Silva, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

http://lattes.cnpq.br/9988115880438149

Citas

BACA, M.; LOPEZ, S. C.; MUNTANER-BATLE, F. A.; SEMANICOVA-FENOVCIKOVA. The n-Queens Problem: A New Approach. Technical Report, 2018.

BELL, J.; STEVENS, B. A. Survey of Known Results and Research Areas for n-Queens. Discrete Mathematics, v. 309, n. 1, p. 1-31, Jan. 2009. DOI: https://doi.org/10.1016/j.disc.2007.12.043.

BEZZEL, M. Proposal of 8-queens problem. Berliner Schachzeitung, v. 3, p. 363, 1848.

BLOOM, G.; LAMPIS, M.; MUNTANER-BATLE, F. A.; RIUS-FONT, M.; ARUMUGAM, S. Queen Labelings, AKCE International Journal of Graphs and Combinatorics, v. 8, n. 1, 2011. Available in: https://www.tandfonline.com/doi/abs/10.1080/09728600.2011.12088927. Access at: 30 May 2022.

BOLLOBAS, B. Modern Graph Theory. New York: Springer, 2002.

FIGUEROA-CENTENO, R. M.; ICHISIMA, R.; MUNTANER-BATLE, F. A.; RIUS-FONT, M. Labeling generating matrices. Journal of Combinatorial Mathematics and Combinatorial Computing, v. 67, p. 189-216, 2008.

LIONNET, F. J. E. Question 963. Jornales Annales de Matematiques, v. 8, p. 560, 1869.

LOPEZ, S. C.; ICHISIMA, R.; MUNTANER-BATLE, F. A.; RIUS-FONT, M. The Power of Digraph Products Applied to Labelings. Discrete Mathematics, v. 312, n. 2, p. 221-228, 28 Jan. 2012. DOI: https://doi.org/10.1016/j.disc.2011.08.025.

LOPEZ, S. C.; MUNTANER-BATLE, F. A. Graceful, Harmonious and Magic Type Labelings. New York: Springer, 2017.

MIKHAILOVSKI, D. New Explicit Solution to the N-Queens Problem and its Relation to the Millenium Problem. Technical Report, 2018. Available in: https://arxiv.org/abs/1805.07329. Access at: 30 May 2022.

PAULS, E. Das maximalproblem der Damen auf dem Schachbrete II. Deutsche Schachzeitung. Organ für das Gesammte Schachleben. v. 29, n. 9, p. 257-267, 1874.

POLYA, G. Uber die doppelt-periodischen Losungen des n-Damen-Problems. Matematische Unterhaltungen und Spiele, v. 2, p. 364-374, 1918.

RIVIN, I.; VARDI, I.; ZIMMERMAN, P. The n-Queens Problem. The Americal Mathematical Monthly, v. 101, n. 7, p. 629-639, 1994. DOI: https://doi.org/10.1080/00029890.1994.11997004.

Descargas

Publicado

2022-05-31

Cómo citar

KOLOSSOSKI, O.; MATIOLI, L. C.; TORREALBA, E. M. R.; SILVA, J. G. da. Generalized Graph Product and its Application on Generating Solutions of the Millennium n-Queens Problem. REMAT: Revista Eletrônica da Matemática, Bento Gonçalves, RS, v. 8, n. 1, p. e3006, 2022. DOI: 10.35819/remat2022v8i1id5379. Disponível em: https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/5379. Acesso em: 22 jul. 2024.

Número

Vol. 8 Núm. 1 (2022)

Sección

Matemática

Licencia

Derechos de autor 2022 REMAT: Revista Eletrônica da Matemática

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

REMAT conserva los derechos de autor de los artículos publicados, teniendo derecho a la primera publicación del trabajo, mención de la primera publicación en la revista en otros medios publicados y distribución de partes o del trabajo en su conjunto con el fin de promover la revista.

Esta es una revista de acceso abierto, lo que significa que todo el contenido está disponible de forma gratuita, sin costo para el usuario o su institución. Los usuarios pueden leer, descargar, copiar, distribuir, imprimir, buscar o vincular los textos completos de los artículos, o utilizarlos para cualquier otro propósito legal, sin solicitar permiso previo a la revista o al autor. Esta declaración está de acuerdo con la definición de BOAI de acceso abierto.

Artículos más leídos del mismo autor/a