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

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.

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.

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.

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

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

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