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

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.

Downloads

Published

2022-05-31

How to Cite

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.

Issue

Vol. 8 No. 1 (2022)

Section

Mathematics

License

Copyright (c) 2022 REMAT: Revista Eletrônica da Matemática

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

REMAT retains the copyright of published articles, having the right to first publication of the work, mention of first publication in the journal in other published media and distribution of parts or of the work as a whole in order to promote the magazine.

This is an open access journal, which means that all content is available free of charge, at no cost to the user or his institution. Users are permitted to read, download, copy, distribute, print, search or link the full texts of the articles, or use them for any other legal purpose, without requesting prior permission from the magazine or the author. This statement is in accordance with the BOAI definition of open access.

Most read articles by the same author(s)