Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@ibrahimsn98
Created December 8, 2018 12:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ibrahimsn98/9c7981e61d7d325b1b86c575f8f49e18 to your computer and use it in GitHub Desktop.
Save ibrahimsn98/9c7981e61d7d325b1b86c575f8f49e18 to your computer and use it in GitHub Desktop.
C Sudoku Solver Backtracing
#include <stdio.h>
int sudo[9][9];
int isExistsInRow(int row, int s) {
int i;
for(i=0; i<9; i++)
if(sudo[row][i] == s)
return 1;
return 0;
}
int isExistsInCol(int col, int s) {
int i;
for(i=0; i<9; i++)
if(sudo[i][col] == s)
return 1;
return 0;
}
int isExistsInSquare(int row, int col, int s) {
int i, j, x, y;
x = (row/3)*3;
y = (col/3)*3;
for(i=x; i<x+3; i++)
for(j=y; j<y+3; j++)
if(sudo[i][j] == s)
return 1;
return 0;
}
int isAny0(int *row, int *col) {
int i, j;
for(i=0; i<9; i++)
for(j=0; j<9; j++)
if(sudo[i][j] == 0) {
*row = i;
*col = j;
return 1;
}
return 0;
}
int solve() {
int row, col, i;
if(isAny0(&row, &col) == 0)
return 1;
for(i=1; i<=9; i++)
if(!isExistsInRow(row, i) && !isExistsInCol(col, i) && !isExistsInSquare(row, col, i)) {
sudo[row][col] = i;
if(solve())
return 1;
sudo[row][col] = 0;
}
return 0;
}
int main() {
int i, j;
for(i=0; i<9; i++)
for(j=0; j<9; j++)
scanf("%d", &sudo[i][j]);
if (solve())
for (i=0; i<9; i++) {
for (j = 0; j < 9; j++)
printf("%d ", sudo[i][j]);
printf("\n");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment