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 n-Queens Completion Problem transparent and simple to apply:

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, Christopher Jefferson, and 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 Walter Kosters who as well leads unique 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 theory differs standard vs modular chessboard that ‘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) as Q(n), and the number of solutions for the modular board as M(n)’ (4).

Regular vs. superimposable solutions!?

Question here is how many solution (family) we can place on a given n×n board: “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 noticed some doubtful sequences of solutions on modular board e.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:

Lemma 1

Image 1: for i=0, the whole N-sequence is condensed to the F-field…

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:

Above: W-pathway definition

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

1.2.3 In general:

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

Lemma-2

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

Lemma-2, q-variation

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

Above: W(3) pathway multiplied by 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

Above: p x p squares with F at the most upper and left field

2.1 Designing the sQ-matrices by manually superposing pxp layers
Example p=5

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

Image 3: marking given 5x5 squares in C-Grid

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

Image 4

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

image 5

… and superpose all layers:

Image 6, above: superposed layers from the C-Grid

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:

Image 7

2.2.1.1 Modulation (example):

Illustration (2.2.1.1): modulated pathways for r≤5

2.2.1.2 … modulated sQ5:

Image 8: sQuaricon(5) matrix

.

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 that is enough to find the exact modular solution

3.1 Attacking queens
(definition)

Upon the mentioned article in JAIR magazine (1) the 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 (see 3.0.4)
• Step 2: IF NOT → complete the n-Queens pathway by iterating the given ratio until the full pathway populated
• Step 3: Continue until complete the entire sQuaricon matrix
  a) choose any of the given queens (step-2) to be ‘the F’, i.e. starting position (q’) for any remaining Queens-pathways,
  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:

Image 9: Scan the given ratio rectangle (Step-1)

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

Image 10: on a torus, the translation sets back the queen to the visible field (Step 2)

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

Image 11: Iterate the given ratio-rectangle to populate full 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:

Image 12: starting always from the “F” as q’ (left square) place the new queen as the second point (q’’)…; repeat the procedure to fulfill the entire sQuaricon pattern

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.

Illustration: sQ3 — Queen on F attacks all fields

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

Image 13: W(0), W(1), W(4), W(5) pathways are not n-Queen-5-solution pathways

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.

Illustration: sQ-5 pattern translation over F-row gives ostensibly new p-Queen pathways

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 :

Note the number of translated pathways — the last digit is never 2 or 6 (above)

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’?

Two default 5-queens paths on sQ5-pattern

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.

Illustration: the n-Queens family solution for n=p: six pathways for p=5

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)

While the sQ-pathways are mutually interchangeable (by matrix’ shearing), the equilibrium of the pattern remains the same — not possible on the Latin squares (illustration above: sQ7 in action)

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 :)

sQ-11 Quadrature :)

solving the n-Queens Completion Problem :)

the combinatorics

the timing and time/space synchronisation

the constraint optimization CP

the simulating hardly relaxing systems such 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 control and deadlock prevention… Finding its applications in branches like Artificial Intelligence, it can be viewed as a very critical method to generate optimum solutions” link

likely, an ideal tool for encrypting, decrypting and all similar tasks

testing the different solutions (similar to Latin squares)

the tool for producing perfect jams, marmalades, sauces, sausages and drinks

perfect tool with balancing input/output values in any engineering tasks from the construction to processing industries

as a tool for solving Millennial Prize problems

Up to you!

I will make a video game