Regresar

New Constructions for the n-Queens Problem

Abstract:

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.