Quest for most stupid Sudoku solver

I started to get little regret of my simpleton child doing such a hard work in my normal PPS (Post Posting Syndrome:icon_cheesygrin:)

So here is some doubled checked removed, and sudoku minisquare function also inlined in the two places where it used (pity for the repetition of code though, but that is life with interpreted language where function calls cost too much) and first extra check of possibilities removed.

Also I had removed the ability to give up when get too many failures. It is controlled by 'constant' FAIL_LIMIT. I have not found solvable sudoku harder than the limit 3000.

from __future__ import print_function
import time
import itertools
import sys
import pretty

numbers=set('123456789')
FAIL_LIMIT = 3000
# without izip_longest to be python3 compatible. builtin zip is faster
def grouper(n, iterable): return zip(*((iter(iterable),) * n)) if iterable else ()

def correct(s):
    if not s: return False
    s = ''.join(c for part in s for c in part if part and c in numbers)
    ss = set(s)
    return len(s) == len(ss)

def remaining(s): return numbers - set(c for item in s for c in item) # if c in numbers)# does not need as s is checked

def remaining_neighbours(s, i, j):
    start =  i//3 * 27 + j//3 * 3 # start corner of minisquare where i,j belongs
    return (remaining(s[ss:ss+3] for ss in range(start, start + 27, 9)) &
            remaining(s[9*i:9*i+9])  &
            remaining(s[j::9]))

def check(s):
    if len(s) == 81 :
        s = tuple(c if len(c) == 1 else '.' for c in s)
        value = (all(correct(s[ss:ss+3] for ss in range(start, start + 27, 9)) for start in range(0,81,27))
                and all(correct(gr) for gr in itertools.chain(grouper(9, s), (s[start::9] for start in range(9)) )))
        return value

def possibilities(s):
    s = [value if len(value)==1 else '.' for value in s]
    return itertools.takewhile(lambda x: x, (''.join(sorted(remaining_neighbours(s, i, j)))
                       if s[i * 9 + j] in '.0' or len(s[i * 9 + j]) > 1 else s[i * 9 + j]
                       for i in range(9) for j in range(9)))

def solve(sudoku_list):
    sol, fails = [list(possibilities(sudoku_list))], 0
    while sol and fails < FAIL_LIMIT:
        base = sol.pop()
        if all(len(item) == 1 for item in base):
            return map(int, base)
        shortest = tuple((ind,val) for ind, val in enumerate(base) if len(val)>1)
        if shortest:
            ind, prod = min(shortest, key = lambda x: len(x[1]))
            for v in prod:
                under_test, under_test[ind] = base[:], v
                under_test = list(possibilities(under_test))
                if check(under_test): sol.append(under_test)
                else: fails += 1
    return ()

def solve_from_file(fn):
    n, puzzle = 1, ''
    print ('Puzzle set', fn.split('.') [0])
    for sudoku_line in open(fn):
        if not sudoku_line.startswith(tuple('G=#')): puzzle += sudoku_line.strip()
        if len(puzzle) == 81:
            print(n, end=',')
            sys.stdout.flush()
            yield tuple(grouper(9, solve(puzzle)))
            puzzle, n = '', n+1

if __name__=='__main__':
    t0, count, fn = time.clock(), 0, 'hardest.txt'
    result, t0 = tuple(solve_from_file(fn)), time.clock()- t0
    pretty.printer(result, indent_level = 10)
    print('\nSolving time {t:0.2f} s for {solved} out of {count} puzzles.'.format(t=t0, solved = sum(1 for r in result if r), count = len(result)))

BTW the problem solves the sudoku '.....6....59.....82....8....45........3........6..3.54...325..6..................' in 0.13 s which was very hard for the recurvive search and propagation version. http://norvig.com/sudoku.html

