test_sudoku_mieux.py 21.2 KB
Newer Older
1
2
3
4
5
6


import numpy as np
import random
import copy

7
8
## REMARQUES
#les indices x et y sont parfois inversés à cause de la convention mathématique (y puis x)
9
#pour enlever les 0 au debut et fin : np.trim_zeros
10
# il faut changer xIndex et yIndex en hIndex et vIndex...
11

12

13
14
15
class Grid (object) :

    def __init__ (self, grid) :
16
17
18
        """ tempGrid corresponds to the grid where the little numbers are written
            Because of python, the third dimension is of length 9 all the time
        """
19
        self.grid = grid
20
21
22
23
24
25
26
        someGrid = np.zeros((9,9,9))
        for k in range (9) :
            for i in range (9) :
                someGrid[k,i,0] = grid[k,i]
        self.tempGrid = someGrid
        #self.tempGrid = grid[:,:,np.newaxis] #to make it a 3D array and not 2D

Antoine Roux's avatar
Antoine Roux committed
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    def __str__ (self) :
        string = ""
        string += " -----------------------" + "\n"
        for k in range (9) :
            for i in range (9) :
                if (i==0) or (i == 3) or (i == 6):
                    string += "|" + " "
                string += str(int(self.grid[k,i])) + " "
            string += "|"
            string += "\n"
            if (k == 2) or (k==5) :
                string += "|-----------------------|" + "\n"
        string += " -----------------------" + "\n"
        return string
