Monday, May 9, 2011

Sudoku checker

Time for another home assignment! :P
Given a solved sudoku board, the aim is to check whether it is a valid solution or not. The program pasted below will do the same. In fact, it prints out ALL the offending rows, columns and blocks (if the solution is not valid). The idea is simple, if a row/column/block has all its elements to be unique, then the sum of all it's elements will be (N*(N+1))/2, where NxN is the size of the sudoku board.

#include <stdio.h>
void isCorrect(int** grid, int N, int sqrootN) {
    int sum = (N * (N + 1)) >> 1;
    // all rows
    for(int i=0;i<N;i++) {
        int actual = 0;
        for(int j=0;j<N;j++) {
            actual += grid[i][j];
        }
        if(actual != sum) {
            printf("Row '%d' is incorrect!\n", i+1);
        }
    }
    // all columns
    for(int i=0;i<N;i++) {
        int actual = 0;
        for(int j=0;j<N;j++) {
            actual += grid[j][i];
        }
        if(actual != sum) {
            printf("Column '%d' is incorrect!\n", i+1);
        }
    }
    // all blocks
    for(int i=0;i<N;i+=sqrootN) {
        for(int j=0;j<N;j+=sqrootN) {
            int actual = 0;
            for(int a=0;a<sqrootN;a++) {
                for(int b=0;b<sqrootN;b++) {
                    actual += grid[i+a][j+b];
                }
            }
            if(actual != sum) {
                printf("Block starting at '%d,%d' is incorrect!\n", i+1,j+1);
            }
        }
    }
}

int main(int argc, char** argv) {
    if(argc == 2) {
        FILE* fp = fopen(argv[1], "r");
        if(fp == NULL) {
            fprintf(stderr, "Failed to open '%s' for reading!\n", argv[1]);
            return 1;
        }
        int N, sqrootN;
        int** grid;
        fscanf(fp, "%d", &N);
        fscanf(fp, "%d", &sqrootN);
        grid = new int* [N];
        for(int i=0;i<N;i++) {
            grid[i] = new int [N];
            for(int j=0;j<N;j++) {
                fscanf(fp, "%d", &(grid[i][j]));
            }
        }
        isCorrect(grid, N, sqrootN);
        for(int i=0;i<N;i++) {
            delete grid[i];
        }
        delete grid;
        fclose(fp);
    }
    else {
        fprintf(stderr, "USAGE: %s <file>\n", argv[0]);
        return 1;
    }
    return 0;
}

How to compile?
(Assuming the above program is saved in the file sudokuChecker.cpp)
g++ -o checker sudokuChecker.cpp

How to run?
./checker <file>
<file> = the file containing the sudoku board

Format of the <file>?
<BoardSize> <squareRootOfBoardSize>
Each of the elements in the board in row-major order.

Complexity?
Obviously, the above program has a time complexity of O(N^2).

Saturday, May 7, 2011

Finding (and printing) cycles in a directed graph

I know... this seems some kind of under-grad assignments. But I was feeling boring last night and hence decided to write this code to kill time. I spent about 20-30 minutes in coming up with this program. The program is available at git://github.com/teju85/Cycles.git. This code takes a file as input (containing the adjacency matrix for the graph of interest) and prints all the elementary cycles in the directed graph.

PS: However, I haven't tested this code rigorously, yet! So, if you find any issues with this code, just drop in a comment here and I'll take a look into it.