任意形状数独算法代码c语言
时间: 2023-12-06 07:00:43 浏览: 26
数独是一种古老的数学逻辑游戏,通过填入数字1-9,使得每行、每列和每个3x3的小九宫格内数字都不重复。下面是一个简单的C语言数独算法:
#include <stdio.h>
#define N 9
bool isSafe(int board[N][N], int row, int col, int num) {
for (int x = 0; x < N; x++) {
if (board[row][x] == num || board[x][col] == num) {
return false;
}
}
int startRow = row - row % 3;
int startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i + startRow][j + startCol] == num) {
return false;
}
}
}
return true;
}
bool solveSudoku(int board[N][N]) {
int row, col;
bool isEmpty = false;
for (row = 0; row < N; row++) {
for (col = 0; col < N; col++) {
if (board[row][col] == 0) {
isEmpty = true;
break;
}
}
if (isEmpty) {
break;
}
}
if (!isEmpty) {
return true;
}
for (int num = 1; num <= 9; num++) {
if (isSafe(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) {
return true;
}
board[row][col] = 0;
}
}
return false;
}
void printBoard(int board[N][N]) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
printf("%d ", board[row][col]);
}
printf("\n");
}
}
int main() {
int board[N][N] = {{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}};
if (solveSudoku(board)) {
printBoard(board);
} else {
printf("No solution exists");
}
return 0;
}