Sudoku game output problem

[ponki d monkey]

Hi! I'm having problems creating a sudoku puzzle. I'm using functions srand(); and rand(); to generate numbers from 1 to 9. I also constructed a whole lot of conditions to check if there are repeating numbers in every row and column. The main problem is sometimes it displays the output, sometimes it does not. I'm thinking that the seed (I used srand(time(NULL));) can't keep pace with the conditions and loops that I created that's why it's having problems assigning values to the 2x2 array that should display the completed puzzle. Anyway, I know it's a bit confusing. I'm a bit confused too. Please check out my code:

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void main(void)
   {
   int sudoku[9][9],gen=0,check,a,b,c;
   bool marker[9]={0,0,0,0,0,0,0,0,0};
   clrscr();

   srand(time(NULL)*10000000);//trying to convert to milliseconds.

   for(a=0;a<=2;a++)//first 3x3 block
      {
      for(b=0;b<=2;b++)
         {
         do{
            gen=rand()%9+1;
            sudoku[a][b]=gen;
         }while(marker[gen-1]==1);
         marker[gen-1]=1;//'marker' checks if the number has already been generated for this block
         }
      }

   for(a=0;a<=2;a++)//second 3x3 block
      {
      for(b=3;b<=5;b++)
      	{
        do{
           do{
              check=0;
              gen=rand()%9+1;
              sudoku[a][b]=gen;
              for(c=0;c<=2;c++)
                 {
                 if(sudoku[a][c]==sudoku[a][b])
                    {
                    ++check;//'check' checks if there's an equivalent value on the other block.
                    }
                 }
           }while(check>0);
        }while(marker[gen-1]==0);
        marker[gen-1]=0;
        }
      }

   for(a=0;a<=2;a++)//and so on...
      {
      for(b=6;b<=8;b++)
         {
         do{
            do{
               check=0;
               gen=rand()%9+1;
               sudoku[a][b]=gen;
               for(c=0;c<=5;c++)
                  {
                  if(sudoku[a][c]==sudoku[a][b])
                     {
                     ++check;
                     }
               	  }
            }while(check>0);
         }while(marker[gen-1]==1);
         marker[gen-1]=1;
         }
      }

   for(a=3;a<=5;a++)
      {
      for(b=0;b<=2;b++)
         {
         do{
            do{
               check=0;
               gen=rand()%9+1;
               sudoku[a][b]=gen;
               for(c=0;c<=2;c++)
                  {
                  if(sudoku[c][b]==sudoku[a][b])
               	     {
                     ++check;
                     }
               	   }
            }while(check>0);
         }while(marker[gen-1]==0);
         marker[gen-1]=0;
         }
      }

   for(a=3;a<=5;a++)
      {
      for(b=3;b<=5;b++)
         {
         do{
            do{
               check=0;
               gen=rand()%9+1;
               sudoku[a][b]=gen;
               for(c=0;c<=2;c++)
                  {
                  if(sudoku[a][c]==sudoku[a][b])
                     {
                     ++check;
                     }
                  }
               for(c=0;c<=2;c++)
                  {
                  if(sudoku[c][b]==sudoku[a][b])
                     {
                     ++check;
                     }
                  }
            }while(check>0);
         }while(marker[gen-1]==1);
         marker[gen-1]=1;
         }
      }

   for(a=3;a<=5;a++)
      {
      for(b=6;b<=8;b++)
         {
         do{
            do{
               check=0;
               gen=rand()%9+1;
               sudoku[a][b]=gen;
               for(c=0;c<=5;c++)
                  {
                  if(sudoku[a][c]==sudoku[a][b])
                     {
                     ++check;
                     }
                  }
               for(c=0;c<=2;c++)
                  {
                  if(sudoku[c][b]==sudoku[a][b])
                     {
                     ++check;
                     }
               	  }
            }while(check>0);
         }while(marker[gen-1]==0);
         marker[gen-1]=0;
         }
      }

   for(a=0;a<=5;a++)//this loop should display the generated numbers...
      {
      for(b=0;b<=8;b++)
         {
         cout<<sudoku[a][b]<<"  ";
         }
      cout<<endl<<endl;
      }
   getch();
   }

Lastly, can anyone tell me if I can convert time(NULL); to milliseconds or is there a way that I can set the seed to milliseconds? Thanks!

*Note: This is not yet a completed puzzle. I encountered a problem so I'm not sure if should continue doing this method or not...

[jsmith]

Couple things:

1) time() returns seconds. 1000 milliseconds = 1 second. So
srand(time(NULL)*10000000); is totally wrong.

