[UE5] 사용자 제작 퍼즐 - 퍼즐 검증, 노노그램 Solver

 

제일 핵심 기능인 퍼즐을 검증하는 기능부터 구현하기로 했다.

나머지는 이 기능에 맞춰서 구현할 수 있기 때문이다.

 

 

 

---

 

 

 

노노그램은 풀이 공식이 있다.

노노그램에 좀 익숙하면 웬만해선 대부분 아는 방법들이라서 이 글에서는 자세히 다루지 않겠다.

자세한건 위키에 나와있다.

https://ko.wikipedia.org/wiki/%EB%85%B8%EB%85%B8%EA%B7%B8%EB%9E%A8#%ED%92%80_%EB%95%8C%EC%9D%98_%EC%A0%95%EC%84%9D

노노그램 - 위키백과, 우리 모두의 백과사전

 

풀이 방법이 어느정도 정해져있다보니 노노그램을 자동으로 풀어주는 알고리즘도 여러개 있는듯 하다.

관련 논문도 찾을 수 있었다.

그래서 시간을 들여서 알고리즘을 짜는 대신에 공개되어있는 코드를 사용하기로 했다.

코드는 아래 링크에서 찾았다.

https://rosettacode.org/wiki/Nonogram_solver

Nonogram solver

다양한 언어로 제공된다.

이 프로젝트에서는 장고에서 사용해야하므로 파이썬 코드를 사용했다.

하지만 코드만 그대로 가져다 쓰는 것으로는 문제가 해결되지 않는다.

 

---

 

이 파이썬 코드에는 한계점이 있다.

힌트가 0으로 되어있는 경우는 고려되지 않았기 때문에 힌트가 0인 줄이 존재하면 의도대로 작동하지 않는다.

그러한 퍼즐을 넣고 코드를 실행해보면 무한루프에 빠진건가 싶을 정도로 루프가 오래 돌아간다.

분석해본 결과 무한루프는 아니라는 것을 알게됐지만 그래도 힌트가 0인 줄이 하나씩 늘어날 때마다 루프가 도는 횟수가 기하급수적으로 증가한다.

해당 문제를 해결하고, 프로젝트에 맞게 수정하기 위해서 코드를 디버깅하면서 분석하기로 했다.

 

 

 

---

 

 

 

전체 파이썬 코드는 아래와 같다.

# https://rosettacode.org/wiki/Nonogram_solver#Python_3

from functools import reduce

def gen_row(w, s):
    """Create all patterns of a row or col that match given runs."""
    def gen_seg(o, sp):
        if not o:
            return [[2] * sp]
        return [[2] * x + o[0] + tail
                for x in range(1, sp - len(o) + 2)
                for tail in gen_seg(o[1:], sp - x)]
 
    return [x[1:] for x in gen_seg([[1] * i for i in s], w + 1 - sum(s))]
 
 
def deduce(hr, vr):
    """Fix inevitable value of cells, and propagate."""
    def allowable(row):
        return reduce(lambda a, b: [x | y for x, y in zip(a, b)], row)
 
    def fits(a, b):
        return all(x & y for x, y in zip(a, b))
 
    def fix_col(n):
        """See if any value in a given column is fixed;
        if so, mark its corresponding row for future fixup."""
        c = [x[n] for x in can_do]
        cols[n] = [x for x in cols[n] if fits(x, c)]
        for i, x in enumerate(allowable(cols[n])):
            if x != can_do[i][n]:
                mod_rows.add(i)
                can_do[i][n] &= x
 
    def fix_row(n):
        """Ditto, for rows."""
        c = can_do[n]
        rows[n] = [x for x in rows[n] if fits(x, c)]
        for i, x in enumerate(allowable(rows[n])):
            if x != can_do[n][i]:
                mod_cols.add(i)
                can_do[n][i] &= x
 
    def show_gram(m):
        # If there's 'x', something is wrong.
        # If there's '?', needs more work.
        for x in m:
            print(" ".join("x#.?"[i] for i in x))
        print()
 
    w, h = len(vr), len(hr)
    rows = [gen_row(w, x) for x in hr]
    cols = [gen_row(h, x) for x in vr]
    can_do = list(map(allowable, rows))
 
    # Initially mark all columns for update.
    mod_rows, mod_cols = set(), set(range(w))
 
    while mod_cols:
        for i in mod_cols:
            fix_col(i)
        mod_cols = set()
        for i in mod_rows:
            fix_row(i)
        mod_rows = set()
 
    if all(can_do[i][j] in (1, 2) for j in range(w) for i in range(h)):
        print("Solution would be unique")  # but could be incorrect!
    else:
        print("Solution may not be unique, doing exhaustive search:")
 
    # We actually do exhaustive search anyway. Unique solution takes
    # no time in this phase anyway, but just in case there's no
    # solution (could happen?).
    out = [0] * h
 
    def try_all(n = 0):
        if n >= h:
            for j in range(w):
                if [x[j] for x in out] not in cols[j]:
                    return 0
            show_gram(out)
            return 1
        sol = 0
        for x in rows[n]:
            out[n] = x
            sol += try_all(n + 1)
        return sol
 
    n = try_all()
    if not n:
        print("No solution.")
    elif n == 1:
        print("Unique solution.")
    else:
        print(n, "solutions.")
    print()
 
 
def solve(s, show_runs=True):
    s = [[[ord(c) - ord('A') + 1 for c in w] for w in l.split()]
         for l in p.splitlines()]
    if show_runs:
        print("Horizontal runs:", s[0])
        print("Vertical runs:", s[1])
    deduce(s[0], s[1])

축약된 문법이 많아서 한눈에 알아보긴 어려운 편이었다.

 

일단 이 코드는 힌트를 문자열로 입력받는다.

A=1, B=2, ... , Z=26 이런 식이다.

그래서 만약 한 줄의 힌트가 [ 1, 5 ] 라면 문자열로 AE가 된다.

한 줄의 힌트는 붙어있고, 줄의 구분은 공백으로 하며, 행과 열의 구분은 줄바꿈으로 구분한다.

 

예를 들어

행 힌트: [ 3 ], [ 2, 1 ], [ 3, 2 ], [ 2, 2 ], [ 6 ], [ 1, 5 ], [ 6 ], [ 1 ], [ 2 ]
열 힌트: [ 1, 2 ], [ 3, 1 ], [ 1, 5 ], [ 7, 1 ], [ 5 ], [ 3 ], [ 4 ], [ 3 ]

 

이런 힌트는 아래처럼 변환된다.

C BA CB BB F AE F A B
AB CA AE GA E C D C

 

이러한 문자열을 입력받아서 코드 맨 아래의 solve 함수에서 숫자로 변환해서 사용한다.

solve 함수의 파라미터는 s가 아니라 p가 들어가는게 맞을 듯 하지만 외부에 p라는 변수를 만들면 되기 때문에 큰 문제는 없다.

그리고 A를 1로 변환하는데 이 프로젝트에서는 힌트가 0인 경우도 포함할 예정이기 때문에 A를 0으로, Z를 25로 변경한다.

그리고 가로, 세로가 25칸 이상인 퍼즐도 포함할 예정이기 때문에 a는 26으로, b는 27으로, z는 51으로 정한다.

그리고 줄바꿈 대신에 |를 사용하고, 줄의 구분은 공백 대신에 ;을 사용하기로 했다.

그렇게 규칙을 바꾸면 위의 예시 힌트는 다음과 같이 바뀐다.

D;CB;DC;CC;G;BF;G;B;C|BC;DB;BF;HB;F;D;E;D

 

solve 함수도 아래와 같이 변경했다.

 

def solve(p, show_runs=True) -> int:
    s = [
            [
                [
                  ord(c) - ord('A') if ord(c) < ord('a') else ord(c) - 71 # ord(c) - ord('A') - (ord('a') - ord('Z') - 1)
                  for c in w
                ]
                for w in l.split(';')
            ]
            for l in p.split('|')
        ]
    if show_runs:
        print("Horizontal runs:", s[0])
        print("Vertical runs:", s[1])
    return deduce(s[0], s[1])

이렇게만 변경하고 실행해보면 답이 하나인 퍼즐을 중복된 여러개의 답이 있다고 판단하거나, 오류가 발생해서 중단되는 문제가 있다.

예를 들어 A;A;D;A;A|A;B;B;B;A의 경우에는 다음과 같은 답이 나온다.

 

퍼즐은 맞췄지만 1296개의 답을 찾았다.

그리고 1296개의 답은 모두 같다.

이런 결과를 내보낸 곳은 deduce 함수 내부의 try_all 함수다.

decude 함수는 힌트를 통해 퍼즐을 풀고 결과를 리턴한다.

퍼즐을 푸는 과정이 모두 여기에서 진행된다고 생각하면 된다.

그리고 deduce 함수 내부에서 try_all 함수를 선언하고 호출한다.

아래의 코드는 deduce 함수 내부에서 try_all 함수와 관련된 코드다.

# We actually do exhaustive search anyway. Unique solution takes
# no time in this phase anyway, but just in case there's no
# solution (could happen?).
out = [0] * h

def try_all(n = 0):
    if n >= h:
        for j in range(w):
            if [x[j] for x in out] not in cols[j]:
                return 0
        show_gram(out)
        return 1
    sol = 0
    for x in rows[n]:
        out[n] = x
        sol += try_all(n + 1)
    return sol

n = try_all()
if not n:
    print("No solution.")
elif n == 1:
    print("Unique solution.")
else:
    print(n, "solutions.")
print()

try_all 함수는 퍼즐의 답이 여러개 있다고 판단된 경우 하나씩 대입해봐서 가능한 답의 개수를 모두 찾는 역할을 한다.

답이 하나인 경우에는 대입할 필요가 없다.

 

이곳에서 1296개의 답을 찾은 것이다.

하지만 예시의 퍼즐은 1296개의 답이 나올 수가 없다.

단 하나의 답만 가능한 상태인데 어떻게 이런일이 발생했는지를 알아야 한다.

그리고 1296개의 답이 나왔다는 것은 다음 if 조건문에서 False를 리턴했다는 뜻이 된다.

deduce 함수 내부의 코드다.

if all(can_do[i][j] in (1, 2) for j in range(w) for i in range(h)):
    print("Solution would be unique")  # but could be incorrect!
else:
    print("Solution may not be unique, doing exhaustive search:")

if의 조건문은 can_do 리스트를 순환하면서 모든 값들이 1또는 2인지를 검사한다.

w는 퍼즐의 width, h는 퍼즐의 height를 뜻한다.

즉, can_do 리스트는 이중 리스트고, 퍼즐의 크기만큼 숫자형 값을 가지고 있다.

여기에서 1또는 2가 아닌 다른 값을 가지고 있었기에 답이 여러개라고 판단했을 것이다.

 

하지만 디버깅 해본 결과 그렇지 않았다.

 

위의 if문 직전의 can_do 값

can_do 리스트에는 1또는 2를 제외한 값을 가지고 있지 않았고, 유일한 답이라는 문자열을 출력했다.

그리고 각 값들의 형태를 보면 퍼즐의 정답과 같은 형태임을 알 수 있다.

1은 칸이 채워져야할 곳을 뜻하고, 2는 비어있는 칸을 뜻한다.

그리고 이것은 show_gram이라는 퍼즐의 정답을 출력하는 함수에서도 알 수 있다.

def show_gram(m):
    # If there's 'x', something is wrong.
    # If there's '?', needs more work.
    for x in m:
        print(" ".join("x#.?"[i] for i in x))
    print()

can_do에 저장된 숫자는 "x#.?" 문자열에서 문자 하나를 고르는데 사용되는 인덱스일 것이다.

출력 결과를 예상해보면 위에서 나왔던 퍼즐의 답과 똑같이 나온다.

만약 리스트의 값이 0이라면 무언가 잘못된 것이고, 3이라면 아직 답을 알수없는 칸일 것이다.

 

다시 돌아와서 can_do 리스트를 확인해본 결과 답이 유일함을 나타내고 있다.

try_all 함수가 can_do 리스트와는 별개로 작업을 진행한 듯 해서 다시 확인해보니 rows와 cols라는 변수를 사용하고 있다.

rows와 cols라는 변수는 리스트로, deduce 함수의 초반 작업에서 선언된다.

def deduce(hr, vr):
    """Fix inevitable value of cells, and propagate."""
    
    # ...
 
    w, h = len(vr), len(hr)
    rows = [gen_row(w, x) for x in hr]
    cols = [gen_row(h, x) for x in vr]
    can_do = list(map(allowable, rows))
    
    # ...

이 두 리스트에서 문제가 발생한 것이 분명하다.

참고로 hr은 horizontal run, vr은 vertical run을 뜻하고, 가로 힌트와 세로 힌트의 값들이 들어있는 2차원 리스트다.

solve함수에서 문자열로 입력받은 힌트를 숫자형 리스트로 변환한 결과 값이다.

그리고 그 리스트의 길이로 w와 h값을 지정했으니 w는 퍼즐의 width, h는 퍼즐의 height를 뜻한다.

 

rows는 이런 값을 가지고있다.

 

다음은 cols다.

 

잘못된 결과값이기 때문에 이 리스트가 어떤 값을 가지고있어야하는지 알기 어려운듯하다.

정상적으로 작동하는 BB;C|B;B;C 라는 예시로 다시 보겠다.

이 퍼즐의 답은 아래처럼 나온다.

 

 

이 퍼즐의 rows와 cols는 이런 값을 가지고 있다.

 

1과 2의 의미를 생각하고 보면 이 두 리스트는 각 줄의 가능한 모든 경우를 저장하고 있다.

gen_row 함수의 역할이 그것이다.

 

이제 gen_row라는 함수를 봐야한다.

def gen_row(w, s):
    """Create all patterns of a row or col that match given runs."""
    def gen_seg(o, sp):
        if not o:
            return [[2] * sp]
        return [[2] * x + o[0] + tail
                for x in range(1, sp - len(o) + 2)
                for tail in gen_seg(o[1:], sp - x)]
 
    return [x[1:] for x in gen_seg([[1] * i for i in s], w + 1 - sum(s))]

gen_row 함수는 한 줄의 힌트를 통해 가능한 모든 경우의 수를 리스트에 담아서 리턴한다.

코드가 많이 축약되어있어서 알아보기 어렵다.

좀 풀어서 적으면 아래와 같다.

def gen_row(width, line_hint):
    """Create all patterns of a row or col that match given runs."""
    def gen_seg(hints, remaining_space):
        if not hints:
            return [[2] * remaining_space]
        
        result = []
        for x in range(1, remaining_space - len(hints) + 2):
            for tail in gen_seg(hints[1:], remaining_space - x):
                result.append([2] * x + hints[0] + tail)
        return result

    result = []
    for x in gen_seg([[1] * i for i in line_hint], width + 1 - sum(line_hint)): # [1, 3] --> [[1], [1, 1, 1]], [0] -> [[]]
        result.append(x[1:])
    return result

gen_seg 함수도 해당하는 줄의 힌트를 입력 받는데 특이하게 힌트의 숫자에 맞게 1을 넣어서 전달해준다.

주석에 나와있듯이 줄의 힌트가 [ 1, 3 ]인 경우 [[1], [1, 1, 1]]으로 변환해서 전달해준다.

그렇다는 것은 힌트가 [ 0 ]인 경우 [[]]이 전달된다는 뜻이 된다.

이 부분에서 문제가 생긴 것이다.

gen_seg 함수는 힌트가 더이상 없는 경우 남은 공간만큼 2를 채워서 넣어주는데, hints가 [[]]이면 not hints의 결과는 False가 나와서 해당 작업을 하지 못하고 재귀가 반복되어 가능한 경우의 수를 계속 생산하게 된다.

 

따라서 예시의 rows의 값을 다시 보면 어떤 상황인지 알 수 있다.

 

힌트가 0인 줄은 중복된 경우의 수가 여러개 존재하게 된다.

따라서 gen_seg 함수에 조건을 추가해서 문제를 해결했다.

def gen_seg(hints, remaining_space):
    if not hints or hints == [[]]:
        return [[2] * remaining_space]

    # ...

수정한 결과는 다음과 같다.

 

중복되는 경우가 더이상 포함되지 않는다.

 

