Brute force sudoku cracker

Discussion in 'Python' started by Bas, Sep 16, 2005.

  1. Bas

    Bas Guest

    Hi group,

    I came across some of these online sudoku games and thought after
    playing a game or two that I'd better waste my time writing a solver
    than play the game itself any longer. I managed to write a pretty dumb
    brute force solver that can at least solve the easy cases pretty fast.

    It basically works by listing all 9 possible numbers for all 81 fields
    and keeps on striking out possibilities until it is done.

    -any ideas how to easily incorporate advanced solving strategies?
    solve(problem1) and solve(problem2) give solutions, but solve(problem3)
    gets stuck...

    -any improvements possible for the current code? I didn't play a lot
    with python yet, so I probably missed some typical python tricks, like
    converting for-loops to list expressions.

    TIA,
    Bas

    ***********

    from itertools import ifilterfalse

    problem1 = [' 63 7 ',
    ' 69 8',
    '9 7 2',
    ' 2 1 8 ',
    ' 5 8 6 9 ',
    ' 9 7 2 ',
    '6 1 3',
    '7 45 ',
    ' 9 14 ']

    problem2 = [' 3 9 7',
    ' 1 8 ',
    ' 1 9 ',
    ' 49 5 6',
    ' 2 1 ',
    '5 6 74 ',
    ' 5 1 ',
    ' 4 2 ',
    '7 5 3 ']

    problem3 = [' 3 5 81 ',
    ' 76 9 ',
    '4 ',
    ' 439 5 6',
    ' 1 7 ',
    '6 8 193 ',
    ' 9',
    ' 9 86 ',
    ' 61 2 8 ']

    #define horizontal lines, vertical lines and 3x3 blocks
    groups = [range(9*i,9*i+9) for i in range(9)] + \
    [range(i,81,9) for i in range(9)] + \
    [range(0+27*i+3*j,3+27*i+3*j) + range(9+27*i+3*j,12+27*i+3*j)
    + \
    range(18+27*i+3*j,21+27*i+3*j) for i in range(3) for j in
    range(3)]

    def display(fields):
    for i in range(9):
    line = ''
    for j in range(9):
    if len(fields[9*i+j]) == 1:
    line += ' ' + str(fields[9*i+j][0])
    else:
    line += ' '
    print line


    def all(seq, pred=bool):
    "Returns True if pred(x) is True for every element in the iterable"
    for elem in ifilterfalse(pred, seq):
    return False
    return True

    def product(seq):
    prod = 1
    for item in seq:
    prod *= item
    return prod

    def solve(problem):
    fields = [range(1,10) for i in range(81)] #fill with all
    posibilities for all fields
    for i,line in enumerate(problem):
    for j,letter in enumerate(line):
    if letter != ' ':
    fields[9*i+j]=[int(letter)] #seed with numbers from
    problem
    oldpos = 0
    while True:
    pos = product(len(field) for field in fields)
    if pos == oldpos: #no new possibilities eliminated, so stop
    break
    display(fields)
    print pos,'possibilities'
    oldpos = pos
    for group in groups:
    for index in group:
    field = fields[index]
    if len(field) == 1: #if only number possible for field
    remove it from other fields in group
    for ind in group:
    if ind != index:
    try:
    fields[ind].remove(field[0])
    except ValueError:
    pass
    else: #check if field contains number that does not
    exist in rest of group
    for f in field:
    if all(f not in fields[ind] \
    for ind in group if ind!=index):
    fields[index] = [f]
    break
     
    Bas, Sep 16, 2005
    #1
    1. Advertising

  2. Bas

    Guest

    Bas ha escrito:

    > Hi group,
    >
    > I came across some of these online sudoku games and thought after
    > playing a game or two that I'd better waste my time writing a solver
    > than play the game itself any longer. I managed to write a pretty dumb
    > brute force solver that can at least solve the easy cases pretty fast.
    >
    > It basically works by listing all 9 possible numbers for all 81 fields
    > and keeps on striking out possibilities until it is done.
    > [snip]


    This problem is desperately begging for backtracking. The cost is still
    exponential but it works nicely with small problems. Fortunately, a 9x9
    grid is small enough. I programmed this about two months ago, it's not
    really pretty but it works perfectly. Beware, some variable names are
    in spansih...
    [let's hope the tabs are kept...]
    Regards,
    Al


    from sets import Set

    class sudoku:
    def __init__(self,cadena):
    self.numeros=Set(range(1, 10))
    self.m=[['X']*9 for i in range(9)]
    for fila in range(9):
    for columna in range(9):
    if cadena[fila*9 + columna].isdigit():
    self.m[fila][columna]=int(cadena[fila*9+columna])
    self.posiciones=[(i,j) for i in range(9) for j in range(9) if
    self.m[j]=='X']
    def __repr__(self):
    res=""
    for fila in range(9):
    if fila%3==0: res+= "-------------------------\n"

    for columna in range(9):
    if columna%3==0: res+= "| "
    res+="%s "%str(self.m[fila][columna])
    res+= "|\n"

    res+= "-------------------------\n"
    return res

    def fila(self,fila, columna):
    return self.numeros-Set(elem for elem in self.m[fila] if
    elem!='X')
    def columna(self,fila, columna):
    return self.numeros-Set(self.m[columna] for i in range(9)
    if self.m[columna]!='X')

    def cuadro(self,fila, columna):
    s=Set()
    f_ini=3*(fila/3)
    c_ini=3*(columna/3)
    for f in range(f_ini, f_ini+3):
    for c in range(c_ini, c_ini+3):
    if self.m[f][c]!='X' and self.m[f][c] not in s:
    s.add(self.m[f][c])

    return self.numeros-s

    def resuelve(self):
    print "Resolviendo"
    def actua(i):
    if i==len(self.posiciones):
    print self
    return
    f, c=self.posiciones
    posibles=self.fila(f, c).intersection(self.columna(f,
    c)).intersection(self.cuadro(f, c))
    for num in posibles:
    self.m[f][c]=num
    actua(i+1)
    self.m[f][c]='X'
    actua(0)

    def main():
    problem3=" 3 5 81 76 9 4 439 5 6 1 7 6 8 193
    9 9 86 61 2 8 "
    t=sudoku(problem3)
    print t
    t.resuelve()

    if __name__=="__main__":
    main()
     
    , Sep 16, 2005
    #2
    1. Advertising

  3. Bas enlightened us with:
    > I came across some of these online sudoku games and thought after
    > playing a game or two that I'd better waste my time writing a solver
    > than play the game itself any longer. I managed to write a pretty
    > dumb brute force solver that can at least solve the easy cases
    > pretty fast.


    I've got a solver too - I'm joining the Linux Format programming
    contest. My program can solve and create Sudoku puzzles - and not only
    9x9 ones. Check http://www.unrealtower.org/sodoku. In the LFX
    programming contest they call the puzzle Sodoku, not Sudoku, so that's
    why I'm sticking with the name Sodoku for now.

    > -any improvements possible for the current code? I didn't play a lot
    > with python yet, so I probably missed some typical python tricks,
    > like converting for-loops to list expressions.


    It all depends on what you want to do. My program can create & solve
    puzzles from any size, load and save them to disk, check them for
    validity and rank them ('easy', 'medium', 'hard', 'near impossible').
    It also implements a puzzle in a class, so it can be used in an OOP
    fashion.

    > def all(seq, pred=bool):


    What's this? What is bool?

    Sybren
    --
    The problem with the world is stupidity. Not saying there should be a
    capital punishment for stupidity, but why don't we just take the
    safety labels off of everything and let the problem solve itself?
    Frank Zappa
     
    Sybren Stuvel, Sep 17, 2005
    #3
  4. Bas

    Tom Anderson Guest

    On Fri, 16 Sep 2005, Bas wrote:

    > -any ideas how to easily incorporate advanced solving strategies?
    > solve(problem1) and solve(problem2) give solutions, but solve(problem3)
    > gets stuck...


    the only way to solve arbitrary sudoku problems is to guess.

    of course, you have to deal with guessing wrongly, and it helps if you can
    make good guesses!

    i wrote a solver based entirely on guessing and backtracking a few months
    ago; it's fairly simple, although i wrote it in fairly fine-grained java,
    so there's actually quite a lot of code. i had a very different program
    structure to you, since i was only doing guesswork; i had a recursive
    function that looked like this:

    def solve(grid):
    """Solves a grid.

    The solution is written in the grid; if no solution can be found, does
    nothing to the grid. Returns True if a solution was found, False if not.
    """
    x, y = pick_an_empty_cell_to_try(grid)
    letters = letters_which_can_be_written_in_this_cell(grid, x, y)
    if (letters == []):
    return False # there are no legal moves; give up
    for letter in letters:
    grid.write(x, y, letter) # try a move ...
    if (solve(grid)):
    return True # we win!
    grid.erase(x, y) # ... undo it if it didn't work
    return False # none of the legal moves work; give up

    the implementation of the grid class is pretty straightforward - it's just
    a two-dimensional matrix with some bells and whistles.
    letters_which_can_be_written_in_this_cell is also fairly simple, although
    it can be made a lot faster by keeping summary information in the grid
    object: i had a set for each row, column and region saying which letters
    had been written already, so the set of available letters was the inverse
    of the union of the sets relevant to the cell; the sets were implemented
    as bitmaps, so this was all very fast.

    the only tricky bit is pick_an_empty_cell_to_try; you can have fun trying
    different heuristics here! the nice thing is that it's okay to use quite
    computationally expensive heuristics, since a modestly better choice can
    save huge numbers of recursions.

    there are a number of much, much more advanced algorithms out there, doing
    all sorts of clever stuff. however, my algorithm solves any sudoku i can
    throw at it (barring seriously unreasonable stuff) in under a second, so
    i'm happy with it.

    tom

    --
    I content myself with the Speculative part [...], I care not for the Practick. I seldom bring any thing to use, 'tis not my way. Knowledge is my ultimate end. -- Sir Nicholas Gimcrack
     
    Tom Anderson, Sep 17, 2005
    #4
  5. Tom Anderson a écrit :
    > On Fri, 16 Sep 2005, Bas wrote:
    >
    >> -any ideas how to easily incorporate advanced solving strategies?
    >> solve(problem1) and solve(problem2) give solutions, but
    >> solve(problem3) gets stuck...

    >
    >
    > the only way to solve arbitrary sudoku problems is to guess.


    Well, that's true, but most of the sudoku puzzles can be solved in
    linear time ! And also having a linear time solving algorithm allows you
    to really reduce the time used when you need backtracking.

    BTW, the three given examples can be solved without backtracking.

    I made one very recently (mmhh ... first complete version made
    yesterday, still need a little bit of debug on the backtracking part),
    and it's pretty quick (made in Ruby but well, I suppose timing are
    similar), it never get stuck for long even if it fails, it fails quickly ...

    Pierre
     
    Pierre Barbier de Reuille, Sep 17, 2005
    #5
  6. Bas

    Benji York Guest

    Benji York, Sep 17, 2005
    #6
  7. Bas

    David Durkee Guest

    Hi Bas,

    I came across Soduko puzzles recently too and had the same reaction:
    why waste my time solving the things when it would be much more fun
    to write a Python program to do so?



    I've enclosed my script and four puzzle files. The puzzle files are
    text files containing nine lines of text, and containing nine digits
    or spaces. Your puzzle 3 is the one in the file puzzle4.txt.
    Interestingly, the file puzzle3.txt is the first one I ran across
    that my earlier version couldn't solve. You must pass in the puzzle
    file path as a single parameter to the script.

    My script originally used two strategies, which I called solve-by-
    needed and solve-by-possible. I found that neither strategy used by
    itself completed as much of the difficult puzzles as alternating
    between both strategies. However, even both together didn't
    completely solve my puzzle 3 (or yours). I found I wasn't even able
    to solve it myself unless I narrowed one space down to two
    possibilities and took a guess. Of course, sometimes I would guess
    wrong and have to keep track of where I was to be able to go back to
    that state and make the other guess. Obviously a computer program can
    do this more easily than I can, so I incorporated that as a third,
    last resort strategy. This, so far, has always worked, and I can't
    imagine it not working on a solvable puzzle. It seems like cheating,
    though. I wrote it recursively, as making one guess can lead to
    another situation where the puzzle is still solvable but strategies
    one and two get stuck. I've never seen it recurse more than twice
    with a real puzzle. With a really gross test I call "ones test", a
    puzzle in which only nine ones are filled in (which obviously has
    many possible solutions), it recursed very deeply and still succeeded
    in producing a possible solution.

    David

    On Sep 16, 2005, at 3:45 PM, Bas wrote:

    > I came across some of these online sudoku games and thought after
    > playing a game or two that I'd better waste my time writing a solver
    > than play the game itself any longer. I managed to write a pretty dumb
    > brute force solver that can at least solve the easy cases pretty fast.
    >
     
    David Durkee, Sep 17, 2005
    #7
  8. Bas

    Bas Guest

    Bas, Sep 17, 2005
    #8
  9. On 16 Sep 2005 13:45:24 -0700, "Bas" <> declaimed the
    following in comp.lang.python:

    >
    > It basically works by listing all 9 possible numbers for all 81 fields
    > and keeps on striking out possibilities until it is done.
    >
    > -any ideas how to easily incorporate advanced solving strategies?
    > solve(problem1) and solve(problem2) give solutions, but solve(problem3)
    > gets stuck...
    >

    My version doesn't handle the really ugly ones either.

    I never incorporated back-tracking, and the "level 3" puzzles in my
    book are full of such ... (watch out for line wrap) {I've just converted
    the input logic, it isn't fully tested, and should have a way to "erase"
    prior rows for correction}

    -=-=-=-=-=-=-=-=-=-

    import time


    class Cell(object):
    def __init__(self):
    self.locked = False # final value found
    self.value = None
    self.candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    def set(self, value):
    self.locked = True
    self.value = value
    self.candidates = None

    def eliminate(self, value):
    if not self.locked:
    if value in self.candidates:
    self.candidates.remove(value)
    return True
    return False


    class Grid(object):
    def __init__(self):
    self.cells = [ [Cell(), Cell(), Cell()],
    [Cell(), Cell(), Cell()],
    [Cell(), Cell(), Cell()] ]

    def completed(self):
    for r in range(3):
    for c in range(3):
    if not self.cells[r][c].locked:
    return False
    return True

    class Table(object):
    def __init__(self):
    self.grids = [ [Grid(), Grid(), Grid()],
    [Grid(), Grid(), Grid()],
    [Grid(), Grid(), Grid()] ]

    self.rows = [None] * 9
    for r in range(9):
    row = [None] * 9
    for c in range(9):
    row[c] = self.grids[r / 3][c / 3].cells[r % 3][c % 3]

    def set(self, row, col, value):
    self.grids[row / 3][col / 3].cells[row % 3][col % 3].set(value)

    def get(self, row, col):
    return self.grids[row / 3][col / 3].cells[row % 3][col % 3]

    def eliminate(self, row, col, value):
    changed = False
    for c in range(9):
    changed = (self.grids[row / 3][c / 3].cells[row % 3][c %
    3].eliminate(value)
    or changed)

    for r in range(9):
    changed = (self.grids[r / 3][col / 3].cells[r % 3][col %
    3].eliminate(value)
    or changed)

    grid = self.grids[row / 3][col / 3]
    for c in range(3):
    for r in range(3):
    changed = (grid.cells[r][c].eliminate(value) or changed)

    return changed

    def display(self):
    print "\n\n0 1 2 3 4 5 6 7 8\n=================="
    for r in range(9):
    for c in range(9):
    if self.get(r, c).value:
    print "%s" % (self.get(r, c).value),
    else:
    print " ",
    print "|%s" % r

    def completed(self):
    for r in range(3):
    for c in range(3):
    if not self.grids[r][c].completed():
    return False
    return True


    if __name__ == "__main__":
    myTable = Table()
    ## print "\n\nEnter a value of 0 to exit setup"
    ## print "\tRow and Column range 0..8"
    ##
    ## while True:
    ## cin = raw_input("Enter the cell Value Row Column (space
    separated: ")
    ## try:
    ## cv, cr, cc = cin.split()
    ## value = int(cv)
    ## if value == 0: break
    ## row = int(cr)
    ## col = int(cc)
    ## myTable.set(row, col, value)
    ## myTable.display()
    ## print
    ## except:
    ## print "Error processing input: try again"
    ## pass
    print "\n\nEnter row data in the form: x..y.z..."
    print "\twhere . represents and empty cell, and"
    print "\t x, y, z represent digits in the range 1..9\n"
    for cr in range(9):
    while True:
    while True:
    cin = raw_input("Enter Row %s: " % cr)
    if len(cin) == 9: break #correct length
    print "*** Enter 9 characters only; '%s' is %s
    characters" % (cin, len(cin))
    good_row = True
    for cc in range(9):
    if cin[cc] == ".": continue #empty cell
    value = int(cin[cc])
    if value == 0:
    good_row = False #bad character
    print "*** Only 1..9, or . are allowed"
    for ec in range(9):
    myTable.set(cr, ec, None) #clear row
    break
    else:
    myTable.set(cr, cc, value)
    if good_row: break #escape from row input loop
    myTable.display()



    print "\n\nBuilding table ",
    for r in range(9):
    for c in range(9):
    if myTable.get(r, c).locked:
    myTable.eliminate(r, c, myTable.get(r, c).value)

    myTable.display()

    while True:
    print "Evaluating "
    change = False
    done = True
    for r in range(9):
    for c in range(9):
    print ".",
    time.sleep(0.01)
    if not myTable.get(r, c).locked:
    if len(myTable.get(r, c).candidates) == 1:
    myTable.set(r, c, myTable.get(r,
    c).candidates[0])
    change = myTable.eliminate(r, c,
    myTable.get(r,
    c).value)
    myTable.display()
    if change: break
    if change: break

    print

    # check for completion
    if myTable.completed():
    print "Completed"
    break

    if not change:
    deadlock = True
    print "Resolving initial deadlock"
    for gr in range(3):
    for gc in range(3):
    myGrid = myTable.grids[gr][gc]
    count = [0] * 9
    if deadlock:
    for r in range(3):
    for c in range(3):
    if deadlock and
    myGrid.cells[r][c].candidates:
    for n in
    myGrid.cells[r][c].candidates:
    count[n-1] += 1

    try:
    n = count.index(1) + 1
    deadlock = False
    for r in range(3):
    for c in range(3):
    if (myGrid.cells[r][c].candidates
    and n in
    myGrid.cells[r][c].candidates):
    myGrid.cells[r][c].set(n)
    myTable.eliminate(gr * 3 + r, gc
    * 3 + c, n)
    myTable.display()
    except:
    pass

    if deadlock:
    print "Deadlocked; must be resolved manually"
    cin = raw_input("Enter value row column: ")
    cv, cr, cc = cin.split()
    value = int(cv)
    row = int(cr)
    col = int(cc)
    myTable.set(row, col, value)
    myTable.eliminate(row, col, value)
    myTable.display()
    -=-=-=-=-=-=-=-
    >
    > problem3 = [' 3 5 81 ',
    > ' 76 9 ',
    > '4 ',
    > ' 439 5 6',
    > ' 1 7 ',
    > '6 8 193 ',
    > ' 9',
    > ' 9 86 ',
    > ' 61 2 8 ']
    >

    Yes, that is a deadlock set... (You'll need fixed width font)

    0 1 2 3 4 5 6 7 8
    ==================
    3 5 8 1 |0
    1 7 6 9 |1
    4 |2
    8 4 3 9 7 5 1 2 6 |3
    1 6 7 8 |4
    6 8 1 9 3 |5
    1 5 7 9 |6
    9 8 6 1 |7
    6 1 9 2 8 |8
    Evaluating
    .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    .. . . . . . . . . . . .
    .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    Resolving initial deadlock


    0 1 2 3 4 5 6 7 8
    ==================
    3 5 8 1 |0
    1 7 6 9 |1
    4 1 |2
    8 4 3 9 7 5 1 2 6 |3
    1 6 7 8 |4
    6 8 1 9 3 |5
    1 5 7 9 |6
    9 8 6 1 |7
    6 1 9 2 8 |8
    Evaluating
    .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    .. . . . . . . . . . . .
    .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    Resolving initial deadlock
    Deadlocked; must be resolved manually
    Enter value row column:

    Given a set like that, the next approach would be to add recursion:
    clone (deep copy) the tableau, find the first empty cell, pick the first
    available number for it (saving a list of those tried), then recursively
    try to finish the puzzle after using that number... Next deadlock,
    clone, pick next empty cell, pick candidate... If you get to a deadlock
    where there is an empty cell and NO viable candidates, pop back to the
    previous saved tableau and try the next candidate at that location. If
    all candidates fail, pop back yet again...



    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Home Page: <http://www.dm.net/~wulfraed/> <
    > Overflow Page: <http://wlfraed.home.netcom.com/> <
     
    Dennis Lee Bieber, Sep 17, 2005
    #9
  10. As everyone posts his, I'll do the same :) It uses some constraint based
    solving techniques - but not too complicated ones. When stuck, it
    backtracks. So far it never failed me, but I haven't tested it too
    thouroughly.

    Diez

    import copy

    def condense(vals):

    if len(vals) == 0:
    return ""
    ranges = [0]
    ranges += [i+1 for i, v in enumerate(vals[:-1]) if vals[i+1] - v > 1]
    ranges.append(len(vals))
    ranges = zip(ranges[:-1], ranges[1:])
    def f(l):
    if len(l) > 1:
    return "%i-%i" % (l[0], l[-1])
    return "%i" % l[0]
    return ", ".join([f(vals[a:b]) for a,b in ranges])


    riddle1 = """
    1**83***2
    57***1***
    ***5*9*64
    7*4**859*
    **3*1*4**
    *514**3*6
    36*7*4***
    ***6***79
    8***52**3
    """
    riddle2 = """
    **2*9*1*7
    *386*****
    4********
    *****5***
    **9*1*3**
    ***4*****
    ********4
    *****792*
    8*6*3*7**
    """
    class Constraint(object):
    def __init__(self, fields):
    self.__fields = fields

    def apply(self, sudoko, all_nums = set(xrange(1,10))):
    changed = False
    placed = set()
    [placed.update(sudoko[x][y]) for x,y in self.__fields if len(sudoko[x][y]) == 1]
    news = []
    for x,y in self.__fields:
    old = sudoko[x][y]
    if len(old) > 1:
    new = old.intersection(all_nums.difference(placed))
    if len(new) == 0:
    raise ValueError()
    if old != new:
    changed = True
    sudoko[x][y] = new
    news.append(((x,y), new))
    # naked pair elimination
    if changed:
    return True
    pair_found = False
    #print "-" * 30
    #print sudoko
    #print "-" * 30
    for i in xrange(2, 5):
    all = [list(n) for f,n in news if len(n) == i]
    [l.sort() for l in all]
    all = [tuple(l) for l in all]
    all.sort()
    #print "all ", all
    for j, l in enumerate(all[:-1]):
    if len(all[j:j+i]) == i and len(set(all[j:j+i])) == 1:
    np = set(l)
    #print "naked pair", np
    for k, (f, n) in enumerate(news):
    if n != np:
    #print "Adjusted ", f, n
    new = n.difference(np)
    if len(new) == 0:
    raise ValueError()

    if new != n:
    pair_found =True
    news[k] = (f, new)
    if pair_found:
    for (x,y), n in news:
    sudoko[x][y] = n
    return pair_found

    class Sudoku(object):
    def __init__(self, parent=None):
    if parent is None:
    self.__field = [[set(xrange(1, 10)) for i in xrange(9)] for j in xrange(9)]
    self.__constraints = []
    # row constraints
    for y in xrange(9):
    self.__constraints.append(Constraint([(x,y) for x in xrange(9)]))
    # column constraints
    for x in xrange(9):
    self.__constraints.append(Constraint([(x,y) for y in xrange(9)]))
    # field constraints
    for xx in xrange(0,9,3):
    for yy in xrange(0,9,3):
    self.__constraints.append(Constraint([(x+xx, y+yy) for x in xrange(3) for y in xrange(3)]))
    else:
    self.__field = copy.deepcopy(parent.__field)
    self.__constraints = parent.__constraints


    def __getitem__(self, index):
    class Column(object):
    def __init__(self, column, field):
    self.__column = column
    self.__field = field

    def __setitem__(self, index, value):
    self.__field[self.__column][index] = value

    def __getitem__(self, index):
    return self.__field[self.__column][index]

    return Column(index, self.__field)

    def __repr__(self):
    res = [[None for i in xrange(9)] for j in xrange(9)]
    col_widths = [0 for i in xrange(9)]
    for x in xrange(9):
    for y in xrange(9):
    vals = list(self[x][y])
    vals.sort()
    r = condense(vals)
    res[x][y] = r
    if col_widths[x] < len(r):
    col_widths[x] = len(r)

    rows = []
    for y in xrange(9):
    rows.append(" ".join(["%s%s" % (res[x][y], " " * (col_widths[x] - len(res[x][y]))) for x in xrange(9)]))

    return "\n".join(rows)

    def load(self, instance):
    lines = [line for line in instance.split() if line]
    for x in xrange(9):
    for y in xrange(9):
    v = lines[y][x]
    if v != "*":
    self[x][y] = set([int(v)])


    def solve(self):
    changed = set([True])
    while True in changed:
    changed = set([c.apply(self) for c in self.__constraints])
    if not self.solved:
    #print self
    def enum_squares():
    sqs = [(len(sq), (pos, sq)) for pos, sq in self.squares if len(sq) > 1]
    sqs.sort()
    for _, (pos, square) in sqs:
    for v in square:
    yield pos, v
    for (x, y), v in enum_squares():
    child = Sudoku(self)
    child[x][y] = set([v])
    try:
    child.solve()
    if child.solved:
    self.__field = child.__field
    return
    except ValueError:
    pass

    def squares(self):
    for x in xrange(9):
    for y in xrange(9):
    yield (x,y), self[x][y]
    squares = property(squares)

    def solved(self):
    return len([1 for _, square in self.squares if len(square) == 1]) == 81
    solved = property(solved)



    if __name__ == "__main__":
    s = Sudoku()
    s.load(riddle2)
    s.solve()
    print s
     
    Diez B. Roggisch, Sep 18, 2005
    #10
  11. Bas

    Guest

    Had the same reaction as everyone when I saw theses puzzles a month or
    so ago, so here is my solution...
    the solve function is recursive, so it can also solve the 'deadlock
    set' (example3). find_cell looks for an empty cell with the most filled
    cells in it's row and column, so the search tree doesn't grow too
    'wide'.

    -----------------------------------

    example1 = """8 9 - - - - 3 - 4
    - - 5 - 3 - - - -
    - 7 - - 8 1 5 - -
    - 4 - - - 7 - - 3
    - - - 5 4 3 - - -
    2 - - 1 - - - 5 -
    - - 7 9 1 - - 4 -
    - - - - 7 - 2 - -
    9 - 8 - - - - 7 5"""

    example2 = """- 5 2 - - - - - -
    9 - - 1 - - - 5 -
    - - 4 8 3 - - - 2
    - 3 - - 9 - 1 - 5
    - - - - - - - - -
    5 - 7 - 6 - - 4 -
    1 - - - 7 3 6 - -
    - 7 - - - 9 - - 3
    - - - - - - 2 7 -"""

    example3 = """- 3 - 5 - - 8 1 -
    1 - - 7 6 - - 9 -
    4 - - - - - - - -
    8 4 3 9 7 5 1 2 6
    - 1 - 6 - - - 7 8
    6 - - 8 - 1 9 3 -
    - - - 1 5 7 - - 9
    - 9 - - 8 6 - - 1
    - 6 1 - 9 2 - 8 -"""

    class ImpossibleException(Exception): pass


    def field_from_string(field_str):
    def mapper(x):
    if x == '-': return None
    else: return int(x)
    return [map(mapper, line.split()) for line in
    field_str.split('\n')]


    def field_from_file(filename):
    f = open(filename)
    field = field_from_string(f.read())
    f.close()
    return field


    def print_field(field):
    def mapper(x):
    if x == None: return ' '
    else: return str(x)+' '
    str_rows = [map(mapper, x) for x in field]
    str_rows = ['| ' + " ".join(str_row) + '|' for str_row in str_rows]
    print 'x'+'-'*27+'x'
    print "\n".join(x for x in str_rows)
    print 'x'+'-'*27+'x'


    def check_constraint(field, (x,y), num):
    """Checks if putting num at (x,y) is valid."""
    #row constraint
    occ = [elem for elem in field[x] if elem == num]
    if occ:
    return False
    #column constraint
    occ = [field[k][y] for k in range(9) if field[k][y] == num]
    if occ:
    return False
    #subfield constraint
    sub_x, sub_y = x//3, y//3
    occ = [field[k+3*sub_x][l+3*sub_y] for k in range(3) for l in
    range(3)
    if field[k+3*sub_x][l+3*sub_y] == num]
    if occ:
    return False
    return True


    def find_cell(field):
    """Returns coords of an empty cell or None if all cells are filled.
    Returns cells with most row and column 'neighbours' first."""
    def count(row):
    return len([x for x in row if x is not None])

    #[(count, index), ... ]
    x_counts = zip((count(row) for row in field), range(9))
    sorted_x_counts = sorted(x_counts, reverse=True)
    x_keys = [l for k,l in sorted_x_counts]

    columns = [[field[k][y] for k in range(9)] for y in range(9)]
    y_counts = zip((count(column) for column in columns), range(9))
    sorted_y_counts = sorted(y_counts, reverse=True)
    y_keys = [l for k,l in sorted_y_counts]

    for x in x_keys:
    for y in y_keys:
    if field[x][y] == None:
    return (x,y)
    else:
    return None


    def set_value(field, (x,y), num):
    """Returns copy of field with cell (x,y) set to num."""
    #new_field = copy.deepcopy(field)
    new_field = [row[:] for row in field]
    new_field[x][y] = num
    return new_field


    def solve(field):
    xy = find_cell(field)
    if not xy:
    return field
    poss = [e for e in range(1,10) if check_constraint(field, xy, e)]
    for e in poss:
    new_field = set_value(field, xy, e)
    try:
    return solve(new_field)
    except ImpossibleException:
    pass #try next possibility
    raise ImpossibleException()


    if __name__ == '__main__':
    field = field_from_string(example3)
    print 'initial field:'
    print_field(field)
    print 'solution:'
    try:
    print_field(solve(field))
    except ImpossibleException:
    print 'not solvable'
     
    , Sep 18, 2005
    #11
  12. Diez B. Roggisch wrote:
    > As everyone posts his, I'll do the same :) It uses some constraint based
    > solving techniques - but not too complicated ones. When stuck, it
    > backtracks. So far it never failed me, but I haven't tested it too
    > thouroughly.


    Thanks to all for sharing. I like to program sudoku and review such
    code. So below here is my current file, I think it uses some techniques
    not yet posted here. It also has a difficult 16x16 puzzle which I know
    to be solvable (barring typing mistakes) but which my file can't solve
    before I get tired of waiting, this might draw some heavyweights in the
    ring :)

    I have also read the sudoku wiki page:

    http://en.wikipedia.org/wiki/Sudoku

    which was very helpfull and interesting (especially the link to Knuths
    paper about dancing links was nice, even though I think (but maybe
    wrongly so) that we don't need dancing links now that we've got sets,
    but it's still a very very interesting paper)

    I think the first important step is to realize that some variations
    have fewer values so that it is possible to reduce the search space
    early. Currently I'm exploring ideas about contigengies as explained in
    the wiki above which seems promising, but I haven't found a nice way to
    implement them yet. Maybe an easy optimization would be to find values
    that don't come up often and choose variations containing those. And
    maybe I should switch to an approach that has possibility values inside
    the cells instead of computing them on the fly each time, that could
    make contigency elimination easier.

    Anton


    from __future__ import generators
    from sets import Set as set

    problem1 = ['063000700','000690008','900007002',
    '002010080','050806090','090070200',
    '600100003','700045000','009000140']

    problem2 = ['030009007','010080000','000100090',
    '004905006','020000010','500607400',
    '050001000','000040020','700500030']

    problem3 = ['030500810','000760090','400000000',
    '043905006','010000070','600801930',
    '000000009','090086000','061002080']

    problem4 = ['004530080','060009000','900000005',
    '000800350','000000000','027006000',
    '800000007','000300040','090072600']

    X =[' 1 0 0 0 0 12 0 10 11 7 6 0 0 4 0 0',
    ' 0 7 0 0 15 13 0 0 0 0 2 0 0 8 0 0',
    ' 3 0 0 0 4 0 0 0 0 5 0 12 0 16 0 0',
    ' 0 0 14 2 0 9 0 0 0 0 1 0 0 0 0 0',
    '10 15 0 1 0 0 0 2 0 16 0 0 3 0 0 0',
    '12 0 0 3 0 0 15 0 0 13 0 4 0 1 9 5',
    ' 5 0 11 0 7 0 8 0 0 0 0 0 0 15 0 0',
    ' 7 13 0 16 0 0 0 6 0 0 0 14 0 10 0 0',
    ' 0 0 13 0 11 0 0 0 10 0 0 0 1 0 12 0',
    ' 0 0 7 0 0 0 0 0 0 3 0 16 0 14 0 13',
    '16 8 0 0 14 0 5 0 0 15 0 0 4 0 0 6',
    ' 0 0 0 9 0 0 4 0 1 0 0 0 2 0 0 7',
    ' 0 0 0 0 0 16 0 0 0 0 8 0 10 5 0 0',
    ' 0 0 4 0 12 0 6 0 0 0 16 7 0 0 0 14',
    ' 0 0 6 0 0 1 0 0 0 0 12 13 0 0 11 0',
    ' 0 0 15 0 0 8 11 3 2 0 9 0 0 0 0 1']

    problem5 = [row.split() for row in X]

    class State:

    def __init__(self,solved,unsolved):
    self.solved = solved
    self.unsolved = unsolved
    self.size = int((len(solved)+len(unsolved))**.25)

    def choiceset(self,x,y):
    "the set of possible choices for an empty cell"
    sz = self.size
    res = set(range(1,sz*sz+1))
    r,c = x/sz*sz,y/sz*sz
    for (i,j),v in self.solved.iteritems():
    if x == i or y == j or (r<=i<r+sz and c<=j<c+sz):
    res.discard(v)
    return res

    def celldict(self):
    """dictionary of (cellcoords,choiceset) for each empty cell
    if *any* empty cell cannot be filled return an empty dict
    to signal an illegal position
    """
    res = {}
    for x,y in self.unsolved:
    c = self.choiceset(x,y)
    if not c:
    return {}
    res[x,y] = c
    return res

    class Node:

    def __init__(self,state):
    self.state = state
    self.issolved = not bool(state.unsolved)

    def children(self):
    state = self.state
    cd = state.celldict()
    if cd: #position is still legal
    ml = min([len(x) for x in cd.itervalues()])
    #select empty cells which have the minimum number of
    choices
    items = [(k,v) for k,v in cd.iteritems() if len(v) == ml]
    (x,y),S = min(items) #arbitrary choice of cell here
    for v in S:
    solved,unsolved =
    dict(state.solved),dict(state.unsolved)
    solved[x,y] = v
    del unsolved[x,y]
    yield Node(State(solved,unsolved))

    def __repr__(self):
    R = range(self.state.size**2)
    res = [["__" for i in R] for j in R]+['']
    for (i,j),v in self.state.solved.iteritems():
    res[j] = "%02i" %v
    return '\n'.join(map(' '.join,res))

    def solutions(N):
    if N.issolved:
    yield N
    else:
    for child in N.children():
    for g in solutions(child):
    yield g

    def todicts(P):
    M = [map(int,row) for row in P]
    solved = {}
    unsolved = {}
    for i,row in enumerate(M):
    for j,x in enumerate(row):
    if x:
    solved[i,j] = x
    else:
    unsolved[i,j] = x
    return solved,unsolved

    def test():
    solved,unsolved = todicts(problem4)
    N = Node(State(solved,unsolved))
    print N
    for S in solutions(N):
    print S

    if __name__=='__main__':
    test()
     
    Anton Vredegoor, Sep 18, 2005
    #12
  13. Bas

    Gregory Bond Guest

    My current solver does 1 level of backtracking (i.e. constant space, and
    bounded time) only, and it has been able to solve every puzzle I've
    thrown at it. It's based on the usual logic and book-keeping for the
    most part. (It also explains how it comes up with each answer step as
    it goes, which is handy...)

    Once it gets to the stage where it needs to guess, it arranges all the
    unknowns then tries them in some arbitary order. It saves the state,
    applies the guess (square x,y is N) and then re-applies all the logic
    rules. There are 3 possible outcomes from here:

    - We've solved it, which is good (this happens surprisingly often....)

    - We can't solve it using this guess (so ignore this possibility,
    restore the state & try the next guess)

    - The Resulting puzzle is badly formed / inconsistant (represented by
    a python exception, naturally!) In this case, we know the guessed
    square/number is not valid, so we backtrack (restore the state before we
    made this guess), remove that possibility (x,y is N) and then apply all
    the logic rules again. Often times, this is enough to solve, but it
    usually progreses things a little even if it doesn't solve it.

    I've not yet found a (9x9) puzzle that this cannot solve. The downside
    is that it cannot detect cases where there are multiple solutions.
     
    Gregory Bond, Sep 19, 2005
    #13
  14. Op 2005-09-16, schreef <>:
    >
    > Bas ha escrito:
    >
    >> Hi group,
    >>
    >> I came across some of these online sudoku games and thought after
    >> playing a game or two that I'd better waste my time writing a solver
    >> than play the game itself any longer. I managed to write a pretty dumb
    >> brute force solver that can at least solve the easy cases pretty fast.
    >>
    >> It basically works by listing all 9 possible numbers for all 81 fields
    >> and keeps on striking out possibilities until it is done.
    >> [snip]

    >
    > This problem is desperately begging for backtracking.


    I don't think so. I regularly solve one and I never needed
    to try something out, to see if it worked or not except
    when there were muliple solutions.

    I think it is a beautifull problem, to make people think of
    how they could code some of their thought processes, which
    would be a more fruitfull experience as programming this
    with backtracking.

    --
    Antoon Pardon
     
    Antoon Pardon, Sep 19, 2005
    #14
  15. Op 2005-09-17, Tom Anderson schreef <>:
    > On Fri, 16 Sep 2005, Bas wrote:
    >
    >> -any ideas how to easily incorporate advanced solving strategies?
    >> solve(problem1) and solve(problem2) give solutions, but solve(problem3)
    >> gets stuck...

    >
    > the only way to solve arbitrary sudoku problems is to guess.


    That is strange, in al the puzzles that I have solved untill now,
    I never needed to guess, unless the puzzle had multiple solutions,
    which personnally I find inferior.

    --
    Antoon Pardon
     
    Antoon Pardon, Sep 19, 2005
    #15
  16. Gerard Flanagan, Sep 19, 2005
    #16
  17. mathschallenge.net WAS Brute force sudoku cracker

    Very interesting that sudoku solving appears on the python group - there
    is a programming competition at mathschallenge.net (euler) where one of
    the puzzles is developing a sudoku solving algorithm...

    Actually the python entrants are giving the C guys a good run!

    On Mon, 19 Sep 2005 09:12:54 +0200, Antoon Pardon
    <> wrote:

    > Op 2005-09-16, schreef
    > <>:
    >>
    >> Bas ha escrito:
    >>
    >>> Hi group,
    >>>
    >>> I came across some of these online sudoku games and thought after
    >>> playing a game or two that I'd better waste my time writing a solver
    >>> than play the game itself any longer. I managed to write a pretty dumb
    >>> brute force solver that can at least solve the easy cases pretty fast.
    >>>
    >>> It basically works by listing all 9 possible numbers for all 81 fields
    >>> and keeps on striking out possibilities until it is done.
    >>> [snip]

    >>
    >> This problem is desperately begging for backtracking.

    >
    > I don't think so. I regularly solve one and I never needed
    > to try something out, to see if it worked or not except
    > when there were muliple solutions.
    >
    > I think it is a beautifull problem, to make people think of
    > how they could code some of their thought processes, which
    > would be a more fruitfull experience as programming this
    > with backtracking.
    >
     
    Caleb Hattingh, Sep 19, 2005
    #17
  18. Bas

    Guest

    , Sep 21, 2005
    #18
  19. Bas

    Tom Anderson Guest

    On Wed, 21 Sep 2005 wrote:

    > Excellent strategies are provided by Dan Rice's blog:
    > http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html


    There's an interesting remark in this post:

    http://sudokublog.typepad.com/sudokublog/2005/08/where_do_sudoko.html

    "Some Sudoku generators skip the step of generating a board altogether.
    It's enough to place some random numbers in the board and see if it has a
    solution. For a backtracking solver, which can solve puzzles very quickly,
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    the time wasted analyzing impossible sets of clues will be minor. For a
    human-style solver, it seems reasonable to exclude the possibility of
    self-contradictory clues by first generating a consistent underlying
    board."

    He seems to think that backtrackers are faster than reasoners. That's
    somewhat counter-intuitive; i wonder if it's really true. It would
    certainly be rather sad if it was.

    > You won't find any better solver than this:
    > http://sudoku.sourceforge.net/


    That's a fairly straightforward backtracker. In fact, it's the solver
    which inspired me to write mine - which i believe has a more sophisticated
    heuristic (i haven't compared them formally, but my heuristic
    sophistication estimation heuristic - which is itself, of course, fairly
    sophisticated - suggests that it is). Clearly, what we need is a sudoku
    solver shootout.

    tom

    --
    everything from live chats and the Web, to the COOLEST DISGUSTING PORNOGRAPHY AND RADICAL MADNESS!!
     
    Tom Anderson, Sep 21, 2005
    #19
  20. Bas

    Tom Anderson Guest

    On Mon, 19 Sep 2005, Antoon Pardon wrote:

    > Op 2005-09-17, Tom Anderson schreef <>:
    >> On Fri, 16 Sep 2005, Bas wrote:
    >>
    >>> -any ideas how to easily incorporate advanced solving strategies?
    >>> solve(problem1) and solve(problem2) give solutions, but
    >>> solve(problem3) gets stuck...

    >>
    >> the only way to solve arbitrary sudoku problems is to guess.

    >
    > That is strange, in al the puzzles that I have solved untill now, I
    > never needed to guess, unless the puzzle had multiple solutions, which
    > personnally I find inferior.


    Well, if we are to believe Lance Fortnow, a fairly expert comptational
    complexionist, that's probably not generally true:

    http://weblog.fortnow.com/2005/08/sudoku-revisited.html

    It's this bit:

    "Since we don't believe that NP has fast probabilistic algorithms, we
    expect that there are no efficient procedures to completing a generalized
    Sudoku grid"

    That makes me think that there probably isn't a non-backtracking method,
    since that would almost certainly be polynomial-time.

    The thing is, the puzzles you encounter in the wild have been designed to
    be solved by humans, using non-backtracking methods; they're much easier
    to solve than the general class of Sudoku.

    tom

    --
    everything from live chats and the Web, to the COOLEST DISGUSTING
    PORNOGRAPHY AND RADICAL MADNESS!!
     
    Tom Anderson, Sep 21, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Apps
    Replies:
    3
    Views:
    7,837
    Alvin Bruney [MVP - ASP.NET]
    May 26, 2005
  2. David List

    Re: brute force

    David List, Aug 22, 2003, in forum: C++
    Replies:
    4
    Views:
    608
    Karl Heinz Buchegger
    Aug 22, 2003
  3. Stuart Golodetz

    Re: brute force

    Stuart Golodetz, Aug 22, 2003, in forum: C++
    Replies:
    2
    Views:
    491
    Stuart Golodetz
    Aug 23, 2003
  4. ago
    Replies:
    11
    Views:
    688
    Anton Vredegoor
    Jan 20, 2006
  5. Boon

    Yet another brute force sudoku solver

    Boon, Oct 16, 2008, in forum: C Programming
    Replies:
    34
    Views:
    1,130
    user923005
    Oct 24, 2008
Loading...

Share This Page