New Constructions for the n-Queens Problem

M. Bača, S. C. López, F. A. Muntaner-Batle, A. Semaničová-Feňovčíková

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

2 Citas (Scopus)

Resumen

Let D be a digraph, possibly with loops. A queen labeling of D is a bijective function l: V(G) ⟶ { 1 , 2 , … , | V(G) | } such that, for every pair of arcs in E(D), namely (u, v) and (u, v) we have (i) l(u) + l(v) ≠ l(u) + l(v) and (ii) l(v) - l(u) ≠ l(v) - l(u). Similarly, if the two conditions are satisfied modulo n= | V(G) | , we define a modular queen labeling. There is a bijection between (modular) queen labelings of 1-regular digraphs and the solutions of the (modular) n-queens problem. The ⊗ h-product was introduced in 2008 as a generalization of the Kronecker product and since then, many relations among labelings have been established using the ⊗ h-product and some particular families of graphs. In this paper, we study some families of 1-regular digraphs that admit (modular) queen labelings and present a new construction concerning to the (modular) n-queens problem in terms of the ⊗ h-product, which in some sense complements a previous result due to Pólya.

Idioma originalInglés
Número de artículo41
PublicaciónResults in Mathematics
Volumen75
N.º1
DOI
EstadoPublicada - 1 mar. 2020
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'New Constructions for the n-Queens Problem'. En conjunto forman una huella única.

Citar esto