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.
353 lines
9.5 KiB
353 lines
9.5 KiB
#include <stdio.h>
|
|
|
|
void putboard(int board[][9])
|
|
{
|
|
printf("|-----------------------|\n");
|
|
for (int i = 0; i < 9; i++)
|
|
{
|
|
printf("|");
|
|
for (int j = 0; j < 9; j++)
|
|
{
|
|
printf("%2d", board[i][j]);
|
|
if (j == 2 || j == 5 || j == 8)
|
|
printf(" |");
|
|
}
|
|
printf("\n");
|
|
if (i == 2 || i == 5 || i == 8)
|
|
printf("|-----------------------|\n");
|
|
}
|
|
}
|
|
|
|
int main()
|
|
{
|
|
int board[9][9] = {{5,3,4,6,7,8,9,1,2},
|
|
{6,7,2,1,9,5,3,4,8},
|
|
{1,9,8,3,4,2,5,6,7},
|
|
{8,5,9,7,6,1,4,2,3},
|
|
{4,2,6,8,5,3,7,9,1},
|
|
{7,1,3,9,2,4,8,5,6},
|
|
{9,6,1,5,3,7,2,8,4},
|
|
{2,8,7,4,1,9,6,3,5},
|
|
{3,4,5,2,8,6,1,7,9}};
|
|
putboard(board);
|
|
return 0;
|
|
}
|
|
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
#define ROWS 9
|
|
#define COLS 9
|
|
|
|
void printMatrix(char matrix[ROWS][COLS]);
|
|
|
|
int main() {
|
|
srand(time(NULL)); // 设置随机数种子
|
|
char matrix[ROWS][COLS];
|
|
|
|
// 初始化矩阵为'.'
|
|
int i,j,k;
|
|
for (i = 0; i < ROWS; ++i) {
|
|
for ( j = 0; j < COLS; ++j) {
|
|
matrix[i][j] = '.';
|
|
}
|
|
}
|
|
|
|
// 填充矩阵
|
|
for ( i = 0; i < ROWS; ++i) {
|
|
int positions[3];
|
|
int numbers[3];
|
|
int posIndex = 0, numIndex = 0;
|
|
|
|
// 随机选择3个不同的位置
|
|
while (posIndex < 3) {
|
|
int randPos = rand() % COLS;
|
|
if (matrix[i][randPos] == '.' && posIndex < 3) {
|
|
positions[posIndex++] = randPos;
|
|
}
|
|
}
|
|
|
|
// 随机选择3个不同的数字
|
|
while (numIndex < 3) {
|
|
int randNum = rand() % 9 + 1;
|
|
if (numIndex < 3 && !(numbers[0] == randNum || numbers[1] == randNum || numbers[2] == randNum)) {
|
|
numbers[numIndex++] = randNum;
|
|
}
|
|
}
|
|
|
|
// 将数字放置在随机位置上
|
|
for ( k = 0; k < 3; ++k) {
|
|
matrix[i][positions[k]] = numbers[k] + '0';
|
|
}
|
|
}
|
|
|
|
printMatrix(matrix); // 打印矩阵
|
|
return 0;
|
|
}
|
|
|
|
void printMatrix(char matrix[ROWS][COLS]) {
|
|
printf("|-----------------------|\n");
|
|
int i,j;
|
|
for ( i = 0; i < ROWS; ++i) {
|
|
if (i % 3 == 0 && i != 0) {
|
|
printf("|-----------------------|\n");
|
|
}
|
|
for ( j = 0; j < COLS; ++j) {
|
|
if (j % 3 == 0 ) {
|
|
printf("| ");
|
|
}
|
|
if (matrix[i][j] == '.') {
|
|
printf(". ");
|
|
} else {
|
|
printf("%c ", matrix[i][j]);
|
|
}
|
|
if (j == 8) {
|
|
printf("|\n");
|
|
}
|
|
}
|
|
}
|
|
printf("|-----------------------|\n");
|
|
}
|
|
|
|
|
|
#include <stdio.h>
|
|
|
|
#define SIZE 9
|
|
|
|
void printBoard(int board[SIZE][SIZE]) {
|
|
printf("The original Sudoku matrix:\n");
|
|
for (int i = 0; i < SIZE; i++) {
|
|
for (int j = 0; j < SIZE; j++) {
|
|
printf("%d ", board[i][j]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
int isValidSudoku(int board[SIZE][SIZE]) {
|
|
int row[SIZE][SIZE] = {0};
|
|
int col[SIZE][SIZE] = {0};
|
|
int block[SIZE][SIZE] = {0};
|
|
|
|
for (int i = 0; i < SIZE; i++) {
|
|
for (int j = 0; j < SIZE; j++) {
|
|
int num = board[i][j];
|
|
if (num < 1 || num > 9) continue; // Skip zeros
|
|
|
|
int blockIndex = (i / 3) * 3 + (j / 3);
|
|
|
|
// Check row
|
|
if (row[i][num - 1]) {
|
|
printf("False: Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the row %d has been used!\n", num, i + 1);
|
|
return 0;
|
|
}
|
|
row[i][num - 1] = 1;
|
|
|
|
// Check column
|
|
if (col[j][num - 1]) {
|
|
printf("False: Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the col %d has been used!\n", num, j + 1);
|
|
return 0;
|
|
}
|
|
col[j][num - 1] = 1;
|
|
|
|
// Check block
|
|
if (block[blockIndex][num - 1]) {
|
|
printf("False: Invalid initial Sudoku matrix!\n");
|
|
printf("The number %d in the block %d has been used!\n", num, blockIndex + 1);
|
|
return 0;
|
|
}
|
|
block[blockIndex][num - 1] = 1;
|
|
}
|
|
}
|
|
printf("True: Valid initial Sudoku matrix!\n");
|
|
return 1;
|
|
}
|
|
|
|
int main() {
|
|
int board0[SIZE][SIZE] = {
|
|
{5, 3, 0, 0, 7, 0, 0, 0, 0},
|
|
{6, 0, 0, 1, 9, 5, 0, 0, 0},
|
|
{0, 9, 8, 0, 0, 0, 0, 6, 0},
|
|
{8, 0, 0, 0, 6, 0, 0, 0, 3},
|
|
{4, 0, 0, 8, 0, 3, 0, 0, 1},
|
|
{7, 0, 0, 0, 2, 0, 0, 0, 6},
|
|
{0, 6, 0, 0, 0, 0, 2, 8, 0},
|
|
{0, 0, 0, 4, 1, 9, 0, 0, 5},
|
|
{0, 0, 0, 0, 8, 0, 0, 7, 9}
|
|
};
|
|
|
|
printBoard(board0);
|
|
isValidSudoku(board0);
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
#define ROWS 9
|
|
#define COLS 9
|
|
|
|
int checkValid(char matrix[ROWS][COLS]);
|
|
void printMatrix(char matrix[ROWS][COLS]);
|
|
int isSafe(char matrix[ROWS][COLS], int row, int col, char num);
|
|
int solveSudoku(char matrix[ROWS][COLS]);
|
|
void generateSudoku(char matrix[ROWS][COLS]);
|
|
|
|
int main() {
|
|
srand(time(NULL)); // 设置随机数种子
|
|
char matrix[ROWS][COLS] = {0};
|
|
|
|
// 循环直到生成一个有解的数独矩阵
|
|
do {
|
|
generateSudoku(matrix);
|
|
} while (!checkValid(matrix));
|
|
|
|
printf("The original Sudoku matrix: \n");
|
|
printMatrix(matrix);
|
|
|
|
if (solveSudoku(matrix)) {
|
|
printf("True: Valid initial Sudoku matrix!\n");
|
|
printf("The solution of Sudoku matrix:\n");
|
|
printMatrix(matrix);
|
|
} else {
|
|
printf("False: Invalid initial Sudoku matrix!\n");
|
|
printf("No solution!\n");
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void generateSudoku(char matrix[ROWS][COLS]) {
|
|
// 初始化矩阵为'.'
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
for (int j = 0; j < COLS; ++j) {
|
|
matrix[i][j] = '.';
|
|
}
|
|
}
|
|
|
|
// 填充矩阵
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
for (int j = 0; j < COLS; ++j) {
|
|
if (rand() % 2) { // 随机决定是否填充数字
|
|
int num = rand() % 9 + 1;
|
|
matrix[i][j] = num + '0';
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int checkValid(char matrix[ROWS][COLS]) {
|
|
// 检查每行是否有重复的数字
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
int rowUsed[10] = {0};
|
|
for (int j = 0; j < COLS; ++j) {
|
|
if (matrix[i][j] != '.') {
|
|
int num = matrix[i][j] - '0';
|
|
if (rowUsed[num]) {
|
|
return 0; // 行中有重复数字
|
|
}
|
|
rowUsed[num]++;
|
|
}
|
|
}
|
|
}
|
|
|
|
// 检查每列是否有重复的数字
|
|
for (int j = 0; j < COLS; ++j) {
|
|
int colUsed[10] = {0};
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
if (matrix[i][j] != '.') {
|
|
int num = matrix[i][j] - '0';
|
|
if (colUsed[num]) {
|
|
return 0; // 列中有重复数字
|
|
}
|
|
colUsed[num]++;
|
|
}
|
|
}
|
|
}
|
|
|
|
// 检查每个3x3子矩阵是否有重复的数字
|
|
for (int i = 0; i < ROWS; i += 3) {
|
|
for (int j = 0; j < COLS; j += 3) {
|
|
int subUsed[10] = {0};
|
|
for (int x = i; x < i + 3; ++x) {
|
|
for (int y = j; y < j + 3; ++y) {
|
|
if (matrix[x][y] != '.') {
|
|
int num = matrix[x][y] - '0';
|
|
if (subUsed[num]) {
|
|
return 0; // 子矩阵中有重复数字
|
|
}
|
|
subUsed[num]++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return 1; // 数独矩阵有效
|
|
}
|
|
|
|
int isSafe(char matrix[ROWS][COLS], int row, int col, char num) {
|
|
// 检查行
|
|
for (int i = 0; i < COLS; ++i) {
|
|
if (matrix[row][i] == num) return 0;
|
|
}
|
|
|
|
// 检查列
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
if (matrix[i][col] == num) return 0;
|
|
}
|
|
|
|
// 检查3x3子矩阵
|
|
int startRow = row - row % 3, startCol = col - col % 3;
|
|
for (int i = 0; i < 3; ++i) {
|
|
for (int j = 0; j < 3; ++j) {
|
|
if (matrix[i + startRow][j + startCol] == num) return 0;
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
int solveSudoku(char matrix[ROWS][COLS]) {
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
for (int j = 0; j < COLS; ++j) {
|
|
if (matrix[i][j] == '.') {
|
|
for (int num = 1; num <= 9; ++num) {
|
|
char numChar = num + '0';
|
|
if (isSafe(matrix, i, j, numChar)) {
|
|
matrix[i][j] = numChar;
|
|
if (solveSudoku(matrix)) return 1;
|
|
matrix[i][j] = '.';
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
void printMatrix(char matrix[ROWS][COLS]) {
|
|
for (int i = 0; i < ROWS; ++i) {
|
|
if (i % 3 == 0 && i != 0) {
|
|
printf("--------------|\n");
|
|
}
|
|
for (int j = 0; j < COLS; ++j) {
|
|
if (j % 3 == 0) {
|
|
printf("|");
|
|
}
|
|
printf("%c ", matrix[i][j] == '.' ? '.' : matrix[i][j]);
|
|
if (j == 8) {
|
|
printf("|\n");
|
|
}
|
|
}
|
|
}
|
|
printf("--------------|\n");
|
|
} |