Eleagant and fast Sudoku with generator expressions

TrustyTony 0 1K Views

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
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
52...6.........7.13...........4..8..6......5...........418.........3..2...87.....
6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....
48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....
....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....
.524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........
6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....
.923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....
6..3.2....5.....1..........7.26............543.........8.15........4.2........7..
.6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...
..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..
3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....
1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......
6..3.2....4.....1..........7.26............543.........8.15........4.2........7..
....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.
45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..
.237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......
..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56
.98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..
..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...
4.....8.5.3..........7......2.....6.....5.4......1.......6.3.7.5..2.....1.9......
.2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4
1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46
4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......
.......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....
6..3.2....4.....8..........7.26............543.........8.15........8.2........7..
.47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.
......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....
38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..
.2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....
.8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....
..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4
4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......
1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......
1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........
249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...
...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1
...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36....
......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....
.476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7
.....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................
.4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..
.834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..
..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8
.26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4
2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......
6..3.2....1.....5..........7.26............843.........8.15........8.2........7..
1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.
.........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9
.2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5
9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.
...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.
53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.
1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4
....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..
.47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..
......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....
.2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..
1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......
2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5
..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.
...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...
34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82
......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....
.4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........
.......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3
8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2
.8...4.5....7..3............1..85...6.....2......4....3.26............417........
....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....
......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....
.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.
.52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9
....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....
1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....
4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....
......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....
963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..
15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423
..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6
....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........
6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....
....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..
.32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.
...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..
.5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..
..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.
..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.
...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..
.2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9
.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........
3...8.......7....51..............36...2..4....7...........6.13..452...........8..
# 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]:
        return values # Already eliminated
    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)))
               for grid in open(filename).read().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 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
Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

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]:
        return values # Already eliminated
    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')
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview