Author 
Topic: 3D Chessboard Full Control (Read 13870 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


3D Chessboard Full Control
« on: Sep 25^{th}, 2003, 12:25pm » 
Quote Modify

It is known that N rooks may be placed on a 2dimensional NxN chessboard so that every square is controled by at least one rook. What's the minimal number of rooks on 3D chessboard NxNxN to meet this condition? Generalize to Kdimensional chessboard. If this is important: I don't know the answer


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: 3D Chessboard Full Control
« Reply #1 on: Sep 25^{th}, 2003, 12:48pm » 
Quote Modify

Well, since each rook can control at most 3N2 squares, it should be evident that we need at least N^{3}/(3N2), which is a little larger than N^{2}/3. But we could also show that we can't meet this lower bound, because you can only put N rooks in there before you have at least some squares controlled by more than one rook. It should also be obvious that we can do it with N^{2} rooks, but this is not necessarily the best we can do. In fact, it's definitely not the best, because a 2x2x2 board can be controlled by 2 rooks. Hmm ...

« Last Edit: Sep 25^{th}, 2003, 12:50pm by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #2 on: Sep 25^{th}, 2003, 6:46pm » 
Quote Modify
Remove

It's easy enough to figure out a theoretical minimum. Start by placing N rooks on each horizontal level. Now you will remove M rooks from each level. That will leave M^2 free spaces on that level that are not being controlled. Each of those spaces must have a rook directly above or directly below it, so the remaining N1 levels must have at least M^2 rooks total. So for an 8x8x8 board: if M is 4 then N1 levels will have 28 rooks, more than enough to cover the M^2 free spaces on each level. And in fact you can remove 4 more rooks (from 4 different levels, so M for those 4 levels is 5 (matching the 25 rooks available to cover their free spaces). The total is 28 rooks. Now whether those rooks can actually be given a satisfactory arrangement, I don't know. And I'm not very good at visualizing a Kdimensional chessboard to generalize.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: 3D Chessboard Full Control
« Reply #3 on: Sep 26^{th}, 2003, 7:18am » 
Quote Modify

I think the visitor's method may be assuming too much symmetry. Is it really obvious that there must be an optimum solution with as nearly as possible the same number of rooks per level.


IP Logged 



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #4 on: Sep 26^{th}, 2003, 7:26am » 
Quote Modify
Remove

My theoretical minimum is too minimum. The best I could come up with is for N=3: 5 for N=4: 8 for N=5: 13 for N=6: 18 for N=8: 32 To generalize for a Kdimensional board, it's best to define the problem numerically. Create a list of numbers in base N1, up to K digits long, such that you can generate any number up to K digits long by changing a single digit in one of your numbers. SUppose N is 11 and K is 4. Then our riddle would be in base 10 and we'd be asking for a list of 4 digit numbers (including leading 0's) that can generate all numbers up to 9999 by changing a single digit. Can any of our local mathematicians solve that? I figured out the 2x2x2x2 chessboard, at least. It's 4. That is, 1111, 1000, 0001, 0110


IP Logged 



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #5 on: Sep 26^{th}, 2003, 9:05am » 
Quote Modify
Remove

Duh, change that N1 to N. I don't know what I was thinking. Anyway, my first attempt at a solution for 3x3x3x3 is 16. That's probably not optimal, but close.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #6 on: Sep 29^{th}, 2003, 1:16am » 
Quote Modify

on Sep 26^{th}, 2003, 7:26am, visitor wrote:My theoretical minimum is too minimum. The best I could come up with is... 
 Visitor, this is interesting... Are you confident these are the optimal numbers? How did you get them? I only managed to get the numbers for N = 3, 4. By the way, assuming your numbers are correct: this sequence does not appear in Sloane's Encyclopedia. I also tried to realize what conditions the optimal placement may satisfy. For instance:  Is it true that for any N, there exists an optimal placement where N rooks may be chosen so that no two of them control the same field? The answer is No (counterexample given by N=3), meaning that the greedy placement algorithm won't always give an optimum.  Is it true that for any N, there exists an optimal placement which is symmetric (with respect to a subgroup of a symmetry group of a cube). The answer seems to be Yes, but I haven't got an evidence. Just thinking aloud... on Sep 26^{th}, 2003, 7:18am, rmsgrey wrote:Is it really obvious that there must be an optimum solution with as nearly as possible the same number of rooks per level. 
 I agree, it's intuitive. Also, the N=3, 4 cases satisfy this.


IP Logged 



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #7 on: Sep 29^{th}, 2003, 6:26am » 
Quote Modify
Remove

I'm not at all confident that my numbers are optimal, but I used a method that is easy to expand for any N (when K is 2) The formula is simply (N^2)/2 when N is even and ((N1)/2)^2+((N+1)/2)^2 when N is odd. Here's my visualized solution for N=5, which should make the method obvious (the numbers are what level the rook is on) 12300 123000 23100 231000 31200 312000 00045 000456 00054 000564 000645 It appears that this method can be expanded to any K as well; (I think you'll just replace the ^2 with ^(K1).) The 3x3x3x3 board is optimal at 15. Here's my 4x4x4x4 solution (32), 1200 2100 0034 0043 2100 1200 0043 0034 0034 0043 1200 2100 0043 0034 2100 1200 //Corrected by Icarus in accordance with Visitor's later post below.

« Last Edit: Sep 30^{th}, 2003, 7:08pm by Icarus » 
IP Logged 



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #8 on: Sep 29^{th}, 2003, 6:28am » 
Quote Modify
Remove

That first chart is both N=5 and N=6 (not quite formatted correctly) The second set of numbers shows one set of numbers for each of the 4th dimension levels.


IP Logged 



visitor
Guest


Re: 3D Chessboard Full Control
« Reply #9 on: Sep 30^{th}, 2003, 6:45am » 
Quote Modify
Remove

In my N=5 and N=6 solutions (for K=3), I made a last minute change that threw in an error. The first line of each should be 12300 or 123000. I was hoping somebody else would jump in with a better solution. My 4dimensional method of extending the same method works, but it seems horribly inefficient. But I can't seem to improve on it. In 2 dimensions you needed N rooks per level. In 3 dimensions N/2 rooks per level. But in 4 dimensions (and I presume beyond) my method doesn't reduce that any further. In that 4x4x4x4 solution, by the time you've placed the rooks onthe first 3 boards, those three are completely controlled, and the fourth has 24 of its 64 spaces controlled; yet it's still going to take just as many rooks to finish it off. Anyone who's good at 4dimensional analysis should feel free to point me to a better answer.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #10 on: Sep 30^{th}, 2003, 9:51am » 
Quote Modify

on Sep 30^{th}, 2003, 6:45am, visitor wrote:In my N=5 and N=6 solutions (for K=3), I made a last minute change that threw in an error. The first line of each should be 12300 or 123000. 
 That's OK. I managed to reconstruct the right configuration. It's so simple... I was thinking in a completely different direction. on Sep 30^{th}, 2003, 6:45am, visitor wrote:I was hoping somebody else would jump in with a better solution. 
 There are some hints that your solution for K=3 is optimal. However, the proof is still missing. on Sep 30^{th}, 2003, 6:45am, visitor wrote:My 4dimensional method of extending the same method works, but it seems horribly inefficient. But I can't seem to improve on it. In 2 dimensions you needed N rooks per level. In 3 dimensions N/2 rooks per level. But in 4 dimensions (and I presume beyond) my method doesn't reduce that any further 
 My friend (who introduced me to this problem) told me that this problem was once proposed at the Soviet Olympiad, and that the exact answer was known just for K=3; for higher dimensions only the bounds were known. Anyway, I think you made an excellent progress on this puzzlle, Visitor!


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 3D Chessboard Full Control
« Reply #11 on: Sep 30^{th}, 2003, 7:18pm » 
Quote Modify

I corrected your original post, so that those reading it for the first time will see it in the right form. May I suggest again that you register. Then you can correct erroneous posts yourself! And as a bonus, you're great knowledge and experience in international investment will be acknowledged with the financial opportunity of a lifetime (a possibly rather short lifetime if you were to act upon it ) Okay  so the latter inducement is not exactly a strong selling point. But this is the only time it has happened so far. Hopefully, more of them can be avoided.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Perfection
Newbie
Gender:
Posts: 17


Re: 3D Chessboard Full Control
« Reply #12 on: Nov 22^{nd}, 2003, 10:45pm » 
Quote Modify

Please excuse the [nu]b question, but what exactly is a "3d chessboard" ? Is it just an NxNxN grid? And what exactly are the rules for a rook in a 3d chessboard? And what is defined as full control?


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: 3D Chessboard Full Control
« Reply #13 on: Nov 23^{rd}, 2003, 12:04am » 
Quote Modify

A kdimensional "chessboard" is just a regular grid of kcubes forming a kcube of side N  so the 3D chessboard is indeed an NxNxN grid. A krook can move parallel to any of the edges of its kchessboard, so it "controls" any cell that differs in at most one coordinate (so a 3rook at (1,2,3) on a 3x3x3 board would control (1,2,3), (2,2,3), (3,2,3), (1,1,3), (1,3,3) (1,2,1) and (1,2,2)) "Full control" is the situation where every cell is controlled by at least one rook.


IP Logged 



godskook
Guest


Re: 3D Chessboard Full Control
« Reply #14 on: Feb 17^{th}, 2004, 7:58am » 
Quote Modify
Remove

This is what I have so far on the 3dimensional board. Each NxNxN cube has "S" as a solution. Here are some of the numbers I got. N=1 S=1 N=2 S=2 N=3 S=5 N=4 S=8 N=5 S=13* N=6 S=20+ N=7 S=21* N=8 S=32+ N=9 S=40# N=10 S=52+ N=12 S=80+ N=14 S=84+ N=16 S=128+ A * means that I am reasonably sure but not positive A + means that I used a technique which relied on an earlier number, that does give a solution just possibly not the optimal one A # means that I have good reasons to doubt my answer as the most optimal I while try and post some of the trends I found later, but I don't have time right now.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #15 on: Feb 19^{th}, 2004, 12:34am » 
Quote Modify

godskook, there is a strong evidence (I don’t know the proof, however) that S = N^{2}/2 for N even, and S = (N^{2} + 1)/2 for N odd. This contradicts your results for N = 6, 10 and 12. I would like to see the actual configurations, if you have them.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3D Chessboard Full Control
« Reply #16 on: Feb 19^{th}, 2004, 1:03am » 
Quote Modify

he did mark them with a plus, so as he said they might not be optimal (and in all three cases you predict it to be lower, so that fits)


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #17 on: Feb 19^{th}, 2004, 4:00am » 
Quote Modify

towr, you are right, I missed the direction... If so, there are N=7 and 9 where goodskook claims to make better than predicted optimum (for N=9 I am not sure 'cause I don't understand exactly the meaning of # sign).


IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: 3D Chessboard Full Control
« Reply #18 on: Feb 19^{th}, 2004, 4:41am » 
Quote Modify

on Feb 19^{th}, 2004, 4:00am, Barukh wrote:(for N=9 I am not sure 'cause I don't understand exactly the meaning of # sign). 
 on Feb 17^{th}, 2004, 7:58am, godskook wrote:A # means that I have good reasons to doubt my answer as the most optimal 



IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



godskook
Guest


Re: 3D Chessboard Full Control
« Reply #19 on: Feb 19^{th}, 2004, 8:41am » 
Quote Modify
Remove

for all my higher even resultsthose marked with a + I used the following technique 1.Divide the cube into eight equal regions each of size N/2 2.Take the solution to the previously solved case of N/2 and insert it into the size N cube so that each S(N/2) solution occuppies one and only one of the regions found in step one without any rook being able to capture any other rook. Although this technique does not guarentee optimization, it does guarentee a solution. It is easy to check because all you have to consider is any one of the four regions that does not have the N/2 solutions in them(thanks to symmetry) and show that the rooks from the three adjacent regions control all the spaces in this one. this suggests the relationship: S(2N)<=4S(N) my solution configs for 6,7,9,10,12 are as follows: the solutions for 12 and 6 use the solution to 3 and are the the direct result of the above relationship  If someone needs the solution to N=3 let me know My 10 is base on my 5 using the above technique the solution to my N=5,and N=7 I use the following placements for both <3.3.3> <3.5.5> <4.4.4> <5.5.3> <5.3.5> <1.1.1> <2.2.2> <4.1.2> <4.2.1> <1.4.2> <2.4.1> <1.2.4> <2.1.4> For just the 7 <6.6.6> <7.7.7> <4.6.7> <4.7.6> <6.4.7> <7.4.6> <7.6.4> <6.7.4> Hope that helps


IP Logged 



Guest
Guest


Re: 3D Chessboard Full Control
« Reply #20 on: Feb 19^{th}, 2004, 9:26am » 
Quote Modify
Remove

In your solution for N=7, I don't see any rook attacking 3,(6 or 7),(1 or 2) or (6 or 7),3,(1 or 2) or (1 or 2),(6 or 7),5 or (6 or 7),(1 or 2),5 or (1 or 2),(3 or 5),(6 or 7) or (3 or 5), (1 or 2), (6 or 7)


IP Logged 



godskook
Guest


Re: 3D Chessboard Full Control
« Reply #21 on: Feb 22^{nd}, 2004, 3:20pm » 
Quote Modify
Remove

You're right I missed those. thats what I get for thinking I could generalize


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: 3D Chessboard Full Control
« Reply #22 on: Apr 27^{th}, 2004, 12:10am » 
Quote Modify

If we reformulate this puzzle in terms of errorcorrecting codes and link to it from the CS section, we can bring a new life to this thread.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7517


Re: 3D Chessboard Full Control
« Reply #23 on: Apr 28^{th}, 2004, 1:55pm » 
Quote Modify

Except that in errorcorrecting codes, the aim would be to put as many rooks as possible without having 2 rooks attacking the same cell.


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: 3D Chessboard Full Control
« Reply #24 on: Apr 28^{th}, 2004, 3:09pm » 
Quote Modify

on Apr 28^{th}, 2004, 1:55pm, grimbal wrote:Except that in errorcorrecting codes, the aim would be to put as many rooks as possible without having 2 rooks attacking the same cell. 
 Rather "controlling the same cell" (a rook does not attack a cell it is in). My understanding is that our aim is equivalent to constructing a minimal code that has a (weird) property of all singledigit errors being correctable or detectable, but not one doubledigit error can as a doubledigit error.


IP Logged 



