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!:-)

A "chessboard" problem
 

On Dec 25, 4:16 pm, Joel 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

A "chessboard" problem
 

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

A "chessboard" problem
 

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 =
"6815050701299347364385964726987227011845628294694 0829277556802127127796280441531804255520"

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" wrote in message
...
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 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

A "chessboard" problem
 

Please disregard that idea! My mistake.
Numbers above 22 all have the "same value", which are blank.
So when we swap two blank locations, they are different, but give the same
general layout.
Therefore the size is too large for the number of possible layouts.
It's more like =PERMUT(64,22) = 9.03E+37
This requies different code. Sorry.
--
Dana DeLouis

<snip