2144.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2144 on 2006-07-23 at 15:44:22 */ 
#include <cstdio>
#include <cstring>

const int LEN = 9;
const int f[3] = {0, 3, 6};

class Sudoku {
private:
	bool row[LEN+1][LEN+1];
	bool col[LEN+1][LEN+1];
	bool squ[LEN+1][LEN+1];
	bool check(int n, int m) {
		int i;
		int p = table[n][m];
		int X = 0, Y = 0;
		for(i = 2; i >= 0; i--) {
			if(n >= f[i] && X == 0) {
				X = f[i] / 3;
			}
			if(m >= f[i] && Y == 0) {
				Y = f[i] / 3;
			}
		}
		if(row[n][p] || col[m][p] || squ[X*3+Y][p]) {
			return false;
		} else {
			return true;
		}
	}
public:
	int table[LEN][LEN];
	void init() {
		memset(row, false, sizeof(row));
		memset(col, false, sizeof(col));
		memset(squ, false, sizeof(squ));
	}
	void change(int n, int m, bool e) {
		int p = table[n][m];
		if(p != 0) {
			int X = 0, Y = 0, i;
			for(i = 2; i >= 0; i--) {
				if(n >= f[i] && X == 0) {
					X = f[i] / 3;
				}
				if(m >= f[i] && Y == 0) {
					Y = f[i] / 3;
				}
			}
			row[n][p] = col[m][p] = squ[X*3+Y][p] = e;
		}
	}
	bool slove(int n, int m) {
		if(m == 9) {
			return slove(n+1, 0);
		} else if(n == 9) {
			return true;
		} else if(table[n][m] != 0) {
			return slove(n, m+1);
		} else {
			int i;
			for(i = 1 ; i <= LEN; i++) {
				table[n][m] = i;
				if(check(n, m)) {
					change(n, m, true);
					if(slove(n, m+1)) {
						return true;
					} else {
						change(n, m, false);
					}
				}
			}
			table[n][m] = 0;
			return false;
		}
	}
};

int main()
{
	Sudoku sudoku;
	int n;
	int i, j, k;

	scanf("%d", &n);
	for(i = 0; i < n; i++) {
		sudoku.init();
		for(j = 0; j < LEN; j++) {
			for(k = 0; k < LEN; k++) {
				scanf("%1d", &sudoku.table[j][k]);
				sudoku.change(j, k, true);
			}
		}
		sudoku.slove(0, 0);
		for(j = 0; j < LEN; j++) {
			for(k = 0; k < LEN; k++) {
				printf("%d", sudoku.table[j][k]);
			}
			putchar('\n');
		}
	}
}