Sudoku
题目
Sudoku puzzles go like this:
Problem
| . | . | 4 | 8 | . | . | . | 1 | 7 |
| 6 | 7 | . | 9 | . | . | . | . | . |
| 5 | . | 8 | . | 3 | . | . | . | 4 |
| 3 | . | . | 7 | 4 | . | 1 | . | . |
| . | 6 | 9 | . | . | . | 7 | 8 | . |
| . | . | 1 | . | 6 | 9 | . | . | 5 |
| 1 | . | . | . | 8 | . | 3 | . | 6 |
| . | . | . | . | . | 6 | . | 9 | 1 |
| 2 | 4 | . | . | . | 1 | 5 | . | . |
Solution
| 9 | 3 | 4 | 8 | 2 | 5 | 6 | 1 | 7 |
| 6 | 7 | 2 | 9 | 1 | 4 | 8 | 5 | 3 |
| 5 | 1 | 8 | 6 | 3 | 7 | 9 | 2 | 4 |
| 3 | 2 | 5 | 7 | 4 | 8 | 1 | 6 | 9 |
| 4 | 6 | 9 | 1 | 5 | 3 | 7 | 8 | 2 |
| 7 | 8 | 1 | 2 | 6 | 9 | 4 | 3 | 5 |
| 1 | 9 | 7 | 5 | 8 | 2 | 3 | 4 | 6 |
| 8 | 5 | 3 | 4 | 7 | 6 | 2 | 9 | 1 |
| 2 | 4 | 6 | 3 | 9 | 1 | 5 | 7 | 8 |
Every spot in the puzzle belongs to a (horizontal) row and a (vertical) column, as well as to one single 3x3 square (which we call "square" for short). At the beginning, some of the spots carry a single-digit number between 1 and 9. The problem is to fill the missing spots with digits in such a way that every number between 1 and 9 appears exactly once in each row, in each column, and in each square.
解题
首先，使用回溯法求出每个3x3方格的可行解（方格内的数字不重复）。然后，使用回溯法组合九个3x3方格的可行解，求出在全局有效的组合（任意行或列上的数字不重复）。
代码实现
def resolveSquare(square):
if isCompleted(square):
return [square]
nums = availableNums(square)
return reduce(concat,
[resolveSquare(fill(square, num)) for num in nums],
[])
def isCompleted(square):
return reduce(and_,
[(lambda x:x is not None)(e)
for e in reduce(concat, square, [])],
True)
def availableNums(square):
all = [num for num in range(1, 10)]
used = [num for num in reduce(concat, square, []) if num is not None]
return [num for num in all if num not in used]
def fill(square, num):
newSquare = copy.deepcopy(square)
for v in range(0, len(newSquare)):
for h in range(0, len(newSquare[v])):
if newSquare[v][h] is None:
newSquare[v][h] = num
return newSquare
return newSquare
使用回溯法求出单个方格内所有的填字方式。
from functools import reduce
from operator import concat, and_
import copy
import numpy as np
def sudoku(puzzle):
squares = puzzleToSquares(puzzle)
solutions = resolveSudoku(squares, [])
return [squaresToPuzzle(solution) for solution in solutions]
def puzzleToSquares(puzzle):
squares = []
d = 3
array = np.array(puzzle)
for v in range(0, d):
for h in range(0, d):
squares.append((array[v*d:v*d+d,h*d:h*d+d]).tolist())
return squares
def resolveSudoku(squares, solution):
if len(squares) == 0:
return [[]]
square = squares[0]
remainSquares = squares[1:]
return [[squareSolution] + remain
for squareSolution in resolveSquare(square)
for remain in resolveSudoku(remainSquares, solution+[squareSolution])
if isValid(solution + [squareSolution])]
def isValid(solutions):
puzzleSolution = squaresToPuzzle(solutions)
for row in puzzleSolution:
nums = [num for num in row if num is not None]
if len(nums) != len(set(nums)):
return False
for y in range(0, 9):
nums = [puzzleSolution[x][y]
for x in range(0, 9) if puzzleSolution[x][y] is not None]
if len(nums) != len(set(nums)):
return False
return True
def squaresToPuzzle(squares):
d = 3
puzzle = [[None for h in range(0, 9)] for v in range(0, 9)]
for i in range(0, len(squares)):
hOffset = (i % d)*d
vOffset = (i // d)*d
square = squares[i]
for v in range(0, len(square)):
for h in range(0, len(square[v])):
puzzle[vOffset+v][hOffset+h] = square[v][h]
return puzzle
同样使用回溯法纙列出九个方格可行解的所有组合，再在这些组合中选出符合全局要的组合为解（任意行或列上的数字不重复）。