editing lists / sudoku solver

[monagro]

Hi all,

Effectively what I'm trying to do is to write a sudoku solver in python. I wrote one in Matlab a while ago at undergraduate, so I have a basic idea of how to do so. I'm running it on Spyder as part of the latest Anaconda package.

My approach is to create 2 matrices using lists. Here list A is 2 dimensional representing the sudoku, and all unknown numbers are set to 0. List M is 3 dimensional, where the 3rd dimension indicates for which number it would be possible to have the value: a 1 if it is still possible, a 0 if not.
For example if A[2][2] = 4 (in the sudoku, the third row and 3rd column shows a 4), then A[2][1] cannot be 4, so M[2][1][4 - 1] must be 0 (minus one because python lists start at zero).
However A[3][3] can still be 4, so M[3][3][4-1] should still be 1.

To set these values to zero, I've written the following:

1 2 3 4 5 6 7 8 9 10 11 12 13

if A[i][j] > 0 :                       """set this row to no longer being able to     use this number - dummy variable a """                       for a in range(9):         M[a][j][ A[i][j] - 1 ] = 0                       """set this column to no longer being able to     use this number - dummy variable a """                   for a in range(9):         M[i][a][ A[i][j] - 1 ] = 0

However this sets all 4th numbers in the entire M to zero, so both M[2][1][3] and M[3][3][3].
What am I doing wrong?




Full code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

def openfile(csvfile):           """Open matrix from csv file (comma delimited only)"""           import csv       matrix = []       with open(csvfile, newline = '') as inputfile:                  for row in csv.reader(inputfile) :             for i in range(len(row)):                 row[i] = int(row[i])             matrix.append(row)           return matrix           """ START PROGRAMME"""   """import matrix """   startmatrix = openfile('matrixinput.csv')     """Create full possibilities matrix A & M - dummy variable a""" M = [] a = []   A = startmatrix   for i in range(9) :     a.append([1, 1, 1, 1, 1, 1, 1, 1, 1])       for i in range(9) :     M.append(a)     """ run sodoku solver """       """ Function to solve Sudokus without guessing, adding something in to keep it running until finished   A is 2D matrix solution M is 3D matrix of possibilities (1s & 0s) """ flag = 0   AA = [] MM = []   while flag == 0:           """ Update matrix           Stop cycling if neither A nor M changed """           AA = A     MM = M                   for i in range(9) :         for j in range(9) :             if A[i][j] > 0 :                                   """set this row to no longer being able to                 use this number - dummy variable a """                                   for a in range(9):                     M[a][j][ A[i][j] - 1 ] = 0                                   """set this column to no longer being able to                 use this number - dummy variable a """                               for a in range(9):                     M[i][a][ A[i][j] - 1 ] = 0                                   """set this quadrant to 0 for this value, dummmy variables:                     a - which quadrant row                     b - which quadrant column                     l , k - dummy variables                     """                 a = round( i / 3 - 0.48 , 0)                 b = round( j / 3 - 0.48 , 0)                                   for l in range(3) :                     for k in range(3):                         M[3*a + l][3*b + k][A[i][j]-1] = 0                               """Clear all other possibilities from A[i][j], dummy = a                 but ensure the correct value is a possibility                 """                                   for a in range(9) :                     M[i][j][a] = 0                                       M[i][j][A[i][j]-1] = 1                                   """ If there is only one possibility left, update A                 """                              else :                 if sum(M[i][j][:]) == 1 :                     a = M[i][j][:].index(1) + 1                     A[i][j] = a           if M == MM and A == AA :         flag = 1             print(A)   print(M)

[Gribouillis]

I think the problem is with the creation of M because you fill M with 9 pointers to the same copy of a 2D matrix. Instead of this, you can try to define M with the following statement

1	M = [[[1 for i in range(9)] for j in range(9)] for k in range(9)]

[monagro]

Thank you! That worked!

Can you explain why this worked and the other thing did not?

I'm also running into a second issue: later on, the while loop stops running too early. Somehow when I change M, MM also gets changed, and similarly when I change A, AA also gets changed. Do you understand why it does not simply remains constant?

[ljmetzger]

You are pointing to the same list as you discovered - mutable vs immutable.

You can use one of the following:

1 2 3 4 5 6

import copy   b = a[:] b = list(a) b = copy.copy(a) b = copy.deepcopy(a)

See the following for a discussion of the code above: https://stackoverflow.com/questions/2612...opy-a-list

Lewis

[sylas]

For sudoku solver, you may find what you search, looking at "Project kudoSudoku follows SUDO project", at the GUI forum.

[monagro]

Thank you all, very interesting. The solver works :D