Advertisement
Guest User

Untitled

a guest
Dec 7th, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. class Solution {
  2. public:
  3. Solution() {
  4. mBoardLen = 9;
  5. }
  6.  
  7. void solveSudoku(vector<vector<char>>& board) {
  8. solveByDFS(0, 0, board);
  9. }
  10.  
  11. bool solveByDFS(const int &row, const int &col, vector<vector<char>>& board) {
  12. //> ending criteria
  13. if(row == mBoardLen) {
  14. return true;
  15. }
  16. else if(col == mBoardLen) {
  17. return solveByDFS(row+1, 0, board);
  18. }
  19.  
  20. //> solve sudoku
  21. if(board[row][col] == '.') {
  22. for(int i = 0; i < 9; i++) {
  23. char ch = static_cast<char>('1' + i);
  24. board[row][col] = ch;
  25.  
  26. if(isValid(row, col, board)) {
  27. if(solveByDFS(row, col+1, board)) {
  28. return true;
  29. }
  30. }
  31.  
  32. //> current number is either non-valid
  33. //> or non-solvable
  34. board[row][col] = '.';
  35. }
  36. }
  37. else {
  38. return solveByDFS(row, col+1, board);
  39. }
  40.  
  41. return false;
  42. }
  43.  
  44. bool isValid(const int &row, const int &col, vector<vector<char>>& board) {
  45. //> check row
  46. for(int c = 0; c < mBoardLen; c++) {
  47. if(c != col && board[row][c] == board[row][col]) {
  48. return false;
  49. }
  50. }
  51.  
  52. //> check col
  53. for(int r = 0; r < mBoardLen; r++) {
  54. if(r != row && board[r][col] == board[row][col]) {
  55. return false;
  56. }
  57. }
  58.  
  59. //> check cube
  60. int rStart = 3 * (row / 3);
  61. int cStart = 3 * (col / 3);
  62. for(int r = rStart; r < rStart + 3; r++) {
  63. for(int c = cStart; c < cStart + 3; c++) {
  64. if(r != row && c != col && board[r][c] == board[row][col]) {
  65. return false;
  66. }
  67. }
  68. }
  69.  
  70. return true;
  71. }
  72.  
  73. private:
  74. int mBoardLen;
  75. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement