OpenVMS Source-Code Demos

SUDOKU2

//=======================================================
// title: Sudoku2.c (a system benchmark)
// ref  : http://codereview.stackexchange.com/questions/37430/sudoku-solver-in-c
// notes: 1. Sudoku (soo-doh-koo) is a number-placement logic puzzle. The objective
//	     is to fill a partially constructed 9*9 grid with digits so that each
//	     column, each row, and each of the nine 3*3 sub-grids that compose the
//	     main grid contain all of the digits from 1 to 9.
//      : 2. the test run should look like this
//
//	+-----+-----+-----+
//	|7|4|8|6|3|5|2|9|1|
//	|1|9|3|4|7|2|6|5|8|
//	|6|5|2|8|1|9|4|3|7|
//	+-----+-----+-----+
//	|2|6|5|9|4|8|7|1|3|
//	|8|7|9|1|2|3|5|4|6|
//	|3|1|4|7|5|6|8|2|9|
//	+-----+-----+-----+
//	|9|2|7|3|6|4|1|8|5|
//	|5|3|6|2|8|1|9|7|4|
//	|4|8|1|5|9|7|3|6|2|
//	+-----+-----+-----+
//=======================================================
#include <stdio.h>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;
    int i, j;

    for(i=0; i<9; ++i)
    {
        if (puzzle[row][i] == num) return 0;
        if (puzzle[i][col] == num) return 0;
        if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }
    return 1;
}

int fillSudoku(int puzzle[][9], int row, int col)
{
    int i;
    if(row<9 && col<9)
    {
        if(puzzle[row][col] != 0)
        {
            if((col+1)<9) return fillSudoku(puzzle, row, col+1);
            else if((row+1)<9) return fillSudoku(puzzle, row+1, 0);
            else return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if(isAvailable(puzzle, row, col, i+1))
                {
                    puzzle[row][col] = i+1;
                    if((col+1)<9)
                    {
                        if(fillSudoku(puzzle, row, col +1)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else if((row+1)<9)
                    {
                        if(fillSudoku(puzzle, row+1, 0)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else return 1;
                }
            }
        }
        return 0;
    }
    else return 1;
}

int main()
{
    int i, j;
    int puzzle[9][9]={{0, 0, 0, 0, 0, 0, 0, 9, 0},
                      {1, 9, 0, 4, 7, 0, 6, 0, 8},
                      {0, 5, 2, 8, 1, 9, 4, 0, 7},
                      {2, 0, 0, 0, 4, 8, 0, 0, 0},
                      {0, 0, 9, 0, 0, 0, 5, 0, 0},
                      {0, 0, 0, 7, 5, 0, 0, 0, 9},
                      {9, 0, 7, 3, 6, 4, 1, 8, 0},
                      {5, 0, 6, 0, 8, 1, 0, 7, 4},
                      {0, 8, 0, 0, 0, 0, 0, 0, 0}};

    if(fillSudoku(puzzle, 0, 0))
    {
        printf("\n+-----+-----+-----+\n");
        for(i=1; i<10; ++i)
        {
            for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
            printf("|\n");
            if (i%3 == 0) printf("+-----+-----+-----+\n");
        }
    }
    else printf("\n\nNO SOLUTION\n\n");

    return 0;
}