Проблема с алгоритмом обратной матрицы Python - PullRequest
Новая
       62

Проблема с алгоритмом обратной матрицы Python

0 голосов
/ 08 мая 2020

Я отрабатываю свои маленькие Python навыки, программируя алгоритм решения судоку.

Я реализовал модульный тест для. Теперь я реализовал решатель, который возвращает решенную матрицу судоку, и я проверяю его в модульных тестах.

Но переменная результата, присвоенная возвращением результата решателя None. Я сделал несколько точек останова, и в конце решателя возвращаемое значение - это правильная решенная матрица. Может кто-нибудь подсказать, в каком месте я что-то упускаю?

Большое спасибо!

Мой класс алгоритма судоку: 


    class SudokuSolver():

    def testTester(self):
        print('TDDisworking')
        return 'TDDisworking'

    def IsInsertPossible(self, grid:list, x:int, y:int, n:int):

        for i in range(0,9):
            if grid[i][x] == n:
                return False
        for i in range(0,9):
            if grid[y][i] == n:
                return False

        sqX = (x//3)*3
        sqY = (y//3)*3
        for i in range(0,3):
            for j in range(0,3):
                if grid[sqY+i][sqX+j] == n:
                    return False
        return True

    def Solve(self, grid:list, yRange:int, xRange:int):
        localgrid = grid
        for y in range(yRange):
            for x in range(xRange):
                if localgrid[y][x] == 0:
                    for n in range(1,10):
                        if self.IsInsertPossible(localgrid, x, y, n):
                            localgrid[y][x] = n
                            self.Solve(localgrid, yRange, xRange)
                            localgrid[y][x] = 0
                    return
        print(localgrid)
        return localgrid

Мой класс модульного теста: 

import unittest
from Main.SudokuSolver import SudokuSolver

class SudokuSolverTester(unittest.TestCase):

sudoku_solver = SudokuSolver()
grid = [[0, 0, 0, 0, 0, 3, 0, 1, 7],
        [0, 1, 5, 0, 0, 9, 0, 0, 8],
        [0, 6, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 7, 0, 0, 0],
        [0, 0, 9, 0, 0, 0, 2, 0, 0],
        [0, 0, 0, 5, 0, 0, 0, 0, 4],
        [0, 0, 0, 0, 0, 0, 0, 2, 0],
        [5, 0, 0, 6, 0, 0, 3, 4, 0],
        [3, 4, 0, 2, 0, 0, 0, 0, 0]]

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

def test_row0_results(self):
    yRange = 9
    xRange = 9
    #This result var is every time : None
    result = self.sudoku_solver.Solve(self.grid, yRange, xRange)
    self.assertListEqual(result[0], self.solgrid[0])

if __name__ == '__main__':
  unittest.main()

1 Ответ

0 голосов
/ 11 мая 2020

Я нашел ответ. Проблема заключалась в том, что алгоритм не знает, когда есть свободные ячейки для заполнения. Таким образом, рекурсия не останавливается на конце решения. Если я вставлю элемент управления, который проверяет наличие свободных ячеек, алгоритм работает.

Вот мое обновленное решение:

class Cell Utilities: 

class CellUtilities():

def findNextCellToFill(self, sudoku):
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                return x, y
    return -1, -1

def IsInsertPossible(self, sudoku, i, j, n):
    rowOk = all([n != sudoku[i][x] for x in range(9)])
    if rowOk:
        columnOk = all([n != sudoku[x][j] for x in range(9)])
        if columnOk:
            secTopX, secTopY = 3 * (i // 3), 3 * (j // 3)
            for x in range(secTopX, secTopX + 3):
                for y in range(secTopY, secTopY + 3):
                    if sudoku[x][y] == n:
                        return False
            return True
    return False

class SudokuSolverI: 

from Main.CellUtilities import CellUtilities
class SudokuSolverI():

cellUtil = CellUtilities()

def solveSudoku(self, sudoku, row_i=0, col_j=0):
    row_i, col_j = self.cellUtil.findNextCellToFill(sudoku)
    if row_i == -1:
        return True
    for num in range(1, 10):
        if self.cellUtil.IsInsertPossible(sudoku, row_i, col_j, num):
            sudoku[row_i][col_j] = num
            if self.solveSudoku(sudoku, row_i, col_j):
                return True
            sudoku[row_i][col_j] = 0
    return False

Спасибо всем, кто помогает мне найти решение!

...