place 20 chess pieces on a checkerboard, in random places

Question

An idea I had to solve this, is to make up an buffer of size 8x8, fill it up with pointers to my checkers (all 20 of them), and the rest leave 0 (null), then run a shuffling algorithm on the buffer, and thats it (just read it as a 8x8 array)

1. I was wondering if there's a better way to do this.
2. I need to write it in C#, and my proposal wouldn't work in the way I described it

anyone ?

Answer 1

An 8x8 matrix which contains either pointers (c++) to piece objects or references (c#/java) seems like a very reasonable design.

You could use an 1D array that is 64 elements big (you can easily map 2D indexes to a 1D array) and use something like this:

using System;
using System.Linq;

Piece[] board = whatever();

// New random number generator.
Random random = new Random();

// LINQ query orders each element by the next random number.
Piece[] randomBoard = (from piece in board
    orderby random.Next()
    select piece).ToArray();

NOTE: I'm not a c# programmer, but this seems reasonable.

To convert an x,y pair to an array index, you use this algorithm:

int index = (y * 8) + x;

NOTE2: I don't know if you have to follow placement rules of checkers or not, if you do, you need to do something more clever. You could maybe have an array 32 elements big (representing all black squares). Shuffle around in that, then assign each element in the 32 big array to each "black" square of the real 64 element array.

Answer 2

If you have to follow placement rules, given your 8x8 matrix example, I would also consider it a 1d array as Evan pointed out -- (see his math for determining x & y) --

Black and white squares are the odd and even index values; But, hey, you never said you needed placement rules -- I also presume you aren't looking for c# code but more "logic" level ideas...

If you are trying for a Linq-Challenged solution, consider the following;

1. Construct the "board" array, all empty; (64 elements)
2. Construct the "game piece" array consisting of your pieces
3. Create a loop from 1 to # of pieces
4. Generate a random number between 1 and # of board spaces (64)
5. If board space pointed to by #4 is !0, redo step 4 (or you can "while" !0)
6. Place the piece (# from loop in step 3) into square X from step 4

Just ONE idea of which are sure to be many --

Hope it helps ...

Answer 3

To piggyback on Borzio's idea, as you approach the twentieth piece, there is a 1 in 3 chance that you will have to re-generate the random number and try again. With 20 pieces, you're probably still safe, but were you to have, say, 40 pieces, there would be better than a 1 in 2 chance and you might be stuck waiting a while.

1. Construct the board array, all empty.
2. Copy a reference to each board square to a list (emptySquareList).
3. Loop for each piece you want to add:
   1. Generate a random number between 0 and emptySquareList.Length-1.
   2. Put the piece in that square
   3. Remove the square from the emptySquareList.

This way, you're always maintaining a list of empty squares, and choosing from them. Note that an array of indexes into your board array works just as well and might be faster (Enumerable.Range(0,64)).

I encourage you to experiment with the random-and-check algorithm, as well as this one; see which one's more efficient.

Answer 4

To answer the question that has been posed:

1. Place the first chess piece in a random spot that isn't already occupied
2. Repeat for the other 19 pieces

Seriously, you haven't given us enough information to go on to answer this question at all. Here's some questions:

• Which chess pieces?
• Which colors (there's 16 of each), and does color matter? Will whites have to avoid being captured by blacks, and vice versa?

Assuming there's no rules to follow, except that you need to place all 20 on the board, ie. no collisions, this will do what you want:

Piece[] pieces = ... your 20 pieces here
Piece[] board = new Piece[8 * 8];
Random r = new Random();
foreach (Piece piece in pieces)
{
    while (true)
    {
        Int32 location = r.Next(board.Length);
        if (board[location] == null)
        {
            board[location] = piece;
            break;
        }
    }
}

A simpler solution, provided you already have helper-routines somewhere, would be to just place them at the start of the 64-element array, then shuffle the entire array. This would shuffle those 20 pieces and the 44 empty squares around, and would effectively place them in random spots.