Created
December 8, 2018 12:20
-
-
Save ibrahimsn98/9c7981e61d7d325b1b86c575f8f49e18 to your computer and use it in GitHub Desktop.
C Sudoku Solver Backtracing
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
#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