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

Authors

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

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

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

References

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.