Sudoku Solver!

Solution: Below is the code to solve a sudoku.

/*
Input Matrix:
 7  0  0  1  0  0  0  0  0 
 0  2  0  0  0  0  0  1  5 
 0  0  0  0  0  6  3  9  0 
 2  0  0  0  1  8  0  0  0 
 0  4  0  0  9  0  0  7  0 
 0  0  0  7  5  0  0  0  3 
 0  7  8  5  0  0  0  0  0 
 5  6  0  0  0  0  0  4  0 
 0  0  0  0  0  1  0  0  2 
*/

#define TRUE 1
#define FALSE 0
#define N 9
int S[N+1][N+1] = {0,};

void printMat(int S[][N+1])
{
    int i = 0;
    int j = 0;


    for(i=1; i<=N; i++) {
        for(j=1; j<=N; j++) {
            printf("%2d ", S[i][j]);
        }
        printf("\n");
    }
}

void initMat(int S[][N+1])
{
    S[1][1] = 7;
    S[1][4] = 1;

    S[2][2] = 2;
    S[2][8] = 1;
    S[2][9] = 5;

    S[3][6] = 6;
    S[3][7] = 3;
    S[3][8] = 9;

    S[4][1] = 2;
    S[4][5] = 1;
    S[4][6] = 8;
    
    S[5][2] = 4;
    S[5][5] = 9;
    S[5][8] = 7;

    S[6][4] = 7;
    S[6][5] = 5;
    S[6][9] = 3;

    S[7][2] = 7;
    S[7][3] = 8;
    S[7][4] = 5;

    S[8][1] = 5;
    S[8][2] = 6;
    S[8][8] = 4;

    S[9][6] = 1;
    S[9][9] = 2;
}

int permitted(int S[][N+1], int i, int j, int a)
{
    int x;

    for(x=1; x<=N; x++) {
        if(S[i][x] == a) {
            return FALSE;
        }
    }

    for(x=1; x<=N; x++) {
        if(S[x][j] == a) {
            return FALSE;
        }
    }

    return TRUE;
}

void solve(int S[][N+1], int i, int j)
{
    int a = 0;

    /*
     * this row is filled, jump to next row
     */
    if(j > N) {
        j = 0;
        i++;
    }

    /*
     * all rows are filled, print sol. and exit
     */
    if(i > N) {
        printMat(S);
        printf("\n");
        exit(0);
    }

    /*
     * each cell can take a value belonging to [1,9]
     */
    for(a=1; a<=N; a++) {
        /*
         * cell is already occupied, move to next cell
         */
        if (S[i][j]) {
            solve(S, i, j+1);
            return;
        }
        else if (permitted(S, i, j, a)) {
            S[i][j] = a;
            solve(S, i, j+1);
            S[i][j] = 0;
        } else {
            continue;
        }
    }
}

int main()
{
    initMat(S);
    printMat(S);
    printf("\n");
    solve(S, 1, 1);
}

Knapsack Problem

Solution: Below is the code using dynamic programming,

#define MAX(a,b) (a)>(b)?(a):(b)
/*
 * Number of objects = 4
 * Capacity ig Knapsack = 8
 */
#define N 4
#define W 8
typedef struct {
    int32_t v;
    int32_t w;
} Object;

Object obj[N+1] = {{0, 0}, {15, 1}, {10, 5}, {9, 3}, {5, 4}};
int32_t V[N+1][W+1] = {0, };

int main()
{
    int32_t n = 0;
    int32_t w = 0;
    int32_t value = 0;
    int32_t weight = 0;

    for(n=1; n<=N; n++) {
        for(w=0; w<=W; w++) {
            weight = obj[n].w;
            value = obj[n].v;

            /*
             * Cases:
             * - Last item is excluded from the final set: V[n-1][w]
             * - Last item is included in the final set: value + V[n-1][w-weight]
             *
             * Corner case:
             * - If weight > w, choose V[n-1][w]
             */
            if(w >= weight) {
                V[n][w] = MAX( V[n-1][w], value + V[n-1][w-weight] );
            }
            else {
                V[n][w] = V[n-1][w];
            }
        }
    }

    printf("Ans = %d\n", V[N][W]);
    return 0;
}