Sudoku Solver in Python

Question

So, I'm trying to create a function that will take in a list of lists, each consisting of 9 integers numbered 1 through 9, and return a Boolean if it is a valid solution to for a Sudoku. Right now, I've managed to solve part of the problem with checking for rows and columns, but I am stuck on the implementation of checking the three by three boxes. Here's my code so far.

alist = [1,2,3,4,5,6,7,8,9]

def checkSudoku(grid):
    a = grid
    b = grid
    c = grid
    d = False
    e = False
    f = False
    newlist = []
    for i in a:
        i.sort()
        if i == alist:
            d = True
        else:
            d = False
            break
    for j in range(9):
        for k in b:
            newlist.append(k)

        newlist.sort()
        if i == alist:
            e = True
            newlist = []
        else:
            e = False
            break

    if d == True and e == True:
        return True
    else:
        return False

Basically, My was to test all three factors necessary for it to be true, then return True if all three are True, else return false. Any help?

Good news: someone has already solved this exact problem. http://norvig.com/sudoku.html — Casey, Apr 22 '14 at 01:59
A suggestion to improve your code: Use better variable names. I cannot poosibly know what your `a` through `f` variables mean without digging through a bunch of code. If they had meaninful names, I might be able to see issues immediately. Single letter variable names are often bad except in very limited situations (`i` and `j` are often traditional index variables in loops, and `x`, `y` and `z` have long mathematical tradition as coordinate names, etc). — Blckknght, Apr 22 '14 at 02:08
Any time you are setting a variable to `False`, you could just be returning `False`. You may also be interested in taking a look at the `set` class. — U2EF1, Apr 22 '14 at 02:09
@emodendroket If this question has been solved elsewhere on Stack Overflow, then this could be marked as duplicate. However there's nothing wrong with asking a question that has been answered externally. — SimonT, Apr 22 '14 at 02:09
@SimonT It wasn't meant as a criticism. Is there something wrong with posting a link to an offsite solution to a problem? — Casey, Apr 22 '14 at 02:14
@emodendroket No there isn't, I misunderstood your intention. My bad. — SimonT, Apr 22 '14 at 02:18

score 1 · Answer 1 · answered Apr 22 '14 at 02:07

Not sure if this is your problem, but there is a pretty obvious problem with this code:

a = grid
b = grid
c = grid

It looks like you think this creates 3 copies of the grid, but it doesn't. It creates three different references to the same object. This means that your i.sort() on a will affect the logic on b later on.

What you should do is actually copy the object. That it's a nested list makes this a little bit tricky, but an easy way to do this is with the library function deepcopy:

a = copy.deepcopy(grid)
b = copy.deepcopy(grid)
c = copy.deepcopy(grid)

A simpler fix might be to make the copy when you're doing the sorting of a sublist, using the `sorted` function. Then there's no need to have multiple grid copies at all! — Blckknght, Apr 22 '14 at 02:10

score 1 · Answer 2 · edited May 23 '17 at 11:57

One major problem with how your code works is that you're using list.sort, meaning that grid itself changes. Consider using sorted, which works with all iterables and returns a copy instead:

for row in grid:
    if sorted(row) == alist:
        # now you know that the row contains all ints 1-9.

This also means you don't need to try to manually duplicate grid. If you need help duplicating a list (especially a multidimensional list) check out this question.

As for checking each 3x3 box: iterate through each of the 9 "top left" corners first like so:

for x in (0,3,6):
    for y in (0,3,6):
        subgrid = grid[y][x:x+3] + grid[y+1][x:x+3] + grid[y+2][x:x+3]
        if sorted(subgrid) == alist:
            # do your thing

For help with list slicing check this out.

Sudoku Solver in Python

2 Answers2