Python中的数独求解器

我用Python编写了这个数独求解器。这是我的第一个重要项目，我希望收到任何评论或反馈。

import csv
import copy 

def main() :
  cells = [cell() for i in range(81)] #creates a list of 81 instances of the cell() class.
  openpuzzle(cells)
  printboard(cells)
  cells = solve(cells) 
  printboard(cells)

class cell() : 
  """This class stores the state of each cell on the board. 
  If self.value = 0, the cell is still unknown."""
  def __init__(self) :
    self.value = 0
    self.poss = [1,2,3,4,5,6,7,8,9]
  def __repr__(self) : 
    return "Value: {0} Possibles: {1}".format(self.value, self.poss)

def openpuzzle(cells) : 
  '''Open puzzle, copy into "cells" list'''
  with open('puzzle1.csv') as csvfile : 
    newCells = next(csv.reader(csvfile, delimiter=","))  #read first line
    for i in range(len(cells)) : 
      cells[i].value = int(newCells[i])
  return cells

def printboard(cells) :
  """prints out the board"""
  divider = "." * 21 
  print divider
  for i in range(len(cells)) :
    if cells[i].value == 0 : 
      cValue = " " 
    else : 
      cValue = str(cells[i].value)
    if i % 27 == 0 and i != 0 : 
      print "------+-------+------"
    if (i + 1) % 9 != 0 :
      if i % 9 in [2,5] : 
        print "{} |".format(cValue),
      else :
        print cValue ,
    else : 
      print cValue
  print divider , "\n"

def printposs(cells) :

  possList = []
  for row in range(27) : #iterates over rows to print
    if row % 9 == 0 and row != 0 : #dividers 
      print "{0}\n{0}".format("*" * 76)
    elif row % 3 == 0 and row != 0 : 
      print "{}{}{}{}{}".format("-" * 24 , "**" , "-" * 25 , "**" , "-" * 24) #end dividers 
    for cell in range(9) : #iterates over cells in the row
      for i in range((row % 3) * 3 ,((row % 3) * 3) + 3 ) : #iterates over the three slots for each cell in a row.
        if cells[cell + (row / 3 * 9)].value != 0 : 
          if row % 3 in [0,2] :
            possList.append("#") 
          elif i % 3 in [0,2] : 
            possList.append("#") 
          else :
            possList.append(cells[cell + (row / 3 * 9)].value)
        elif (i + 1) in cells[cell + (row / 3 * 9)].poss :
          possList.append(i + 1)
        else : 
          possList.append(" ")
    print" {} {} {} | {} {} {} | {} {} {}  **  {} {} {} | {} {} {} | {} {} {}  **  {} {} {} | {} {} {} | {} {} {}".format(*possList)
    possList = []

def printkey() :
  """prints out a key of cell indicies"""
  divider = "." * 30
  print divider
  for i in range(81) :
    if i % 27 == 0 and i != 0 : 
      print "---------+----------+---------"
    if (i + 1) % 9 != 0 :
      if i % 9 in [2,5] : 
        print "{1}{0} |".format(i , " " * (len(str(i)) % 2)),
      else :
        print "{1}{0}".format(i ," " * (len(str(i)) % 2)) ,
    else : 
      print "{1}{0}".format(i ," " * (len(str(i)) % 2))
  print divider , "\n"

def elim(cells, check) :
  """recieves the board and a check cell, eliminates possibles in check cell based on known values in the row, column, and square."""
  printStats = False
  #Is value known? 
  if check.value != 0 : 
    check.poss = [] 
  else :
    #row
    for i in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) :
      if cells[i].value in check.poss :
        check.poss.remove(cells[i].value)
    #column 
    start = cells.index(check) % 9 
    for i in range(9) :
      if cells[start + i * 9].value in check.poss :
        check.poss.remove(cells[start + i * 9].value)
    #square
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for i in range(3) : 
      for j in range(3) : 
        if cells[start + (i * 9) + j].value in check.poss : 
          check.poss.remove(cells[start + (i * 9) + j].value)
    #Check if one poss is left
    if len(check.poss) == 1 :
      check.value = check.poss[0]
      if printStats :
        print "elimination......." , cells.index(check) 
      check.poss = []
  return cells

