[LeetCode]Sudoku Solver-白红宇

[LeetCode]Sudoku Solver

阅读量：4150 次

发布时间：2019-05-25

本文共 3673 字，大约阅读时间需要 12 分钟。

class Solution {//brute-force//modified from http://discuss.leetcode.com/questions/216/sudoku-solver @Lu-An Gongpublic:	// 返回第一个空白的位置，如果没找到就返回 (-1, -1)	pair
   
     findFirstEmpty(const vector< vector
    
      >& board) 	{		for (int i = 0; i < 9; ++i)			for (int j = 0; j < 9; ++j)				if (board[i][j] == '.') return make_pair(i, j);		return make_pair(-1, -1);	}	// 检查连续的 9 个格子是否有效	bool isValid(const vector< vector
     
       >& board, int topX, int topY, int botX, int botY) 	{		vector
      
        occur(9, false);		for (int row = topX; row <= botX; row++)		{			for (int col = topY; col <= botY; col++)			{				if ( isdigit(board[row][col]) )				{					if (occur[board[row][col]-'1']) return false;					else occur[board[row][col]-'1'] = true;				}			}		}		return true;	}	// 检查往某个位置填入一个数之后整个 board 是否有效（只需要考虑当前行、	// 当前列和所属的田字格）	bool isValidBoard(const vector< vector
       
         >& board, pair
        
          pos) { // 检查当前行是否有效 if (!isValid(board, pos.first, 0, pos.first, 8)) return false; // 检查当前列是否有效 if (!isValid(board, 0, pos.second, 8, pos.second)) return false; // 检查所在的田字格是否有效 int blockRow, blockCol; for (blockRow = 0; blockRow < 3; ++blockRow) { bool flag = false; for (blockCol = 0; blockCol < 3; ++blockCol) { if (blockRow*3 <= pos.first && pos.first <= blockRow*3+2 && blockCol*3 <= pos.second && pos.second <= blockCol*3+2) { flag = true; break; } } if(flag) break; } if (!isValid(board, blockRow*3, blockCol*3, blockRow*3+2, blockCol*3+2)) return false; // 如果以上都有效，则返回 true return true; } // 检查从当前局面开始是否能够得到最终合法有效的解 bool solveSudoku(vector
         
          
            >& board) { // 如果没有找到空白的格子，说明已经填满了，成功返回 pair
           
             pos = findFirstEmpty(board); if (pos.first == -1 && pos.second == -1) return true; // 否则依次尝试往当前格子中填入数字 1-9，并判断能否得到可行的解 for (int i = 1; i <= 9; ++i) { board[pos.first][pos.second] = i + '0'; if (isValidBoard(board, pos) && solveSudoku(board)) return true; // 恢复原样 board[pos.first][pos.second] = '.'; } return false; }};

second time

class Solution {public:    bool checkRectangle(vector
   
    
      >& board, int x1, int y1, int x2, int y2)    {        vector
     
       digitCnt(10, 0);        for(int i = x1; i <= x2; i++)        {            for(int j = y1; j <= y2; ++j)            {                if(board[i][j] != '.')                {                    if(++digitCnt[board[i][j]-'0'] > 1) return false;                 }            }        }        return true;    }    bool isValidSudoku(vector
      
       
         > &board, int curX, int curY) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        //row check        if(!checkRectangle(board, curX, 0, curX, board.size()-1)) return false;        //column check        if(!checkRectangle(board, 0, curY, board.size()-1, curY)) return false;        //block check        for(int i = 0; i < board.size(); i+=3)        {            for(int j = 0; j < board.size(); j+=3)            {                if(i <= curX && curX <= i+2 && j <= curY && curY <= j+2                  && !checkRectangle(board, i, j, i+2, j+2)) return false;            }        }                return true;    }    bool solveSudokuUtil(vector
        
         
           > &board, int curIdx) { if(curIdx == 81) return true; int curX = curIdx/9; int curY = curIdx-curX*9; if(board[curX][curY] != '.') return solveSudokuUtil(board, curIdx+1); else { for(int i = 1; i <= 9; ++i) { board[curX][curY] = i+'0'; if(isValidSudoku(board, curX, curY) && solveSudokuUtil(board, curIdx+1)) return true; board[curX][curY] = '.'; } } return false; } void solveSudoku(vector
          
           
             > &board) { // Start typing your C/C++ solution below // DO NOT write int main() function solveSudokuUtil(board, 0); }};