2) This is probably the hardest way to do what you are trying to do.

[ponki d monkey]

I see. If I multiply it by 1000, will it convert it to milliseconds? I'm just really not sure. I'm just trying to do all the things that I can think of right now.

Second, when you say 'the hardest way'...are you referring to the method of how I'm creating the Sudoku puzzle? Because if you are, then maybe it's safe to say that there's probably no point of continuing this?

Anyway, is there any other method that you can think of on how to create a Sudoku puzzle? If so, can you share it?

[jpeg]

1. Yes, multiplying by 1000 will get you milliseconds.

2. I can't read jsmith's mind so I'll let him explain it his way.

[ponki d monkey]

Thanks jpeg. Anyway, I already tried multiplying it by 1000 and I'm still encountering the same problem. Maybe I'll just figure out some other way to create a Sudoku Puzzle...

[jsmith]

So basically as I understand your program, it is essentially brute force with no backtracking. That is, it is possible for your program to get into a state in which there is no possible solution, but it will keep trying forever.

This is the first problem you need to fix. Secondly, making a 2D array, although making sense given the 2D nature of sudoku puzzles, actually makes the program harder to write. I personally would use a one dimensional array of 81 elements, and then write functions that convert (row,col) pairs to the linear index and vice versa.

Since this problem seemed a bit challenging, I'm writing my own version. Although it doesn't quite work yet, all of the functionality is there in only 57 lines of code. My solution uses recursion (it will recurse no more than 82 function calls deep) and works by storing in each cell the possible valid values it can hold. As I randomly choose one of the valid values for the current cell, I go through all the other cells in that row, column, and block and remove that value as a valid value. At any point if any cell has no possible valid values, I must backtrack (by returning from the inner-most function call and trying a different value).

And speaking of which, I just realized my bug...

[jsmith]

I have the program working. It is 57 lines of code (excluding blanks and lines that have only braces on them) and it runs virtually instantaneously. It uses the algorithm I described in my last post.

[ponki d monkey]

Hmm...I think using a one-dimensional array would fix it. My friend did the same problem in Java using 2D arrays and it worked fine at first that's why I thought the problem is with using srand(time(NULL));. I believe in Java you don't need to use a function like srand(); to initialize the seed which is one of the difference between Java and C++. After a few more tries, my friend already encountered the same problem that I encountered.

Anyway, thanks a lot for your ideas jsmith! I really appreciate it. I've been doing this problem for a week now. It's already giving me headaches.

[ponki d monkey]

jsmith, I already improved my code, but I still can't get it to produce an output. I already tried using a 1-dimensional array and I'm still encountering the same problem. Here's my new code:

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

struct cells_t {
   int values[9];
};

int randomGenerator(int a,cells_t cellvalcheck[])
   {
   int random;
   random=rand()%9+1;
   if(cellvalcheck[a].values[random-1]==0)
      {
      while(cellvalcheck[a].values[random-1]==0)
         {
         random=rand()%9+1;
         }
      }
   return(random);
   }

int coordinateXMaker(int index)
   {
   for(int coorx=0;coorx<=72;coorx=(coorx+9))
      {
      if(index>=coorx && index<=(coorx+8))
         {return(coorx);}
      }
   }

int coordinateYMaker(int index)
   {
   for(int coory=0;coory<=8;coory++)
   	{
   	if((index%9)==coory)
   		{return(coory);}
       }
   }             

//To remove generated random value within the row...
void markValuePerRow(int a,int b,int randnum,cells_t cellperrow[])
   {
   int end;
   end=coordinateXMaker(a)+8;
   if(b<=end)
      {
      if(a!=b)
         {
         cellperrow[b].values[randnum-1]=0;
         }
      markValuePerRow(a,b+1,randnum,cellperrow);
      }
   }

//To remove generated random value within the column...
void markValuePerCol(int a,int b,int randnum,cells_t cellpercol[])
   {
   int end;
   end=coordinateYMaker(a)+72;
   if(b<=end)
      {
      if(a!=b)
      	{
         cellpercol[b].values[randnum-1]=0;
         }
      markValuePerCol(a,b+9,randnum,cellpercol);
      }
   }

/*void markValuePerBlo(int a,int b,cells_t cellperblo[])
	{

	}           */