이제 결과가 정상적으로 나온다.

 

여기까지만 하면 힌트가 0인 줄이 포함됐을때 발생하는 문제는 해결된다.

 

 

 

---

 

 

 

다음은 나머지 작업의 진행 과정을 분석한 글이다.

 

다음으로 can_do에는 어떤 값이 저장되는지 보겠다.

def allowable(row):
        return reduce(lambda a, b: [x | y for x, y in zip(a, b)], row)
        
can_do = list(map(allowable, rows))

결론부터 말하면 이전에 각 줄마다 가능한 모든 경우를 만들었는데 이것들을 서로 비교해서 겹치는 부분은 확정된 것으로 지정하고 그렇지 않은 부분은 아직 모르는 부분으로 지정하는 작업을 한다.

이때 리스트의 값은 1 또는 2가 저장되어있음을 기억해야 한다.

그래서 확정되지 않은 부분은 or 비트연산으로 인해서 3이 저장될 것이다.

 

조금 더 풀어서 설명하겠다.

일단 can_do 변수에는 map함수의 리턴값을 리스트로 저장한다.

map함수는 함수와 iterable 값을 입력받고, iterable 값을 순환하면서 지정받은 함수를 수행한다.

리턴 값은 map 오브젝트라서 리스트로 변환하는 과정을 거쳐야한다.

그러면 함수의 결과값들이 리스트에 저장된 상태가 된다.

만약 iterable값이 [1, 2, 3]이고 함수가 x * 2라면 결과는 [2, 4, 6] 된다.

[x*2 for x in [1, 2, 3]]이라고 생각하면 된다.

하지만 map 함수를 쓰면 더 복잡한 작업을 할 수 있다.

 

이 경우에는 함수가 allowable이고, iterable은 rows다.

rows의 값을 하나씩 순환하면서 allowable 함수를 수행하고 결과값이 can_do에 저장된다.

rows는 각 줄의 가능한 경우들을 가지고있기 때문에 한 줄씩 순환하게 된다.

따라서 allowable 함수의 파라미터인 row에는 한 줄의 가능한 경우들이 2차원 리스트 형태로 들어간다.

 

allowable 함수는 reduce 함수의 결과값을 리턴한다.

reduce함수도 map함수와 비슷하게 수행할 함수와 iterable을 입력받는다.

대신에 reduce는 함수의 결과값을 계속 누적시키는 방식으로 iterable의 차원을 낮추게 한다.

1차원 리스트가 들어가면 단일 값을 리턴하고, 2차원 리스트가 들어가면 1차원 리스트를 리턴한다.

그리고 이때 지정되는 함수는 2개의 값을 입력받아야하는데 그중 하나는 지금까지 누적된 값이고, 다른 하나는 새로 누적될 값이다.

만약 reduce 함수에 지정된 함수가 a와 b를 더하는 함수고, iterable으로 [1, 2, 3]을 지정한다면 ((1 + 2) + 3)을 한 값이 리턴될 것이다.

 

이 경우에는 a와 b를 입력받아서 zip 함수로 묶고, 그 값을 x와 y로 구분해서 둘을 or 비트연산한다.

zip 함수는 두개의 iterable을 입력받아서 인덱스가 일치하는 두 iterable의 원소를 튜플로 묶는다.

이때 크기가 작은 iterable을 기준으로 크기를 맞춘다.

iterable이 아니어도 가능은 하지만 그런 경우에는 그냥 튜플을 만들면 된다.

만약 zip([1, 2, 3], [4, 5, 6])을 하고 결과값을 리스트로 변환하면 [(1, 4), (2, 5), (3, 6)]이 된다

 

이 경우에는 한 줄의 가능성 있는 모든 경우의 결과 리스트들을 인덱스별로 묶어서 각 인덱스의 값들을 or 비트연산한다.

실제로는 하나하나 누적되면서 진행되겠지만 그렇게 생각하면 복잡하니 그냥 다 묶어버린 후에 진행한다고 생각하면 편하다.

예를들어 줄의 길이가 10일때 힌트가 7이라면 아래와 같은 경우들이 존재한다.

 

그리고 아래와 같이 인덱스별로 묶어서 or 비트연산을 하게 된다.

 

이때 리스트에 저장된 값을 생각해보면 칸이 채워져있을 경우 1이, 비어있을경우 2가 저장되어있을텐데 이 경우의 0번 인덱스의 or 비트연산 결과는 3이 된다.

2진수로 보면 01|10|10|10 이니깐 결과값은 11으로 3이 된다.

 

다음으로 3번 인덱스를 보자.

 

이 경우는 01|01|01|01으로 결과값은 01인 1이 된다.

따라서 allowable 함수를 수행한 결과 값은 [3, 3, 3, 1, 1, 1, 1, 3, 3, 3]이 된다.

 

가능한 모든 경우들 중에 모두 겹치는 것들은 확정하는 작업이다.

결국 can_do 변수에는 2차원 리스트가 들어가고, 이 2차원 리스트의 크기는 노노그램의 퍼즐 크기와 같으며, 각 값들은 확실한 경우 칸의 종류에 따라 1 또는 2를 가지고있고, 확실하지 않은 경우 3을 가지고있게 된다.

 

처음에 예시로 들었던 퍼즐의 경우에는 다음과 같은 값을 가지게 된다.

 

horizontal 힌트만 보고 정한 것이기 때문에 이런 결과값이 나온다.

 

---

 

그 다음 코드로 넘어간다.

def fits(a, b):
    return all(x & y for x, y in zip(a, b))

def fix_col(n):
    """See if any value in a given column is fixed;
    if so, mark its corresponding row for future fixup."""
    c = [x[n] for x in can_do]
    cols[n] = [x for x in cols[n] if fits(x, c)]
    for i, x in enumerate(allowable(cols[n])):
        if x != can_do[i][n]:
            mod_rows.add(i)
            can_do[i][n] &= x

def fix_row(n):
    """Ditto, for rows."""
    c = can_do[n]
    rows[n] = [x for x in rows[n] if fits(x, c)]
    for i, x in enumerate(allowable(rows[n])):
        if x != can_do[n][i]:
            mod_cols.add(i)
            can_do[n][i] &= x

# ...

mod_rows, mod_cols = set(), set(range(w))
 
while mod_cols:
    for i in mod_cols:
        fix_col(i)
    mod_cols = set()
    for i in mod_rows:
        fix_row(i)
    mod_rows = set()

사실상 마지막 단계라고 볼 수 있다.

이 과정만 거치면 퍼즐의 답이 유일한지, 여러개가 존재하는지 구분할 수 있다.

 

일단 mod_rows와 mod_cols는 업데이트 해야 할 row와 column의 인덱스를 저장하게 된다.

이전에 row들은 한번 업데이트 했으니 다음은 column차례이므로 mod_cols에 모든 column의 인덱스를 넣는다.

그리고 fix_col 함수에서 각 column들을 업데이트한다.

 

def fits(a, b):
    return all(x & y for x, y in zip(a, b))

def fix_col(n):
    """See if any value in a given column is fixed;
    if so, mark its corresponding row for future fixup."""
    c = [x[n] for x in can_do] # can_do의 n번째 column
    cols[n] = [x for x in cols[n] if fits(x, c)] # can_do의 n번째 column을 기준으로 가능한 경우만 선택
    for i, x in enumerate(allowable(cols[n])):
        if x != can_do[i][n]:
            mod_rows.add(i)
            can_do[i][n] &= x

일단 c 리스트에는 can_do 리스트의 n번째 column이 들어있다.

확실한 부분은 1 또는 2가 저장되어있고, 확실하지 않은 부분은 3이 저장되어있다.

그 다음 cols가 다시 나오는데 cols에는 해당하는 column의 가능한 모든 경우를 가지고있다.

그리고 그 경우들을 fits 함수로 하나씩 검사하면서 현재 c의 값을 기준으로 가능한 경우만 골라내게 된다.

 

can_do 2차원 리스트를 만들면서 row들을 검사해서 확실한 부분을 찾아냈고, 그 확실한 결과를 기준으로 column들에서 가능한 경우들만 골라내는 작업이다.

확실한 결과를 찾을 때 or 비트연산을 했던 것을 기억해야한다.

