HHS Sudoku Week 4

main.c

/**
 * Sudoku Opdracht - Week 4.
 * A practical computer science project.
 *
 * @author Tim Visee
 * @version 2
 * @website http://timvisee.com/
 * @copyright Copyright (c) Tim Visee 2014. All rights reserved.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/** Defines the sudoku as an 2D array */
int sudoku[9][9] = {
        {5, 6, 3, 9, 4, 8, 1, 2, 7},
        {9, 7, 8, 2, 5, 1, 6, 4, 3},
        {2, 4, 1, 6, 7, 3, 5, 8, 9},
        {4, 8, 9, 5, 1, 7, 3, 6, 2},
        {7, 3, 2, 8, 9, 6, 4, 5, 1},
        {6, 1, 5, 3, 2, 4, 7, 9, 8},
        {3, 2, 7, 4, 6, 9, 8, 1, 5},
        {8, 5, 6, 1, 3, 2, 9, 7, 4},
        {1, 9, 4, 7, 8, 5, 2, 3, 6}};

/**
* Print the sudoku on the console with proper formatting.
*/
void printSudoku();

/**
* Validate the sudoku. This will check for duplicated values and invalid blocks.
*
* @return True if the sudoku is valid, false otherwise.
*/
bool validateSudoku();

/**
* Validate the rows of the sudoku. This method checks whether there are any duplicated numbers in each row.
*
* @return The number of the first invalid row, or zero if all rows were valid.
*/
int validateRows() ;

/**
* Validate the columns of the sudoku. This method checks whether there are any duplicated numbers in each column.
*
* @return The number of the first invalid column, or zero if all columns were valid.
*/
int validateColumns();

/**
 * Validate the blocks of the sudoku. This method checks whether there are any duplicated numbers in each block.
 *
 * @return The number of the first invalid block, or zero if all blocks were valid.
 */
int validateBlocks();

/**
 * Check whether an integer array has any duplicated values.
 *
 * @param arr The integer array to check.
 * @param size Size of the array.
 *
 * @return True if the integer array has any duplicated values, false otherwise.
 */
bool hasDuplicates(int *arr, int size);

/**
 * Main function, called on initialization.
 *
 * @return int Application exit code.
 */
int main(int argc, char *argv[])
{
    // Print the sudoku
    printSudoku();
    printf("\n");

    // Validate the sudoku, print the result
    if(validateSudoku())
        printf("[INFO] The sudoku is valid, because it doesn't have duplicated numbers in any row, column or block!\n");
    else
        printf("[ERROR] Found duplicated numbers in some rows, columns or blocks!\n");

    // Pause and exit
    system("PAUSE > NUL");
    return 0;
}

void printSudoku()
{
    // Predefine some variables used in the for loops
    int i, bc, br, c, r;

    // Loop through all the block-rows
    for(br = 0; br < 4; br++)
    {
        // Print a header
        for(i = 0; i < 7 * 3 + 2; i++)
            printf("=");
        printf("\n");

        // Break the for loop just in time, so the last header gets printed
        if(br > 2)
            continue;

        // Loop through all the rows inside a block-row
        for(r = 0; r < 3; r++)
        {
            // Print the prefix character
            printf("|");

            // Loop through all the block-columns inside the row
            for(bc = 0; bc < 3; bc++)
            {
                // Loop through all the columns inside the block-column
                for(c = 0; c < 4; c++)
                {
                    // Print the separation character
                    printf("|");

                    // Break the for loop just in time, so the last block character gets printed
                    if(c > 2)
                        continue;

                    // Print the number
                    printf("%d", sudoku[br * 3 + r][bc * 3 + c]);
                }
            }

            // Print the suffix character and enter a new line
            printf("|\n");
        }
    }
}

bool validateSudoku() {
    // Set whether the sudoku is valid
    bool valid = true;
    int val = 0;

    // Show a status message
    printf("[INFO] Scanning for duplicates...\n");

    // Validate the rows
    if((val = validateRows()) == 0)
        printf("[INFO] No duplicated numbers found in any row!\n");
    else
    {
        printf("[ERROR] Found duplicated numbers in row: %d!\n", val);
        valid = false;
    }

    // Validate the columns
    if((val = validateColumns()) == 0)
        printf("[INFO] No duplicated numbers found in any columns!\n");
    else
    {
        printf("[ERROR] Found duplicated numbers in column: %d!\n", val);
        valid = false;
    }

    // Validate the blocks
    if((val = validateBlocks()) == 0)
        printf("[INFO] No duplicated numbers found in any blocks!\n");
    else
    {
        printf("[ERROR] Found duplicated numbers in block: %d!\n", val);
        valid = false;
    }

    // Show a status message
    printf("[INFO] Done scanning for duplicates!\n");

    // Return true if the sudoku was valid
    return valid;
}

int validateRows() {
    // Predefine the variable used in the for loop
    int r;

    // Validate all rows
    for(r = 0; r < 9; r++)
        // Check for duplicates in this row
        if(hasDuplicates(sudoku[r], 9))
            return r + 1;

    // All rows seem to be valid, return true
    return 0;
}

int validateColumns() {
    // Predefine the variables used in the for loops
    int c, r;

    // Validate all rows
    for(c = 0; c < 9; c++)
    {
        // Define the array to put the column in
        int column[9];

        // Get the column
        for(r = 0; r < 9; r++)
            column[r] = sudoku[r][c];

        // Check for duplicates in this row
        if(hasDuplicates(column, 9))
            return c + 1;
    }

    // All rows seem to be valid, return true
    return 0;
}

int validateBlocks() {
    // Predefine some variables used in the for loops
    int br, bc, r, c;

    // Loop through all the block-columns inside the row
    for(bc = 0; bc < 3; bc++)
    {
        // Loop through all the block-rows
        for(br = 0; br < 3; br++)
        {
            // Define the array to put the block in
            int block[9];

            // Loop through all the rows and colums inside the block
            for(r = 0; r < 3; r++)
                for(c = 0; c < 3; c++)
                    block[r * 3 + c] = sudoku[br * 3 + r][bc * 3 + c];

            // Check for duplicates in this block
            if(hasDuplicates(block, 9))
                return br * 3 + bc + 1;
        }
    }

    // The block doesn't seem to have any duplicates, return true
    return 0;
}

bool hasDuplicates(int *arr, int size) {
    // Make sure the array contains at least two items
    if(size < 2)
        return false;

    // Check for duplicates
    int i, j;
    for(i = 0; i < size; i++)
    {
        for(j = i + 1; j < size; j++)
        {
            // Make sure i is compared with a different number
            if(i == j)
                continue;

            // Check whether the numbers equal
            if(arr[i] == arr[j])
                return true;
        }
    }

    // No duplicate found, return false
    return false;
}