What is the best way to put 20 pieces on a chessboard in random places?

An idea I had to solve this, is to make up an buffer of size 8×8, 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 8×8 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 ?

11 thoughts on “What is the best way to put 20 pieces on a chessboard in random places?

  1. user

    "proposal wouldn't work in the way I described it" Which means what? Do you have a specific question? A code snippet that doesn't work? Do you have an example of what wouldn't work the way you described it?

    Reply
  2. user

    Also, you imply both checkers and chess piece for use (title says chess, content says checkers). Which is is, I assumed checkers.

    Reply
  3. user

    S.Lott: what I wrote works, but I thought there's a smarter way. mitch: no rules, as I said, just fill them in random places, but all 20 of them.

    Reply
  4. user

    @Ido: just to be clear, are you talking about checkers or chess pieces? Cause in chess, there are initially 32 pieces on the board and in checkers there are initially 24 pieces on the board. Where did 20 come from?

    Reply
  5. user

    An 8×8 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.

    Reply
  6. user

    If you have to follow placement rules, given your 8×8 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 …

    Reply
  7. user

    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.

    Reply
  8. user

    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.

    Reply

Leave a Reply

Your email address will not be published.