leetcode: Valid Sudoku

leetcode Valid Sudoku Problem Description:

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.

leetcode Valid Sudoku Solution and Precautions:

The algorithm for this problem is simple and just involves simulation to test the validity of each row, column and square of the given input sudoku. That is, we could use brute force way to check each row and each column and each of the 9 sub 3*3 grids. Only when all of them are valid (by the rules of sudoku), this input is a valid one.

However, the point of asking this problem might not be to check whether you know how to solve it, but to see if you could write code as elegant as you can. I will first give a basic solution (I recommend to avoid premature optimization) and then optimize the code step by step. The number of code lines is deduced from 45 lines to 41 lines and finally reduced to 31 lines.

(1) Basic Solution, just simulate and separate the test of all the rows, columns, squares into 3 parts, the accepted code is as follows:

class Solution {
public:
	const int valid_size = 9;

	bool isValid(const vector &vecNumbers) {
		vector aryHash(valid_size, false);
		for (int i = 0; i < valid_size; ++i) { 			
                        if ('.' == vecNumbers[i]) continue; 			
                        if (vecNumbers[i] > '9' || vecNumbers[i] < '1') return false;

			if (aryHash[vecNumbers[i] - '1'])
				return false;
			else
				aryHash[vecNumbers[i] - '1'] = true;
		}
		return true;
	}

    bool isValidSudoku(vector &board) {
		int m = board.size();
		if (m != valid_size) return false;
		int n = board[0].size();
		for (int i = 0; i < n; ++i)
			if (board[i].size() != valid_size) return false;

		for (int i = 0; i < m; ++i)
			if (!isValid(board[i])) return false;
		vector vecToTest(valid_size, '.');
		for (int j = 0; j < n; ++j) {
			for (int i = 0; i < m; ++i)
				vecToTest[i] = board[i][j];
			if (!isValid(vecToTest)) return false;
		}

		for (int i = 0; i < m; i += 3)
			for (int j = 0; j < n; j += 3) {
				for (int k = 0; k < 3; ++k)
					for (int s = 0; s < 3; ++s) 	
					      vecToTest[s + k * 3] = board[i + k][j + s]; 
   			        if (!isValid(vecToTest)) return false; 			
                        } 	
                return true;     
          } 
}; 

(2) We do two optimizations in this step: a) the 4 embedded for loops above is a bit scary, we reduce the number of loops to 2; b) we use bit manipulation to replace the array version of hash table. The source code is as follows:

class Solution { 
  public:    
            const int valid_size = 9;     
            bool isValid(const vector &vecNumbers) {      
                      int hashTable = 0, hashTmp = 0;        
                      for (int i = 0; i < valid_size; ++i) {        
                           if ('.' == vecNumbers[i]) continue; 
                           if (vecNumbers[i] > '9' || vecNumbers[i] < '1') return false;
                           hashTmp = (hashTable ^ (1 << (vecNumbers[i] - '0')));
                           if (hashTmp < hashTable) return false;
                           hashTable = hashTmp;
                      }
                      return true;
             }

    bool isValidSudoku(vector<vector> &board) {
        int m = board.size();
        if (m != valid_size) return false;
        int n = board[0].size();
        for (int i = 0; i < n; ++i)
        if (board[i].size() != valid_size) return false;

        /*
                ... same as above
        */

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                vecToTest[j] = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3];
            }
            if (!isValid(vecToTest)) return false;
        }
        return true;
    }
};

(3) finally we compact the code into a single for loops to test row, col, square inside one body. Note this could not reduce the time complexity but just make the code more compact. The code is as follow:

class Solution {
public:
    const int valid_size = 9;
    bool isValidSudoku(vector<vector > &board) {
		int m = board.size();
		if (m != valid_size) return false;
		int n = board[0].size();
		for (int i = 0; i < n; ++i)
			if (board[i].size() != valid_size) return false;

		for (int i = 0; i < m; ++i) {
			int row = 0, rowTmp = 0; int a;
			int col = 0, colTmp = 0; int b;
			int square = 0, squareTmp = 0; int c;

			for (int j = 0; j < n; ++j) {   			
			    a = board[i][j] - '0'; // row 				
			    b = board[j][i] - '0'; // col 				
			    c = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3] - '0'; // square 
    	                    if (a > 0) rowTmp = row ^ (1 << a); 				
                            if (b > 0) colTmp = col ^ (1 << b); 				
                            if (c > 0) squareTmp = square ^ (1 << c);

			    if (rowTmp < row || colTmp < col || squareTmp < square)
			 	return false;
			    row = rowTmp, col = colTmp, square = squareTmp;
			}
		}
		return true;
    }
};

We finish our optimization here.

leetcode Valid Sudoku Remarks:

  1. Never assume anything like the input size, even when the Leetcode OJ does not include test cases with invalid size, in the code, this is a good point to show that you have this issue in your mind.

  2. The position calculation mapping from 2-D array to the correct positions within each row, column and square is a key point to be tested or for you to show when asked this problem;

  3.  Put all the test for rows, column, squares together into a single for loop might not increase the efficiency (since the number of total test remains to be the same) but could make the code more compact and might be another test point when asked this problem.

  4. The problem here is different from the one which asks you if there is a solution for a given partial Sudoku. The latter one might involve trying to find a real solution for the given Sudoku, see “leetcode: Sudoku Solver” for further discussion on this.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 27, 2013