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).

No comments:

Post a Comment