Place 16 queens in a $16\times 16$ board peacefully, also in subboards!

Question

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)$?

Answer 1

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.

Answer 2

[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.

Answer 3

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