Created
May 15, 2018 10:10
-
-
Save asela38/79d346a02a336eb79632a889dedb9757 to your computer and use it in GitHub Desktop.
Code written sometime back in C to solve a sudoku
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* File : sudoku.c | |
* Using coding samples show in the Richard Buckland' lecture | |
* series on Higher computing (http://www.youtube.com/watch?v=Rxvv9krECNw) | |
* (lecture 22 and 21 ) | |
* Created on: May 12, 2009 | |
* Author: Asela | |
*/ | |
#include | |
#include | |
#include | |
#define SQ_SIZE 3 | |
#define LENGTH (SQ_SIZE*SQ_SIZE) | |
#define MAX_SIZE (LENGTH*LENGTH) | |
#define MIN_VALUE 1 | |
#define MAX_VALUE 9 | |
#define EMPTY 0 | |
#define TRUE 1 | |
#define FALSE 0 | |
typedef int Cell; | |
typedef int Value; | |
typedef Value SudokuGrid [MAX_SIZE]; | |
void readGame(SudokuGrid); | |
void displayGame(SudokuGrid); | |
int hasSolution(SudokuGrid); | |
int hasEmptyCell(SudokuGrid); | |
int nextEmptyCell(SudokuGrid); | |
int isLegal(SudokuGrid, Cell,Value); | |
int isInRow(SudokuGrid,Cell); | |
int isInColumn(SudokuGrid ,Cell); | |
int isInSquare(SudokuGrid , Cell); | |
int main(int argc, char *argv[]){ | |
SudokuGrid game; | |
readGame(game); | |
printf("\n-------Problem----------\n"); | |
displayGame(game); | |
printf("\n-------Solution-------j---\n"); | |
if(hasSolution(game)){ | |
displayGame(game); | |
} | |
return EXIT_SUCCESS; | |
} | |
/* | |
* displays the game | |
*/ | |
void displayGame(SudokuGrid game){ | |
Cell cell = 0; | |
for( cell = 0 ; cell < MAX_SIZE ; cell++ ){ | |
printf(" %d" , game[cell]); | |
if( (cell+1) % 3 == 0 ) printf(" "); | |
if( (cell+1) % 9 == 0 ) printf("\n"); | |
if( (cell+1) % 27 == 0 ) printf("\n"); | |
} | |
} | |
/* | |
* get the user input | |
* only numerical values | |
*/ | |
void readGame(SudokuGrid game){ | |
printf("insert numbers\n"); | |
Cell cell = 0; | |
while(cell < MAX_SIZE){ | |
char ch = getchar(); | |
if(isalnum(ch) && !isalpha(ch)){ | |
game[cell] = ch - '0' ; | |
cell++; | |
} | |
} | |
printf("\nCharacter intakes is over\n"); | |
} | |
/* | |
* checks if the game has a solution | |
* as a side effect it solves the game. | |
*/ | |
int hasSolution(SudokuGrid game){ | |
int solved = FALSE; | |
Cell cell = 0; | |
Cell checkValue = 0 ; | |
if(hasEmptyCell(game)){ | |
cell = nextEmptyCell(game); | |
checkValue = MIN_VALUE; | |
while(!solved && checkValue <= MAX_VALUE){ | |
if(isLegal(game , cell , checkValue)){ | |
game[cell] = checkValue; | |
if(hasSolution(game)){ | |
solved = TRUE; | |
} | |
} | |
checkValue++; | |
} | |
} else { | |
solved = TRUE; | |
} | |
return solved; | |
} | |
/* | |
* checks the gave for a empty cell | |
*/ | |
int hasEmptyCell(SudokuGrid game){ | |
Cell cell = 0; | |
while(cell < MAX_SIZE){ | |
if(game[cell] == 0 ){ | |
return TRUE; | |
} | |
cell++; | |
} | |
return FALSE; | |
} | |
/* | |
* gets the cell which is empty | |
*/ | |
int nextEmptyCell(SudokuGrid game){ | |
Cell cell = 0; | |
while(game[cell] != 0 ){ | |
cell++; | |
} | |
return cell; | |
} | |
/* | |
* checks whether the value is legal to put in | |
* the | |
*/ | |
int isLegal(SudokuGrid game , Cell cell, Value value){ | |
game[cell] = value; | |
int leagal = FALSE; | |
if(!isInRow(game , cell) && | |
!isInColumn(game , cell) && | |
!isInSquare(game , cell)){ | |
leagal=TRUE; | |
} | |
game[cell] = 0; | |
return leagal; | |
} | |
/* | |
* checks whether value is unique in the column | |
* if there is a cell with same value then return | |
* False. | |
*/ | |
int isInColumn( SudokuGrid game , Cell cell){ | |
int temp = (cell % LENGTH ) ; | |
while( temp < MAX_SIZE ){ | |
if( temp != cell && game[temp] == game[cell] ){ | |
return TRUE; | |
} | |
temp += LENGTH ; | |
} | |
return FALSE; | |
} | |
/* | |
* checks whether value is unique in the row | |
* if there is a cell with same value then | |
* return True. | |
*/ | |
int isInRow(SudokuGrid game ,Cell cell){ | |
int row = cell / LENGTH; | |
int col = 0 ; | |
Cell checkCell = row * LENGTH ; | |
while( col < LENGTH){ | |
if( checkCell != cell && game[checkCell] == game[cell] ){ | |
return TRUE ; | |
} | |
checkCell++; | |
col++; | |
} | |
return FALSE; | |
} | |
/* | |
* checks whether value is unique in the square | |
* if there is a cell with same value then returns | |
* True. | |
*/ | |
int isInSquare(SudokuGrid game , Cell cell){ | |
int sqRow = cell / ( LENGTH * SQ_SIZE ); | |
int sqCol = (cell % LENGTH) / SQ_SIZE ; | |
int checkCell = 0 ; | |
for(checkCell= 0 ; checkCell< MAX_SIZE ;checkCell++){ | |
if((checkCell / ( LENGTH * SQ_SIZE ) == sqRow) | |
&& (( (checkCell % LENGTH) / SQ_SIZE )== sqCol)){ | |
if( checkCell != cell && game[checkCell] == game[cell]){ | |
return TRUE; | |
} | |
} | |
} | |
return FALSE; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment