# ---------------------------------------------------------
# 안드로이드 패턴 잠금의 경우의 수를 완전탐색(백트래킹)으로 직접 세는 코드
#
# 3x3 격자, 점 번호는 아래와 같이 배치되어 있다고 가정한다.
#   1 2 3
#   4 5 6
#   7 8 9
#
# 규칙 두 가지:
#   1) 4개 이상 9개 이하의 점을 순서대로 연결한다 (한 번 쓴 점은 재사용 불가)
#   2) 두 점을 잇는 직선 위에 '아직 지나가지 않은' 점이 있으면 그 두 점을 바로 연결할 수 없다
#      (예: 1과 3 사이에는 2가 있으므로, 2를 먼저 지나지 않으면 1->3 은 불가능)
# ---------------------------------------------------------

# '건너뛰기 금지' 규칙을 딕셔너리로 정의한다: (점A, 점B) -> 그 사이에 낀 점
# 직선 위에 점이 끼는 경우는 가로 3쌍, 세로 3쌍, 대각선 2쌍 -> 총 8개 조합(양방향이라 16개 키)
SKIP = {
    (1, 3): 2, (3, 1): 2,   # 1행: 1과 3 사이에 2가 있다
    (4, 6): 5, (6, 4): 5,   # 2행: 4와 6 사이에 5가 있다
    (7, 9): 8, (9, 7): 8,   # 3행: 7과 9 사이에 8이 있다
    (1, 7): 4, (7, 1): 4,   # 1열: 1과 7 사이에 4가 있다
    (2, 8): 5, (8, 2): 5,   # 2열: 2와 8 사이에 5가 있다
    (3, 9): 6, (9, 3): 6,   # 3열: 3과 9 사이에 6이 있다
    (1, 9): 5, (9, 1): 5,   # 대각선: 1과 9 사이에 5가 있다
    (3, 7): 5, (7, 3): 5,   # 대각선: 3과 7 사이에 5가 있다
}

MIN_LEN = 4   # 패턴은 최소 4개의 점을 연결해야 유효하다
MAX_LEN = 9   # 점은 최대 9개까지 연결할 수 있다


def count_patterns_from(start_point, length_breakdown=None):
    """
    start_point에서 출발하는 모든 유효한 패턴의 개수를 백트래킹으로 센다.
    length_breakdown 딕셔너리를 넘기면, 길이(연결한 점의 개수)별 개수도 함께 누적한다.
    """
    total = 0  # 이 시작점에서 나온 유효 패턴의 총 개수를 담을 변수

    def backtrack(path, visited):
        nonlocal total
        # 지금까지 이어온 길이가 4 이상이면, 이 경로 자체가 유효한 패턴 하나로 인정된다
        if len(path) >= MIN_LEN:
            total += 1
            if length_breakdown is not None:
                length_breakdown[len(path)] = length_breakdown.get(len(path), 0) + 1

        if len(path) == MAX_LEN:
            return  # 9개를 다 썼으면 더 이어갈 점이 없으므로 종료

        last = path[-1]  # 방금 도착한 점 (다음 연결의 출발 기준)

        for candidate in range(1, 10):        # 1번부터 9번까지 다음 후보를 하나씩 검토
            if candidate in visited:
                continue                       # 이미 지나온 점은 다시 쓸 수 없다

            skip_point = SKIP.get((last, candidate))  # 두 점 사이에 낀 점이 있는지 확인
            if skip_point is not None and skip_point not in visited:
                continue                       # 낀 점을 아직 안 지났다면 이 후보는 불가능 (가지치기)

            visited.add(candidate)             # 이 후보를 방문 처리하고
            path.append(candidate)             # 경로에 추가한 뒤
            backtrack(path, visited)           # 재귀적으로 다음 단계를 탐색한다
            path.pop()                         # 되돌아올 때는 추가했던 것을 되돌리고 (백트랙)
            visited.remove(candidate)          # 방문 표시도 지운다

    backtrack([start_point], {start_point})    # 시작점 하나로 탐색을 시작한다
    return total


def unrestricted_baseline():
    """제약이 없다고 가정했을 때의 경우의 수: 9P4 + 9P5 + ... + 9P9 (합의 법칙)"""
    def nPr(n, r):
        result = 1
        for i in range(r):
            result *= (n - i)   # n부터 하나씩 줄여가며 r번 곱한다 (순열 계산)
        return result

    return sum(nPr(9, k) for k in range(MIN_LEN, MAX_LEN + 1))


if __name__ == "__main__":
    print("=" * 50)
    print("1. 제약이 없다면? (단순 순열, 9P4~9P9의 합)")
    print("=" * 50)
    baseline = unrestricted_baseline()
    print(f"결과: {baseline:,}가지\n")

    print("=" * 50)
    print("2. 실제 규칙(건너뛰기 금지)을 적용해 9곳 모두에서 직접 세기")
    print("=" * 50)
    total_all = 0
    length_totals = {}
    for start in range(1, 10):
        total_all += count_patterns_from(start, length_totals)
    print(f"길이별 경우의 수: {dict(sorted(length_totals.items()))}")
    print(f"총 경우의 수: {total_all:,}가지\n")

    print("=" * 50)
    print("3. 대칭성을 이용해 대표점 3개만 계산 후 재구성")
    print("=" * 50)
    corner_rep = count_patterns_from(1)   # 모서리 대표: 1번
    edge_rep = count_patterns_from(2)     # 변 대표: 2번
    center_rep = count_patterns_from(5)   # 중앙: 5번

    print(f"모서리(1,3,7,9) 대표값 = {corner_rep:,}  ->  ×4 = {corner_rep * 4:,}")
    print(f"변(2,4,6,8) 대표값     = {edge_rep:,}  ->  ×4 = {edge_rep * 4:,}")
    print(f"중앙(5) 값             = {center_rep:,}  ->  ×1 = {center_rep:,}")

    reconstructed = corner_rep * 4 + edge_rep * 4 + center_rep
    print(f"\n재구성한 합계: {reconstructed:,}가지")
    print(f"9곳 전체 계산 결과와 일치하는가? {reconstructed == total_all}")

    print("\n" + "=" * 50)
    print("결론 비교")
    print("=" * 50)
    print(f"제약 없을 때 (단순 순열)     : {baseline:,}가지")
    print(f"실제 규칙 적용 (정답)        : {total_all:,}가지")
    print(f"차이                         : {baseline - total_all:,}가지가 규칙 때문에 무효화됨")