Sudoku Puzzle Generator

This was in my task list since long, and I was not able to figure out any algorithm which can generate different sudoku puzzles. (Solving a sudoku is very far from here, the first step is to generate a sudoku puzzle grid). I spent some time last week but none of the algorithm were working. Most of the time I was relying on the random numbers generated and fill the grid accordingly using different patterns but none of them worked. I was not able to figure out any solid pattern that can generate me a basic solved grid.

Initially I tried to fill this 2-d array in spiral fashion, filling the random numbers all the way in first pass. In second pass, I will see if the number can be put there or not, so 2nd pass was also working. But in third pass, if the number cannot be put, there is no way I can recover. So dumped this idea of filling the grid in spiral fashion. Next idea was to fill the grid in "right angle" method. For example consider the 2-d array of 4×4, then I would fill it in this way:
1st pass – element 0,0
2nd pass – elements 0,1 – 1,1 – 1,0
3rd pass – elements 0,2 – 1,2 – 2,2 – 2,1 – 2,0
And so on. But this also didn’t work, as there was no way of recovering if something goes wrong. I tried to modified this thing a little and skipped all the even passes. So I will fill the array only in 1st, 3rd, 5th and so on passes. But no luck. And I left the work last week.

Today, I again resume and thought of doing simple thing. Start with 1, put 1 in all the cubes (3×3 cubes in sudoku grid) in uniform fashion. Like put 1st 1 in 0x0, 2nd in 2×1, 3rd in 3×8, 4th in 2×1, 5th in 4×5, 6th in 5×6.. If you fill this manually, you will observe a pattern that all the 1s are shifting once cell right in a uniform fashion. I filled the whole grid in this fashion and I got my first SOLVED sudoku grid prepared. Sigh. Now, to generate the different grids, I need to swap the rows or columns within a cube or I have to swap them in uniform fashion – like the one with having 1,2,3 in a particular 3×3 cube only can be swapped with anther similar row. Same is true for column. I am not sure of how many sudoku’s I can generate out of this dumb logic.

By the way –  Here is the master gird

    {1,2,3,9,7,8,5,6,4},
    {4,5,6,3,1,2,8,9,7},
    {7,8,9,6,4,5,2,3,1},
    {3,1,2,8,9,7,4,5,6},
    {6,4,5,2,3,1,7,8,9},
    {9,7,8,5,6,4,1,2,3},
    {2,3,1,7,8,9,6,4,5},
    {5,6,4,1,2,3,9,7,8},
    {8,9,7,4,5,6,3,1,2}

I will google a bit if I can find a better algorithm to generate the sudoku grids.

Anyway, here is some complex code which I’ve written in recent past. It takes one argument which is the starting element of the SOLVED sudoku grid.

File : gen_new.c

#include <stdio.h>
#include <string.h>

extern int matrix[9][9];

void print_matrix()
{
    int i, j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}
void generate(int start)
{
    int i, j;
    int row, col = 0;
    int col_inc = 0;
    int row_inc = 0;
    int col_start = 0;
    int row_start = 0;
    row = 0;
    int rand = start;
    int flag = 0;
    memset (matrix, 0x0, sizeof(matrix));
    for (i = 0; i < 9; i++) {
        col = i % 3;
        col_inc = 0;
        col_start = 0;
        row_start = (row_inc/3);
        for (j = 0; j < 9; j++) {
            matrix[row][col] = ((i+rand)%10) ? (i+rand)%10 : ({rand++; (i+rand)%10;});
            row = ((row+1)%3) + (3*(j/3));
           

            col_start += 3;
            col = ((col+4)%3) + col_start;
           
            col_inc++;
            if (col_inc % 3 == 0) {
                col = ((i%3) + (col_inc/3))%3;
                col_start = 0;
                row_start = j + (row_inc/3)+1;
                row = row_start%9;
            }
        }
        row_inc++;
        if (row_inc % 3 == 0) {
            row = row_inc / 3;
        }
    }
}
int main(int argc, char *argv[])
{
    generate(atoi(argv[1]));
    if (!verify())
        printf("Sudoku solved\n");
    print_matrix();
    return 0;
}

File: verifier.c
#include <stdio.h>
#include <string.h>

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

#define swap(a,b) {a^=b; b^=a; a^=b;}

void swap_row(int row_a, int row_b)
{
    int limit = sizeof(matrix[row_a])/sizeof(matrix[row_a][0]);
    int i;
    for (i = 0; i < limit; i++)
        swap(matrix[row_a][i], matrix[row_b][i]);
}

void swap_col(int col_a, int col_b)
{
    int limit = sizeof(matrix)/sizeof(matrix[col_a]);
    int i;
    for (i = 0; i < limit; i++)
        swap(matrix[i][col_a], matrix[i][col_b]);
}

int verify()
{
    int i, j, k;
    int bitmap[27] = {0};
    int bmp_idx;
#define bi    (i)
#define bj    (9+j)
#define bk    (18+(3*(i/3)+(j/3)))

    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if ((((bitmap[bi] >> matrix[i][j]) & 0x1) == 0x0) &&
                    (((bitmap[bj] >> matrix[i][j]) & 0x1) == 0x0) &&
                    (((bitmap[bk] >> matrix[i][j]) & 0x1) == 0x0)) {
                bitmap[bi] |= 1 << matrix[i][j];
                bitmap[bj] |= 1 << matrix[i][j];
                bitmap[bk] |= 1 << matrix[i][j];
            } else {
                printf("Sudoku Error: i = %d, j = %d\n", i, j);
                return -1;
            }

        }
    }
    return 0;
}
/*
int main()
{
    if (!verify()) {
        printf("Sudoku Solved\n");
    } else
        printf("Sudoku has error\n");

    return 0;
}
*/

Now, to add a little bit of randomisation in this, I am planning to start the grid with a random element from 1 to 9. Once basic grid is generated, I will swap the rows and columns of the same cube. That all will happen randomly, like which cube’s row will be swapped and which cube’s column will be swapped. I am not sure if the swapping would break the sudoku. Let’s see if it works.

Advertisements

One thought on “Sudoku Puzzle Generator

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s