中级编程通关练习题 #3 – Sudoku 数独九宫格游戏

数独九宫格（Sudoku）是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。下图是一个数独的范例，图片来自Wikipedia。

实现一个函数来自动解决Sudoku的问题。函数的参数是一个9×9的二维数组，数字零代表未知数。

输入样例：

puzzle = [[5,3,0,0,7,0,0,0,0],
          [6,0,0,1,9,5,0,0,0],
          [0,9,8,0,0,0,0,6,0],
          [8,0,0,0,6,0,0,0,3],
          [4,0,0,8,0,3,0,0,1],
          [7,0,0,0,2,0,0,0,6],
          [0,6,0,0,0,0,2,8,0],
          [0,0,0,4,1,9,0,0,5],
          [0,0,0,0,8,0,0,7,9]]

输出样例：

 [[5,3,4,6,7,8,9,1,2],
  [6,7,2,1,9,5,3,4,8],
  [1,9,8,3,4,2,5,6,7],
  [8,5,9,7,6,1,4,2,3],
  [4,2,6,8,5,3,7,9,1],
  [7,1,3,9,2,4,8,5,6],
  [9,6,1,5,3,7,2,8,4],
  [2,8,7,4,1,9,6,3,5],
  [3,4,5,2,8,6,1,7,9]]

算法思路：

• 方法一：采用递归算法中的backtrack方法，从九宫格中寻找数字选择最少的一个位置开始填数字，每填一个数字后重复寻找下一个选择最少的位置，如果发现没有数字可选的位置则说明需要回退到上一个有多个选择的位置重新开始。如此反复进行一直到整个九宫格都填满为止。
• 方法二：采用while循环加for循环，用数据结构栈来记录每次找到的位置和相关数字选择，如果发现有找不到可填数字的位置，和方法一一样需要回退，从栈顶弹出上一个位置的信息重新进行填写。