LeetCode|37.数独求解 LeetCode|C++

Sudoku Solver 问题描述： Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

文章图片

A sudoku puzzle…

文章图片

…and its solution numbers marked in red.
知识补充：学会灵活使用结构体，结构体也可以作为元素放入栈和队列中。这样的话就有多种存储数据的方法了
char型相互转化为int型

char c = '1'; int i; i = (int)c; //强制转换 i = c-'0'; //差值即为所要转换数字 c = (char)i; //强制转换 c = char(48+i); //通过差值转换

参考答案：

class Solution { bool check(vector> &board, int i, int j, char val) { int row = i - i%3, column = j - j%3; for(int x=0; x<9; x++) if(board[x][j] == val) return false; for(int y=0; y<9; y++) if(board[i][y] == val) return false; for(int x=0; x<3; x++) for(int y=0; y<3; y++) if(board[row+x][column+y] == val) return false; return true; } bool solveSudoku(vector> &board, int i, int j) { if(i==9) return true; if(j==9) return solveSudoku(board, i+1, 0); if(board[i][j] != '.') return solveSudoku(board, i, j+1); for(char c='1'; c<='9'; c++) { if(check(board, i, j, c)) { board[i][j] = c; if(solveSudoku(board, i, j+1)) return true; board[i][j] = '.'; } }return false; } public: void solveSudoku(vector>& board) { solveSudoku(board, 0, 0); } };

性能： 【LeetCode|37.数独求解】

文章图片

参考答案：

class ValidMoves { private: int num_valid; int blocked_count[9]; public: ValidMoves() : num_valid(9), blocked_count {0, 0, 0, 0, 0, 0, 0, 0, 0} {}inline int valid() const { return num_valid; }inline void block(int move) { mod(move, 1); }inline void unblock(int move) { mod(move, -1); }void mod(int move, int d) { if(blocked_count[move] == 0) { num_valid--; } blocked_count[move] += d; if(blocked_count[move] == 0) { num_valid++; } }inline bool isValid(int move) const { return blocked_count[move] == 0; } }; class Solution { public: void solveSudoku(vector>& board) { vector> validMoves (9, vector(9)); for(int i1=0; i1<9; i1++) { for(int i2=0; i2<9; i2++) { if(board[i1][i2] != '.') { makeMove(board, validMoves, i1, i2, board[i1][i2] - '1'); } } }_solveSudoku(board, validMoves); }private: void makeMove(vector>& board, vector>& validMoves, int i1, int i2, int move) { board[i1][i2] = (char)(move + '1'); modRow(board, validMoves, i1, move, 1); modCol(board, validMoves, i2, move, 1); modBlock(board, validMoves, i1/3, i2/3, move, 1); }void unMakeMove(vector>& board, vector>& validMoves, int i1, int i2, int move) { modBlock(board, validMoves, i1/3, i2/3, move, -1); modCol(board, validMoves, i2, move, -1); modRow(board, validMoves, i1, move, -1); board[i1][i2] = '.'; }inline void modRow(const vector>& board, vector>& validMoves, int i1, int move, int d) { for(int i2=0; i2<9; i2++) { if(board[i1][i2] != '.') { continue; } validMoves[i1][i2].mod(move, d); } }inline void modCol(const vector>& board, vector>& validMoves, int i2, int move, int d) { for(int i1=0; i1<9; i1++) { if(board[i1][i2] != '.') { continue; } validMoves[i1][i2].mod(move, d); } }inline void modBlock(const vector>& board, vector>& validMoves, int bi1, int bi2, int move, int d) { for(int i1=0; i1<3; i1++) { for(int i2=0; i2<3; i2++) { int i1_ = i1 + bi1*3, i2_ = i2 + bi2*3; if(board[i1_][i2_] != '.') { continue; } validMoves[i1_][i2_].mod(move, d); } } }bool _solveSudoku(vector>& board, vector>& validMoves) { int most_constrained_count = INT_MAX, most_constrained_i1, most_constrained_i2; for(int i1=0; i1<9; i1++) { for(int i2=0; i2<9; i2++) { if(board[i1][i2] == '.' && validMoves[i1][i2].valid() < most_constrained_count) { most_constrained_count = validMoves[i1][i2].valid(); most_constrained_i1 = i1; most_constrained_i2 = i2; } } }if(most_constrained_count == 0) { return false; } if(most_constrained_count == INT_MAX) { return true; }ValidMoves& vm = validMoves[most_constrained_i1][most_constrained_i2]; for(int move=0; move<9; move++) { if(!vm.isValid(move)) { continue; }makeMove(board, validMoves, most_constrained_i1, most_constrained_i2, move); if(_solveSudoku(board, validMoves)) { return true; } else { unMakeMove(board, validMoves, most_constrained_i1, most_constrained_i2, move); } }return false; } };