Can You Help Me Find an Algorithm to Fill a Grid Without Repeating Places?

[calluscus]

Hi:

I'm looking for an algorithm to fill a grid without repeating places.
I have looking for Pseudorandom number lists (http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators#gsl_rng_minstd) but i do not get it clearly...

Any help ? :)

 

[Sartak]

Hi:

I'm looking for an algorithm to fill a grid without repeating places.
I have looking for Pseudorandom number lists (http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators#gsl_rng_minstd) but i do not get it clearly...

Any help ? :)

Well, what exactly are you trying to accomplish? If the grid is small enough, you could fill in the grid with integers, 1 ... r * c, and then for each cell, swap its value with another, random cell, that is to the right or below the current cell. This is similar to Knuth's shuffling algorithm except in two dimensions. C code follows.

#include <stdlib.h>

#define X (80)
#define Y (24)

int main()
{
  int x, y; /* current grid position */
  int i, j; /* x, y for random grid position with which to swap*/
  int k;    /* auxiliary variable to fill out the initial sorted grid */
  int t;    /* auxiliary variable for swapping */
  int grid[X][Y];

  srand(time(NULL)); /* seed the random number generator */
  k = 0;

  /* fill in the grid with (1, 2, ..., x*y) */
  for (y = 0; y < Y; ++y)
    for (x = 0; x < X; ++x)
      grid[x][y] = ++k;

  for (y = 0; y < Y; ++y)
    for (x = 0; x < X; ++x)
    {
      /* select a random row between this one and the last one */
      j = rand() % (Y - y) + y;

      if (j == y)
      {
        /* if it's on the current row, select a column to our right */
        i = rand() % (X - x) + x;
      }
      else
      {
        /* if it's on a row below, select _any_ column */
        i = rand() % X;
      }

      /* swap */
      t = grid[i][j];
      grid[i][j] = grid[x][y];
      grid[x][y] = t;
    }

  /* do stuff with the grid here */

  return 0;
}

(note: I have not even so much as compiled the above code, but hopefully you can follow what I'm trying to do)

 

[calluscus]

ty very much