41

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
    def verify(self) :
        """ verifies that finished grid is correct
            by checking that all sums of blocks, lines and columns equal 45
            returns : True if grid is correct, False otherwise
        """
        for k in range (9) :
            currentColumn = myGrid.getColumn(k)
            if (np.sum(currentColumn.column) != 45) :
                return False
            currentLine = myGrid.getLine(k)
            if (np.sum(currentLine.line) != 45) :
                return False

        for k in range (3) :
            for i in range (3) :
                currentBlock = myGrid.getBlock(k,i)
                if (np.sum(currentBlock.block) != 45) :
                    return False
        return True

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
116
117
118
119
120
121
122
123
124
125
126
127
    def getBlock (self, xIndex, yIndex) :
        index1 = 3 * yIndex
        index2 = 3 + 3 * yIndex
        index3 = 3 * xIndex
        index4 = 3 + 3 * xIndex
        return Block(self.grid[index1:index2, index3:index4], xIndex, yIndex)

    def getLine (self, myIndex) :
        return Line(self.grid[myIndex, :], myIndex)

    def getColumn (self, myIndex) :
        return Column(self.grid[:, myIndex], myIndex)

    def getTile (self, xIndex, yIndex) :
        return Tile(self.grid[xIndex, yIndex], xIndex, yIndex)

    def searchForTwoOutOfThree (self) :
        """
        searches for lines/columns of blocks in which we know 2 identical numbers
        if found, we put them where they belong
        """
        #vertically
        for k in range (3) :
            #one for each group of 3 columns
            for i in range (1, 10) :
                numberOfOccurences = 0
                columnsWhereFound = []
                blocksWhereFound = []
                for j in range (3) :
                    #one for each of column of the groups
                    currentColumn = self.getColumn(3*k+j)

                    if (i in currentColumn.column) :
                        numberOfOccurences += 1
                        columnsWhereFound.append(3*k+j)
                        columnInList = currentColumn.column.tolist() #we use "tolist" because index doesnt work on ndarrays
                        blocksWhereFound.append(columnInList.index(i)//3)

                if (numberOfOccurences == 2) :
                    #In that case we have to find if the number of possibilities for the third number in
                    #the group of 3 columns is equal to 1

                    #We find the column and block to study
                    if (3*k not in columnsWhereFound) :
                        columnToStudy = 3*k
                    elif (3*k+1 not in columnsWhereFound) :
                        columnToStudy = 3*k+1
                    else :
                        columnToStudy = 3*k+2

                    if (0 not in blocksWhereFound) :
                        blockToStudy = 0
                    elif (1 not in blocksWhereFound) :
                        blockToStudy = 1
                    else :
                        blockToStudy = 2

                    #We find the 3 vertically aligned tiles to study
                    blockStudied = myGrid.getBlock(k, blockToStudy)
                    tilesStudied = blockStudied.block[:, columnToStudy%3]

                    #Now we check if 2 out of 3 tiles are filled
                    #if it is the case we can fill the last one
                    if (np.count_nonzero(tilesStudied) == 2) :
                        indicesNotZero = np.array(np.nonzero(tilesStudied))
                        if (0 not in indicesNotZero) :
128
129
                            tileToModify = myGrid.getTile(3*blockToStudy,columnToStudy)
                            #myGrid.grid[3*blockToStudy,columnToStudy] = i
130
                        elif (1 not in indicesNotZero) :
131
132
                            tileToModify = myGrid.getTile(3*blockToStudy+1,columnToStudy)
                            #myGrid.grid[3*blockToStudy+1,columnToStudy] = i
133
                        else :
134
135
136
                            tileToModify = myGrid.getTile(3*blockToStudy+2,columnToStudy)
                            #myGrid.grid[3*blockToStudy+2,columnToStudy] = i
                        tileToModify.modifyValue(tileToModify.xIndex, tileToModify.yIndex, i)
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
                #il reste encore à gérer le cas où les deux autres tuiles ont encore plusieurs possibilités mais qu'on peut quand même conclure

        #horizontally
        for k in range (3) :
            #one for each group of 3 lines
            for i in range (1, 10) :
                numberOfOccurences = 0
                linesWhereFound = []
                blocksWhereFound = []
                for j in range (3) :
                    #one for each of column of the groups
                    currentLine = self.getLine(3*k+j)

                    if (i in currentLine.line) :
                        numberOfOccurences += 1
                        linesWhereFound.append(3*k+j)
                        lineInList = currentLine.line.tolist() #we use "tolist" because index doesnt work on ndarrays
                        blocksWhereFound.append(lineInList.index(i)//3)

                if (numberOfOccurences == 2) :
                    #In that case we have to find if the number of possibilities for the third number in
                    #the group of 3 columns is equal to 1
                    #We find the column and block to study
                    if (3*k not in linesWhereFound) :
                        lineToStudy = 3*k
                    elif (3*k+1 not in linesWhereFound) :
                        lineToStudy = 3*k+1
                    else :
                        lineToStudy = 3*k+2
                    if (0 not in blocksWhereFound) :
                        blockToStudy = 0
                    elif (1 not in blocksWhereFound) :
                        blockToStudy = 1
                    else :
                        blockToStudy = 2

                    #We find the 3 vertically aligned tiles to study
                    blockStudied = myGrid.getBlock(blockToStudy, k)
                    tilesStudied = blockStudied.block[lineToStudy%3]

                    #Now we check if 2 out of 3 tiles are filled
                    #if it is the case we can fill the last one
                    if (np.count_nonzero(tilesStudied) == 2) :
                        indicesNotZero = np.array(np.nonzero(tilesStudied))
                        if (0 not in indicesNotZero) :
182
183
                            tileToModify = myGrid.getTile(lineToStudy, 3*blockToStudy)
                            #myGrid.grid[lineToStudy, 3*blockToStudy] = i
184
                        elif (1 not in indicesNotZero) :
185
186
                            tileToModify = myGrid.getTile(lineToStudy, 3*blockToStudy+1)
                            #myGrid.grid[lineToStudy, 3*blockToStudy+1] = i
187
                        else :
188
189
190
                            tileToModify = myGrid.getTile(lineToStudy, 3*blockToStudy+2)
                            #myGrid.grid[lineToStudy, 3*blockToStudy+2] = i
                        tileToModify.modifyValue(tileToModify.xIndex, tileToModify.yIndex, i)
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
                #il reste encore à gérer le cas où les deux autres tuiles ont encore plusieurs possibilités mais qu'on peut quand même conclure

class Block (object) :

    def __init__ (self, block, xIndex, yIndex) :
        self.block = block
        self.xIndex = xIndex
        self.yIndex = yIndex

    def checkIfTrivial (self) :
        """ returns :
           true if there is only one number missing, false otherwise
           position of number to change
           value to put
        """
        flattenedArray = self.block
        numberOfZeros = np.count_nonzero(flattenedArray)
        if numberOfZeros == 8 :
            positionOfZero = np.argmin(flattenedArray)
            for k in range (1,10) :
                if (k not in flattenedArray) :
                    valueToPut = k
            return (True, positionOfZero, valueToPut)
214
        return (False, -1, -1)
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

class Line (object) :

    def __init__ (self, line, index) :
        self.line = line
        self.index = index

    def checkIfTrivial (self) :
        """ returns :
           true if there is only one number missing, false otherwise
           position of number to change
           value to put
        """
        flattenedArray = self.line
        numberOfZeros = np.count_nonzero(flattenedArray)
        if numberOfZeros == 8 :
            positionOfZero = np.argmin(flattenedArray)
            for k in range (1,10) :
                if (k not in flattenedArray) :
                    valueToPut = k
            return (True, positionOfZero, valueToPut)
236
        return (False, -1, -1)
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257

class Column (object) :

    def __init__ (self, column, index) :
        self.column = column
        self.index = index

    def checkIfTrivial (self) :
        """ returns :
           true if there is only one number missing, false otherwise
           position of number to change
           value to put
        """
        flattenedArray = self.column
        numberOfZeros = np.count_nonzero(flattenedArray)
        if numberOfZeros == 8 :
            positionOfZero = np.argmin(flattenedArray)
            for k in range (1,10) :
                if (k not in flattenedArray) :
                    valueToPut = k
            return (True, positionOfZero, valueToPut)
258
        return (False, -1, -1)
259
260
261
262
263
264
265
266

class Tile (object) :

    def __init__ (self, value, xIndex, yIndex) :
        self.value = value
        self.xIndex = xIndex
        self.yIndex = yIndex

267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
    def getNeighbors(self) :
        """ checks the neighbors of the tile,
            returns a list of the neighbors without duplicates
        """
        allNeighbors = []
        allNeighbors.append(myGrid.getBlock(self.yIndex//3, self.xIndex//3).block.flatten())
        allNeighbors.append(myGrid.getLine(self.xIndex).line)
        allNeighbors.append(myGrid.getColumn(self.yIndex).column)
        allNeighborsFlat = np.array(allNeighbors).flatten()
        allNeighborsNoDuplicates = list(set(allNeighborsFlat))
        allNeighborsNoDuplicates.remove(0)
        return(allNeighborsNoDuplicates)

    def evaluate(self) :
        """ gets the neighbors using getNeighbors
282
283
            if there is only one missing, in that case we modify the tiles
            if there are multiples choices, we put them in the tempGrid
284
            doesn't return anything, except -1 if tile is not 0
285
        """
286
287
        if (self.value != 0) :
            return -1
288

289
290
291
292
        #we first check if there is only one possibility in the tempGrid
        possibilitiesNonZero = np.trim_zeros(myGrid.tempGrid[self.xIndex, self.yIndex])
        if (len(possibilitiesNonZero) == 1) :
            self.modifyValue(self.xIndex, self.yIndex, myGrid.tempGrid[self.xIndex, self.yIndex, 0])
293

294
295
296
297
298
299
300
301
302
303
304
305
306
307
        #we now compute the neighbors as usual
        neighbors = np.array(self.getNeighbors())

        if (len(neighbors) == 8) :
            for k in range(1,10) :
                if k not in neighbors :
                    #we modify the value of the tile
                    self.modifyValue(self.xIndex, self.yIndex, k)

        else :
            for k in range(1,10) :
                if (k not in neighbors) and (k not in myGrid.tempGrid[self.xIndex, self.yIndex]) :
                    someArray = np.delete(myGrid.tempGrid[self.xIndex, self.yIndex], 8)
                    myGrid.tempGrid[self.xIndex, self.yIndex] = np.append(k, someArray)
308

309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
    def modifyValue (self, xIndex, yIndex, value) :
        """ Once we found the value of a tile, we modify it
            We also modify the possible values of all of the neighbors of the tile
        """
        #we modify the value of the tile
        myGrid.grid[self.xIndex, self.yIndex] = value
        myGrid.tempGrid[self.xIndex, self.yIndex, 0] = value
        myGrid.tempGrid[self.xIndex, self.yIndex, 1:9] = 0

        #we modify the possible values of the neighbors : block
        xIndexBlock = self.yIndex//3
        yIndexBlock = self.xIndex//3
        for k in range (3) :
            for i in range (3) :
                possibleTileValuesList = list(myGrid.tempGrid[3*xIndexBlock+k, 3*yIndexBlock+i])
                if (value in possibleTileValuesList) :
                    #in that case we have to remove "value" from the possibilities
                    possibleTileValuesList.remove(value)
                    possibleTileValuesList.append(0)
                    myGrid.tempGrid[3*xIndexBlock+k, 3*yIndexBlock+i] = np.array(possibleTileValuesList)

        #we modify the possible values of the neighbors : line
        for k in range (9) :
            possibleTileValuesList = list(myGrid.tempGrid[xIndex, k])
            if (value in possibleTileValuesList) :
                #in that case we have to remove "value" from the possibilities
                possibleTileValuesList.remove(value)
                possibleTileValuesList.append(0)
                myGrid.tempGrid[xIndex, k] = np.array(possibleTileValuesList)

        #we modify the possible values of the neighbors : column
        # for k in range (9) :
            possibleTileValuesList = list(myGrid.tempGrid[k, yIndex])
            if (value in possibleTileValuesList) :
                #in that case we have to remove "value" from the possibilities
                possibleTileValuesList.remove(value)
                possibleTileValuesList.append(0)
                myGrid.tempGrid[k, yIndex] = np.array(possibleTileValuesList)
347

348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
    def narrowPossibilities(self) :
        """ Once ALL tiles have been evaluated, we can check if the possibilities for one number are only for one tile
            doesn't return anything, except -1 if the tile is already known
        """

        if (self.value != 0) :
            return -1

        #first we check for the block
        blockPossibilities = np.array(myGrid.tempGrid[(self.xIndex//3)*3 : (self.xIndex//3)*3+3, (self.yIndex//3)*3 : (self.yIndex//3)*3+3])
        # for k in range (9) :
        #     if (len(np.array(np.nonzero(blockPossibilities[k])).flatten()) == 1) :
        #         #meaning if we already know the value of the tile
        #         blockPossibilities[k] = 0
        blockPossibilities = np.reshape(blockPossibilities, (1,81))
        blockPossibilities = np.sort(blockPossibilities[0])
        blockPossibilities = np.trim_zeros(blockPossibilities)
        #we now have a list of all the possibilities for the tiles from the block
        #if one of the possibilities only appears one, we know where we can put it
        singles = [x for x in list(blockPossibilities) if list(blockPossibilities).count(x) == 1]

        #now we have to check if the singles are part of this tile's possibilities
        for k in singles :
            if k in myGrid.tempGrid[self.xIndex, self.yIndex] :
                self.modifyValue(self.xIndex, self.yIndex, k)

        #then we check for the line
        linePossibilities = np.array(myGrid.tempGrid[self.xIndex, :])
        linePossibilities = np.reshape(linePossibilities, (1,81))
        linePossibilities = np.sort(linePossibilities[0])
        linePossibilities = np.trim_zeros(linePossibilities)
        #we now have a list of all the possibilities for the tiles from the line
        #if one of the possibilities only appears one, we know we can put it
        singles = [x for x in list(linePossibilities) if list(linePossibilities).count(x) == 1]

        #now we have to check if the singles are part of this tile's possibilities
        for k in singles :
            if k in myGrid.tempGrid[self.xIndex, self.yIndex] :
                self.modifyValue(self.xIndex, self.yIndex, k)

        #finally we check for the column
        columnPossibilities = np.array(myGrid.tempGrid[:,self.yIndex])
        columnPossibilities = np.reshape(columnPossibilities, (1,81))
        columnPossibilities = np.sort(columnPossibilities[0])
        columnPossibilities = np.trim_zeros(columnPossibilities)
        #we now have a list of all the possibilities for the tiles from the column
        #if one of the possibilities only appears one, we know we can put it
        singles = [x for x in list(columnPossibilities) if list(columnPossibilities).count(x) == 1]

        #now we have to check if the singles are part of this tile's possibilities
        for k in singles :
            if k in myGrid.tempGrid[self.xIndex, self.yIndex] :
                self.modifyValue(self.xIndex, self.yIndex, k)

    def checkIfTrivial(self) :
        """ We use the three methods checkIfTrivial for the block, line and column the tile belongs to
            Doesn't return anything, except -1 if tile is already known
        """
        if (self.value != 0) :
            return -1

        #for the block
        currentBlock = myGrid.getBlock(self.yIndex//3, self.xIndex//3)
        trivialityArray = currentBlock.checkIfTrivial()
        if trivialityArray[0] == True:
            self.modifyValue(self.xIndex, self.yIndex, trivialityArray[2])
        #for the line
        currentLine = myGrid.getLine(self.xIndex)
        trivialityArray = currentLine.checkIfTrivial()
        if trivialityArray[0] == True :
            self.modifyValue(self.xIndex, self.yIndex, trivialityArray[2])
        #for the column
        currentColumn = myGrid.getLine(self.yIndex)
        trivialityArray = currentColumn.checkIfTrivial()
        if trivialityArray[0] == True :
            self.modifyValue(self.xIndex, self.yIndex, trivialityArray[2])
424

425
426
###########################################

427
428
429
430
431
432
433
434
435
436
# TEST_GRID = np.array([[  0,  4,  7,  27,  36,  45,  54,  63,  72.],
#                       [  1,  5,  8,  28,  37,  46,  55,  64,  73.],
#                       [  2,  6,  3,  29,  38,  47,  56,  65,  74.],
#                       [  3,  9,  1,  30,  39,  48,  57,  66,  75.],
#                       [  4,  8,  1,  31,  40,  49,  58,  67,  76.],
#                       [  5,  7,  2,  32,  41,  50,  59,  68,  77.],
#                       [  6,  1,  4,  33,  42,  51,  60,  69,  78.],
#                       [  7,  2,  5,  34,  43,  52,  61,  70,  79.],
#                       [  8,  3,  9,  35,  44,  53,  62,  71,  80.]])

437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
TEST_GRID_1 = np.array([[  0,  0,  0,  4,  0,  0,  8,  7,  0.],
                        [  0,  4,  7,  0,  9,  2,  0,  5,  0.],
                        [  2,  0,  0,  6,  0,  0,  0,  3,  0.],
                        [  9,  7,  0,  5,  0,  0,  2,  0,  3.],
                        [  5,  0,  8,  0,  2,  4,  7,  0,  6.],
                        [  6,  0,  4,  0,  0,  7,  0,  8,  5.],
                        [  0,  9,  0,  3,  0,  8,  0,  0,  7.],
                        [  0,  0,  3,  2,  4,  0,  1,  6,  0.],
                        [  0,  1,  2,  0,  0,  0,  0,  9,  0.]])

TEST_GRID_2 = np.array([[  0,  3,  2,  0,  8,  0,  0,  0,  0.],
                        [  8,  0,  1,  0,  0,  0,  9,  0,  3.],
                        [  0,  0,  0,  6,  0,  3,  0,  0,  0.],
                        [  0,  2,  0,  0,  5,  7,  4,  0,  6.],
                        [  5,  0,  0,  4,  0,  6,  0,  0,  2.],
                        [  7,  0,  4,  8,  3,  0,  0,  9,  0.],
                        [  0,  0,  0,  5,  0,  1,  0,  0,  0.],
                        [  0,  0,  8,  0,  0,  0,  7,  0,  1.],
                        [  4,  0,  0,  0,  7,  0,  6,  3,  0.]])

TEST_GRID_3 = np.array([[  8,  0,  0,  0,  0,  0,  0,  0,  0.],
                        [  0,  0,  3,  0,  0,  0,  0,  0,  0.],
                        [  0,  7,  0,  6,  9,  0,  2,  0,  0.],
                        [  0,  5,  0,  0,  0,  7,  0,  0,  0.],
                        [  0,  0,  0,  0,  4,  5,  7,  0,  0.],
                        [  0,  0,  0,  1,  0,  0,  0,  9,  0.],
                        [  0,  0,  1,  0,  0,  0,  0,  0,  8.],
                        [  0,  0,  8,  5,  0,  0,  0,  0,  0.],
                        [  0,  9,  0,  0,  0,  0,  4,  3,  0.]])

467
TEST_GRID = TEST_GRID_2
468
469
470

myGrid = Grid(copy.deepcopy(TEST_GRID))

471
compteur = 0
472
while (myGrid.verify() != True and compteur<3) :
473
474
475
476
477
478
    compteur+=1
    for k in range (9) :
        for i in range (9) :
            myGrid.searchForTwoOutOfThree()
            someTile = myGrid.getTile(i,k)
            someTile.evaluate()
479

480
481
482
483
484
485
486
print(Grid(myGrid.grid - TEST_GRID))
print(myGrid)

for k in range (9) :
    for i in range (9) :
        someTile = myGrid.getTile(i,k)
        someTile.checkIfTrivial()
487
print(myGrid)