Infinite queens on an infinite chessboard

[skeptical scientist]

Can you place infinitely many queens on an infinite chessboard so that every row, column, and diagonal contains exactly one queen?

(Inspired by the other queen thread, obviously.)

Spoiler:

This one should be pretty easy; there exists a one-line solution.

[Walter.Horvath]

If I had to guess,

Spoiler:

I'd say yes.

Expanding sets that were previously complete in 8x8 to one more row/column on each edge seems to suggest that there will always be some more room? Wait, let me expand it out some more...

[aleph_one]

Yes. Here's a cheap, non-constructive argument.

Spoiler:

Since there are countably many rows, columns, and diagonals we wish to satisfy (call these regions), we may list them. We construct the arrangement by the following infinite process:

In step i, we will satisfy region i of the list. If this region already has a queen, we're done. If not, place a queen in the region that does not attack any already-placed queens. This is possible, since any queen not in the region attacks finitely many squares in the region, and only finitely many queens have been placed, so only a finite number of squares are excluded.

This solution generalizes to placing non-attacking pieces so that each region has a prescribed number of pieces as long as:

- There are countably many regions.
- Each region is infinite.
- Each piece not in a region attacks finitely many squares in that region.

I'd like to see a nice, constructive solution for this, and for the more strict problem in which each arithmetic progress of squares (meaning that the vector offset is constant) has exactly one queen.

Edit:

Spoiler:

A "greedy" solution for the quarter plane places queens on the zero-value spaces of Wythoff's Nim game. See here http://home.att.net/~numericana/answer/games.htm#wythoff.

[quintopia]

Re:constructive solution w/ arithmetic progressions: I can't put it algebraically, but it looks impossible. It seems like the distance to adjacent queens must grow exponentially in some measure.

Basically, I can find no nice neat set of arithmetic progressions that you can just sort of tile with.

[jaap]

Not quite a one-liner:

Spoiler:

Number all the columns, using some bijection from N to Z. For example, 0->0, 1->1, 2->-1, 3->2, 4->-2, ..., 2n->-n, 2n+1->n.
Do the same for the rows, and for the two sets of diagonals.
Place the queens one by one using the following procedcure:
1a. Find the row with the lowest index number that doesn't yet contain a queen.
1b. Put the next queen in that row on any any unattacked square.
2a. Find the column with the lowest index number that doesn't yet contain a queen.
2b. Put the next queen in that column on any any unattacked square.
3a. Find the \ diagonal with the lowest index number that doesn't yet contain a queen.
3b. Put the next queen in that \ diagonal on any any unattacked square.
4a. Find the / diagonal with the lowest index number that doesn't yet contain a queen.
4b. Put the next queen in that / diagonal on any any unattacked square.
5. Repeat ad infinitum.

Clearly the row/column/diagonal with index number n will be covered after 4n queens have been placed. Therefore all rows/columns/diagonals will be covered.

If that one-liner hint was intended as a clue to using queens on a single knights-move line (n,2n), then you were mistaken. That doesn't cover all diagonals, e.g. the diagonal (1+k,1-k).

Edit: Ninja'd - I'm too slow.

[Token]

Spoiler:

If that one-liner hint was intended as a clue to using queens on a single knights-move line (n,2n), then you were mistaken. That doesn't cover all diagonals, e.g. the diagonal (1+k,1-k).

Spoiler:

It wouldn't even cover all rows. It's clear there's no one-line solution in the sense that all the queens lie on a single line - the only way of covering all rows and columns with a single line is to have all the queens on the same diagonal.

[skeptical scientist]

The "one-line" solution I had in mind was indeed aleph_one's. I guess it's not quite one-line, but

Spoiler:

Fix a bijection between N and the set of rows, columns, and diagonals. Place the nth queen somewhere in the first row/column/diagonal that doesn't contain any of the first n-1 queens, somewhere which isn't attacked by any of the first n-1 queens.

is pretty close. I of course meant that the proof was one-line, not that the queens were all on a single line.

This solution is not constructive as given, but it's not hard to turn it into a constructive proof - just make all your choices constructively. (I think constructive proofs are only preferable to non-constructive ones when they provide further insight, which is clearly not the case here.)

[Nitrodon]

A constructive method:

Spoiler:

Step 1:

Code: Select all

.X...
....X
..X..
X....
...X.

Step 2:

Code: Select all

.A...
....A
..A..
A....
...A.

where A is the 5x5 block from step 1.
etc.

The middle ceil(5ⁿ/2) diagonals will all be covered exactly once on step n.

[skeptical scientist]

Nitrodon, it looks like your method is missing some diagonals.

[Sir Fluffum]

I might have missed some diagonals. I didn't bother to check.
You can if you want to.

Spoiler:

Code: Select all

.x.......
...x.....
x....x...
..x....x.
....x....
......x..
........x

continue infinitely

Edit:I just noticed that all the rows contain two.

[aleph_one]

I also thought that Nitrodon's construction missed diagonals, but on investigating further, it seems it hits all of them. It appears that the missed diagonals of each cell level are taken care of by another cell of the same level.

Is there an easy way to show that it hits all the diagonals?

[dedalus]

I think the proof would be in the fact that for any individual square there are two straight (horizontal + vertical) and two diagonals; ergo on an infinite board there are as many diagonals as there are straight lines. Thus, if the proof works for straight lines it will also work for the diagonals. It falls apart on a non-infinite board because there are more diagonal lines then there are straight lines, but you can't do this for a non-infinite board anyway (if it's not square then you need more queens to fulfill the vertical lines then the horizontal or the other way around, if it is square all corners must be filled to fill up the diagonals that only cross the corner of that square, but then the two diagonals of the square remain unfulfilled).

Edit: sorry, as there are as many straight lines as there are diagonal lines, as long as the horizontal/vertical conditions have been fulfilled AND there is max 1 queen per diagonal there must be one queen for every diagonal.

[jaap]

Edit: sorry, as there are as many straight lines as there are diagonal lines, as long as the horizontal/vertical conditions have been fulfilled AND there is max 1 queen per diagonal there must be one queen for every diagonal.

That argument (the pigeonhole principle) doesn't work when you have infinitely many items.
For example, there are just as many normal numbers as there are even numbers. That doesn't mean there are no gaps in there which form the odd numbers.
Just because every column/row is covered, doesn't mean there are no gaps in the coverage of the diagonals.

[Nitrodon]

I recently figured out a good proof for my solution.

Spoiler:

Theorem:
The solution I posted earlier works, where the limit is taken with the center fixed.

Proof:
We must use two important facts about the 5x5 cell (easily verified by observation):

1) It is a solution to the 5-queen problem on a 5x5 torus.
2) There are queens covering both center diagonals and the diagonals adjacent to them.

