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. public class Solution {
  4.     public void solveSudoku(char[][] board) {
  5.         _solveSudoku(board);
  6.     }
  7.     private static boolean _solveSudoku(char[][] board) {
  8.         for (int i = 0; i < 9; ++i)
  9.             for (int j = 0; j < 9; ++j) {
  10.                 if (board[i][j] == '.') {
  11.                     for (int k = 0; k < 9; ++k) {
  12.                         board[i][j] = Character.forDigit(k+1, 10);
  13.                         if (isValid(board, i, j) && _solveSudoku(board))
  14.                             return true;
  15.                         board[i][j] = '.';
  16.                     }
  17.                     return false;
  18.                 }
  19.             }
  20.         return true;
  21.     }
  22.     // 检查 (x, y) 是否合法
  23.     private static boolean isValid(char[][] board, int x, int y) {
  24.         int i, j;
  25.         for (i = 0; i < 9; i++) // 检查 y 列
  26.             if (i != x && board[i][y] == board[x][y])
  27.                 return false;
  28.         for (j = 0; j < 9; j++) // 检查 x 行
  29.             if (j != y && board[x][j] == board[x][y])
  30.                 return false;
  31.         for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
  32.             for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
  33.                 if ((i != x || j != y) && board[i][j] == board[x][y])
  34.                     return false;
  35.         return true;
  36.     }
  37. }

相关题目

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