Sudoku Solver in Python

0
votes

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?

2
pythonsudoku
Good news: someone has already solved this exact problem. norvig.com/sudoku.html - Casey
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
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
@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
@SimonT It wasn't meant as a criticism. Is there something wrong with posting a link to an offsite solution to a problem? - Casey

2 Answers

1
votes

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)
1
votes

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.