Sudoku generator – II

I was reading about the DFS a few days back. It is depth first search, which can be used to solve any problem which has a multiple possible ways leading to solution. I knew the basics – a brief overview that how it can help me in solving a sudoku. This approach looks pretty simple when you are supposed to explain anyone, but I never knew that it may be simple in implementation too. I generated a new sudoku SOLVED grid using DFS today.

DFS in coding is nothing but the recursion. You keep on going to a particular path till the time you don’t reach to dead end. Once reached to dead end, just return to the previous path, and explore the new route from that path. In the context of sudoku, here is what I did:

Each and every cell in sudoku grid can have a possible values, ranging from 1 to 9.
1. Fill the value of cell 0x0 with 1, and update the bitmap of that cell.
2. Go to next cell (i.e. 0x1). Find the possible values of that cell (which will be 2 to 9). Put any value in that cell and keep on repeating this step until there are no possible values found for a cell (this condition happens when you are filling some wrong values to a cell).

For example, if you have reached to a cell 3×5, where you are not able to find any possible values. This may happen because in cell 3×4, you have put a wrong value out of multiple possible values. In such case, go to the previous cell of 3×5 (i.e. 3×4), and put the another possible value. Let say, in cell 3×4, you have 5,3,2,7 as possible values. You started with 5, but with this value you are not able to find any possible values for cell 3×5, so you go back to cell 3×4 and try putting 2 and go ahead.

This is DFS in a way. I was able to create a sudoku grid in a very simple and clean manner via code using this method. Here is the code.

#include <stdio.h>
#include <malloc.h>

#define bi  (i)
#define bj  (9+j)
#define bk  (18+(3*(i/3)+(j/3)))

int matrix[9][9];
int verify()
{
    int i, j, k;
    int bitmap[27] = {0};
    int bmp_idx;
    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;
}

void find_possible(int *arr, int i, int j, int *bmp)
{
        int idx = 0;
        int iter;

        for (iter = 1; iter <= 9; iter++) {
            if (((bmp[bi] >> iter) & 0x1) || ((bmp[bj] >> iter) & 0x1) || ((bmp[bk] >> iter) & 0x1)) {
                continue;
            } else {
                idx++;
                arr[idx] = iter;
            }
        }
        arr[0] = idx;
}

int fill(int *bmp, int i, int j)
{
    int arr[10], temp;
    int flag= 0;
    find_possible(arr, i, j, bmp);
    if (arr) {
        int len = arr[0];
        int iter, ti, tj;
        if (len == 0) {
            return -1;
        }
        for (iter = 0; iter < len; iter++) {
            matrix[i][j] = arr[iter+1];
            ti = i; tj = j;
            flag = 0;
            bmp[bi] |= 1 << arr[iter+1];
            bmp[bj] |= 1 << arr[iter+1];
            bmp[bk] |= 1 << arr[iter+1];
            j++;
            if (j % 9 == 0) { i++; j = 0; }
            if (i == 9) { return 0; }
            if (fill(bmp, i, j) == -1) {
                i = ti; j = tj;
                bmp[bi] ^= 1 << arr[iter+1];
                bmp[bj] ^= 1 << arr[iter+1];
                bmp[bk] ^= 1 << arr[iter+1];
                flag = -1;
            } else
                return flag;
        }
       
    }
    return flag;

}

int main()
{
    int bmp[27] = {0};
    int i = 0, j = 0;
    if (fill(bmp, i, j) == 0) {
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                printf("%d ", matrix[i][j]);
            }
            printf("\n");
        }
    }
    if (verify() == 0) {
        printf("Sudoku generated\n");
    } else
    printf("Failed\n");
    return 0;
}

Next step is to make a sudoku solver :) Sudoku, I am coming !!  YAY!!

Advertisements

4 thoughts on “Sudoku generator – II

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s