Algorithm for generating a Sudoku puzzle

[kinjal2209]

The same algorithm will be able to generate various sudoku puzzles with unique solutions under varying difficulty, mentioned by the user

Important factors describing the difficulty level

1. The initial amount of givens: The no. of givens in the sudoku means the no. of cells which initially hold numbers, the other cells are blank and will hold numbers only when solved.
2. Lower bound of given cells: The lowest no. of givens in a row and column of the sudoku. Any row or column which can have the lowest no. of givens, but all the other rows and columns must have no. of givens more than this given value.

Some facts regarding setting the difficulty level:

Level no.	|Level Name		|Initial no. of Givens		|Lower Bound

1		|Extremely Easy		|more than 50			|5
2		|Easy			|36-40				|4
3		|Medium			|32-45				|3
4		|Hard			|28-31				|2
5		|Evil			|22-27				|0

My code:

int randRange(int low, int high)
{
    return (int)(rand() / (RAND_MAX / (double)(high - low))) + low;
}

void delArr(int arr[], int size, int pos)
{
    for(int i=pos+1; i<size; i++)
        swap(arr[i], arr[i-1]);
}

void printGrid_all(int grid1[N][N], int grid2[N][N], int x, int y);
void printGrid_prob(int grid[N][N], int x, int y);

void generateGrid(int grid[N][N], int lvl)
{
    int ch_num[10] = {1,2,3,4,5,6,7,8,9,-1};

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
            grid[i][j]=0;
    }
    cout<<"Stage1"<<endl;

    int ch_num2[9];

    for(int i=0; i<N; i++)
        ch_num2[i]=ch_num[i];

    int r=8;
    for(int i=0; i<N; i++)
    {
        int temp = randRange(0, r);
        grid[i][i]=ch_num2[temp];
        delArr(ch_num2, r+1, temp);
        r--;
    }
    cout<<"Stage2"<<endl;

    printGrid_prob(grid, 0, 0);
    getch();

    SolveSudoku(grid);

    printGrid_prob(grid, 0, 0);
    getch();

    int lb, given;
    switch(lvl)
    {
    case 1://extremely easy
        {
            lb = 4;// this are actually 9(total in a row/coloumn) - lower bound
            given = randRange(50, 60);
        }

    case 2://easy
        {
            lb = 5;
            given = randRange(36, 49);
        }

    case 3://medium
        {
            lb = 5;
            given = randRange(32, 35);
        }

    case 4://hard
        {
            lb = 7;
            given = randRange(28, 31);
        }

    case 5://Evil
        {
            lb = 9;
            given = randRange(22, 27);
        }
    }
    cout<<"Stage3"<<endl;

    int rORc = randRange(0, 1);

    int ch_num3[9] = {0,1,2,3,4,5,6,7,8};

    for(int i=0; i<N; i++)
        ch_num3[i]=ch_num[i];

    int temp;
    if(rORc == 0)
    {
        temp = randRange(0, 8);

        int r=8;
        for(int i=0; i<lb; i++)
        {
            int temp2 = randRange(0, 8);
            int temp3 = ch_num3[temp2];
            grid[temp][temp3]=0;
            delArr(ch_num2, r, temp2);
            r--;
        }

        cout<<"Stage4"<<endl;

        int fill_zero = 81 - given - lb;

        cout<<"Fill zeros in: "<<fill_zero<<endl;

        while(fill_zero != 0)
        {
            int tempR = randRange(0, 8);
            int tempC = randRange(0, 8);

            if(tempR != temp)
            {
                grid[tempR][tempC]=0;
                fill_zero--;
            }
            else
                continue;
        }
        cout<<"Stage5"<<endl;
    }

    else
    {
        temp = randRange(0, 8);

        int r=8;
        for(int i=0; i<lb; i++)
        {
            int temp2 = randRange(0, 8);
            int temp3 = ch_num3[temp2];
            grid[temp3][temp]=0;
            delArr(ch_num2, r, temp2);
            r--;
        }

        cout<<"Stage4"<<endl;

        int fill_zero = 81 - given - lb;

        cout<<"Fill zeros in: "<<fill_zero<<endl;

        while(fill_zero != 0)
        {
            cout<<fill_zero<<endl;
            int tempR = randRange(0, 8);
            int tempC = randRange(0, 8);

            if(tempC != temp)
            {
                grid[tempR][tempC]=0;
                fill_zero--;
            }
            else
                continue;
        }
        cout<<"Stage5"<<endl;
    }

}