def unique(cells, check) : 
  '''Recieves the board and a check cell, checks if any possibles are unique to row, column, or box. Must be run AFTER elim(). '''
  printStats = False
  #Row
  if check.value == 0 : 
    for i in range(len(check.poss)) : #iterates the check procedure over posslibles for the cell 
      for ref in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over reference cells
        if check.poss[i] in cells[ref].poss and cells.index(check) != ref : #checks if ref cell contains poss, breaks if true, moving to next check.poss 
          break 
      else : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Row....." , cells.index(check)
        break
  #Column
  if check.value == 0 :
    start = cells.index(check) % 9 
    for i in range(len(check.poss)) : #iterates the check procedure over posslibles for the cell 
      for ref in range(9) : #iterate over ref cells 
        if check.poss[i] in cells[start + ref * 9].poss and cells.index(check) != start + ref * 9 : 
          break 
      else : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Column.." , cells.index(check)
        break
  #Square 
  if check.value == 0 : 
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for i in range(len(check.poss)) : #iterates over possibles for cell
      dupFound = False
      for boxRow in range(3) : #iterates over ref cells
        if not dupFound : 
          for boxCol in range(3) : 
            if check.poss[i] in cells[start + (boxRow * 9) + boxCol].poss and cells.index(check) != start + (boxRow * 9) + boxCol : 
              dupFound = True 
              break
      if not dupFound : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Square.." , cells.index(check)        
        break
  return cells

def subset(cells,check) : 
  '''Recieves a cell to check and the board, checks if other cells have identical poss lists in the row, column, or box, and the number of identical cells is equal to the number of possibilities. If so, remove those possibilities from the rest of the row, column, or box.'''
  printStats = False
  if check.value == 0 : 
    #Row 
    dups = [cells.index(check)]
    for ref in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over reference cells
      if check.poss == cells[ref].poss and cells.index(check) != ref : #checks if poss lists are equivalent
        dups.append(ref)
        if printStats : 
          print "Found subset row candidate, cell {}.".format(cells.index(check)) 
        if len(dups) == len(check.poss) : #checks if the number of duplicate cells is equal to number of possibles 
          if printStats : 
            print "***Found subset row, cell {}!".format(cells.index(check))
          for remove in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over cells to remove from 
            if remove not in dups : #if we're not in one of the duplicates
              for poss in check.poss :
                if poss in cells[remove].poss :
                  cells[remove].poss.remove(poss)
    #Column
    dups = [cells.index(check)] 
    start = cells.index(check) % 9 
    for ref in range(9) : #iterates over reference cells
      if check.poss == cells[start + ref * 9].poss and cells.index(check) != start + ref * 9 : # check if equiv
        dups.append(start + ref * 9)
        if printStats : 
          print "Found subset column candidate, cell {}.".format(cells.index(check)) 
        if len(dups) == len(check.poss) : #check if number of dups equals the number of possibles 
          if printStats : 
            print "***Found subset column, cell {}!".format(cells.index(check))
          for remove in range(9) : #iterates over cells to remove from 
            if (start + remove * 9)  not in dups : #if we're not in one of the duplicates
              for poss in check.poss :
                if poss in cells[start + remove * 9].poss :
                  cells[start + remove * 9].poss.remove(poss)
    #Square
    dups = [cells.index(check)] 
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for boxRow in range(3) : #iterate over ref cells
      for boxCol in range(3) : 
        if check.poss == cells[start + (boxRow * 9) + boxCol].poss and cells.index(check) != start + (boxRow * 9) + boxCol : #check if equiv 
          dups.append(start + (boxRow * 9) + boxCol)
          if printStats : 
            print "Found subset square candidate, cell {}.".format(cells.index(check)) 
          if len(dups) == len(check.poss) : #check if number of dups equals the number of possibles 
            if printStats : 
              print "***Found subset square, cell {}!".format(cells.index(check))
            for boxRowRem in range(3) : #iterate over ref cells
              for boxColRem in range(3) : 
                if (start + (boxRowRem * 9) + boxColRem) not in dups : #if we're not in one of the duplicates
                  for poss in check.poss :
                    if poss in cells[start + (boxRowRem * 9) + boxColRem].poss :
                      cells[start + (boxRowRem * 9) + boxColRem].poss.remove(poss)

  return cells       