void main(void)
   {
   cells_t cell[81];
   int rvi,startx,starty,i,j; //rvi =random value index; random value assigned to its corresponding index.
   clrscr();

   for(i=0;i<81;i++)
   	{
      for(j=0;j<9;j++)
      	{
         cell[i].values[j]=j+1;
         }
      }

   srand(time(NULL));

   for(i=0;i<81;i++)
      {
      rvi=randomGenerator(i,cell);
      startx=coordinateXMaker(i);
      starty=coordinateYMaker(i);
      markValuePerRow(i,startx,rvi,cell);
      markValuePerCol(i,starty,rvi,cell);
//      markValuePerBlo(i,rvi,cell);
      }

	for(i=0;i<81;i++)
   	{
      if(i%9==0)
      	{
         cout<<endl<<endl;
         }
      for(j=0;j<9;j++)
      	{
         if(cell[i].values[j]>0)
         	{
      		cout<<cell[i].values[j]<<"  ";
            }
         }
      }
	getch();
   }

I thought I already understood your algorithm, but to be honest, I'm still confused. How did you use recursion for this type of problem? I can't understand how you were able to use only 57 lines for this problem. I'm using Borland 5.02 as my compiler. Could it be a problem with the compiler? I just really want to solve this...

[jsmith]

Your solution is pretty close to mine. If I understand your design (tell me if I'm wrong), your array is laid out such that indices {0..8} are the first horizontal row, {9..17} the second, and so forth.

It looks like your markValuePerRow uses recursion to remove the chosen random value from each cell within the row except the cell you are working on. This sounds right, though I'd just make it a for() loop instead of using recursion.

It looks like your markValuePerCol works in the same way as markValuePerRow.

You'll need a markValuePerBlock yet, which you already know.

So generally speaking our respective programs do the same things. In fact, we have many of the same functions:

Your function My function
markValuePerCol clear_bit_in_column
markValuePerRow clear_bit_in_row
coordinateXMaker optimized out, as it is a one-liner for me
coordinateYMaker optimized out, as it is a one-liner for me
randomGenerator this is part of my solve() function
main solve
main
get_nth_set_bit

I think that the problem with your program is that you need to backtrack. It is possible for
your program to get into a state where it cannot solve the puzzle. When that happens,
your randomGenerator function will never return causing an infinite loop. This is where
my recursive algorithm solves the problem.

That is, after I've assigned values to the first, say, 50 elements in the grid, if I find that
there is no possible value to put into the 51st element, my algorithm back tracks -- it
goes back to the 50th element and tries a different value instead of the first one it picked.
If again it finds that there is no possible value to put into the 51st element, it tries a
different value for the 50th element. If it runs out of values to try for the 50th element,
it goes back to the 49th element and tries a different value there. And the algorithm
continues.

This is where my recursion comes in. So my algorithm goes something like this:

bool solve( puzzle, element ) {
1. figure_out_possible_values_for_cell( puzzle, element );
2. randomly choose one value
3. put value in cell and mark rows, columns, and blocks
4. call solve( puzzle, element + 1 );
5. if it returned false, then remove from the possible values the value we picked
and go back to step 2. If there are no more possible values, then return
false.
}

Now I've left out a detail or two, and certainly this isn't the only way to solve the
problem. (And note, I do not use gotos).

I think the main reason why your code is twice as long as mine is that whereas
you use arrays I use STL containers. The containers are flexible and powerful
enough that I can often do in 1 line of code what takes you a couple to implement
a for loop.

For example, your code uses 3 lines of code to implement a nested for() loop to
initialize your data structure whereas I was able to initialize mine in 1 line of
code.

In fact, here is my main:

int main() {
    srand( time( 0 ) );
    solve( PuzzleBoard( 81, bitset<9>( string( 9, '1' ) ) ), 0 );
}

For me, PuzzleBoard is a vector< bitset<9> >. My vector is equivalent
to your cell[81], and bitset<9> is your values array inside cells_t.
Your code sets value[N] = N + 1 to indicate that N + 1 is a possible
value. My code sets bit N to indicate that N + 1 is a possible value.
So to understand my line of code:

string( 9, '1' ) creates a string of 9 '1's.
bitset<9>( string( 9, '1' ) ) creates the 9-bit value 1 1111 1111
which indicates all 9 values are possible.
vector( 81, bitset<9>( string( 9, '1' ) ) ) creates an array of 81
such 9-bit values to indicate that all 9 values are possible in all 81 cells.

[jsmith]

As an example, I just ran your program and this is how far it got:

5 1 4 2 7 9 3 8 6
4 7 8 5 9 3 2 1

As you can see, the only value left in row 2 is 6, but it can't be put in the last
column because of the 6 above it. In this case, your program has to backtrack -
it has to reconsider its decision to put a 1 in the 8th column. If it puts a 6 there
instead, then a 1 can go in the last column.

[ponki d monkey]

You are a master jsmith! I really appreciate it! I totally understand it now. Thank you so much! This is the best programming day of my life! 'Til next time...

[ponki d monkey]

Yes, that is correct my array is laid out such that indices 0 to8 are the first horizontal row, 9 to 17 the second, and so forth. Again, thank you so much. You took away my sleepless nights...

[jsmith]

Fantastic! Once you have yours working, I will post my solution if you want me to.

[ponki d monkey]

Sure! That would be great. That way, I can also explore how vectors work. I'll just post my solution once I'm done with it.

[jsmith]

Ok this is as short as I'm going to get it without starting to use questionable coding techniques / coding style.

I modified the program to work with blocks of arbitrary size; you just need to change the
BLOCK_WIDTH variable. BLOCK_WIDTH = 3 means that it will generate a 3x3 grid of
3x3 blocks. Setting it to 4 will generate a 4x4 grid of 4x4 blocks, and so forth.

Setting it to 5 took a few minutes to generate a valid grid :)

