Python Sudoku Reduce the number of for loops

Question

I am trying to solve the sudoku problem and I need to add all the tuples that satisfy the constraint.

Here is the problem,

The variables contain non-repeated number from 0 to 9 in sorted order. The domain of each variable can be different.

Eg:

v1 = [1,2,3,4]

v2 = [3,4,6,7]

v3 = [3,5,7,8,9]

...

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

I want all sets of number where there is no repeated number,

I have come up with the following cumbersome and slow algorithm, but is there a better way to do this?

for d0 in v1:
        for d1 in v2:
            ... 
                for d9 in v9:
                    if d0 != d1 and d0 != d2 and d0 != d3 ... d0 != d9
                        ...
                        and d7 != d8 and d7 != d9:
                        and d8 != d9:

                        print(d0,d1,d2,d3,d4,d5,d6,d7,d8,d9)

Is there a more effective way of doing it without using 9 for loops and a long list of and statements??

I can't use the constraint solver like python-constraint since I need to implement it.

Answer 1

I found the solution myself,

So freaking simple, just subtract the current value from the domain of the next list to prevent it from getting selected.

for d0 in v1:
    for d1 in list(set(v2) - set(d0)):
        ... 
            for d9 in list(set(v9) - set(d1,d2,d3,d4,d5,d6,d7,d8,d9):
                print(d0,d1,d2,d3,d4,d5,d6,d7,d8,d9)

Answer 2

I wrote a sudoku solver a while back for fun...

I've posted the code for your reference. It's actually really efficient. I also explain it at the end.

#imports
import sys
import time

#test sudoku puzzle
a =  [[0, 6, 0, 1, 3, 0, 0, 0, 8],
     [0, 0, 2, 0, 0, 6, 0, 0, 0],
     [1, 8, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 7, 0, 4, 2, 0, 0, 0],
     [5, 0, 0, 0, 0, 0, 0, 0, 9],
     [0, 0, 0, 5, 9, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 9, 2],
     [0, 0, 0, 7, 0, 0, 3, 0, 0],
     [7, 0, 0, 0, 1, 3, 0, 4, 0]]

'''
a = [[0, 0, 4, 0],
     [0, 2, 0, 3],
     [2, 0, 0, 0],
     [0, 4, 0, 1]]
'''

#store all of the cells that have been solved already
solved = {}
for p in range(len(a)):
    for q in range(len(a)):
        if a[p][q] != 0:
            solved[p, q] = 1

#denotes what direction the code is moving (if it is moving backwards, then we want the already solved cells to return, and if it is moving forwards, we want the solved cells to call next)
goingForward = True
#if the sudoku is solved or not
done = False
# number of iterations
counter = 0



#prints a sudoku neatly
def printSudoku(a):
    for i in a:
        array = ""
        for j in i:
            array += str(j) + " "
        print array

def next(i, j, a):
    global counter
    global goingForward
    global done

    if done:
        return
    counter += 1
    # gets the vertical in which a[i][j] is located
    vertical = [z[j] for z in a]


    # gets the "box" in which a[i][j] is located
    box = []
    x = (i/3 + 1)*3
    y = (j/3 + 1)*3
    for p in range(x-3, x):
        for q in range(y-3, y):
            box.append(a[p][q])

    #if it already solved and it is going forward, call next
    #else, return
    if solved.has_key((i, j)):
        if i == 8 and j == 8:
            done = True
            printSudoku(a)
            return
        if goingForward:
            if j==8:
                next(i+1, 0, a)
            else:
                next(i, j+1, a)
        else:
            return

    #try every number for cell a[i][j]
    #if none work, return so that the previous number may be changed
    else:
        for k in range(1, 10):
            if k not in a[i] and k not in vertical and k not in box:
                a[i][j] = k
                if i == 8 and j == 8:
                    done = True
                    printSudoku(a)
                    return
                if j==8:
                    goingForward = True
                    next(i+1, 0, a)
                    a[i][j] = 0
                else:
                    goingForward = True
                    next(i, j+1, a)
                    a[i][j] = 0
    goingForward = False
    return

start_time = time.time()
#where we actually call the function
next(0, 0, a)
if done == False:
    print "no solution!!"
print "It took " + str(time.time()-start_time) + " to solve this sudoku"
print "With " + str(counter) + " iterations"

This uses a technique called recursive backtracking. It starts at the very first cell and tries all possible values. If it finds a possible solution, then it keeps that value and goes on the next cell. For that cell, it employs the same method, trying all values from 1-9 until one works, then moving to the next cell. When it encounters a cell for which no values work, it gives up and goes to the previous cell, where it is determined that that particular value does not work and a new one must be used. The previous cell skips the errant value and goes to the next integer. Through a combination of backtracking and guessing, it eventually arrives at the correct answer.

It's also super speedy since a lot of the cases are skipped due to the error backtracking. For most "guessed" values, it does not get past the third or fourth cell.