博客

37 Sudoku Solver

// ----------------Seeing Discuss-----------
/*
	copying codes
	url
	https://discuss.leetcode.com/topic/5002/a-simple-dfs-solution

	Analysis:
		
*/
class Solution {
public:
	bool isValidSudoku(vector<vector<char> > &board) {
		return true;
	}
	void solveSudoku(vector<vector<char> > &board) {
		util(board, 0);
	}
	bool util(vector<vector<char>>& board, int pos)
	{
		if (pos >= 81)
			return true;
		int i = pos / 9;
		int j = pos % 9;
		if (board[i][j] != '.')
			return util(board, pos + 1);
		else
		{
			for (char c = '1'; c <= '9'; c++)
			{
				if (!isInRow(board, i,c) && !isInCol(board, j, c) && !isInRec(board, i, j, c))
				{
					board[i][j] = c;
					if (util(board, pos + 1))
						return true;
					else
						board[i][j] = '.';
				}
			}
			return false;
		}
	}

	bo