#include <bitset>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

static const size_t BLOCK_WIDTH = 3;
static const size_t BLOCK_SIZE  = BLOCK_WIDTH * BLOCK_WIDTH;
static const size_t GRID_SIZE   = BLOCK_SIZE * BLOCK_SIZE;

typedef bitset<BLOCK_SIZE> Cell;
typedef vector< Cell >     PuzzleBoard;


void clear_bit_in_row( PuzzleBoard& board, size_t bit, size_t row ) {
    for( size_t pos = row * BLOCK_SIZE; pos < ( row + 1 ) * BLOCK_SIZE; ++pos )
        board[ pos ].reset( bit );
}


void clear_bit_in_column( PuzzleBoard& board, size_t bit, size_t column ) {
    for( size_t pos = column; pos < board.size(); pos += BLOCK_SIZE )
        board[ pos ].reset( bit );
}


void clear_bit_in_block( PuzzleBoard& board, size_t bit, size_t pos ) {
    size_t first_column = BLOCK_WIDTH * ( ( pos % BLOCK_SIZE ) / BLOCK_WIDTH );
    size_t first_row    = BLOCK_WIDTH * ( ( pos / BLOCK_SIZE ) / BLOCK_WIDTH );
    size_t first_pos    = BLOCK_SIZE * first_row + first_column;

    for( size_t ct = 0; ct < BLOCK_WIDTH; ++ct, first_pos += BLOCK_SIZE )
        for( size_t col = 0; col < BLOCK_WIDTH; ++col )
            board[ first_pos + col ].reset( bit );
}


size_t get_nth_set_bit( Cell bits, size_t which ) {
    for( size_t i = 0; i <= BLOCK_SIZE && which; ++i )
        if( bits.test( i ) && !--which )
            return i;
    // should never get here
    return 0;
}


bool solve( PuzzleBoard board, size_t pos ) {
    if( pos >= board.size() ) {
        for( size_t p = 0; p < board.size(); ++p )
            cout << ( get_nth_set_bit( board[ p ], 1 ) + 1 )
                 << ( ( p + 1 ) % BLOCK_SIZE == 0 ? '\n' : ' ' );
        exit( 0 );
    }

    Cell        cell_values( board[ pos ] );
    PuzzleBoard tmp_board( board );

    while( cell_values.count() ) {
        size_t which_one = rand() % cell_values.count() + 1;
        size_t guess = get_nth_set_bit( cell_values, which_one );

        clear_bit_in_row( tmp_board, guess, pos / BLOCK_SIZE );
        clear_bit_in_column( tmp_board, guess, pos % BLOCK_SIZE );
        clear_bit_in_block( tmp_board, guess, pos );
        tmp_board[ pos ].reset();
        tmp_board[ pos ].set( guess );

        bool is_still_valid = true;
        for( size_t i = 0; i < board.size() && is_still_valid; ++i )
            if( tmp_board[ i ].none() )
                is_still_valid = false;

        if( !is_still_valid || !solve( tmp_board, pos + 1 ) )
            cell_values.reset( guess );

        tmp_board = board;
    }

    return false;
}

int main() {
    srand( time( 0 ) );
    solve( PuzzleBoard( GRID_SIZE, Cell( string( BLOCK_SIZE, '1' ) ) ), 0 );
}

[ponki d monkey]

Oh wow! Thanks a lot for the code jsmith. Don't worry, I'm not doing this as an assignment. I'm just practicing my programming skills. Anyway, it would probably take me days before I decipher your code. I'll just use it to get better ideas so I can finish this problem and proceed to my next experiment. Thanks for all your replies. You really are the best!