LeetCode Valid Sudoku数独有效性验证

Valid Sudoku

Determine if a Sudoku is valid, according to:Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character'.'.

A partially filled sudoku which is valid.

验证已经填好的数独是否合符规则。

思路：

行，列和小九宫分别检查就可以了。

有填好数字的就检查，没填写的可以不管。

但是也可以一起同时检查，时间效率稍微快一点，不过需要额外空间。

下面是分别检查行列和小九宫的程序：

class Solution {
public:
	static const int SQUARENUM = 9;
	static const int LITTLESQU = 3;

	bool isValidSudoku(vector<vector<char> > &board) 
	{
		vector<char> vChar(SQUARENUM);
		for (int i = 0; i < SQUARENUM; i++)
			if (!rowValid(board[i])) return false;
		return colValid(board) && squValid(board);
	}

	bool rowValid(vector<char> &vChar)
	{
		vector<bool> nine(SQUARENUM+1, 0);
		for (int i = 0; i < SQUARENUM; i++)
		{
			if (vChar[i] != '.')
			{
				int t = vChar[i] - '0';
				if (nine[t])
					return false;
				else
					nine[t] = 1;
			}
		}
		return true;
	}

	bool colValid(vector<vector<char> > &board)
	{
		vector<bool> nine(SQUARENUM+1,0);
		for (int i = 0; i < SQUARENUM; i++)
		{
			for (int j = 0; j < SQUARENUM; j++)
			{
				if (board[j][i]!= '.')
				{
					int t = board[j][i] - '0';
					if (nine[t])
						return false;
					else
						nine[t] = 1;
				}
			}
			nine.clear();
			nine.resize(SQUARENUM+1, 0);
		}
		return true;
	}

	bool squValid(vector<vector<char> > &board)
	{
		vector<bool> nine(SQUARENUM+1, 0);
		for (int i = 0; i < SQUARENUM; i++)
		{
			for (int j = 0; j < SQUARENUM; j++)
			{
				int row = j/LITTLESQU + i/LITTLESQU*LITTLESQU, 
				col = j%LITTLESQU + i%LITTLESQU*LITTLESQU;
				if (board[row][col]!= '.')
				{
					int t = board[row][col] - '0';
					if (nine[t])
						return false;
					else
						nine[t] = 1;
				}
			}
			nine.clear();
			nine.resize(SQUARENUM+1, 0);
		}
		return true;
	}
};

下面是leetcode上的，以空间的代价换取代码更加简洁，很好的思路：

http://discuss.leetcode.com/questions/215/valid-sudoku

class Solution {
public:
	bool isValidSudoku(vector<vector<char> > &board) 
	{
		vector<vector<bool> > rows(9, vector<bool>(9, false));
		vector<vector<bool> > cols(9, vector<bool>(9, false));
		vector<vector<bool> > blocks(9, vector<bool>(9, false));

		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				if (board[i][j] == '.') continue;
				int c = board[i][j] - '1';
				if (rows[i][c] || cols[j][c] || blocks[i - i % 3 + j / 3][c])
					return false;
				rows[i][c] = cols[j][c] = blocks[i - i % 3 + j / 3][c] = true;
			}
		}
		return true;
	}
};

省空间的简洁代码：

//2014-1-26
	bool isValidSudoku(vector<vector<char> > &board) 
	{
		vector<bool> row_table(9);
		vector<bool> col_table(9);
		vector<bool> squ_table(9);
		for (int i = 0; i < 9; i++)
		{
			row_table.clear(); row_table.resize(9);
			col_table.clear(); col_table.resize(9);
			squ_table.clear(); squ_table.resize(9);
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] != '.') 
				{
					int r = board[i][j] - '1';
					if (!row_table[r]) row_table[r] = true;
					else return false;
				}
				if (board[j][i] != '.')
				{
					int c = board[j][i] - '1';
					if (!col_table[c]) col_table[c] = true;
					else return false;
				}
				int r = i/3*3+j/3, c = i%3*3+j%3;
				if (board[r][c] != '.')
				{
					int sq = board[r][c] - '1';
					if (!squ_table[sq]) squ_table[sq] = true;
					else return false;
				}
			}
		}
		return true;
	}