You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
104 lines
2.9 KiB
104 lines
2.9 KiB
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
|
|
void generate_sudoku(int board[9][9]) {
|
|
srand(time(NULL));
|
|
int i,j;
|
|
for (i = 0; i < 9; i++) {
|
|
for ( j = 0; j < 9; j++) {
|
|
board[i][j] =rand()%10;
|
|
|
|
}
|
|
}
|
|
}
|
|
|
|
void print_sudoku(int board[9][9]) {
|
|
int i,j;
|
|
for ( i = 0; i < 9; i++) {
|
|
for (j = 0; j < 9; j++) {
|
|
printf("%d ", board[i][j]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
|
|
int test(int board[9][9]) {
|
|
int i,j,k,p,q;
|
|
for (i = 0; i < 9; i++) {
|
|
for (j = 0; j < 9; j++) {
|
|
if (board[i][j] != 0) {
|
|
for (k = 0; k < 9; k++) {
|
|
if (k != j && board[i][j] == board[i][k]) {
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the col %d has been used!\n", board[i][j], j + 1);
|
|
return 0;
|
|
break;
|
|
}
|
|
if (k != i && board[i][j] == board[k][j]) {
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the row %d has been used!\n", board[i][j], i + 1);
|
|
return 0;
|
|
break;
|
|
}
|
|
}
|
|
for (p = i / 3 * 3; p < i / 3 * 3 + 3; p++) {
|
|
for (q = j / 3 * 3; q < j / 3 * 3 + 3; q++) {
|
|
if ((p != i || q != j) && board[i][j] == board[p][q]) {
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the block %d has been used!\n", board[i][j], (p / 3) * 3 + q / 3 + 1);
|
|
return 0;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
printf("True:Valid initial Sudoku matrix!\n");
|
|
return 1;
|
|
}
|
|
|
|
|
|
int add(int board[9][9]) {
|
|
int row,col,num;
|
|
for (row = 0; row < 9; row++) {
|
|
for (col = 0; col < 9; col++) {
|
|
if (board[row][col] == 0) {
|
|
for (num = 1; num <= 9; num++) {
|
|
if (test(board)) {
|
|
board[row][col] = num;
|
|
if (add(board)) {
|
|
return 1;
|
|
}
|
|
else {
|
|
board[row][col] = 0;
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
|
|
int main() {
|
|
int board[9][9];
|
|
generate_sudoku(board);
|
|
printf("The original Sudoku matrix:\n");
|
|
print_sudoku(board);
|
|
test(board);
|
|
if (add(board)) {
|
|
printf("The solution of Sudoku matrix:\n");
|
|
print_sudoku(board);
|
|
} else {
|
|
printf("No solution\n");
|
|
}
|
|
return 0;
|
|
}
|
|
|