def solve(cells) : 
  printStats = False
  change = True
  passes = 0 
  while change : #iterates check process with elim() and unique() until either solved or can't solve
    if printStats : 
      print "Ran Loop {0}".format(passes)
    cellsHist = copy.deepcopy(cells) # create history of cells 
    for i in range(len(cells)) : #iterates elim(), unique(), and subset() over cells of the board. 
      elim(cells,cells[i])
      unique(cells,cells[i])
      subset(cells,cells[i])
    for j in range(len(cells)) : #check if cells is equal to its history, call guess() if so. 
      if cells[j].value != cellsHist[j].value or cells[j].poss != cellsHist[j].poss : 
        cells = guess(cells)
        break 
    else : 
      change = False 
    passes += 1 
    if printStats : 
      printboard(cells)
  for i in range(len(cells)) : #check if puzzle was solved 
    if cells[i].value == 0 : 
      print "Could not solve."
      printposs(cells) 
      break 
  else: 
    print "Solved!"
    checkpuzzle(cells) 
  return cells

def backgroundsolve(cells) : 
  ''' same as solve() without any printouts, gets called by guess()'''
  printStats = False
  change = True
  passes = 0 
  while change : #iterates check process with elim() and unique() until either solved or can't solve
    if printStats : 
      print "Ran Loop {0}".format(passes)
    cellsHist = copy.deepcopy(cells) # create history of cells 
    for i in range(len(cells)) : #iterates elim() and unique() over cells of the board. 
      elim(cells,cells[i])
      unique(cells,cells[i])
      subset(cells,cells[i])
    for j in range(len(cells)) : #check if cells is equal to its history, break while loop if so. 
      if cells[j].value != cellsHist[j].value : 
        break 
      elif cells[j].poss != cellsHist[j].poss : 
        break 
    else : 
      change = False 
    passes += 1 
    if printStats : 
      printboard(cells)
  return cells 

