# The modular n-Queens-Completion problem is solved by a sQuaricon pattern

## (for n=p, n=p-1)

I am a long-time enthusiast in math and would like to keep this status in future. So, all my claims exposed here should be taken with reasonable caution at least until the full experts’ verification. This article is a preprint version in work…

*this is the 3rd Revised version, as of July 21, 2019*

I will try to show and prove (with a little bit of outdated math knowledge and notification) ** 4 Claims** that make

**transparent and simple to apply:**

*n-Queens Completion Problem***Claim-1:*** the n-Queens-**Completion problem** on modular board is **solvable in the polynomial time** for any n=p, (proof in work) *(Chapter 2)

**Claim-2:** *starting with an empty pxp modular board **any two preplaced queens are belonging to the same and unique n-Queens-set **that is enough to find the exact modular solution and consequently complete the board *(Chapter 3)

**Claim-3:*** the sQuaricon*©* pattern gives in **total (p-3) default solutions** and respectively *** (p-3)*p translated solutions**(chapter 4.4)

**Claim-4: **

*The sQuaricon pattern gives*

*a “superimposable completed set” of n-Queen modular solutions,**where n=p, i.e.*

*on the modular board there is a completed form of solutions for any given p**(deterministic algorithm w/o proof is given in Chapter 4).*

n-Queens!?

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

*The n-queens problem *has a 170 Years history; in math literature there is a number of methods to get a solution for all *n*>3. However, *the n-Queens Completion problem* is more complex and not yet ‘completed’.

The n-Queens Completion!?

“The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible.” (1)

# Intro

In September 2017 it was an exciting surprise for me when on the Facebook page of my younger son I have seen an image *(**2**)* of an *8-queens-arrangement* on the chessboard looking similar to *the sQuaricon pattern *that is in the background of our video game *sQuaricon **(**3**) *and later explored what is going around it.

I’ve visited the web page of the Journal of Artificial Intelligence Research and carefully read the article of professors* *** Ian P. Gent**,

**and**

*Christopher Jefferson,***“**

*Peter Nightingale**Complexity of n-Queens Completion*”

*(*

*1*

*).*

Quite recently, I was lucky when finding a comprehensive overview of the n-Queens problem in the work of *Jordan** **Bell** and** Brett Stevens “**A survey of known results and research areas for n-queens” (**4**). *This work returned me to the real world — that I am not that weird :), or at least, I am not alone as some 200 references they have enumerated in the last 170 years.

** Universiteit Leiden** is known for its

*Computer Science department*and

*associate professor in computer science*

**who as well leads unique**

*Walter Kosters*

*n-Queens bibliography**(*

*5*

*),*now with 342 references that seems to be

**.**

*the best place to find the answers*Standard Q(n) vs modular M(n) chessboard!?

The n-Queens theorydiffersstandard vs modular chessboardthat‘the modular chessboard can be thought of as a toroidal board, with left and right edges identified and top and bottom identified’ …. ’We express the number of solutions for the standard n×n board (counting solutions in the same equivalence class as distinct) asQ(n), and the number of solutions for the modular board asM(n)’(4).

Regular vs. superimposable solutions!?

Question here is how many solution (family) we can place on a givenn×nboard:“We call a family of solutions superimposable solutions if they are disjoint, that is can be placed on the chessboard without overlap.”(4)

Default vs. Translated # of solutions on modular board!?

I have found that moving a visual area over a torus may seem like a new solution i.e.translated solution,even neither a single queen has replaced. While preparing this work I have noticedsome doubtful sequences of solutions on modular boarde.g.http://oeis.org/A051906.It will be discussed at Chapter 3.

.

# I Designing the tools for p-Queens Completion

## 1. Design a Combinatorial Grid (C-Grid)

**1.1 C-Grid definition **

*(definition-1)*

*The Combinatorial Grid is CG(i,j) array of infinitive positive integers n, satisfying the following three conditions:*

*The C-Grid defines L(n) locations in the Cartesian coordinate system:*

**Conjecture 1: The C-Grid is a new prime-number sieve?**

**1.2 Pathway W(r) definition **

*(definition-2)*

1.2.1 For *n=r*, let’s the pathway W*(r)* be the sequence of all *r* in C-Grid:

1.2.2 Proof: W(r)=L(r*k*), k=(0, 1, … ∞)

1.2.3 In general:

1.2.4 The W-pathway is an infinite sequence of L*r* location, defined by its *unique L(r0 →r1) vector*:

1.2.5 The ‘step’ in W-pathway can be multiplied by *q-times*, which gives the next variation of Lemma-2:

Illustration W(r)-pathway for *r=3*, *q=2*:

.

## 2. sQuaricon-matrix

**designing the sQ(p) matrices**

*Let’s present how to modulate Combinatorial Grid and how the input pathways transform to the sQ-pattern that is n-Queens-completed for n=p*

**sQ-matrix definition **

*(definition-3)*

*Subset**sQp⊆CG: the sQuaricon-p matrix is a subset of the C-Grid**Size:**the sQp matrix is of size p*p, where p is a prime number**Entries:**the sQp matrix entry is a set of r-elements in the range of 0 ≤ r ≤ p, i<p, and p>2**Field F**by convention is the most upper and most left field when designing the sQp matrix*

