1
\$\begingroup\$

The code below is working however, if more zeros (empty cells) are added to the sudoku grid g, it takes longer to run, if it ever finishes.

def is_solved(grid):
    for row, col in zip(grid, [*zip(*grid)]):
        for i in range(1, 10):
            if (i not in row) or (i not in col):
                return False
    return True


def square_available(rows, x, y, n):
    if 0 <= x < 3:
        rows = rows[:3]
    elif 3 <= x < 6:
        rows = rows[3:6]
    else:
        rows = rows[6:]
    if 0 <= y < 3:
        return not any([n in r[:3] for r in rows])
    elif 3 <= y < 6:
        return not any([n in r[3:6] for r in rows])
    else:
        return not any([n in r[6:] for r in rows])


def is_valid(grid, x, y, n):
    columns = [*zip(*grid)]
    return (
        square_available(grid, x, y, n) and n not in grid[x] and (n not in columns[y])
    )


def solve(grid, empty_cells):
    if is_solved(grid):
        return grid
    for x, y in empty_cells:
        for n in range(1, 10):
            if is_valid(grid, x, y, n):
                grid[x][y] = n
                empty_cells.remove((x, y))
                if solve(grid, empty_cells):
                    return grid
                else:
                    grid[x][y] = 0
                    empty_cells.append((x, y))


if __name__ == '__main__':
    solution = [
        [5, 3, 4, 6, 7, 8, 9, 1, 2],
        [6, 7, 2, 1, 9, 5, 3, 4, 8],
        [1, 9, 8, 3, 4, 2, 5, 6, 7],
        [8, 5, 9, 7, 6, 1, 4, 2, 3],
        [4, 2, 6, 8, 5, 3, 7, 9, 1],
        [7, 1, 3, 9, 2, 4, 8, 5, 6],
        [9, 6, 1, 5, 3, 7, 2, 8, 4],
        [2, 8, 7, 4, 1, 9, 6, 3, 5],
        [3, 4, 5, 2, 8, 6, 1, 7, 9],
    ]
    g = [
        [0, 0, 0, 6, 0, 8, 9, 1, 0],
        [6, 0, 2, 0, 9, 0, 3, 4, 0],
        [1, 9, 8, 3, 0, 0, 0, 6, 7],
        [0, 5, 9, 0, 0, 0, 4, 2, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 1, 3, 0, 2, 0, 8, 0, 0],
        [9, 6, 0, 5, 3, 7, 2, 8, 0],
        [2, 0, 0, 4, 1, 0, 0, 3, 0],
        [3, 4, 0, 2, 8, 0, 1, 7, 9],
    ]
    empty = []
    for i in range(9):
        for j in range(9):
            if not g[i][j]:
                empty.append((i, j))
    solved = solve(g, empty)
    assert g == solution

I tried refactoring the code, and the results just got worse. While it still works for simple grids, it fails to solve the very same test case above.

from collections import defaultdict


def get_possibilities(rows, columns, x, y, visited):
    if (x, y) in visited:
        return visited[x, y]
    x0 = (x // 3) * 3
    x1 = x0 + 3
    y0 = (y // 3) * 3
    y1 = y0 + 3
    possibilities = set()
    for n in range(1, 10):
        square_rows = rows[x0:x1]
        for row in square_rows:
            if n in row[y0:y1]:
                continue
        if (n not in rows[x]) and (n not in columns[y]):
            visited[x, y].add(n)
            possibilities.add(n)
    return possibilities


def solve(rows, columns, empty_cells, visited):
    if not empty_cells:
        return rows
    for x, y in empty_cells:
        for n in get_possibilities(rows, columns, x, y, visited):
            rows[x][y] = n
            columns[y][x] = n
            visited[x, y].remove(n)
            if solve(rows, columns, empty_cells - {(x, y)}, visited):
                return rows
            else:
                rows[x][y] = 0
                columns[y][x] = 0
                visited[x, y].add(n)


if __name__ == '__main__':
    solution = [
        [5, 3, 4, 6, 7, 8, 9, 1, 2],
        [6, 7, 2, 1, 9, 5, 3, 4, 8],
        [1, 9, 8, 3, 4, 2, 5, 6, 7],
        [8, 5, 9, 7, 6, 1, 4, 2, 3],
        [4, 2, 6, 8, 5, 3, 7, 9, 1],
        [7, 1, 3, 9, 2, 4, 8, 5, 6],
        [9, 6, 1, 5, 3, 7, 2, 8, 4],
        [2, 8, 7, 4, 1, 9, 6, 3, 5],
        [3, 4, 5, 2, 8, 6, 1, 7, 9],
    ]
    r = [
        [0, 0, 0, 6, 0, 8, 9, 1, 0],
        [6, 0, 2, 0, 9, 0, 3, 4, 0],
        [1, 9, 8, 3, 0, 0, 0, 6, 7],
        [0, 5, 9, 0, 0, 0, 4, 2, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 1, 3, 0, 2, 0, 8, 0, 0],
        [9, 6, 0, 5, 3, 7, 2, 8, 0],
        [2, 0, 0, 4, 1, 0, 0, 3, 0],
        [3, 4, 0, 2, 8, 0, 1, 7, 9],
    ]
    c = [list(r) for r in [*zip(*r)]]
    cells = set()
    for i in range(9):
        for j in range(9):
            if not r[i][j]:
                cells.add((i, j))
    v = defaultdict(set)
    solved = solve(r, c, cells, v)
    assert r == solution
\$\endgroup\$
1
  • \$\begingroup\$ Other, well-received & answered python, sudoku solvers and generators can be found here: here. \$\endgroup\$
    – Mast
    Commented Oct 23, 2022 at 14:59

1 Answer 1

6
\$\begingroup\$

The algorithm is slow because it tries to check every possible number for every empty cell. After it assumes that a certain cell is a 4 (when in fact it's a 5) it may take a while to realize that it's a dead end. The complexity of this approach is exponential; that's why you had trouble after increasing the number of empty cells even a bit.

Instead try to never let the algorithm use potentially wrong information. For every empty cell find the list of numbers that it potentially can be based on known cells in its row, in its column and in its square. If the list only contains one number, you know what to do. After going through all the empty cells, start over, accounting this time for all the lists you came up with. Do this process over and over until it stops producing any result. At this point you have probably solved the game. If not, it's probably unsolvable, but you can apply your recursive method to it and see what happens.


As for the code in question:

[*arr] is the same as plain arr

Overall code quality is pretty good (I only checked the 1st solution) but you can make names such as n more descriptive.

\$\endgroup\$
2
  • \$\begingroup\$ Any more specific changes do you suggest? perhaps show your approach. \$\endgroup\$
    – watch-this
    Commented Oct 23, 2022 at 11:18
  • 2
    \$\begingroup\$ @watch-this I explained the idea of a better algorithm in detail, writing it would be a bit out of scope of the code review. If you want to improve the current approach I don't think it is possible (or worthwhile). \$\endgroup\$ Commented Oct 23, 2022 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.