Python을 사용한 재귀 스도쿠 솔버

Question

재귀 적으로 작동하는 스도쿠 솔버. 코딩 스타일, 구조 및 개선 방법에 대한 귀하의 의견에 감사드립니다. 시간 내 주셔서 정말 감사합니다.

코드 구조

솔버는 스도쿠 퍼즐 입력을 위해 81 자리 문자열을 받아 작동합니다. 0은 빈 셀로 간주됩니다. 9x9 Numpy 배열로 구문 분석합니다.

이 get_candidates기능은 스도쿠의 규칙에 따라 각 셀을 채우기 위해 가능한 숫자 목록을 생성합니다 (행, 열 및 3x3 하위 그리드를 따라 1-9 자리를 반복하지 않음).

주요 솔버 기능은 solve입니다. 첫째, filter-candidates함수로 잘못된 후보를 버립니다 . "잘못된 후보"는 빈 셀에 채워 졌을 때 스도쿠 그리드의 다른 위치에 더 이상 후보가없는 다른 셀로 이어지는 것입니다.

후보를 필터링 한 후 fill_singles남은 후보가 하나만있는 빈 셀을 채우기 위해 호출됩니다. 이 프로세스가 완전히 채워진 스도쿠 그리드로 이어지는 경우 솔루션으로 반환됩니다. 함수에 None의해 변경 사항을 역 추적하는 데 사용되는 반환 할 절이 make_guess있습니다. 이 함수는 후보 중 하나 인 "추측"값으로 가장 적은 수의 후보로 다음 빈 셀을 채 웁니다. 그런 다음 반복적으로 호출 solve하여 솔루션을 찾거나 솔루션이없는 그리드에 도달합니다 (이 경우 solve반환 None되고 마지막 추측 변경 사항이 되돌림).

from copy import deepcopy
import numpy as np


def create_grid(puzzle_str: str) -> np.ndarray:
    """Create a 9x9 Sudoku grid from a string of digits"""

    # Deleting whitespaces and newlines (\n)
    lines = puzzle_str.replace(' ','').replace('\n','')
    digits = list(map(int, lines))
    # Turning it to a 9x9 numpy array
    grid = np.array(digits).reshape(9,9)
    return grid


def get_subgrids(grid: np.ndarray) -> np.ndarray:
    """Divide the input grid into 9 3x3 sub-grids"""

    subgrids = []
    for box_i in range(3):
        for box_j in range(3):
            subgrid = []
            for i in range(3):
                for j in range(3):
                    subgrid.append(grid[3*box_i + i][3*box_j + j])
            subgrids.append(subgrid)
    return np.array(subgrids)


def get_candidates(grid : np.ndarray) -> list:
    """Get a list of candidates to fill empty cells of the input grid"""

    def subgrid_index(i, j):
        return (i//3) * 3 + j // 3

    subgrids = get_subgrids(grid)
    grid_candidates = []
    for i in range(9):
        row_candidates = []
        for j in range(9):
            # Row, column and subgrid digits
            row = set(grid[i])
            col = set(grid[:, j])
            sub = set(subgrids[subgrid_index(i, j)])
            common = row | col | sub
            candidates = set(range(10)) - common
            # If the case is filled take its value as the only candidate
            if not grid[i][j]:
                row_candidates.append(list(candidates))
            else:
                row_candidates.append([grid[i][j]])
        grid_candidates.append(row_candidates)
    return grid_candidates


def is_valid_grid(grid : np.ndarray) -> bool:
    """Verify the input grid has a possible solution"""

    candidates = get_candidates(grid)
    for i in range(9):
        for j in range(9):
            if len(candidates[i][j]) == 0:
                return False
    return True


def is_solution(grid : np.ndarray) -> bool:
    """Verify if the input grid is a solution"""

    if np.all(np.sum(grid, axis=1) == 45) and \
       np.all(np.sum(grid, axis=0) == 45) and \
       np.all(np.sum(get_subgrids(grid), axis=1) == 45):
        return True
    return False


def filter_candidates(grid : np.ndarray) -> list:
    """Filter input grid's list of candidates"""
    test_grid = grid.copy()
    candidates = get_candidates(grid)
    filtered_candidates = deepcopy(candidates)
    for i in range(9):
        for j in range(9):
            # Check for empty cells
            if grid[i][j] == 0:
                for candidate in candidates[i][j]:
                    # Use test candidate
                    test_grid[i][j] = candidate
                    # Remove candidate if it produces an invalid grid
                    if not is_valid_grid(fill_singles(test_grid)):
                        filtered_candidates[i][j].remove(candidate)
                    # Revert changes
                    test_grid[i][j] = 0
    return filtered_candidates


def merge(candidates_1 : list, candidates_2 : list) -> list:
    """Take shortest candidate list from inputs for each cell"""

    candidates_min = []
    for i in range(9):
        row = []
        for j in range(9):
            if len(candidates_1[i][j]) < len(candidates_2[i][j]):
                row.append(candidates_1[i][j][:])
            else:
                row.append(candidates_2[i][j][:])
        candidates_min.append(row)
    return candidates_min


def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
    """Fill input grid's cells with single candidates"""

    grid = grid.copy()
    if not candidates:
        candidates = get_candidates(grid)
    any_fill = True
    while any_fill:
        any_fill = False
        for i in range(9):
            for j in range(9):
                if len(candidates[i][j]) == 1 and grid[i][j] == 0:
                    grid[i][j] = candidates[i][j][0]
                    candidates = merge(get_candidates(grid), candidates)
                    any_fill = True
    return grid


def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
    """Fill next empty cell with least candidates with first candidate"""

    grid = grid.copy()
    if not candidates:
        candidates = get_candidates(grid)
    # Getting the shortest number of candidates > 1:
    min_len = sorted(list(set(map(
       len, np.array(candidates).reshape(1,81)[0]))))[1]
    for i in range(9):
        for j in range(9):
            if len(candidates[i][j]) == min_len:
                for guess in candidates[i][j]:
                    grid[i][j] = guess
                    solution = solve(grid)
                    if solution is not None:
                        return solution
                    # Discarding a wrong guess
                    grid[i][j] = 0


def solve(grid : np.ndarray) -> np.ndarray:
    """Recursively find a solution filtering candidates and guessing values"""

    candidates = filter_candidates(grid)
    grid = fill_singles(grid, candidates)
    if is_solution(grid):
        return grid
    if not is_valid_grid(grid):
        return None
    return make_guess(grid, candidates)

# # Example usage

# puzzle = """100920000
#             524010000
#             000000070
#             050008102
#             000000000
#             402700090
#             060000000
#             000030945
#             000071006"""

# grid = create_grid(puzzle)
# solve(grid)
```

Answer 1

약 1 시간 만에 알고리즘을 많이 이해하거나 변경하지 않고도 프로그램의 성능을 약 900 % 향상시킬 수있었습니다. 내가 한 일은 다음과 같습니다.

우선 벤치 마크가 필요합니다. 매우 간단합니다. 프로그램 시간을 정하십시오.

start = time.time()
solve(grid)
print(time.time()-start)

제 컴퓨터에서는 4.5 초 정도 걸렸습니다. 이것이 우리의 기준입니다.

다음은 프로파일 링입니다. 제가 선택한 도구는 VizTracer로, 제가 직접 개발했습니다. :)https://github.com/gaogaotiantian/viztracer

VizTracer는 코드 실행 타임 라인의 HTML 보고서 (또는 chrome :: // tracing에 의해로드 될 수있는 json)를 생성합니다. 원래 버전에서는 다음과 같이 보입니다.

아시다시피 거기에 많은 전화가 있습니다. 우리가해야 할 일은 여기서 병목 현상이 무엇인지 파악하는 것입니다. 구조가 복잡하지 않고 많은 fill_singles호출이 호출되며 거기에 무엇이 있는지 확인하려면 확대해야합니다.

대부분의 타임 라인을 차지하는에서 대부분의 get_candidates시간을 유발 한 함수 라는 것은 매우 분명합니다 fill_singles. 이것이 우리가 먼저 살펴보고 싶은 기능입니다.

def get_candidates(grid : np.ndarray) -> list:
    """Get a list of candidates to fill empty cells of the input grid"""

    def subgrid_index(i, j):
        return (i//3) * 3 + j // 3

    subgrids = get_subgrids(grid)
    grid_candidates = []
    for i in range(9):
        row_candidates = []
        for j in range(9):
            # Row, column and subgrid digits
            row = set(grid[i])
            col = set(grid[:, j])
            sub = set(subgrids[subgrid_index(i, j)])
            common = row | col | sub
            candidates = set(range(10)) - common
            # If the case is filled take its value as the only candidate
            if not grid[i][j]:
                row_candidates.append(list(candidates))
            else:
                row_candidates.append([grid[i][j]])
        grid_candidates.append(row_candidates)
    return grid_candidates

내 눈을 먼저 사로 잡은 것은 중첩 된 for 루프의 끝이었습니다. grid[i][j]채워져 있는지 확인했습니다 . 그렇다면 유일한 후보입니다. 그러나 채워지면 candidates중첩 된 for 루프에서 매우 어렵게 계산 한와 관련이 없습니다 .

그래서 제가 한 첫 번째 일은 수표를 for 루프의 시작 부분으로 옮기는 것이 었습니다.

    for i in range(9):
        row_candidates = []
        for j in range(9):
            if grid[i][j]:
                row_candidates.append([grid[i][j]])
                continue
            # Row, column and subgrid digits
            row = set(grid[i])
            col = set(grid[:, j])
            sub = set(subgrids[subgrid_index(i, j)])
            common = row | col | sub
            candidates = set(range(10)) - common
            row_candidates.append(list(candidates)) 

이 최적화만으로도 실행 시간이 절반으로 단축되었으며 현재 약 2.3 초입니다.

그런 다음 중첩 for 루프에서 많은 중복 집합 작업을 수행하고 있음을 알았습니다. row / col / sub도 9 번만 계산하면됩니다. 81 번 계산하는 것입니다. 그래서 계산을 for 루프 밖으로 옮겼습니다.

def get_candidates(grid : np.ndarray) -> list:
    """Get a list of candidates to fill empty cells of the input grid"""

    def subgrid_index(i, j):
        return (i//3) * 3 + j // 3

    subgrids = get_subgrids(grid)
    grid_candidates = []

    row_sets = [set(grid[i]) for i in range(9)]
    col_sets = [set(grid[:, j]) for j in range(9)]
    subgrid_sets = [set(subgrids[i]) for i in range(9)]
    total_sets = set(range(10))

    for i in range(9):
        row_candidates = []
        for j in range(9):
            if grid[i][j]:
                row_candidates.append([grid[i][j]])
                continue
            # Row, column and subgrid digits
            row = row_sets[i]
            col = col_sets[j]
            sub = subgrid_sets[subgrid_index(i, j)]
            common = row | col | sub
            candidates = total_sets - common
            # If the case is filled take its value as the only candidate
            row_candidates.append(list(candidates))
        grid_candidates.append(row_candidates)
    return grid_candidates

이로 인해 실행 시간이 약 1.5 초로 단축되었습니다. 나는 아직 당신의 알고리즘을 이해하려고 노력하지 않았습니다. 내가 한 유일한 일은 VizTracer를 사용하여 최적화가 필요한 기능을 찾고 동일한 논리 변환을 수행하는 것입니다. 15 분 만에 성능이 약 300 % 향상되었습니다.

지금까지는 WSL에서 VizTracer의 오버 헤드가 상당하므로 C 함수 추적을 해제했습니다. 파이썬 함수 만 남았고 오버 헤드는 약 10 %였습니다.

이제 get_candidates개선되었습니다 (더 잘할 수 있지만), 더 큰 그림을 찍을 필요가 있습니다. 내가 VizTracer의 결과에서 관찰 할 수있는 작업은되었다 fill_singles라는 get_candidates, 매우 자주 너무 많은 전화를. (이것은 cProfiler에서 알아 채기 어려운 부분입니다)

그래서 다음 단계는 fill_singles전화를 get_candidates덜 자주 걸 수 있는지 알아내는 것이 었습니다 . 여기에서는 어느 정도의 알고리즘 이해가 필요합니다.

    while any_fill:
        any_fill = False
        for i in range(9):
            for j in range(9):
                if len(candidates[i][j]) == 1 and grid[i][j] == 0:
                    grid[i][j] = candidates[i][j][0]
                    candidates = merge(get_candidates(grid), candidates)
                    any_fill = True

여기에서 하나의 공백을 하나의 후보로만 채우고 전체 그리드의 후보를 다시 계산 한 다음 하나의 후보로 다음 공백을 찾으려고 시도한 것처럼 보입니다. 이것은 유효한 메서드이지만 이로 인해 get_candidates. 생각해 보면 빈칸을 숫자로 채울 때 n하나의 후보자 만있는 다른 모든 빈칸은 n영향을받지 않습니다. 따라서 그리드를 한 번 통과하는 동안 동일한 숫자를 두 번 채우지 않는 한 실제로 더 많은 공백을 채울 수 있습니다. 이렇게하면 통화 get_candidates횟수를 줄일 수 있어 시간을 많이 소비합니다. 나는 이것을하기 위해 세트를 사용했다.

        filled_number = set()
        for i in range(9):
            for j in range(9):
                if len(candidates[i][j]) == 1 and grid[i][j] == 0 and candidates[i][j][0] not in filled_number:
                    grid[i][j] = candidates[i][j][0]
                    filled_number.add(candidates[i][j][0])
                    any_fill = True
        candidates = merge(get_candidates(grid), candidates)

이로 인해 실행 시간이 0.9 초로 늘어났습니다.

그런 다음 VizTracer 보고서를보고 fill_singles거의 항상에 의해 호출되고 filter_candidates유일한 filter_candidates관심사 fill_singles는 유효한 그리드를 반환 하는지 여부 입니다. 이것은 fill_singles후보자가없는 직위를 찾는 한 우리가 일찍 알 수있는 정보 입니다. 일찍 돌아 오면 get_candidates그렇게 여러 번 계산할 필요가 없습니다 .

그래서 코드 구조를 약간 변경하고 유효한 그리드를 찾을 수 없으면 fill_singles반환 None했습니다.

마지막으로 실행 시간을 0.5 초로 만들 수 있었는데, 이는 원래 버전보다 900 % 더 빠릅니다.

내 프로젝트 VizTracer를 테스트하고 시간이 많이 걸리는 부분을 찾는 데 도움이되는지 알아 내려고했기 때문에 실제로 재미있는 모험이었습니다. 잘 작동했습니다. :)

Answer 2

Numpyification

get_subgrids기본적으로 최소 numpy로 numpy 배열을 재정렬합니다. 예를 들어 numpy 자체로 수행 할 수 있습니다.

def get_subgrids(grid: np.ndarray) -> np.ndarray:
    """Divide the input grid into 9 3x3 sub-grids"""

    swapped = np.swapaxes(np.reshape(grid, (3, 3, 3, 3)), 1, 2)
    return np.reshape(swapped, (9, 9))

내가 생각하는 단점은 4D 배열의 가운데 두 축을 바꾸는 것이 약간 마음을 구부린다는 것입니다.

공연

거의 모든 시간이 get_candidates. 그 이유는 주로 다음과 같습니다.

• 너무 자주 호출됩니다. 예를 들어, 셀 (예 : in fill_singles) 을 채운 후 후보를 처음부터 다시 계산하는 대신 동일한 행 / 열 / 하우스의 후보에서 새 값을 제거하는 것이 더 빠릅니다.
• 셀이 채워지면 후보 목록은 채워진 값일 뿐이지 만 값 비싼 집합 계산은 어쨌든 수행됩니다. 그 문을 if.

알고리즘 성능

이 솔버는 Naked Singles를 "전파 기술"로만 사용합니다. Hidden Singles를 추가하는 것은 효율적인 솔버를 향한 매우 큰 단계입니다.