423,850 Members | 1,555 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 423,850 IT Pros & Developers. It's quick & easy.

Limiting duplicate entries in a matrix. How to make it look like a sudoku?

P: 2
Hello. I have made a square matrix of order nxn with random values in it. The entries are 1 to n appearing randomly as desired. Now i would like to limit all entries to appear strictly n times. for e.g. in the code below the output is a 9x9 matrix with entries 1 to 9. I want every number to appear only 9 times in the matrix to make it look like a sudoku. So how to do that?

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4.  
  5. using namespace std;
  6.  
  7. const int ROWS = 9; const int COLS = 9;   //no more magic numbers. Named type now
  8. typedef int Matrix[ROWS][COLS];
  9.  
  10. int getrandomval();
  11.  
  12. void fillrandom(Matrix mat)
  13. {
  14.  
  15.     for (int row = 0; row < ROWS; row++)
  16.     {
  17.         for (int col = 0; col < COLS; col++)
  18.         {
  19.             mat[row][col] = getrandomval();
  20.         }
  21.     }
  22. }
  23.  
  24. int getrandomval()
  25. {
  26.     int x = 0;
  27.     x = rand() % 9 + 1;
  28.     return x;
  29. }
  30.  
  31. void show(Matrix m)
  32. {
  33.     for (int row = 0; row < ROWS; row++)
  34.     {
  35.         for (int col = 0; col < COLS; col++)
  36.         {
  37.             cout << " " << m[row][col] << " ";
  38.         }
  39.         cout << endl;
  40.     }
  41.     cout << endl;
  42. }
  43.  
  44. int main()
  45. {
  46.     srand(time(0));
  47.  
  48.     //using our constant
  49.     cout << "\nGenerating the random number matrix of order" << ROWS << " x " << COLS << "...\n\n\n";
  50.  
  51.     Matrix mat; //declaring the variable
  52.     getrandomval();
  53.     fillrandom(mat); //filling our variable
  54.     show(mat); //showing whats in the matrix
  55.     return 0;
  56. }
  57.  
Oct 3 '16 #1

✓ answered by Oralloy

NewCplusplus,

Here is a potential algorithm for selecting random numbers to meet your criteria:
1) create an array of all the possible numbers (digits).
1.1) call this array "numberCount"
1.2) numberCount.length = 10 for numbers zero through 9.
2) zero all entries in "numberCount".
3) decide how many of each number will be placed into the
matrix
3.1) assign "numberCount[number]" to the "how many" count.
4) compute totalCount as the sum of all numberCount entries.
4.1) totalCount = numberCount[0]+numberCount[1]+...
5) pick a number from zero to (totalCount-1)
5.1) valueCount
6) span the "numberCount" array until the running total of values exceeds valueCount
6.1) keep the index of interest.
6.2) decrement the "numberCount" element that was selected.
7) return index of interest.

In C++, this is my first cut at the algorithm.
Please note that you are responsible for populating the numberCount array before using this method.
Expand|Select|Wrap|Line Numbers
  1. //--histogram of remaining numbers to place
  2. //--this is the initial state, user must populate
  3. int numberCount[10] = {0,0,0,0,0,0,0,0,0,0};
  4.  
  5. // fetch a remaining numbers
  6. // updates numberCount[].
  7. int getRandomValue()
  8. {
  9.   //--remaining number of numbers to place
  10.   int totalCount = 0;
  11.   for (auto count : numberCount)
  12.     totalCount += count;
  13.  
  14.   //--which number do we pick
  15.   int valueCount = rand() % totalCount
  16.  
  17.   //--which number was selected?
  18.   //--march across array from zero to nine.
  19.   int value;
  20.   int incrementCount = 0;
  21.   bool spin = true;
  22.   for (int index; (spin  and  (10 > index)); index++)
  23.   {
  24.     incrementCount += numberCount[index];
  25.     if (incrementCount > valueCount)
  26.     { // found!
  27.       value= index;
  28.       numberCount[index]--;
  29.       spin = false;
  30.     }
  31.   }
  32.  
  33.   //--done
  34.   return value;
  35. }
Good luck; I do hope that you create a new, fun game for us!
Oralloy

Share this Question
Share on Google+
3 Replies


weaknessforcats
Expert Mod 5K+
P: 9,196
Can you not put digits 1-9 in each 9 digit row of the matrix?

After 9 rows each number will appear 9 times.
Oct 3 '16 #2

P: 2
That way in case of a larger size matrix (say 100) i will have to keep on punching in values and the coding would be lengthy and repetitive. This way i can substitute any value for rows and cols and get my matrix already filled with random entries. Now i just have to limit the appearance of the entries according to the order of the matrix. Once i have the matrix as desired then i can start using mathematical operations in them. Just an idea for a fun game, although i am a beginner in programming but i kept on trying and got this far.
Oct 3 '16 #3

Oralloy
Expert 100+
P: 983
NewCplusplus,

Here is a potential algorithm for selecting random numbers to meet your criteria:
1) create an array of all the possible numbers (digits).
1.1) call this array "numberCount"
1.2) numberCount.length = 10 for numbers zero through 9.
2) zero all entries in "numberCount".
3) decide how many of each number will be placed into the
matrix
3.1) assign "numberCount[number]" to the "how many" count.
4) compute totalCount as the sum of all numberCount entries.
4.1) totalCount = numberCount[0]+numberCount[1]+...
5) pick a number from zero to (totalCount-1)
5.1) valueCount
6) span the "numberCount" array until the running total of values exceeds valueCount
6.1) keep the index of interest.
6.2) decrement the "numberCount" element that was selected.
7) return index of interest.

In C++, this is my first cut at the algorithm.
Please note that you are responsible for populating the numberCount array before using this method.
Expand|Select|Wrap|Line Numbers
  1. //--histogram of remaining numbers to place
  2. //--this is the initial state, user must populate
  3. int numberCount[10] = {0,0,0,0,0,0,0,0,0,0};
  4.  
  5. // fetch a remaining numbers
  6. // updates numberCount[].
  7. int getRandomValue()
  8. {
  9.   //--remaining number of numbers to place
  10.   int totalCount = 0;
  11.   for (auto count : numberCount)
  12.     totalCount += count;
  13.  
  14.   //--which number do we pick
  15.   int valueCount = rand() % totalCount
  16.  
  17.   //--which number was selected?
  18.   //--march across array from zero to nine.
  19.   int value;
  20.   int incrementCount = 0;
  21.   bool spin = true;
  22.   for (int index; (spin  and  (10 > index)); index++)
  23.   {
  24.     incrementCount += numberCount[index];
  25.     if (incrementCount > valueCount)
  26.     { // found!
  27.       value= index;
  28.       numberCount[index]--;
  29.       spin = false;
  30.     }
  31.   }
  32.  
  33.   //--done
  34.   return value;
  35. }
Good luck; I do hope that you create a new, fun game for us!
Oralloy
Oct 3 '16 #4

Post your reply

Sign in to post your reply or Sign up for a free account.