Sorry about bombing you on more versions, this I finally deem as version 1.0. Got rid of some last 2d calculations and added fancy histogram. Timing improved to little less than 6.5 s for 50 easy puzzles (which are often more hard than hard ones for my simpistic approach. Imposible case give up time is around 6 s with limit of failures set as 2500.

impossible case from norwig:
# one unsolvable for testing
.....5.8....6.1.43..........1.5........1.6...3.......553.....61........4.........

""" Stupid Sudoku 1.0
    As original as possible Sudoku solver for Project Euler solution
    Keep this comment if you use this code
    Tony Veijalainen 2011, posted in Daniweb as user tonyjv

    """

from __future__ import print_function
import time
import itertools
import pretty

numbers = set('123456789')
FAIL_LIMIT = 2500

# without izip_longest to be python3 compatible (see the manual for itertools version)
def grouper(n, iterable): return zip(*((iter(iterable),) * n)) if iterable else ()

def correct(s):
    s = [c for part in s for c in part if part and c in numbers]
    ls, lss = len(s), len(set(s))
    return ls == lss

def remaining(s): return numbers - set(c for item in s for c in item)

def remaining_neighbours(s, index):
    # start corner of minisquare where index belongs:
    # minisquare row (3*9 lines per minisquare row) and offset by column (integer)divided by 3 * 3
    start =  (index // 27 * 27) + (index % 9 // 3)*3
    return (remaining(s[ss:ss+3] for ss in range(start, start + 27, 9)) &
            remaining(s[index - index % 9:index + 9 - index % 9])  &
            remaining(s[index % 9::9]))

def check(s):
    if len(s) == 81 :
        s = tuple(c if len(c) == 1 else '.' for c in s)
        return (all(correct(s[ss:ss+3]
                    for ss in range(start, start + 27, 9))
                    for start in range(0, 81, 27)) and
                all(correct(gr)
                    for gr in itertools.chain(grouper(9, s), (s[start::9] for start in range(9)))))

def possibilities(s):
    s = [value if len(value)==1 else '.' for value in s]
    return itertools.takewhile(lambda x: x, (''.join(sorted(remaining_neighbours(s, index)))
                       if s[index] in '.0' or len(s[index]) > 1 else s[index]
                       for index in range(81)))

def solve(sudoku_to_solve, histogram_scale = 50):
    t0, sol, fails = time.clock(), [list(possibilities(c for c in sudoku_to_solve if c in numbers or c in '0.'))], 0

    while sol and fails < FAIL_LIMIT:
        base = sol.pop()

        if all(len(item) == 1 for item in base):
            t0 = 1000*(time.clock() - t0)
            print('Success with {0:4} fails, time {1:-7.2f} ms:\t{histogram:50}'.format(fails, t0,
                    histogram = int(t0/histogram_scale)*'*' or '|'))
            return map(int, base)

        shortest = tuple((ind,val) for ind, val in enumerate(base) if len(val)>1)
        if shortest:
            ind, prod = min(shortest, key = lambda x: len(x[1]))
            for v in prod:
                under_test, under_test[ind] = base[:], v
                under_test = list(possibilities(under_test))
                if check(under_test):
                    sol.append(under_test)
                else:
                    fails += 1
    return ()

def solve_from_file(fn):
    n, puzzle = 1, ''
    print ('Puzzle set', fn.split('.') [0],'\n')
    for sudoku_line in open(fn):
        if sudoku_line.strip() and not sudoku_line.startswith(tuple('G=#')):
            puzzle += sudoku_line.strip()
        if len(puzzle) == 81:
            print('Sudoku {0:2}'.format(n), end=': ')
            yield tuple(grouper(9, solve(puzzle)))
            puzzle, n = '', n+1

if __name__=='__main__':
    t0, count, fn = time.clock(), 0, 'sudoku.txt'
    result, t0 = tuple(solve_from_file(fn)), time.clock()- t0
    pretty.printer(result, indent_level = 10)
    print('\nSolving time {t:0.2f} s for {solved} out of {count} puzzles.'.format(t=t0,
            solved = sum(1 for r in result if r), count = len(result)))