**2.1 Designing the sQ-matrices by manually superposing pxp layers E**

*xample*

*p=5*

2.1.1 For *p=5*, let’s mark its *all *5*x5 layers*:

… after cleaning all *n>5*, we will get:

… move* r=5* to most upper row (by convention)…

… and superpose all layers:

**2.2 Design the sQuaricon matrices by the modular arithmetic algorithm**

*Definition-4: sQ-matrix is squared array of *pxp

*fields that has (*p+1)

*entries appearing (*p-1)

*times each and*(F-field)

*belonging to all entry sets with next prepositions:*

So, *the sQuaricon pattern theorem* could be given in the next twin form:

2.2.5 *sQuaricon pattern theorem *for *r<p*:

2.2.6 *sQuaricon pattern theorem *for *r=p*:

2.2.7 This way all sQ-matrices are connected by its ** sQuaricon pattern**.

.

**2.2.1 Modulation**

*Example:*

2.2.1.0 Illustration — entries from the *C-Grid *before *sQ-modulation*:

2.2.1.1 Modulation (example):

2.2.1.2 … modulated sQ5:

.

# 3. n-Queens-Completion algorithm

*(deterministic algorithm for n=p)*

**Claim-2:** *starting with an empty pxp modular board **any two preplaced queens are belonging to the same and unique n-Queens-set** *t*hat is enough to find the exact modular solution*

**3.1 Attacking queens**

*(definition)*

Upon the mentioned article in *JAIR magazine (**1**) t*he attacking queens’ description *(p. 818) is*:

“*Given a queen represented by an ordered pair (α,β), the value α represents the queen’s column, and β its row on the chessboard. The values α+β and α-β represent the two diagonals the queen is on… To avoid possible confusion about which direction is which, we follow Bell and Stevens (2009) in simply calling α + β the ‘sum-diagonal’ and α — β the ‘difference-diagonal’*.”

Let’s adopt the given *attacking-queens definition *to the sQuaricon patterns:

**3.2** *Problem definition:*

We know:

- the matrix’s size, should be pxp
- at the sQ-space are given any 2 preplaced queens

**3.3** *p-Queens Completion algorithm:*

**Step 1:**check-out*if given queens attack each other***Step 2:****IF NOT**→ complete*the n-Queens pathway*byuntil the full pathway populated*iterating the given ratio***Step 3:**Continue until*complete the entire sQuaricon matrix*

a) choose any of the given queens (step-2) to be ‘’, i.e. starting position (q’) for any remaining Queens-pathways,*the F*

b) starting from*the F (q’),*place the new queen in any free position as*the second point (q’’)*… iterate the given ratio until the new pathway populated,

c) repeat the step 1 until the whole sQuaricon matrix fulfilled

Prove for Claim-2:

Any two preplaced queens by definition have one of all available ratios(see Image 1, the C-Grid includes ALL n-numbers and ALL their respective W(r) unique iterative ratios)

**3.4 sQuaricon Completion Algorithm**

Let’s have 2 Queens (Q’,Q’’) in an sQ7 matrix array; find W(*r)*-pathway they belong to:

3.4.1 We will ** translate the given ratio-rectangle** to a new position, to get 3rd queen:

3.4.2 Continue the translation by the given ratio-rectangle until populate all 7 queens:

3.4.3 in the last step let’s transform any of given queens to the F-point and finish the sQuaricon arrangement:

# 4. Default vs translated M(p) solutions

*and clearing some doubts by counting the solutions*

**4.1 Wasted Queen**

For **sQ3-matrix **there are zero n-Queen solutions as *all* *4* *available paths *are attacked by one single queen.

**4.2 Default Solutions**

So, for any *p>3* the next pathways *W0*, *W1*, *W(p-1),* and *W(p)* are never an *n-Queen solution *and should be deducted from the total # of solutions

E.g. for p=5, we have a total of 6 pathways (p+1) of whom 4 [(W(0), W(1), W(4), W(5)] should be deducted, i.e. number of default correct solution is M(p)=(p+1)-4 …. that could be written as** M(p)=p-3**

**4.3 Translated Solutions**

When moving an sQ-pattern over a torus we are in fact moving the visible area, while the *sQ-pattern* will not change. So, for all solutions with the F-field located on (0,0), we will name ‘*default*’ to differentiate it from ‘*translated*’ solutions.

**4.4 M(p) sequence — Number of default solutions**

As shown above, the sQuaricon pattern generates a total of p+1 default solution, thus, after we deduct 4 wasted pathways we get:

M(p) sequence** — **Number of translated solutions :

**4.5 Doubtful #of default solutions on modular board in the math literature**

Note: this chapter has moved as it needs repairing after I’ve received links (6, 7) to works of prof. M. R. Engelhardt who was exploring the n-Queens problem theoretically and by backtracking methods.

**4.6 Claim-4 Proof:**

**Claim-4: ***If Claim- 2 is true, the sQuaricon pattern gives **a specific ‘finite’ set of n-Queen modular solutions, **where n=p, i.e. **on the modular board there is a completed form of all solutions **for any given p*

*Proof*:

*It’s proved the Claim-2 that**any two preplaced queens**are enough proposition to get unique n-Queens set**In a given pxp modular space**any 2 preplaced queens**are belonging to the single pathway-solution**total number of non-solution pathways**that are eventually available to find new solutions**is constant 4**Since the**minimum possible n-Queens pathway**needs 5 places in pxp modular space (5>4), it means there is no way to find one more solution*

**4.7 sQuaricon is a new ‘family of the n-Queens solution’?**

As said already in the Intro of this article “*We call a family of solutions superimposable solutions if they are disjoint, that is can be placed on the chessboard without overlap.*” Such a categorization — because of ** the F-field that belongs to both categories **— now has one new model that belongs to

*regular*as well as

*superimposable*solutions.

As may be seen in bellow illustration, the sQuaricon pattern consists of p+1 pathways that are ‘overlapping at the F-field, which would mean — until proven opposite — ** the sQuaricon pattern is a new category of the n-Queen solutions**.

.

# 5. Instead of a conclusion

*Prime numbers* are one of the biggest secrets for mathematicians and such an enthusiast’s discovery of ** a squared structure system of p-numbers **should be considered as a usual exception from the rule.

**5.1 Some hunches**

5.1.1 *Prime numbers are interconnected by the singular sQuaricon pattern?*

Unlike natural non-primes, prime numbers are unique and non-composite. Regarding the fact that the sQ-matrix is doable with the prime numbers only, it ** seems like the sQuaricon pattern interconnects the primes in a solid whole**…?

5.1.2* sQuaricon pattern shows the synergy effects?*

*Synergy is the mystical word* so often in everyday use, even in scientific language. However, no precise math expression is known.

If *a point of synergy *is to make a surplus over the ordinary input entries sum (as in this case there is ** p*(p+1)>p²**), then

*the sQuaricon pattern is a maybe candidate to serve as a model to construct magic that works**.*

** The n-Queens theory** gave a bit of attention to the modular (toroidal) n-queen board, maybe as a modular board has

*considered as a variance*of the standard board.

*The sQ-matrices *are *easy to construct and simple to use*. At the end of this work, there is a link to download a *sQuaricon matrix generator* for p<200, so the reader can test their own assumptions or use it anywhere the n-queens are useful.

Feel free to check out if is there any sense to ** adopt the sQuaricon pattern as a tool **for further exploration of

*the prime numbers’*

*internal structure*and its possible applications.

Finally, I would like if you to pardon me for my poor math language and outdated knowledge.

As said above, this article is in a ** preprinted form **and needs professional revision to be considered as finished.

Goran Umicevic © 2018

*I**have found the sQuaricon matrices w/o awareness of the n-queens theory.*

# Appendices:

Appendix 1: Latin square is given as submatrix of sQ(p)

- Any sQuaricon matrix reduced for F-row/column is the
:*Latin square of size (p-1)x(p-1)*

Appendix 2: the sQuaricon pattern in its ‘elusive’ modular movement (with speculative interpretation)

In the animation above it looks like ‘the whole picture’ is in a move, but in fact, one of Yin Yang’s rows or columns is not moving during this ‘kaleidoscope show’. Why?

It is known — many *mathematics phenomena* have been considered as proof of the existence of some religious mystic power, but here it is *the physical phenomena of a time*: if time would not exist — any move would not be possible as the moving thing would not be able to find a free space — all the places are already occupied!

Here, it means simply — *the non-moving pathway *is a precondition for *the moving pathway* to be possible. In fact, if all things around you are moving then you are maybe not aware that you have moved too, i.e. *a ‘non-moving’ pathway is the position of the observer*.

Appendix 3: Download the sQuaricon matrix generator

*rename*the file to*tst1.exe*and then:

-*start it*

-*input prime number*p<200

-*get copied*the aimed sQ-matrix in a*clipboard*,

-*paste*to e.g. Excel,

-*examine*how it works*(code:**Gordan Sikic**)*

.

# Some illustrations

*a/ reflections, rotations, symmetries…*

*b*/* quadrature *:)

solving the

n-Queens CompletionProblem :)

the combinatoricsthe timing and time/space

synchronisationthe

constraint optimizationCPthe

simulating hardly relaxing systemssuch as spin glasses (Koji Hukushima,link)… “‘We also discuss the thermodynamic properties of the N queens problem at finite temperatures introduced artificially”the

Big Data sampling(in work)the placement in limited space, the placement in

limited space/time“ N queens problem has great application in the field of

artificial intelligence,parallel memory storage schemes,testing,traffic controlanddeadlock prevention… Finding its applications in branches likeArtificial Intelligence, it can be viewed as a very critical method to generate optimum solutions” linklikely, an ideal tool for

encrypting, decryptingand all similar tasks

testingthe different solutions (similar to Latin squares)the tool for producing

perfectjams, marmalades, sauces, sausages and drinksperfect tool with

balancing input/output valuesin any engineering tasks from the construction to processing industriesas a tool for solving Millennial Prize problems

Up to you!I will make a video game