filling unique random nos in an array

[ronnieaka]

i've sudoku to make and for that, i need to generate it too. so for the generation, i've decided out that filling each successive column is a task of filling each column cell in the same row with a random no but seeing that it isn't already there in that row before.

i've seen topics on random function but they are hardly the thing i want.
suppose already the numbers 3,4,7 are entered, then i want to enter a random number from the rest of the numbers left from 1-9 except the 3,4,7. so how do i do that? is there a particular function for that? generating a random no but with excluding a particular set of numbers?

to do that in the most basic and primitive way as possible i deviced a method in which i will do a linear search on the previous elements and see if the currently generated random # is there or not, if not then obviously put it in the array. otherwise generate another random no until i get something unique.
but its so time consuming and inefficient...would hog up system time i guess.
so please help me with this.
i can't go further in my generate function of sudoku without having this figured out

[daviddoria]

What you have described is called "rejection sampling". That sounds like a reasonable way to go about this to me. If you use std::vector to to store the elements you can then use find() from the stl to do the search. It shouldn't be that bad for something as small as a sudoku game.

Dave

[gusano79]

What you have described is called "rejection sampling". That sounds like a reasonable way to go about this to me. If you use std::vector to to store the elements you can then use find() from the stl to do the search. It shouldn't be that bad for something as small as a sudoku game.

I'd use rejection sampling if the sample space were much larger than the number of samples I needed, but for this, it seems like overkill.

So far we've been approaching this as a "generate some random numbers" problem, when it really isn't. You already know which numbers you want, i.e., 1-9 inclusive. What you want to be random is the order of these numbers; you're looking for a random permutation.

One way to do this is to start with a list of the numbers, and then walk through the list, exchanging each element with a random other element, which mixes them up nicely. This is called the Fisher-Yates shuffle.

Also, remember that the diagonals and each of the 3x3 square regions can't have the same number twice. Simply generating random permutations for each row doesn't guarantee these constraints will be met.

[daviddoria]

Good idea gusano79, but I was thinking that he had to check many conditions (rows, columns, and boxes), so generating a permutation of a whole row at a time and then checking all 9 elements for those conditions may be just as slow as doing it one number at a time. If you do want to use a permutation of the numbers 0-9, it is very easy with the STL:

#include <iostream>
#include <algorithm>
#include <vector>

int main(int argc, char* argv[])
{
  std::vector<int> v;
  
  //add 10 integers (0 to 9)
  for(int i = 0; i < 10; i++)
  {
    v.push_back(i);
  }
  
  std::cout << "Ordered" << std::endl;
  for(int i = 0; i < 10; i++)
  {
    std::cout << v[i] << " ";
  }
  
  std::random_shuffle(v.begin(), v.end());
  
  std::cout << std::endl << "Shuffled" << std::endl;
  for(int i = 0; i < 10; i++)
  {
    std::cout << v[i] << " ";
  }
	
  return 0;
}

[gusano79]

Good idea gusano79, but I was thinking that he had to check many conditions (rows, columns, and boxes), so generating a permutation of a whole row at a time and then checking all 9 elements for those conditions may be just as slow as doing it one number at a time.

If you mean using rejection sampling with respect to the entire 9x9 grid, absolutely! I was just addressing the permutation issue.

An alternative would be as you generate the rows, modify each one if it doesn't fit the constraints. For example, if randomly-permuted row 2 has a number that doesn't fit, swap it with the next one after it in the row that does match all constraints. By the time you finish with the last row, you'll have a working Sudoku grid.