Thread: Sudoku solution generator algorithm

I get 0.003s if I have the whole board filled out in input file... so most of the time is spent in IO. I get the time using the "time" command in my shell (Linux machine).

But then I used -O3...

Ah oh well, I don't think it's meaningful comparing times at this magnitude I get significantly different times between different but identical runs, too.

I think the influences thing, the bitset stuff, and incrementally updating everything are just "linear optimizations" and don't change the complexity.

I'm trying to make a sudoku generator, its for a game. This is my solution code so far, although it doesn't work how it should.

Code:

/* solution.cpp */

#include "solution.h"

void GAME_SOLUTION::GenerateSolution()
{
     /* This method generates a solution which the user must then try and get.
        The way this method will work, is by going through the grid, 1 square at
        a time, and randomly selecting a number. It will then check in turn if
        there is another number either in the smaller 3x3 grid, the same row or
        the same column, if there is, then another number is selected until 1
        fits.
     */
     
     int idx1,idx2,ret=0;
     int num1;
     
     for(idx1=0; idx1<BUTTON_NUM; idx1++)
     {
                 for(idx2=0; idx2<BUTTON_NUM; idx2++)
                 {
                             do
                             {
                                                ret = 0;
                                                num1 = (rand()%BUTTON_NUM) + 1;
                                                
                                                /* Do the tests */
                                                ret += this->TestRow(num1, idx1);
                                                ret += this->TestColumn(num1, idx2);
                                                ret += this->TestSmallGrid(num1, (int)(idx1/3), (int)(idx2/3));
                                                
                                                /* Correct any potential errors */
                                                ret = this->CorrectError(num1, idx2, idx1, ret);
                             } while(ret != 0);
                             
                             this->SetSolution(num1, idx2, idx1);
                 }
     }
     
     return;
}

bool GAME_SOLUTION::CorrectError(int num, int idx_x, int idx_y, int ret)
{
     /* This tests to see if another number which has already been placed can be
        replaced by the one listed to be put down.
     */
     int idx0,idx1;
     int ret2=0,val=0;
     
     if(ret != 0)
     {
            for(idx0=0; idx0<=idx_y; idx0++)
            {
                        if(idx0 == idx_y)
                        {
                                for(idx1=0; idx1<idx_x; idx1++)
                                {
                                            /* Check if the number fits */
                                            ret2 = 0;
                                            
                                            val = this->GetSolution(idx1, idx0);
                                            
                                            ret2 += this->TestRow(val, idx_y);
                                            ret2 += this->TestColumn(val, idx_x);
                                            ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3));
                                            
                                            ret2 += this->TestRow(num, idx0);
                                            ret2 += this->TestColumn(num, idx1);
                                            ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3));
                                            
                                            if(ret2 == 0)
                                            {
                                                   this->SetSolution(num, idx1, idx0);
                                                   this->SetSolution(val, idx_x, idx_y);
                                                   return false;
                                            }
                                }
                        }
                        else
                        {
                            for(idx1=0; idx1<BUTTON_NUM; idx1++)
                            {
                                        /* Check if the number fits */
                                            ret2 = 0;
                                            
                                            val = this->GetSolution(idx1, idx0);
                                            
                                            ret2 += this->TestRow(val, idx_y);
                                            ret2 += this->TestColumn(val, idx_x);
                                            ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3));
                                            
                                            ret2 += this->TestRow(num, idx0);
                                            ret2 += this->TestColumn(num, idx1);
                                            ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3));
                                            
                                            if(ret2 == 0)
                                            {
                                                   this->SetSolution(num, idx1, idx0);
                                                   this->SetSolution(val, idx_x, idx_y);
                                                   return false;
                                            }
                            }
                        }
            }
     }
                
     return false;
}

bool GAME_SOLUTION::TestRow(int num, int idx_y)
{
     /* This method tests if there are two identical values in the same row */
     int idx=0;
     
     for(idx=0; idx<BUTTON_NUM; idx++)
     {
                if(num == this->solution[idx][idx_y])
                {
                                              return true;
                }
     }
     
     return false;
}

bool GAME_SOLUTION::TestColumn(int num, int idx_x)
{
     /* This method tests if there are two identical values in the same column */
     int idx=0;
     
     for(idx=0; idx<BUTTON_NUM; idx++)
     {
                if(this->solution[idx_x][idx] == num)
                {
                                              return true;
                }
     }
     
     return false;
}

bool GAME_SOLUTION::TestSmallGrid(int num, int idx1, int idx2)
{
     int idx,idx0;
     
     for(idx=0; idx<(BUTTON_NUM/3); idx++)
     {
                for(idx0=0; idx0<(BUTTON_NUM/3); idx0++)
                {
                            if(this->solution[(3*idx1) + idx0][(3*idx2) + idx] == num)
                            {
                                                       return true;
                            }
                }
     }
     
     return false;
}

void GAME_SOLUTION::ClearSolution()
{
     /* This clears a solution ready for the next game */
     int idx1, idx2;
     
     for(idx1=0; idx1<BUTTON_NUM; idx1++)
     {
                 for(idx2=0; idx2<BUTTON_NUM; idx2++)
                 {
                             this->solution[idx2][idx1] = 0;
                 }
     }
     
     /* This seeds the RNG */
     time(&(this->rand_num1));
     srand((unsigned int)(this->rand_num1));
     
     return;
}

void GAME_SOLUTION::SetSolution(int num, int idx_x, int idx_y)
{
     /* This method just sets a solution value */
     this->solution[idx_x][idx_y] = num;
     
     return;
}

unsigned int GAME_SOLUTION::GetSolution(int idx_x, int idx_y)
{
         /* This returns the solution value for a given position */
         /* The check for the win will be made in main.cpp, in the form of a function call
            to here inside a loop, checking if game_board gives the same result
         */
         
         unsigned int num;
         
         num = this->solution[idx_x][idx_y];
         
         return num;
}