算法解决数独 [英] Algorithm for solving Sudoku
问题描述
我想写一个code在python解决数独谜题。你们是否有一个好的算法，用于此目的的任何想法。我在网上读到一个算法，与所有可能的数字填补了整个盒子解决了某个地方，然后插入已知值到相应boxes.From行和已知值的coloumn已知值removed.If你们知道什么更好算法比这个请大家帮我写一个。我也很困惑，那我应该如何读取用户的已知值。这是真的很难由一个通过控制台输入值之一。任何简单的方法为这个除了使用GUI？
I want to write a code in python to solve a sudoku puzzle. Do you guys have any idea about a good algorithm for this purpose. I read somewhere in net about a algorithm which solves it by filling the whole box with all possible numbers, then inserts known values into the corresponding boxes.From the row and coloumn of known values the known value is removed.If you guys know any better algorithm than this please help me to write one. Also I am confused that how i should read the known values from the user. It is really hard to enter the values one by one through console. Any easy way for this other than using gui?
推荐答案
下面是用Python我数独解算器。它使用简单回溯算法来解决这一难题。 为简单起见没有输入验证或花哨的输出完成。它的最低限度code这解决了这个问题。
Here is my sudoku solver in python. It uses simple backtracking algorithm to solve the puzzle. For simplicity no input validations or fancy output is done. Its the bare minimum code which solves the problem.
- 找到一个给定的小区的所有合法值
- 对于每一个法律价值，去递归并尝试解决电网
它采用9X9格部分填充数字。值为0的单元格表示它不填充。
Solution
It takes 9X9 grid partially filled with numbers. A cell with value 0 indicates that it is not filled.
def findNextCellToFill(grid, i, j):
for x in range(i,9):
for y in range(j,9):
if grid[x][y] == 0:
return x,y
for x in range(0,9):
for y in range(0,9):
if grid[x][y] == 0:
return x,y
return -1,-1
def isValid(grid, i, j, e):
rowOk = all([e != grid[i][x] for x in range(9)])
if rowOk:
columnOk = all([e != grid[x][j] for x in range(9)])
if columnOk:
# finding the top left x,y co-ordinates of the section containing the i,j cell
secTopX, secTopY = 3 *(i/3), 3 *(j/3)
for x in range(secTopX, secTopX+3):
for y in range(secTopY, secTopY+3):
if grid[x][y] == e:
return False
return True
return False
def solveSudoku(grid, i=0, j=0):
i,j = findNextCellToFill(grid, i, j)
if i == -1:
return True
for e in range(1,10):
if isValid(grid,i,j,e):
grid[i][j] = e
if _solveSudoku(grid, i, j):
return True
# Undo the current cell for backtracking
grid[i][j] = 0
return False
测试code
>>> input = [[5,1,7,6,0,0,0,3,4],[2,8,9,0,0,4,0,0,0],[3,4,6,2,0,5,0,9,0],[6,0,2,0,0,0,0,1,0],[0,3,8,0,0,6,0,4,7],[0,0,0,0,0,0,0,0,0],[0,9,0,0,0,0,0,7,8],[7,0,3,4,0,0,5,6,0],[0,0,0,0,0,0,0,0,0]]
>>> Tricks.solveSudoku(input)
True
>>> input
[[5, 1, 7, 6, 9, 8, 2, 3, 4], [2, 8, 9, 1, 3, 4, 7, 5, 6], [3, 4, 6, 2, 7, 5, 8, 9, 1], [6, 7, 2, 8, 4, 9, 3, 1, 5], [1, 3, 8, 5, 2, 6, 9, 4, 7], [9, 5, 4, 7, 1, 3, 6, 8, 2], [4, 9, 5, 3, 6, 2, 1, 7, 8], [7, 2, 3, 4, 8, 1, 5, 6, 9], [8, 6, 1, 9, 5, 7, 4, 2, 3]]
以上的是这是在很多地方解释的很基本的回溯算法。但最有趣的和自然的数独的解决策略，我碰到的是这一个从这里
这篇关于算法解决数独的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