[Handy Andy]

Hello kinjal2209,

As keskiverto once said:

Please note that this is not a homework site. We won't do your homework for you. The purpose of homework is that you learn by doing. However we are always willing to help solve problems you encountered, correct mistakes you made in your code and answer your questions.

We didn't see your attempts to solve this problem yourself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again.

To that I would add that I believe your instructions are a bit lacking.

In a Sudoku puzzle each 9 X 9 square can only contain the numbers 1 - 9 once and each row and each column can only contain the numbers 1 - 9 only once. So there is more to just putting some numbers around the board for a game.

Initial thoughts are two 2D arrays of some kind, could be vectors, one to hold the answers and one for the play. From the answers array yo could use this to seed the other array to start the game. Just a thought for now.

Your instructions do not say if you need to use any classes or structs in this program. Do not know if they would be of any use, but something to think about.

Hope that helps,

Andy

[kinjal2209]

Thanks, @Handy Andy for your support...

Firstly i am sorry to tell you that this isn't my homework. I don't do homework(or better say i don't want others doing my homework). I code for fun. I faced a problem so i posted a question here.

Secondly, i have edited my question and added my code. Now this code doesn't work as it must work following the above guidelines

Thirdly putting mere numbers all around the board won't make a valid sudoku with a unique solution.

Also, consider reading my question once. I wanted to have different kinds of puzzles depending upon their difficulty level

The different difficulty level has its own criteria mentioned in that table

Hope you understand,

Kinjal

[Handy Andy]

Hello kinjal2209,

Sorry about the homework part. I see so many that are homework I just got the wrong idea.

Normally I would tell you not to edit the original post, because some people change things and it makes the thread hard to follow. In this case it is not a problem. Although I would put the word "Edit:" at the end to dray attention that it has changed. And maybe add a comment about what has changed.

When my headache goes away I will load up your program and see what is happening.

I did not forget about the difficulty levels. That part is minor compared to what needs to be done.

Andy

[icy1]

kinjal2209 wrote:

Secondly, i have edited my question and added my code.

I did a Ctrl+F on this page for a question mark and did not find one ;D

[Manga]

If this is Sudoku, which is a 9x9 grid, why have a variable in the 2d array?

[dhayden]

Do you need to apply the difficulty bounds to each 3x3 box, or just the rows and columns?

There isn't enough code in your post to compile (e.g., no main() function and no SolveSudoku(), which is called on line 44).

Can you explain how the code is supposed to work? What is your algorithm?

FWIW, I found it a TON of fun to write a sudoku solver. There are many algorithms you can apply to solve the puzzle. If you pay a little attention to performance, your solver will run in milliseconds or faster.

[Handy Andy]

Hello kinjal2209,

@Manga Actually it is nine 9 X 9 squares. A 2D array makes sense.

I will concede that I was hoping for a program the works because what you have posted does not compile for me. There is many things that are missing.

Header files to make things work.

You have two prototypes, but no function definitions. What I did notice is the way the prototypes are written:

void printGrid_all(int grid1[N][N], int grid2[N][N], int x, int y);
void printGrid_prob(int grid[N][N], int x, int y);

"N" where does it come from and how does it get its value?

This may work better for you:

// Header files here

constexpr std::size_t MAXSIZE{ 9 };
constexpr std::size_t MAXROW{ 9 };
constexpr std::size_t MAXCOL{ 9 };

void printGrid_all(int grid1[MAXROW][MAXCOL], int grid2[MAXROW][MAXCOL], int x, int y);
void printGrid_prob(int grid[MAXROW][MAXCOL], int x, int y);

And later on in the file where you might type 9, say in a for loop, you can use "MAXSIZE" or one of the other two. This way, maybe not in this program, but another, You only have one place to make changes instead of looking through the whole program.

The "SolveSudoku" function is missing.

This may take awhile to figure out how to test it.

Hope that helps,

Andy

[Manga]

The original post is also Sudoku...

We are given part of the code and we must fill in the missing pieces ourselves.

Not a bad game actually!