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

Oliver Kolossoski; Luiz Carlos Matioli; Elvis Manuel Rodriguez Torrealba; Juliana Gomes da Silva

doi:10.35819/remat2022v8i1id5379

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 descarga aún 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

Referencias

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.