Skip to content

Instantly share code, notes, and snippets.

@timvisee
Last active August 29, 2015 14:07
Show Gist options
  • Save timvisee/a7945edfde5aa865c22b to your computer and use it in GitHub Desktop.
Save timvisee/a7945edfde5aa865c22b to your computer and use it in GitHub Desktop.
HHS Sudoku Week 4
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment