import java.util.Scanner; public class Main { static int arr[][]; static Scanner in = new Scanner(System.in); public static void main(String[] args) { arr = new int[9][9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { arr[i][j] = in.nextInt(); } } dfs(0); } private static void dfs(int index) { if (index == 81) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(arr[i][j] + " "); } System.out.println(); } return; } int row = index / 9; int col = index % 9; if (arr[row][col] == 0) { for (int i = 1; i <= 9; i++) { if (valid(i, row, col)) { arr[row][col] = i; dfs(index + 1); arr[row][col] = 0; } } } else dfs(index + 1); } private static boolean valid(int num, int raw, int col) { for (int i = 0; i < 9; i++) { if ( arr[raw][i] == num||arr[i][col] == num) { return false; } } int tmpx = raw / 3; int tmpy = col / 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (arr[tmpx * 3 + i][tmpy * 3 + j] == num) return false; } } return true; } }
#include #include using namespace std; const int N = 9; int ones[1 << N], map[1 << N]; //ones 表示 x 里面有几个1;//小抄 map表示 一个数最右边的1以及跟剩下的0组成后 为第几位 int row[N], col[N], cell[3][3]; char str[100]; inline int lowbit(int x) //lowbit 计算最低位!!! { return x & -x; } void init() ////全部赋值位111111111 表示1~9个数都可以选择 简化后面的与运算 { for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1; for (int i = 0; i < 3; i ++ ) for (int j = 0; j < 3; j ++ ) cell[i][j] = (1 << N) - 1; } // 求可选方案的交集 inline int get(int x, int y) ////进行与运算 表示真正可以选哪些数 { return row[x] & col[y] & cell[x / 3][y / 3]; } bool dfs(int cnt) { if (!cnt) return true; // 找出可选方案数最少的空格 int minv = 10; int x, y; for (int i = 0; i < N; i ++ ) for (int j = 0; j < N; j ++ ) if (str[i * 9 + j] == '.') { int t = ones[get(i, j)]; if (t < minv) { minv = t; x = i, y = j; } } for (int i = get(x, y); i; i -= lowbit(i)) { int t = map[lowbit(i)]; // 修改状态 row[x] -= 1 << t; col[y] -= 1 << t; cell[x / 3][y / 3] -= 1 << t; str[x * 9 + y] = '1' + t; if (dfs(cnt - 1)) return true; // 恢复现场 row[x] += 1 << t; col[y] += 1 << t; cell[x / 3][y / 3] += 1 << t; str[x * 9 + y] = '.'; } } int main() { for (int i = 0; i < N; i ++ ) map[1 << i] = i; for (int i = 0; i < 1 << N; i ++ ) { int s = 0; for (int j = i; j; j -= lowbit(j)) s ++ ; ones[i] = s; // i的二进制表示中有s个1 } while (cin >> str, str[0] != 'e') { init(); int cnt = 0; for (int i = 0, k = 0; i < N; i ++ ) for (int j = 0; j < N; j ++ , k ++ ) if (str[k] != '.') { int t = str[k] - '1'; row[i] -= 1 << t; col[j] -= 1 << t; cell[i / 3][j / 3] -= 1 << t; } else cnt ++ ; dfs(cnt); cout << str << endl; } return 0; }