이번엔 and 비트연산을 하면서 아직 모르는 부분(or 비트연산을 한 결과값)은 모두 통과하지만, 1과 2가 만나서 확실하게 다른 경우는 제외하게 된다.

1 & 1, 1 & 3, 2 & 2, 2 & 3 은 True를 리턴하지만, 1 & 2는 False를 리턴한다.

1, 2, 3의 의미를 생각해보면 어떤 의도인지 알 수 있다.

그래서 가능한 모든 경우를 모아놨던 cols 리스트는 걸러지고 걸러진 값들만 남게 된다.

 

그 다음 for 루프로 가능한 경우들을 순환한다.

이때 가능한 경우들을 allowable 함수를 통해 확실한 부분만 골라서 가져온다.

그래서 1차원 리스트가 되고, x에는 단일 숫자값이 들어가게 된다.

그 다음 if문으로 can_do에 현재 저장되어있는 값과 걸러지고 걸리진 다음 확실한 결과값을 비교해서 서로 다른 부분이 있는지 찾는다.

이때 if문이 참이 되려면 can_do[i][n]의 값이 3일 수밖에 없다.

그리고 x는 1 또는 2가 될 것이다.

그리고 can_do[i][n]의 값은 x의 값으로 변경되고, mod_rows에 해당 row의 인덱스를 넣음으로서 해당 row가 추가로 업데이트 될 가능성이 있음을 알려주게 된다.

코드에서는 can_do[i][n] &= x을 했는데 can_do[i][n] = x으로 해도 된다.

 

그 다음은 mod_rows에 저장된 row들의 인덱스를 통해 각 row들을 업데이트하면서 can_do에 저장된 3의 값을 하나씩 줄여나간다.

fix_row도 fix_col과 같은 역할을 하므로 넘어가겠다.

만약 답이 여러개라면 can_do에서는 3이 남게 된다.

유일한 답만 존재한다면 1 또는 2만 저장된다.

풀 수 없는 문제라면 0이 들어있게 된다.

그래서 can_do의 모든 값을 검사해보면 답이 유일한지, 여러 답이 존재하는지 알 수 있다.

 

 

 

---

 

 

 

퍼즐을 검증하는 기능은 답이 유일한지 아닌지만 구분할 수 있다면 그 이상은 필요 없다.

여기까지만 해도 어느 칸들이 모호한 칸들인지 구분할 수 있고, 모든 답을 찾는 과정은 너무 오래걸릴 수도 있어서 검증하는 시간이 지나치게 늘어날 수 있다.

try_all 함수는 하나씩 대입해서 모든 답을 찾는 함수라는 것만 알면 될 듯하다.

 

 

- 2024.01.05 내용 추가 -

 

노노그램 퍼즐을 보는 중에 try_all 함수를 거치지 않으면 답을 찾지 못하는 퍼즐을 발견했다.

해당 퍼즐 링크: https://onlinenonograms.com/16256

Nonogram #16256

풀어보면 알겠지만 기본적인 방식으로는 풀리지 않고 직접 대입해봐야 풀리는 퍼즐이다.

그리고 대입을 해봐도 가능한 답은 하나만 나온다.

따라서 try_all 함수를 통해 대입을 하는 과정은 필요하다는 것을 알게됐다.

대신에 찾은 답이 2개가 되는 순간 찾는 과정을 멈추고 답이 여러개 있다는 정보를 리턴하게 했다.

def try_all(n = 0):
    if n >= height:
        for j in range(width):
            if [x[j] for x in out] not in cols[j]:
                return 0
        show_gram(out)
        return 1
    sol = 0
    for x in rows[n]:
        out[n] = x
        sol += try_all(n + 1)
        if sol > 1:
            break
    return sol

 

대입을 하지 않으면 위의 퍼즐을 검사한 결과는 이런 결과가 나온다.

 

 

대입을 하면 결과가 이렇게 나온다.

답이 하나가 아닌듯 하다는 결과가 나왔지만 대입을 해보니 답이 하나만 나온다.

 

만약 이런 경우가 아니고 답이 여러개 나올 수 있는 경우에는 아래처럼 답을 2개 까지만 찾고 멈춘다.