Skip to content

Instantly share code, notes, and snippets.

@asela38
Created May 15, 2018 10:10
Show Gist options
  • Save asela38/79d346a02a336eb79632a889dedb9757 to your computer and use it in GitHub Desktop.
Save asela38/79d346a02a336eb79632a889dedb9757 to your computer and use it in GitHub Desktop.
Code written sometime back in C to solve a sudoku
/*
* 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