5
$\begingroup$

What is the smallest number, $n$ in which $n$ queens can live in a $n\times n$ board peacefully? Of course not more than 8. ☺ (read about the eight queen puzzle)

But this was not the question.

Before asking the question let's first sport you with the following definition.

Definition: a peaceful area of size $k$ on a chessboard, is a $k$ by $k$ square of squares containing $k$ queens in which no two queens threaten each other, i.e. no two queen are in the same row, column or diagonal.

Question:
Given an integer $N>7$, let $f(N)$ be the smallest number such that it is possible to place $N$ queens on an $N$ by $N$ chessboard in a way that for every $k$ with $f(N)\le k\le N$, there is a peaceful area of size $k$.

  1. What is $f(16)$?

  2. Is it the case that for all $N>16$, $f(N)=f(16)$?

  3. Does there exist an $M$ such that for all $N>M$, $f(N)=f(M)$?

$\endgroup$
  • $\begingroup$ I've edited the question for clarity. If this isn't what you intended, undo the edit. $\endgroup$ – f'' Jun 13 '16 at 0:38
  • $\begingroup$ @f'' Thanks, I did some minor tweaks on your edition, if you think it needs more, would you please help? $\endgroup$ – Omid Ghayour Jun 13 '16 at 1:33
  • $\begingroup$ Certainly $f(8)=7$ since all fundamental solutions either have $3$ or $4$ queens on the perimeter, we can only find a peaceful area within of size $k=7$ for those with $3$ queens on the perimeter (solutions 2 and 3 in the linked Wikipedia page) and of those solutions the only $k=7$ areas then have $4$ on that square's perimeter. This approach may lead to an answer for the question at hand. $\endgroup$ – Jonathan Allan Jun 13 '16 at 3:03
2
$\begingroup$

Partial Answer - i am not 100% sure of my analysis, but am happy to have people pick at it...

Note that

Since $k$-regions are continuous, $f(n)$ results from those $n$-solutions such that maximal recursive removals, $r$, of queens occupying a corner of the current region (and their occupied row and column) are possible. $f(n) = n - r$

Also

$f(n)\geq f(n-1)$ since any sub-region may be considered as a whole region.

Further observations

Any $k$-region may only have a single corner occupied (since a queen on a corner threatens the other $3$)

Each time a queen is removed during the recursive process for finding $r$ referenced above the new sub-region may only have a queen occupying at most one of $2$ of the $4$ corners, since the queen that was previously removed was threatening the other $2$ corners of the sub-region.

The sub-region must be solvable without placing a queen on any of the diagonals the previously removed queens threatened.

Any solution with a queen on a corner is a member of a set of $8$ isomorphic solutions under symmetry (the only time the set is smaller is when rotation by quarter turns or reflections in the horizontal or vertical thereof are the same, which cannot be the case with a queen on the corner as it would be in conflict with the other queen to which it translated) thus we only need to consider one such arrangement.

Labelling positions as $(\text{row}, \text{column})$ with top-left as $(0,0)$ and bottom-right as $(n-1,n-1)$ the arrangement to be considered is then one isomorphic to that of placing the queens to be removed at locations in the first $r$ positions of the sequence: $((0,0), (1,n-1), (2,1), (3,n-2), (4,2), (5,n-3), (6,3), \cdots, (n-1, \lfloor\frac{n}{2}\rfloor))$
Note: Certainly this sequence can never be fully utilised (making $r=n$) since at some point a position will be on a diagonal already used earlier (e.g. $n=5$ has $(5,n-3)=(5,5)$ sharing a diagonal with $(0,0)$.

$f(n)$ results given $n<16$ (utilising a DLX based solver and exhaustive search):

\begin{align}f(4)&=4\\f(5)&=4\\f(6)&=6\\f(7)&=6\\f(8)&=7\\f(9)&=8\\f(10)&=8\\f(11)&=9\\f(12)&=9\\f(13)&=9\\f(14)&=11\\f(15)&=11\\\end{align}

  1. What is $f(16)$ ?

    $f(16)=13$ (confirmed by exhaustive search)

    There are $334$ solutions of the isomorphic form suggested such as the following:
    (ignore A; then A and B; then A, B and C)

    A . . . . . . . . . . . . . . . 
    . . . . . . . . . . . . . . . B 
    . C . . . . . . . . . . . . . . 
    . . . . . . . . . Q . . . . . . 
    . . Q . . . . . . . . . . . . . 
    . . . . . . Q . . . . . . . . . 
    . . . . . . . . . . . . . Q . . 
    . . . . . . . . . . . Q . . . . 
    . . . . . Q . . . . . . . . . . 
    . . . . . . . . . . . . . . Q . 
    . . . . . . . . . . . . Q . . . 
    . . . Q . . . . . . . . . . . . 
    . . . . . . . . Q . . . . . . . 
    . . . . Q . . . . . . . . . . . 
    . . . . . . . Q . . . . . . . . 
    . . . . . . . . . . Q . . . . . 

  2. Is it the case that for all $n>16$, $f(n)=f(16)$ ?

    If my analysis is correct, no - a counter-example would be $f(18)=14$.

  3. Does there exist an $m$ such that for all $n>m$, $f(n)=f(m)$ ?

    I strongly suspect not. As we place queens in the sequence suggested the sub-region always allows the next placement to make $r$ potentially one bigger as would be required, but the sub-region seems to not always be solvable, some analysis of the regions excluded by the diagonals threatened by removed queens should be made here to show that this will always occur.

$\endgroup$
  • $\begingroup$ Your answer impressed me! $\endgroup$ – Omid Ghayour Jun 14 '16 at 15:18
  • $\begingroup$ I would like to see your calculation... I think there is no Mathematical proof for what you find till now... am I write!? $\endgroup$ – Omid Ghayour Jun 14 '16 at 15:19
  • $\begingroup$ You are right that there is no formal proof, but it is a logical argument - we must reduce to sub-regions queen by queen and the only way we can do that is for the queen we are removing to be on a corner of the current region. $\endgroup$ – Jonathan Allan Jun 14 '16 at 15:21
0
$\begingroup$

[The following (1) used to say 3 and 2 where it now says 4 and 3, which was the result of a misreading; sorry about that. More to the point, it (2) is answering the question originally asked which is not the question as it now stands. So, wrong in multiple ways, but I believe in being honest about one's mistakes so I'm not deleting it :-). Also, the paper referenced may be of some relevance.]

Perhaps I'm misunderstanding the question, but I think the answer is always

$n=4$

because

whenever $n>3$ you can put $n$ non-attacking queens on an $n\times n$ chessboard: see e.g. this paper.

$\endgroup$
  • $\begingroup$ This is not true even for 3! $\endgroup$ – Omid Ghayour Jun 13 '16 at 0:16
  • 1
    $\begingroup$ Try putting 3 queens on a 3x3 board... I think you've misread the paper you're citing. $\endgroup$ – f'' Jun 13 '16 at 2:50
0
$\begingroup$

Let me add something that would help in a formal proof.

Any $n$ by $n$ peaceful region has either 3 or 4 queens living in its $4n-4$ house large boundary. But just those which has just 3 queens on their border has as a peaceful subregion of size $n-1$ by $n-1$.

If $l<m<n$ is it necessary that an $l$ by $l$ peaceful region to be a subregion of an $m$ by $m$ region!?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.