数独求解

//数独求解：递归+回溯 #include <stdio.h> int map[9][9]; #define false 0 #define true 1 void display() //打印输出 { int i, j; for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { printf("%d ", map[i][j]); } printf("\n"); } } int check(int c) //检查 { int x, y, i, j, dx, dy; x = c / 9; y = c % 9; for (i = 0; i < 9; i++) { if (map[i][y] == map[x][y] && x != i) { return false; } } for (j = 0; j < 9; j++) { if (map[x][j] == map[x][y] && y != j) { return false; } } dx = x / 3 * 3; dy = y / 3 * 3; for (i = dx; i < dx + 3; i++) { for (j = dy; j < dy + 3; j++) { if (map[i][j] == map[x][y] && i != x && j != y) { return false; } } } return true; } void backtrack(int n) //递归+回溯 { int x, y; int i; if (n == 81) { display(); printf("\n"); return ; } x = n / 9; y = n % 9; if (map[x][y] == 0) //如果这个数等于0，就要试探 { for (i = 1; i <= 9; i++) { map[x][y] = i; //试探 if (check(n)) { backtrack(n + 1); //递归 } map[x][y] = 0; //回溯 } return; } else { backtrack(n + 1); } } int main() { int i, j; for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { scanf("%d", &map[i][j]); } } backtrack(0); return 0; }