Python中的Sudoku Solver

Question

我用Python写了这个sudoku解算器。这是我的第一个实质性项目，我希望任何意见或反馈。

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()

这就是谜题1.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

Answer 1

1. 我将比安德鲁乌的建议更进一步一步。您将大量的代码和时间用于迭代行、列和方格。既然这些单元是“固定的”，为什么不构建一些共享的数据结构并从每个单元中链接到它们呢？也就是说，在单元格对象中，创建: cell.row ={单元格集，包括这个单元格，行} cell.col ={单元格集，包括这个单元格，包括这个单元格集，cell.square ={单元格集，包括这个单元格，正方形}这些单元格集对9个单元格是相同的--相同的单元格中的每个单元格具有相同的.col值，等等，它们只是对单元格的引用列表，因此它们应该具有空间效率。也就是说，您可以快速地遍历成员，而无需计算任何内容。
2. 使用列表表示单元格的可能值。尝试使用set，它将使您的代码更短，因为它支持不需要检查的.discard(elem)：def (单元格，检查)：#.对于范围内的I( (cells.index( check ) / 9) * 9，(cells.index(Check)/ 9) *9+ 9)：如果单元格我.value in check.poss: check.poss.remove(cells我.value)变成:对于check.row中的其他单元: check.poss.discard(other.value)和unique看起来是: def唯一(单元格，校验)：“”接收板和检查单元，检查是否有任何可能性对行、列或框是唯一的。必须在elim()之后运行。“”“printStats = False如果不是check.value: this_row = check.row - {check} # set difference for p in check.poss:如果没有(p in other.poss for other in this_row)：check.value =p check.poss.clear()如果printStats :打印“在行中唯一”，Cells.index(检查)中断
3. 你需要去看奈德巴特的“活生生的本地人”的演示，一路走来！您正在编写这样的代码:对于范围内的I(len(check.poss))：这在几乎每种情况下都是自动错误的。如果您想要迭代这些可能性，那么就迭代它们！观看谈话，然后在check.poss中写: for p:或写: for i，p in枚举(check.poss)：酌情。

Answer 2

祝贺你完成了你的重大工程。对你来说，征求反馈意见是非常聪明和勇敢的。我要告诉您，您的代码有什么不完美的地方，毕竟，这就是重点所在，对吗？但不要气馁，因为你做得不错！

让我们从高级算法开始：

我要指出的第一件事是内存的使用，在不同的地方，你要对所有的细胞进行深度复制。这样做很方便，但也占用了很多空间。对于唯一/elim/子集函数，您可以简单地返回一个标志，如果董事会被更改，并将副本保存在解决方案函数中。

可能很难删除猜测函数中的深度副本，这可能是很好的，因为您可能正在做许多更改。

尽量节省一些空间，您应该注意到性能的变化。

那么，让我们来谈谈代码：

校验题函数和背景校验题几乎是相同的，为什么不像在“唯一”中那样参数化它呢？

许多代码都具有遍历每一行/列/平方的结构。在我看来好像有很多重复。如果你把它们抽象成一个叫做块的概念，然后遍历所有的块，会怎样呢？

最后，也可能是最起码，你做了一些排印，‘接收’，‘可能’‘指示’，我非常怀疑‘可能性’这个词，尽管维基百科说它是一个形容词的复数。

Answer 3

理论上，您根本不应该需要elim，因为subset应该涵盖它所做的事情以及更多的功能。(“如果一个组中有N个空方格，而且它们都只有相同的N个可能值，那么同一组中的所有其他方格都不能有任何相同的值。”)elim函数应该与subset函数相同，其中N被限制为1。

还有一个更通用的unique版本，它将涵盖它所做的事情，它将允许您解决更困难的谜题，并将unique函数作为冗余删除。(“如果一个组中有N个空方格，而它们是该组中唯一可能有N个可能值的方格，那么这些方块就不能有任何其他值。”)

我认为没有必要人为地限制elim和unique (或它们的超级操作)的运行顺序。以任何顺序执行它们应该是安全的，有时在以不同的顺序运行时，执行它们的步骤会更少。不过，我没有关于最佳重新计算顺序的建议，因为我自己从来没有想过这一点。但是，如果您发现当您更改应用规则的顺序时，您的解决程序会崩溃，那么这可能是您的实现中的一个错误的证据。

我不知道有多少自动求解器使用相当于您的guess函数，但我从未为自己的解决程序编写过一个。在我所见过的大多数地方，“如何玩”数独强调强调“不猜”，强调逻辑演绎方面。这意味着，如果您不能单独使用静态分析对拼图进行任何逻辑推断，那么它就不是一个“公平的谜题”。尽管另一方面，在报摊书籍和在线上发表的一些难题，由于难度很高，但根据这个定义，“公平的谜题”并不是(甚至有许多人有多种有效的解决方案)。如果你的解谜者停下来，却没有找到解决网络上一本书中给出的谜题的方法，那并不意味着你的解谜者就会被打破。

我想这是一个判断调用，是否有一个guess函数作为求解器的一部分。但我认为，如果所有静态分析都不能在某一时刻取得进展，那绝对应该是最后的手段。这一政策将有助于表现和尊重游戏的精神。与现有的while change循环不同，有两个嵌套循环：

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

请注意，与前面一样，使用这种方法，一旦您对guess进行了修改，求解器实际上可能会在益智状态下出现矛盾，在这个状态下，在一个具有相同值的组中，一个单元格或多个单元格没有可能的值。您还没有为您的猜测实现回溯，所以这仍然是一种可能性。您的checkpuzzle例程只会在离此一步的地方停止执行，这并不是完全的猜测回溯。