Skip to content

Instantly share code, notes, and snippets.

@m-zakeri

m-zakeri/sudoku.c

Created Jan 25, 2018
Embed
What would you like to do?
/*
*
*
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSOLUTIONS 5
//---------------------------------------------
int grid[9][9], solutions;
//---------------------------------------------
static void reset_grid()
{
int i, j;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
grid[i][j] = 0;
}
}
//-----------------------------------------------
static int CheckValueInGrid(int i,int j, int val)
{
int k, m;
//check in row
for (k=0; k<9; k++)
{
if (k!=j)
if (grid[i][k]==val)
return 0;
}
// check in column
for (m=0; m<9; m++)
{
if (m!=i)
if (grid[m][j]==val)
return 0;
}
//check in subgrid
for (k=(i/3)*3; k<(i/3)*3+3; k++)
for (m=(j/3)*3; m<(j/3)*3+3; m++)
{
if ((k!=i) || (m!=j))
if (grid[k][m]==val)
return 0;
}
return 1;
}
//--------------------------------------------------
//read soulotion from file
static int read_grid()
{
int i, j, ch;
reset_grid();
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
for (;;)
{
ch = getchar();
if (ch == EOF)
return -1;
if (ch == '.')
break;
if ('1' <= ch && ch <= '9')
{
if (CheckValueInGrid(i, j, 1+ch-'1'))
{
grid[i][j] = 1+ch-'1';
break;
}
else
{
return -1;
}
}
if (!isspace(ch) && ch != '|' && ch != '-' && ch != '+')
return -1;
}
for (;;)
{
int ch = getchar();
if (ch == EOF)
return 0;
if (!isspace(ch) && ch != '|' && ch != '-' && ch != '+')
return -1;
}
}
//---------------------------------------------------
//print grid[][] in standard output
static void print_grid()
{
int i, j;
for (i = 0; i < 9; i++)
{
if (i%3 == 0)
printf("+---+---+---+\n");
for (j = 0; j < 9; j++)
{
if (j%3 == 0)
printf("|");
printf("%d", grid[i][j]);
}
printf("|\n");
}
printf("+---+---+---+\n\n");
}
//-----------------------------------------------------
static int SearchSolution(int i, int j)
{
int value;
if (j==9)
{
j=0;
i++;
}
if (i==9)
{ //solution
print_grid();
solutions++;
fprintf(stderr," %d solution(s) found !\n", solutions);
return solutions >= MAXSOLUTIONS;
}
if (grid[i][j]!=0)
{
if (SearchSolution(i, j+1))
return 1;
}
else
{
for (value = 1; value < 10; value++) /* Try possible values. */
if (CheckValueInGrid(i, j, value))
{
grid[i][j]=value; //new test value
if (SearchSolution(i, j+1))
return 1;
}
grid[i][j]=0; //unrecord try
}
return 0;
}
//-------------------------------------------------
static int solution()
{
if (read_grid()==-1)
{
fprintf(stderr, "Invalid input matrix\n");
return 1;
}
solutions = 0;
printf("Starting Matrix\n");
print_grid();
printf("\n\nSolving...\n\n");
SearchSolution(0,0);
if (solutions == 0)
{
fprintf(stderr, "No solution found\n");
return 1;
}
return 0;
}
//------------------------------------------------------
int main(int argc, char **argv)
{
char *output = 0;
if (!freopen("SUDOKU.TXT" , "r", stdin))
{
fprintf(stderr,"input file SUDOKU.TXT does not exist.\n");
return 1;
}
if (output && !freopen(output, "w", stdout))
{
perror(output);
return 1;
}
return solution();
}
/* test input:
9 . . 7 . . . . 1
1 . 6 . 4 . . . .
. . . 9 6 . 7 . 4
2 . . . . . 5 9 .
. . 5 2 . 7 . . .
. 1 . . . 5 . 7 .
. 3 . . . . 1 . 6
. . . . 3 . . 8 7
. 2 8 . . . . . .
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.