Inductively, we will first prove that the board is a solution to the 5ⁿ-queen problem on a 5ⁿx5ⁿ torus for each iteration. By (1), this holds for the original 5x5 cell (i.e., the base case). Suppose it holds for the (n-1)th iteration, and consider the nth iteration (in which each queen in the 5x5 cell is replaced by the current board. Each row/column/diagonal of the 5ⁿx5ⁿ torus includes either 1 or 2 row/column/diagonals of the 5x5 torus, and each of those will hit exactly one of the 5^n-1x5^n-1 boards. In fact, the intersection will correspond precisely with a row/column/diagonal on the 5^n-1x5^n-1 torus. Thus, there is exactly one queen in that row/column/diagonal, and the new board is a solution to the 5ⁿ-queen problem on a 5ⁿx5ⁿ torus.

To show that each diagonal is covered, we must use (2). In any iteration, each row, column, and diagonal through the center 5^n-1x5^n-1 board goes through the center row/column/diagonal of the 5x5 and possibly one of the two adjacent diagonals. As a result, it intersects the entirety of the corresponding row/column/diagonal of the 5^n-1x5^n-1 torus, and thus contains exactly one queen. Each row/column/diagonal of the infinite board will eventually go through the 5ⁿx5ⁿ board at some iteration, and thus will go through the center board of all later iterations. Thus, every row, column, and diagonal is covered exactly once. QED

[skeptical scientist]

Ah, that's clever.

[dedalus]

That argument (the pigeonhole principle) doesn't work when you have infinitely many items.
For example, there are just as many normal numbers as there are even numbers. That doesn't mean there are no gaps in there which form the odd numbers.
Just because every column/row is covered, doesn't mean there are no gaps in the coverage of the diagonals.

But that argument fails because of the differing sizes of infinity (i think), and if n is the number of even numbers between 1 and x, the total number of natural numbers = 2n, and this continues to occur as x->infinity. The point is that on any finite board size there are more diagonals then columns/rows because there is a left down diagonal from every square along the top and every diagonal down the side (as opposed to e.g. there is a column only for every square along the top). But, on an infinite board there are no sides, and thus we can reduce the number of diagonals to the number of columns/rows, and I can't see any much logical fallacy in that. If you define the infinite board to have a definite edge, even at infinity, then the top left corner and bottom right corner must be filled, and they would be on the same diagonal.

However, seeing as Nitrodon has made a much more formal and better proof then this, it's fairly redundant.

[dasada122]

I'm not a mathmind just yet, but if there are infinite Queens and infinite spaces, doesn't each space have a queen?

[quintopia]

dasada: no. This is what was just mentioned above, and you can see several threads about it in the math forum. To put it concisely, if you have an infinite set A and and infinite set B you can have A=B or A is a subset of B or B is a subset of A or none of the above. Infinitude doesn't give you any nice properties without more information.

[userxp]

1. Put a queen on arbitrary square
2. Find closest unattacked square (if there are more than one, choose anyone)
3. Place queen on that square
4. GOTO 2

Wouldn't that work?

[jaap]

1. Put a queen on arbitrary square
2. Find closest unattacked square (if there are more than one, choose anyone)
3. Place queen on that square
4. GOTO 2
Wouldn't that work?

Maybe, maybe not. You'll have to prove it.
While it is certainly true this method will ensure every square eventually gets attacked (or gets a queen), who's to say there isn't some row/column/diagonal that never gets a queen? Each time you place a queen an infinite number of squares get attacked that weren't being attacked before. Maybe those happen to keep covering up one row/column/diagonal fast enough that it never contains the nearest unattacked square.

[userxp]

I feel stupid. Only now I have noticed that this is not equal to the n-queens problem for n=∞ (i.e. that you must not only place infinite queens without attacking, you have to place one on each row/column/diagonal).
I have even made a crappy OO.Calc macro to try it:

Spoiler:

"Q" is the initial queen, "X" are the others. Green cells are attacked by some queen.

Anyway I think this time I got the real solution:

Spoiler:

Yes, you can: If you pick any row/column/diagonal that does not have a queen and go far enough, you will always find a free spot.

Explanation:
You can put a queen on every square that is not attacked. For a column to be impossible to have a queen, there should be other queens attacking it, but since the board is infinite, there will always be one more square. Same for rows and diagonals.
Process:
For each square, if the square is attacked by < 3 queens, there must be at least one unattacked square in the same row/column/diagonal. Put a queen there and repeat.
Once this is done each square will be attacked vertically, horizontally and diagonally, which means that there is one queen in every row/column/diagonal.

[dedalus]

I'm pretty sure that the proof fails because of the boundaries of infinitude. It's a similar thing to saying 'for every number between 0 and 1, I can double it to get a number between 0 and 2, thus as all those numbers between 0 and 1 are also included in the set between 0 and 2, there are no numbers in between 1 and two. Basically, as you continue to push out to find squares that aren't attacked and put queens in them, you have no way of proving that the boundaries you're setting on the currently-filled space aren't expanding faster then the number of squares that are being attacked by 4 queens.

[gcoope]

That's not quite right userxp, you can't guarantee that you will ever get to a specified row/column/diagonal.

However with a little tweak:

Spoiler:

There are a countably finite total number of rows/columns/diagonals. Therefore we can give them an index with the natural numbers.

For the lowest index line which isn't covered place a queen in an arbitrary uncovered spot on the line.

Repeat.


Now certainly every line will get covered, and there will always be an available spot (only finitely many can be covered out of an infinite number of options).

[jaap]

Anyway I think this time I got the real solution:

Spoiler:

Yes, you can: If you pick any row/column/diagonal that does not have a queen and go far enough, you will always find a free spot.

Explanation:
You can put a queen on every square that is not attacked. For a column to be impossible to have a queen, there should be other queens attacking it, but since the board is infinite, there will always be one more square. Same for rows and diagonals.
Process:
For each square, if the square is attacked by < 3 queens, there must be at least one unattacked square in the same row/column/diagonal. Put a queen there and repeat.
Once this is done each square will be attacked vertically, horizontally and diagonally, which means that there is one queen in every row/column/diagonal.

That's very nice, and it works. So the procedure is now:

Spoiler:

1. Find the empty square nearest the origin that isn't being attacked by 4 queens.
(not 3 - remember there are 2 diagonals)
2. Find a row/column/diagonal containing that square but not containing a queen.
3. Find an unattacked square in that row/column/diagonal and place a queen there.
4. Goto 1.

Clearly every square will eventually contain a queen or be attacked by four queens, because there are only a finite number of squares closer to the origin. Also, the procedure will never place two queens in the same row/column/diagonal. Therefore every empty square will eventually have its row/column/diagonals each contain exactly one queen. Therefore every row/column/diagonal will eventually contain exactly one queen.

By using the nearest square you implicitly set up this indexing/ordering of the rows/columns/diagonals that's been mentioned.

[dedalus]

Jaap, I might be wrong, but as the area containing queens would expand at a rate greater then the area with the conditions fulfilled, wouldn't you by definition never be able to finish this?

For clarification, If we have a finite square, then there are always 2x-1 left or right diagonals where x is the number of columns or rows. However, seeing as any square lies on just 1 left diagonal, 1 right diagonal, 1 column and 1 row, can we say that an infinite board has the same number of rows and columns as it does diagonals?

[jaap]

Jaap, I might be wrong, but as the area containing queens would expand at a rate greater then the area with the conditions fulfilled, wouldn't you by definition never be able to finish this?

Well, how do you finish an infinite task? I think that is an unanswerable question really.
However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

For clarification, If we have a finite square, then there are always 2x-1 left or right diagonals where x is the number of columns or rows. However, seeing as any square lies on just 1 left diagonal, 1 right diagonal, 1 column and 1 row, can we say that an infinite board has the same number of rows and columns as it does diagonals?

The number of rows is the same as the number of columns, is the same as the number of diagonals, and is the same as the number of squares. Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

[dedalus]

Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...

However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.

[jaap]

Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...

I was not being sarcastic. They are all the same number (or cardinality to be precise). They are all Countably infinite.

However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.

They all lie within the infinite chessboard.
There is no finite rectangular chessboard on which you can place a single queen in every row/column/diagonal, other than the trivial 1x1 case.

[douglasm]

Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...

Counting and equivalencies and such get a bit weird when infinite quantities are involved. Regardless of what your intuition might say about it, all four sets of numbers he mentioned are in fact the same size. If you can transform one set into another by using only 1-to-1 replacements, the two sets have the same size. You can transform the natural numbers into the even numbers by simply replacing every number with its double. You can transform the natural numbers into the odd numbers by replacing every number with its double minus 1. The rationals are a bit trickier, but one way is to put them in order by the sum of the numerator and denominator (ties resolved by the numerator) and then just count how far down the list each number is. 1 gets replaced by 1, 2 by 1/2, 3 by 2, 4 by 1/3, 5 by 3, 6 by 1/4, 7 by 2/3, 8 by 3/2, 9 by 4, and so on. Every natural number gets replaced with a different rational number, and no rational numbers are omitted - for any given rational number it is possible to find its position in the list in finite time - , so the end result is a size-preserving transformation between the set of natural numbers and the set of rational numbers.

However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.

You don't need to. Row 10 could be covered by a queen fifty trillion spaces away and it would still count.

[hnooch]

That's not quite right userxp, you can't guarantee that you will ever get to a specified row/column/diagonal.

However with a little tweak:

Spoiler:

There are a countably finite total number of rows/columns/diagonals. Therefore we can give them an index with the natural numbers.

For the lowest index line which isn't covered place a queen in an arbitrary uncovered spot on the line.

Repeat.


Now certainly every line will get covered, and there will always be an available spot (only finitely many can be covered out of an infinite number of options).

Nice! I wonder if there's a "nice" indexing which makes the pattern particularly easy to describe? Somehow I doubt that there's a nice way to find an index but there might still be a nice way to describe where the queens actually get placed.

[adamadam]

I came to the same solution as nitrodon did before reading the topic, it's defiantly the correct one,

Spoiler:

and you don't need numbers to prove it, just squared paper.
It's simply a fractal where the edges and center of the swastika is the repeating pattern. It's simple, easy to check and would allow you to place the queens at a much higher rate than the four step trial and error method. Not that the speed is relevant in an infinite environment, but I think it's enough to determine that it's a more effective solution.

I really suck at formulating math and it's been a while since I did it, so this is the best formula I could produce, it's probably incorrect in it's formulation, I'd like it if someone much better at math syntax understands my formula and corrects it.
Queens at : X(0,0) and {[X(+2,+1), X(+1,+2), X(-2,-1), X(+1,-2)] * 5} ^ i

[L337R3dN3k]

Here's a little insight into the problem:

Spoiler:

We seem to be assuming through this entire discussion that the size of the chessboard is countably infinite. This needs to be made explicit, as the case in which the chessboard is uncountable but the number of queens countable is not possible.

Assume the size of the chessboard is uncountably infinite, presumably (but not necessarily) implying the numbers of rows, columns, and diagonals are all uncountably infinite, and assume the number of queens is countably infinite.

Since the number of queens is countable, we will lazily number them with the integers.
Since the chess board is uncountable, we can think of it as the set of all real numbers -- any reasonable attempt to cover it with queens will result in an infinite number of spaces lying between each pair of queens. Since we are attempting to cover three different directions in this manner, the queens must be staggered -- meaning there are infinite numbers of spaces in at least two directions between each pair of regularly spaced queens. Since the queens can only provide linear coverage, this implies most of the intervening spaces must be uncovered.

Spoiler:

Assuming the size of the chessboard is countable, I believe jaap's approach will work nicely. Unfortunately, if both the size of the chessboard and the number of queens are uncountable the numbering system breaks down. We could probably find a way to cover the chessboard with the set of real numbers (though it might be easier with the set of complex numbers?), but then we would need to find a way to traverse the entire set.

[aleph_one]

If the chessboard is \mathbb{R}\times\mathbb{R} rather than \mathbb{Z}\times\mathbb{Z}, we can do a similar non-constructive argument if we well-order the lines on the chessboard. This will require the axiom of choice, which is equivalent to the well-ordering principle, and the continuum hypothesis, to guarantee to each queen is preceded by only countably many queens, so a non-attacked spot along the desired line remains.

(Actually, is the continuum hypothesis needed? I think the argument still works if the number of predecessors to each queen in the ordering is a cardinality intermediate to that of \mathbb{Z} and \mathbb{R}. Can it be shown that a subset of \mathbb{R} with such a cardinality has measure 0?)

Of course, if we assume the queen's attack lines are still the standard vertical, horizontal, and diagonal lines, there is a simple constructive solution of placing the queens along any straight line other a horizontal, vertical, or diagonal.

[skeptical scientist]

I think the argument still works if the number of predecessors to each queen in the ordering is a cardinality intermediate to that of \mathbb{Z} and \mathbb{R}. Can it be shown that a subset of \mathbb{R} with such a cardinality has measure 0?

Yes.

Lemma: Let X be a positive measure subset of R. Then there is a closed subset Y of X with positive measure.

Proof: Let I be a closed interval such that X \cap I has positive measure. Then \lambda(X \cap I)=\lambda(I)-\lambda(I \setminus X)>0, so \lambda(I \setminus X)<\lambda(I). By definition, \lambda(I \setminus X)=\inf\{\lambda(U) : U \supset I \setminus X \text{ is open}\}, so there is an open set U containing I \ X with \lambda(U)<\lambda(I). Then I \setminus U is a closed subset of X with positive measure.

Theorem: Let X be a positive measure subset of R. Then X has cardinality c, the cardinality of the continuum.

Proof:
By the lemma, we may assume X is closed. Since X has positive measure, there are disjoint closed intervals I₀ and I₁ of finite length such that each intersects X in a set of positive measure. Given I_s which intersects X in a set of positive measure, iteratively construct disjoint closed subintervals I_s0 and I_s1 such that each intersects X in a set of positive measure. In this way, we iteratively construct intervals I_t for all finite strings t of 0s and 1s, such that if s is a substring of t, then I_t \subset I_s, and if s and t are different strings of the same length, I_s and I_t are disjoint.

For each s, let x_s be an element of I_s \cap X. Given a sequence f of 0s and 1s, let x_f be a limit point of {x_s : s is an initial segment of f}. Since this set is bounded (it is a subset of I₀ or I₁) it contains a limit point. Since X is closed, this point is an element of X. Let f and g be distinct sequences of 0s and 1s. Then they differ at some position n; let u and v be the n-place initial segments of f and g, respectively. Then all but n-1 elements of {x_s : s is an initial segment of f} are elements of I_u, so x_f \in I_u. Similarly, x_g \in I_v. Since I_u and I_v are disjoint, x_f and x_g are distinct. Thus {x_f : f is an infinite sequence of 0s and 1s} is a subset of X of cardinality c.



However, you don't need to use measure. Each point you put a queen takes out at most three points on any line that doesn't contain that queen, so a simple cardinality argument suffices. Just be sure that your well-order has minimal type, so that no element has c-many predecessors.

[aleph_one]

...so a simple cardinality argument suffices...

Doh! I don't know why was so set on using measure when I only needed the difference of two sets to be non-empty.

Thanks, skeptical scientist, for the nifty proof of the measure result. I like how closure was used to show that the set contains an uncountably real number of distinct limit points.