See the link (Solve Every Sudoku Puzzle for fine description of logic of the code) I attach the top95.txt file of tough problems and the sudoku claimed toughest of all time by Finnish mathematician Arto Inkala (The Worlds Hardest Sudoku Puzzle)

Solving this was piece of cake for the code, even it does not consider special rules, but strives for simplicity and fast enough:

``````1     2568   2468 |  458    345     7   |  246     9     346
457     3      46  |  1459    2     159  |  1467   467     8
2478   278     9   |   6     134    138  |   5     2347   134
---------------------+---------------------+---------------------
2478   278     5   |   3     167    126  |   9     4678   146
479     1      34  |  579     8     569  |  467   34567    2
6     2789   238  | 12579   1579    4   |  178    3578   135
---------------------+---------------------+---------------------
3    25689   268  | 245789 45679  25689 |  2468    1     4569
2589    4      1   |  2589   3569  235689|  268    2568    7
2589  25689    7   | 124589 14569  125689|   3    24568   4569
1 6 2 |8 5 7 |4 9 3
5 3 4 |1 2 9 |6 7 8
7 8 9 |6 4 3 |5 2 1
------+------+------
4 7 5 |3 1 2 |9 8 6
9 1 3 |5 8 6 |7 4 2
6 2 8 |7 9 4 |1 3 5
------+------+------
3 5 6 |4 7 8 |2 1 9
2 4 1 |9 3 5 |8 6 7
8 9 7 |2 6 1 |3 5 4
# Got 1 out of 1
Time taken 0.023 s
Push Enter``````
550 Views
``````# Solve Every Sudoku Puzzle

# See http://norvig.com/sudoku.html

# Throughout this program we have:
#   r is a row,    e.g. 'A'
#   c is a column, e.g. '3'
#   s is a square, e.g. 'A3'
#   d is a digit,  e.g. '9'
#   u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
#   g is a grid,   e.g. 81 non-blank chars, e.g. starting with '.18...7...
#   values is a dict of possible values, e.g. {'A1':'123489', 'A2':'8', ...}

# edited lines TV Tony Veijalainen 2010 plus these imports, all function removed as it is standard
from __future__ import print_function
import os,sys
from time import clock

if (sys.version_info[0])==3:
raw_input = input
## TV

def cross(A, B):
return [a+b for a in A for b in B]

rows = 'ABCDEFGHI'
digits  =  cols = '123456789' # TV

squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s))
for s in squares)

def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False # Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values # Solved!
# Chose the unfilled square s with the fewest possibilities
_,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])

def assign(values, s, d):
"Eliminate all the other values (except d) from values[s] and propagate."
if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
return values
else:
return False

def eliminate(values, s, d):
"Eliminate d from values[s]; propagate when values or places <= 2."
if d not in values[s]:
values[s] = values[s].replace(d,'')
if len(values[s]) == 0:
return False # Contradiction: removed last value
elif len(values[s]) == 1:
# If there is only one value (d2) left in square, remove it from peers
d2, = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
# Now check the places where d appears in the units of s
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values

def parse_grid(grid):
"Given a string of 81 digits (or .0-), return a dict of {cell:values}"
grid = [c for c in grid if c in '0.-N123456789']
values = dict((s, digits) for s in squares) # Each square can be any digit
for s,d in zip(squares, grid):
if d in digits and not assign(values, s, d):
return False
printboard(values) #TV show result of first check
return values

def solve_file(filename, sep='\n', action=lambda x: x):
"Parse a file into a sequence of 81-char descriptions and solve them."
t=clock() #TV
results = [action(search(parse_grid(grid)))
print("# Got %d out of %d" % (
sum((r is not False) for r in results), len(results)))
print ('Time taken %.3f s' % (clock()-t)) #TV
return results

def solve(inpstr, sep='\n', action=lambda x: x):
"Parse a input string into a sequence of 81-char descriptions and solve them."
t=clock() #TV
results = [action(search(parse_grid(grid)))
for grid in inpstr.strip().split(sep)]
print( "# Got %d out of %d" % (
sum((r is not False) for r in results), len(results)))
print ('Time taken %.3f s' % (clock()-t)) # TV
return results

def printboard(values):
"Used for debugging."
width = 1+max(len(values[s]) for s in squares)
line = '\n' + '+'.join(['-'*(width*3)]*3)
for r in rows:
print(''.join(values[r+c].center(width)+('|' if c in '36' else '')# TV and or to if else
for c in cols) + (line if r in 'CF' else '')) # TV
return values

def some(seq):
for e in seq:
if e: return e
return False

# all definition removed, standard in Python

if __name__ == '__main__':
## TV
if  len(sys.argv)>1:
if os.path.isfile(sys.argv[1]):
solve_file(sys.argv[1], action=printboard)
elif len(sys.argv[1])>=81: # one sudoku in line
solve(sys.argv[1], action=printboard)
else: # interactive input line by line
puzzle=''
for i in range(9):
row=''
while len(row) != 9:
row = raw_input('Row %i :' % (i+1))
if len(row) != 9:
print("\n%i characters, mistake in line input again!" % len(row))
else:
puzzle += row
print('Solving..')
solve(puzzle, action=printboard)

raw_input('Push Enter')
## TV``````

IT Pro doing Eng-Fin-Eng translations

## TrustyTony 888

Here is little more adapted version of the program, as I had added processing from string, making copies of nearly identical functions. I added some usage info,verbosity switch and also little cleaned up some checks avoiding multiple len's and speeding up the test top95.txt around 120 ms in my machine (enormous ;) 1 ms+ per sudoku)

I took out my signs of edits as they became too many.

``````# Solve Every Sudoku Puzzle

# See http://norvig.com/sudoku.html

# Throughout this program we have:
#   r is a row,    e.g. 'A'
#   c is a column, e.g. '3'
#   s is a square, e.g. 'A3'
#   d is a digit,  e.g. '9'
#   u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
#   g is a grid,   e.g. 81 non-blank chars, e.g. starting with '.18...7...
#   values is a dict of possible values, e.g. {'A1':'123489', 'A2':'8', ...}

# minor tweaks and input by Tony Veijalainen 2010
from __future__ import print_function
import os,sys
from time import clock

if (sys.version_info[0])==3:
raw_input = input

def cross(A, B):
return [a+b for a in A for b in B]
printing = False # show prints to demonstrate the workings of program

rows = 'ABCDEFGHI'
digits  =  cols = '123456789'

squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s))
for s in squares)

def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False # Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values # Solved!
# Chose the unfilled square s with the fewest possibilities
_,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])

def assign(values, s, d):
"Eliminate all the other values (except d) from values[s] and propagate."
if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
return values
else:
return False

def eliminate(values, s, d):
"Eliminate d from values[s]; propagate when values or places <= 2."
if d not in values[s]:
vs = values[s] = values[s].replace(d,'')
if  len(vs) <= 1:
if not vs:
return False # Contradiction: removed last value
else:
# If there is only one value (d2) left in square, remove it from peers
d2, = vs
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
# Now check the places where d appears in the units of s
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) <= 1: ## TV fail faster
if not dplaces:
return False
else: # d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values

def parse_grid(grid):
"Given a string of 81 digits (or .0-), return a dict of {cell:values}"
grid = [c for c in grid if c in '0.-N123456789']
values = dict((s, digits) for s in squares) # Each square can be any digit
for s,d in zip(squares, grid):
if d in digits and not assign(values, s, d):
return False
if printing: printboard(values) #TV show result of first check
return values

def solve_file(filename, sep='\n', action=lambda x: x):
"Parse a file into a sequence of 81-char descriptions and solve them."
t=clock()
print('Printing',printing)
results = [solve(grid,sep,action) for grid in open(filename)]
t = clock()-t
print("\n# Got %d out of %d" % (
sum((r is not False) for r in results), len(results)))
print ('Total time taken %.3f s' % t)
return results

def solve(inpstr, sep='\n', action=lambda x: x):
"Parse a input string into a 81-char description and solve it."
if printing:
print('Sudoku:')
print('\n'.join([inpstr[i-9:i] for i in range(9,81+1,9)]))
t=clock()
results = action(search(parse_grid(inpstr)))
if printing:
print ('\nTime taken %.3f ms' % (1000*(clock()-t)))
print ('='*60) #TV separation between solutions
return results

def printboard(values):
"Used for debugging."
print()
width = 1+max(len(values[s]) for s in squares)
line = '\n' + '+'.join(['-'*(width*3)]*3)
for r in rows:
# and or => if else #
print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols) + (line if r in 'CF' else ''))
print()
return values

def some(seq):
for e in seq:
if e: return e
return False

if __name__ == '__main__':
if '--usage' in sys.argv:
raise SystemExit,"""
1) Give as argument filename of sudokus with unknown values as '.0-'
2) Give as argument sudoku game in same format.
3) Call without arguments to enter the sudoku line by line interactively.

--usage got you this message
--verbose or -v gets you more info of solving times and processing
"""

printing = any(choice in sys.argv for choice in ['--verbose','-v'])

if  len(sys.argv)>1:
if os.path.isfile(sys.argv[1]):
solve_file(sys.argv[1], action=printboard)
elif len(sys.argv[1])>=81: # one sudoku in line
solve(sys.argv[1], action=printboard)
else: # interactive input line by line
puzzle=''
for i in range(9):
row=''
while len(row) != 9:
row = raw_input('Row %i :' % (i+1))
if len(row) != 9:
print("\n%i characters, mistake in line input again!" % len(row))
else:
puzzle += row
print('Solving..')
solve(puzzle, action=printboard)

raw_input('Push Enter')``````