Hi. I find this interesting. Twenty two pieces placed anywhere on 64
squares gives us a permutation size of:
=FACT(64) -> 1.26887E+89
This is a very large size, and makes listing all the Permutations basically
impossible.
Sometimes one only wants a few items from this impossible size list.
Suppose we number the pieces 1-22, and we make numbers 23-64 represent blank
items.
Suppose the first item in this make-believe list are the numbers 1-64 in
order. We interpret this to mean item 1 goes in square 1, item 2 goes in
square 2, etc.
Let's find the n_th number in this list. Here's a very large number in vba
that we must make a string.
item =
"68150507012993473643859647269872270118456282946940829277556802127127796280441531804255520"
With vba, we can immediately tell that the arrangement is:
Layout = UnrankPermutation(item, 64)
{35, 24, 38, 31, 64, 50, 2, 34, 46, 54, 3, 1, 8, 55, 39, 25, 63,
59, 26, 13, 17, 15, 6, 28, 36, 52, 7, 61, 32, 16, 12, 27, 37,
57, 21, 62, 49, 43, 18, 60, 45, 42, 23, 22, 56, 5, 9, 20, 11,
47, 41, 30, 10, 29, 58, 53, 4, 33, 14, 19, 40, 44, 48, 51}
The first 6 squares are blank, and square 7 has piece 2, etc
I'll call another vba program to rearrange the values of the 22 pieces.
Ordering(Layout,22)
{12, 7, 11, 57, 46, 23, 27, 13, 47, 53, 49, 31, 20, 59, 22, 30, 21, 39, 60,
48, 35, 44}
What this means is that piece 1 goes in square 12, piece 2 goes in square 7,
piece 3 goes in square 11, etc.
Most don't like to work with such large numbers in Excel. I always find
this a fun exercise.
We would need more info on what the OP is really trying to do.
--
Dana DeLouis
"Joel" <(E-Mail Removed)> wrote in message
news:0177BCD1-FE04-4A89-BED2-(E-Mail Removed)...
> The best solution even with the reduction is to use the recursive method.
> the 1st piece only need to be placed in 36 squares instead of the full 64
> squares which is a significant reduction (36/64) results.
>
> To get the 36 squares you draw the 2 diagnols across the board. The first
> piece only has to be placed in one triagle orf the 4 triangles created.
> This
> is 11 in first row + 9 in 2nd row + 7 in 3rd row + 5 in 4th row + 3 in 5th
> row + 1 in 6th row.
>
> The second pieces symetry only occurs when this piece is placed iin the
> same
> 36 cells as the first piece. This gives a reduction of 35/36 (only 35
> becuase the 1st piece already occupies one of these spaces).
>
> A full solution would be
> 64 x 63 x 62 x ... x 44 x 43 (22 pieces)
> The reduced solution would be
>
> 36 x (64 - 36 + 1) x (63 - 36 + 1) x ... x (43 - 36 + 1)
>
> 36 x 29 x 28 x ... x 8
>
>
> "SteveM" wrote:
>
>> On Dec 25, 4:16 pm, Joel <J...@discussions.microsoft.com> wrote:
>> > This requires a recursive program. I could write this for you if you
>> > like.
>> >
>> > The first level of recursion would be to take the first piece and place
>> > it
>> > in all 64 locations and make sure no piece is already placed in the
>> > cell.
>> > The piece number 1 to 22 is the same as the level.
>> >
>> > Then call the same function again with the second piece.
>> >
>> > You keep on calling the function over again for 22 times. When you get
>> > to
>> > the 22nd level of recursion you save the results.
>> >
>> > You end up needing a main program which performs initialization and
>> > calls
>> > the recursive routine the for time.
>> >
>> > Here is a start. If basically does everything except saves the results
>> > public Dim MySquare(64)
>> > sub main()
>> >
>> > for SquareNumber = 1 to 64
>> > MySquare(squareNumber) = 0
>> > next SquareNumber
>> > call recursive(1)
>> >
>> > end sub
>> >
>> > sub recursive(piece)
>> >
>> > for SquareNumber = 1 to 64
>> > if MySquare(squareNumber) = 0 then
>> > MySquare(squareNumber) = piece
>> > if piece = 22 then
>> > 'save results
>> > else
>> > call recursive(piece + 1)
>> > end if
>> > 'remove piece by placing 0 in square
>> > MySquare(squareNumber) = 0
>> > end if
>> > next SquareNumber
>> >
>> > "Mac" wrote:
>> > > 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!:-)
>>
>> If this question is for a class and part of your grade is based on how
>> creative and efficient your algorithm is, simple exhaustive
>> enumeration may be too trivial from your prof's point of voice. (The
>> "C" solution." you may want consider symmetries that are are part of
>> the layout. (The "A" solution?) For example, all of the placements on
>> one half of the board have a complement on the other half. So rather
>> than exhaustive enumeration, you can solve for one symmetric area and
>> immediately write out the complement of each solution. Black/White,
>> {even/odd), the diagonal halves, etc are other symmetries that you may
>> be able to exploit. Now that I think about it, a one half enumeration
>> of all combinations with complement capture is the probably best way
>> to go. I suppose a math guy who know combinatorics better I than
>> could help you frame out a fewest iterations solution strategy.
>>
>> Good Luck,
>>
>> SteveM
>>
Similar Threads
