Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
Say I have a chessboard (8x8=64 tiles, of course) and e.g. 22 pieces; tiles
are numbered 1 through 64); I want to deploy these 22 pieces throughout the chessboard (black or white tiles don't matter); every time I do this I get a set of 22 numbers (numbers of the tiles the pieces reside in); I am looking for code that would generate for me all possible deployments of these 22 pieces (sets of 22 numbers); it should not be too complex but I cannot find a clue to start off with... Please, please, give me a hint!:-) |
#2
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
On Dec 25, 10:36*am, Mac wrote:
Say I have a chessboard (8x8=64 tiles, of course) and e.g. 22 pieces; tiles are numbered 1 through 64)[.] I am looking for code that would generate for me all possible deployments of these 22 pieces "Generate" and do what with them? Write them to the Immediate Window? Print them out? Put each on a different worksheet, or at least in a different 8x8 ranges? Display and wait for the user to press OK to continue? No matter. I assure you that is not what you want to do. There are about 8E+16 ways of arranging 22 pieces on an 8x8 board. Even if you could "generate" (generate and display in some form) one combination every microsecond, it would take nearly 2548 years(!) to generate them all. (And I am sure it would take more than one microsecond for each combination, at least on any PC today.) it should not be too complex but I cannot find a clue to start off with... Please, please, give me a hint! You are correct: the structure of the "generate" code (not including displaying results) is relatively simple. It might be doable with 22 nested FOR loops. Alternatively, it could be done with a recursive SUBroutine. The trick is to avoid duplicate combinations. Sometimes that can be done without storing and comparing against previous solutions (very costly in time and space!) by carefully ordering the relative positions of each subsequent piece in a single iteration. I have not given this any thought to see if that can be done in this case because the problem "incomputable", so it makes no difference. There may be ways to break the problem into parts and harness the power of multiple ("a multitude" of) computers to reduce the total compute time significantly. But that goes far beyond the simplicity of your question. |
#3
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
Errata....
On Dec 25, 12:43*pm, I wrote: *There are about 8E+16 ways of arranging 22 pieces on an 8x8 board. Actually, I think the number is 9E+37. Either way, it's a b-i-g number. |
#4
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
9E+37 if each of the 22 pieces are unique.
The OP didn't make it clear whether he wanted to distinguish between 8 white pawns, or between 2 black rooks, or between 2 white bishops (with the interesting complication that the OP said he didn't want to distinguish between black & white squares, which would normally distinguish the 2 white bishops). Nor did he make it clear which 22 of the original 32 pieces he has. -- David Biddulph "joeu2004" wrote in message ... Errata.... On Dec 25, 12:43 pm, I wrote: There are about 8E+16 ways of arranging 22 pieces on an 8x8 board. Actually, I think the number is 9E+37. Either way, it's a b-i-g number. |
#5
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
With just 22 items being scattered around 64, it sounds to me like the
number of Permutations. =FACT(64) - 1.26887E+89 all possible deployments of these 22 pieces (sets of 22 numbers) Sounds like it could be Chess pieces, or maybe not. We would need more info. -- Dana DeLouis "David Biddulph" <groups [at] biddulph.org.uk wrote in message ... 9E+37 if each of the 22 pieces are unique. The OP didn't make it clear whether he wanted to distinguish between 8 white pawns, or between 2 black rooks, or between 2 white bishops (with the interesting complication that the OP said he didn't want to distinguish between black & white squares, which would normally distinguish the 2 white bishops). Nor did he make it clear which 22 of the original 32 pieces he has. -- David Biddulph "joeu2004" wrote in message ... Errata.... On Dec 25, 12:43 pm, I wrote: There are about 8E+16 ways of arranging 22 pieces on an 8x8 board. Actually, I think the number is 9E+37. Either way, it's a b-i-g number. |
#6
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
On Dec 26, 1:43*am, "David Biddulph" <groups [at] biddulph.org.uk
wrote: 9E+37 if each of the 22 pieces are unique. You are right, of course. In my first reponse, I assumed that the pieces were not distinct. But driving home from an Xmas party, I morphed the problem statement into another where pieces are presumed to be distinct. I quickly checked the OP's inquiry when I got home (after midnight) and misread it in a way that "confirmed" my morphed problem statement. Looking back, I think I was right the first time. The OP didn't make it clear whether he wanted to distinguish between 8 white pawns, or between 2 black rooks, or between 2 white bishops (with the interesting complication that the OP said he didn't want to distinguish between black & white squares, which would normally distinguish the 2 white bishops). Nor did he make it clear which 22 of the original 32 pieces he has. For those reasons and others, I presumed that the OP is not talking about chess pieces, or at least not using them as chess pieces per se (with all the accompanying rules). I think the reference to a "chessboard" merely refers to the 8x8 grid. Notice that "chessboard" is even quoted in the subject line, and the text refers to "tiles". |
#7
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
On Dec 26, 10:38*am, "Dana DeLouis" wrote:
With just 22 items being scattered around 64, it sounds to me like the number of Permutations. =FACT(64) *- *1.26887E+89 There are "64 choose 22" ways of selecting 22 of the 64 squares on which to place the pieces. It does not matter whether we choose those squares in the order of 1,2,...,22 or 22,23,...1, for example. In Excel, that would be COMBIN(64,22). If the 22 pieces are distinct (I now believe they are not), there are FACT(22) ways of ordering the pieces on each of the "64 choose 22" combinations. You could multiply the two, or you could simply compute PERMUT(64,22). |
#8
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
A "chessboard" problem
PERMUT(64,22).
You are absolutely correct. My mistake. Thanks for the catch. :) -- Dana "joeu2004" wrote in message ... On Dec 26, 10:38 am, "Dana DeLouis" wrote: With just 22 items being scattered around 64, it sounds to me like the number of Permutations. =FACT(64) - 1.26887E+89 There are "64 choose 22" ways of selecting 22 of the 64 squares on which to place the pieces. It does not matter whether we choose those squares in the order of 1,2,...,22 or 22,23,...1, for example. In Excel, that would be COMBIN(64,22). If the 22 pieces are distinct (I now believe they are not), there are FACT(22) ways of ordering the pieces on each of the "64 choose 22" combinations. You could multiply the two, or you could simply compute PERMUT(64,22). |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
change "true" and "false" to "availble" and "out of stock" | Excel Worksheet Functions | |||
problem with Linking workbooks via "copy" and "paste link" | Excel Discussion (Misc queries) | |||
HELP on "left","right","find","len","substitute" functions | Excel Discussion (Misc queries) | |||
Count occurences of "1"/"0" (or"TRUE"/"FALSE") in a row w. conditions in the next | New Users to Excel | |||
Complex if test program possible? If "value" "value", paste "value" in another cell? | Excel Discussion (Misc queries) |