def checkpuzzle(cells) : 
  ''' checks the puzzle to make sure there were no errors in solving''' 
  noError = True 
  #Rows 
  for row in range(9) : 
    checkList = [] 
    for cell in range(9) : #Build checklist
      checkList.append(cells[(row * 9) + cell].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN ROW {}".format(i, row + 1)
        noError = False
  #Columns 
  for column in range(9) :
    checkList = []
    for cell in range(9) : #Build checklist
      checkList.append(cells[column + (cell * 9)].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN COLUMN {}".format(i, column + 1)
        noError = False
  #Squares 
  for square in range(9) :
    checkList = [] 
    for boxRow in range(3) :
      for boxColumn in range(3) :
        checkList.append(cells[(square / 3) * 27 + ((square % 3) * 3) + (boxRow * 9) + boxColumn].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN BOX {}".format(i, square + 1)
        noError = False
  #Print Results 
  if noError : 
    print "Check complete. No Errors."
  else : 
    print "Check complete."

def backgroundcheckpuzzle(cells) :
  ''' same as checkpuzzle() but without any printouts.''' 
  noError = True 
  #Rows 
  for row in range(9) : 
    checkList = [] 
    for cell in range(9) : #Build checklist
      checkList.append(cells[(row * 9) + cell].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  #Columns 
  for column in range(9) :
    checkList = []
    for cell in range(9) : #Build checklist
      checkList.append(cells[column + (cell * 9)].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  #Squares 
  for square in range(9) :
    checkList = [] 
    for boxRow in range(3) :
      for boxColumn in range(3) :
        checkList.append(cells[(square / 3) * 27 + ((square % 3) * 3) + (boxRow * 9) + boxColumn].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  return noError

def guess(cells) :
  '''Iterates over cells and selects each possibility and sees if that will solve the puzzle with backgroundsolve() and checks it with backgroundcheckpuzzle().'''
  continueCheck = True
  while continueCheck :
    for i in range(len(cells)) : 
      for j in range(len(cells[i].poss)) :
        cellsHist = copy.deepcopy(cells) 
        cells[i].value = cells[i].poss[j] 
        backgroundsolve(cells) 
        if backgroundcheckpuzzle(cells) : 
          continueCheck = False 
          break
        else : 
          cells = cellsHist
    else : 
      continueCheck = False 
  return cells

main()

这是puzzle1.csv包含的内容：

3,0,5,0,0,0,0,8,7,0,4,0,0,0,0,0,3,2,7,0,1,0,0,0,0,5,0,0,0,9,5,0,0,0,0,0,0,0,3,0,6,2,0,0,0,0,0,0,0,0,7,0,2,0,0,6,0,0,0,0,0,0,4,0,0,0,0,1,0,0,0,6,0,0,0,4,3,0,8,0,0

除了在其他答复中给出的建议外，您还可以从一些绝对的最小最小数独求解器中获得启发。

#1 楼

我会比@AndrewAu的建议走得更远。您需要花费大量的代码和时间来迭代行，列和正方形。由于这些是针对某个单元格“固定”的，因此为什么不构建一些共享的数据结构并从每个单元格链接到它们呢？ >

cell.row = {set of cells, including this one, in the row}
cell.col = {set of cells, including this one, in the col}
cell.square = {set of cells, including this one, in the square}

这些集合对于9个单元格将是相同的-同一col中的每个单元格将具有相同的.col值，依此类推，它们只是对单元格的引用列表，因此它们应该节省空间。

也就是说，您可以快速迭代成员，而无需计算任何内容。

您可以使用列表来表示单元格的可能值。尝试使用set，由于它支持.discard(elem)，因此无需进行检查，这会使您的代码更短：

def elim(cells, check):
    # ...

    for i in range((cells.index(check) / 9) * 9, (cells.index(check) / 9) * 9 + 9):
        if cells[i].value in check.poss:
            check.poss.remove(cells[i].value)

成为：

    for other in check.row:
        check.poss.discard(other.value)

unique看起来像：

def unique(cells, check): 
    '''Recieves the board and a check cell, checks if any possibles
    are unique to row, column, or box. Must be run AFTER elim().

    '''
    printStats = False

    if not check.value:
        this_row = check.row - {check}    # set difference

        for p in check.poss:
            if not any(p in other.poss for other in this_row):
                check.value = p
                check.poss.clear()
                if printStats : 
                    print "unique in Row....." , cells.index(check)
                break

您需要观看nedbat的“像本地人一样的循环”演示，所有通过！您正在编写如下代码：

for i in range(len(check.poss)):

在几乎每种情况下，这都是错误的。如果要遍历所有可能性，请遍历所有可能性！观看演讲，然后写：

for p in check.poss:

或写：

for i, p in enumerate(check.poss):

适当。
/>

#2 楼

恭喜您完成了重要的项目。征求反馈意见真的很聪明，也很勇敢。我要告诉您的是，您的代码有什么不完美的地方，毕竟，这是全部，对吗？但不要灰心，因为您做得不错！

让我们从高级算法开始：

我想指出的第一件事是使用内存时，您会在各个地方对所有单元进行深拷贝。这样做很方便，但是也要占用很多空间。对于唯一/ elim / subset函数，如果更换了木板，您可以简单地返回一个标志，然后将副本保存在solve函数中。

在guess函数中删除深拷贝可能很困难，这可能很好，因为您可能会进行很多更改。

尝试节省一些空间，您应该会注意到性能的变化。

然后让我们谈谈代码：

checkpuzzle函数和backgroundcheckpuzzle几乎是相同的，为什么不像在唯一代码中那样仅对其进行参数化设置？

很多代码都具有结构遍历每一行/每一列/每一平方。对我来说，这看起来像很多重复。如果您将它们抽象为称为块的概念，然后仅遍历所有块怎么办？

最后（可能最少），您做了一些错别字，“接收”，“可能”，“指示”和我非常怀疑“可能”一词，尽管维基百科说它是形容词的复数形式。

\ $ \ begingroup \ $
“尝试节省一些空间，您应该注意到性能有所变化。”您在这里谈论什么空间？像这样的笼统声明不一定是正确的。如果替代方法是每次都从文件中重新读取数据，那不是更好。那你有什么建议呢？
\ $ \ endgroup \ $
–桅杆
18年1月8日在12:02

\ $ \ begingroup \ $
保留一个计数器，尝试计算cell.deepcopy（）被调用的次数，那么您就会明白我的意思。
\ $ \ endgroup \ $
–欧安德鲁
18年1月9日在7:13

#3 楼

从理论上讲，您甚至根本不需要elim，因为subset应该涵盖其功能以及更多功能。（“如果一个组中有N个空正方形，并且它们都只有相同的N个可能值，则同一组中的所有其他正方形不能具有任何相同的值。”） elim，其中N限制为1。

还有subset的更通用版本，它将涵盖其功能，这将使您能够解决更难的难题，并删除多余的unique函数。（“如果一个组中有N个空正方形，并且它们是该组中唯一可以具有N个可能值的正方形，那么这些正方形不能具有任何其他值。”）

我认为无需人为地限制unique和elim（或其超级操作）的运行顺序。以任何顺序执行它们应该是安全的，并且有时以不同的顺序运行时将花费较少的步骤来解决。我没有建议最佳的重新计算顺序，因为我自己从来没有想过。但是，如果您发现在更改规则的应用顺序时求解器发生故障，则可能是实现中存在错误的证据。

我不知道有多少自动求解器使用与您的unique函数等效的函数，但我从未为自己的求解器编写过一个。在我见过的大多数地方，数独的“如何玩”解释都强调“不加猜测”，以强调逻辑推理方面。这意味着，如果您不能仅使用静态分析就该难题做出任何逻辑推论，那么它就不是“公平难题”。虽然，另一方面，在报亭和网上发布的一些难题，按照高难度的定义，并不是“公平难题”（甚至还有很多难题有多种有效的解决方案）。如果您的求解器在没有找到解决网络上书中给出的难题的解决方案的情况下停止，那并不意味着您的求解器已自动损坏。

我想这是否是guess作为求解器的一部分。但是我相信，如果所有静态分析都无法在给定的点上取得进展，那绝对应该是最后的选择。该政策将有助于提高性能并尊重游戏精神。与现有的guess循环不同，它具有两个嵌套循环：

while change:
  while change:
    # current activity, but no call to guess(), update change variable
  if not change:
    # call to guess(), update change variable

请注意，与以前一样，一旦使用while change ed，则求解器实际上可能会产生矛盾在拼图状态下，对于一个单元格或组中具有相同值的多个单元格，可能没有值。您尚未为您的猜测实施回溯，因此仍然有可能。您的guess例程将仅停止执行一步，而不是完全的猜测回溯。

\ $ \ begingroup \ $
猜测问题是一个哲学性的问题，或者是关于求解器的一个规范。我写了一个求解器，它只是检查是否存在考虑行，列和块的所有单元格。如果失败，它将猜测第一种可能性，并尝试解决该问题。它“立即”解决了难题，并且只需要很少的程序员工作。如果我们有十亿个难题需要解决，那显然是错误的方法，但我大约有50个。
\ $ \ endgroup \ $
–罗斯·米利坎（Ross Millikan）
18年1月9日在4:42

#4 楼

尝试将其编写为递归解决方案-您的行数会减少很多。定义一个将未解决难题作为参数的函数，找到一个数字，该数字是一个空单元格的有效数字，并且是唯一有效数字，更新难题，然后将其发送回原始函数。

\ $ \ begingroup \ $
这不能解决您看到的大多数Sudoku。您将被所有具有多个可能性的空单元格阻塞。结合猜测功能和处理故障使这项工作成为可能。一直猜测，直到找到解决方案。
\ $ \ endgroup \ $
–罗斯·米利坎（Ross Millikan）
18年1月9日在4:44

\ $ \ begingroup \ $
是的，但是递归仍然是一种方法。
\ $ \ endgroup \ $
–postoronnim
18年1月9日在14:42

编程黑洞网

Python中的数独求解器

评论

#1 楼

#2 楼

评论

#3 楼

评论

#4 楼

评论