Welcome, guest | Sign In | My Account | Store | Cart

A simple algorithm which uses a recursive function to solve the puzzle.


THE ALGORITHM

The credit for this algorithm must go to Richard Buckland: http://www.youtube.com/watch?v=bjObm0hxIYY&feature=autoplay&list=PL6B940F08B9773B9F&playnext=1

Takes a partially filled in grid, inserts the min value in a cell (could be a random cell, in this case the first free cell). If the min value is not legal it will increment until the max value is reached (number 9), checking each time if the incremented value is legal in that cell (ie does not clash with any already entered cells in square, col or row). If it is legal, it will call itself (the hasSolution function) thus using this slightly more filled in grid to find a new cell and check which value is legal in this next cell. If no values are legal in the next cell, it will clear the previous grid entry and try incrementing the value.

isLegal = does not conflict with any other numbers in the same row, column or square

Python, 119 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import re
import random
import os

# GLOBAL VARIABLES
grid_size = 81

def isFull (grid):
    return grid.count('.') == 0
  
# can be used more purposefully
def getTrialCelli(grid):
  for i in range(grid_size):
    if grid[i] == '.':
      print 'trial cell', i
      return i
      
def isLegal(trialVal, trialCelli, grid):

  cols = 0
  for eachSq in range(9):
    trialSq = [ x+cols for x in range(3) ] + [ x+9+cols for x in range(3) ] + [ x+18+cols for x in range(3) ]
    cols +=3
    if cols in [9, 36]:
      cols +=18
    if trialCelli in trialSq:
      for i in trialSq:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            print 'SQU',
            return False
  
  for eachRow in range(9):
    trialRow = [ x+(9*eachRow) for x in range (9) ]
    if trialCelli in trialRow:
      for i in trialRow:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            print 'ROW',
            return False
  
  for eachCol in range(9):
    trialCol = [ (9*x)+eachCol for x in range (9) ]
    if trialCelli in trialCol:
      for i in trialCol:
        if grid[i] != '.':
          if trialVal == int(grid[i]):
            print 'COL',
            return False
  print 'is legal', 'cell',trialCelli, 'set to ', trialVal
  return True

def setCell(trialVal, trialCelli, grid):
  grid[trialCelli] = trialVal
  return grid

def clearCell( trialCelli, grid ):
  grid[trialCelli] = '.'
  print 'clear cell', trialCelli
  return grid


def hasSolution (grid):
  if isFull(grid):
    print '\nSOLVED'
    return True
  else:
    trialCelli = getTrialCelli(grid)
    trialVal = 1
    solution_found = False
    while ( solution_found != True) and (trialVal < 10):
      print 'trial valu',trialVal,
      if isLegal(trialVal, trialCelli, grid):
        grid = setCell(trialVal, trialCelli, grid)
        if hasSolution (grid) == True:
          solution_found = True
          return True
        else:
          clearCell( trialCelli, grid )
      print '++'
      trialVal += 1
  return solution_found

def main ():
  #sampleGrid = ['2', '1', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '.', '.', '.', '9', '4', '.', '.', '.', '.', '7', '8', '2', '5', '.', '.', '4', '.', '.', '.', '.', '.', '.', '6', '.', '.', '.', '.', '.', '1', '.', '.', '.', '.', '8', '2', '.', '.', '.', '7', '.', '.', '9', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '4', '.', '.', '.', '.', '.', '.', '.', '3', '8', '.']
  #sampleGrid = ['.', '.', '3', '.', '2', '.', '6', '.', '.', '9', '.', '.', '3', '.', '5', '.', '.', '1', '.', '.', '1', '8', '.', '6', '4', '.', '.', '.', '.', '8', '1', '.', '2', '9', '.', '.', '7', '.', '.', '.', '.', '.', '.', '.', '8', '.', '.', '6', '7', '.', '8', '2', '.', '.', '.', '.', '2', '6', '.', '9', '5', '.', '.', '8', '.', '.', '2', '.', '3', '.', '.', '9', '.', '.', '5', '.', '1', '.', '3', '.', '.']
  sampleGrid = ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '4', '6', '2', '9', '5', '1', '8', '1', '9', '6', '3', '5', '8', '2', '7', '4', '4', '7', '3', '8', '9', '2', '6', '5', '1', '6', '8', '.', '.', '3', '1', '.', '4', '.', '.', '.', '.', '.', '.', '.', '3', '8', '.']
  printGrid(sampleGrid, 0)
  if hasSolution (sampleGrid):
    printGrid(sampleGrid, 0)
  else: print 'NO SOLUTION'

  
if __name__ == "__main__":
    main()

def printGrid (grid, add_zeros):
  i = 0
  for val in grid:
    if add_zeros == 1:
      if int(val) < 10: 
        print '0'+str(val),
      else:
        print val,
    else:
        print val,
    i +=1
    if i in [ (x*9)+3 for x in range(81)] +[ (x*9)+6 for x in range(81)] +[ (x*9)+9 for x in range(81)] :
        print '|',
    if add_zeros == 1:
      if i in [ 27, 54, 81]:
        print '\n---------+----------+----------+'
      elif i in [ (x*9) for x in range(81)]:
        print '\n'
    else:
      if i in [ 27, 54, 81]:
        print '\n------+-------+-------+'
      elif i in [ (x*9) for x in range(81)]:
        print '\n'

Any suggestions to speed it up?

6 comments

David Adler (author) 11 years, 11 months ago  # | flag

Good job this wasn't written in LISP as reading the title might be quite a challenge ;-)

Patrycja Szabłowska 11 years, 10 months ago  # | flag

I think you can use a shorter form of isFull

def isFull (grid):
    return grid.count('.') == 0

In hasSolution I would return immediately the True result (I'd move prints somewhere else, they make code less readable)

def hasSolution (grid):
    if isFull(grid):
        return True

In this part:

if int(val) < 10: 
    print '0'+str(val),

I would use method zfill from str. Don't reinvent the wheel ;-)

You define the variable grid_size, and then use it only once.

David Adler (author) 11 years, 10 months ago  # | flag

point taken, updated.

what this program needs is a way of solving the obvious cells first. ie getTrialCell should return cells which can only be one possible value and then other random cells after that.

Any ideas?

Kelly 11 years, 10 months ago  # | flag

You could check the first empty cell.

If it has >1 possible solution: Leave it empty and check the next empty cell. Elif it has 1 possible solution: Enter that solution and move to the next empty cell.

Repeat these checks through all empty cells over and over until you reach a point when no cells have only 1 possible solution.

At this point you have probably added definite values to quite a few cells (or maybe completed the whole grid).

prat 8 years, 4 months ago  # | flag

Can you explain this code.

Braden Townsend 7 years, 8 months ago  # | flag

It seems you forgot parentheses. It won't let me run the code because of SyntaxError: Missing parentheses in call to 'print'. Could you please explain how to fix this?