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...

Figure: A sudoku puzzle…

...and its solution numbers marked in red

Figure: …and its solution numbers marked in red

分析

无。

代码

  1. // Sudoku Solver
  2. // 时间复杂度O(9^4)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     void solveSudoku(vector<vector<char> > &board) {
  6.         _solveSudoku(board);
  7.     }
  8. private:
  9.     bool _solveSudoku(vector<vector<char> > &board) {
  10.         for (int i = 0; i < 9; ++i)
  11.             for (int j = 0; j < 9; ++j) {
  12.                 if (board[i][j] == '.') {
  13.                     for (int k = 0; k < 9; ++k) {
  14.                         board[i][j] = '1' + k;
  15.                         if (isValid(board, i, j) && _solveSudoku(board))
  16.                             return true;
  17.                         board[i][j] = '.';
  18.                     }
  19.                     return false;
  20.                 }
  21.             }
  22.         return true;
  23.     }
  24.     // 检查 (x, y) 是否合法
  25.     bool isValid(const vector<vector<char> > &board, int x, int y) {
  26.         int i, j;
  27.         for (i = 0; i < 9; i++) // 检查 y 列
  28.             if (i != x && board[i][y] == board[x][y])
  29.                 return false;
  30.         for (j = 0; j < 9; j++) // 检查 x 行
  31.             if (j != y && board[x][j] == board[x][y])
  32.                 return false;
  33.         for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
  34.             for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
  35.                 if ((i != x || j != y) && board[i][j] == board[x][y])
  36.                     return false;
  37.         return true;
  38.     }
  39. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dfs/sudoku-solver.html