Week-3: 제약 충족 문제

DSA-알고리즘 스터디

Jan 19, 2022

제약 충족 문제
- Constraint
- CSP
1. 호주 지도 색칠 문제
2. 여덟 퀸 문제
3. SEND+MORE=MONEY
4. 단어 검색
연습문제

제약 충족 문제

제약 충족 문제(CSP: Constraint-Satisfaction Problem)는 복수의 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 가리킨다. 백트래킹 검색과 이를 향상시키는 휴리스틱을 통합한 프레임워크를 구축하여 해결할 수 있다.

Constraint

Constraint 클래스

from typing import Generic, TypeVar, Dict, List, Optional
from abc import ABC, abstractmethod

V = TypeVar('V') # 변수(Variable) 타입
D = TypeVar('D') # 도메인(Domain) 타입


class Constraint(Generic[V, D], ABC):
    """
    * 추상 베이스 클래스
    """
    def __init__(self, variables:List[V]) -> None:
        self.variables = variables                              # variables     : 제약 조건 변수

    # 서브클래스 메서드에 의해 재정의된다.
    @abstractmethod
    def satisfied(self, assignment:Dict[V, D]) -> bool:
        ...

Constraint 클래스는 제약 조건 변수와 이를 충족하는지 검사하는 메서드로 구성되며, 이는 제약 충족 문제가 가진 고유의 제약 조건에 따라 조금씩 다르게 재정의된다. abc 모듈의 ABC 클래스를 상속하는 방식으로 Constraint 클래스를 추상 클래스로 정의하면 공통된 필드와 메서드를 통일할 수 있다. @abstractmethod 데코레이터를 사용한 메서드는 추상 메서드로 정의되며, 이후 서브클래스 메서드에 의해 재정의된다.

CSP

CSP 클래스

class CSP(Generic[V, D]):
    """
    * 핵심 클래스
    변수            : self.variables
    도메인          : self.domains
    제약 조건       : self.constraints
    """
    def __init__(self, variables:List[V], domains:Dict[V, List[D]]) -> None:

        # 1. 변수 및 도메인을 저장한다.
        self.variables:List[V] = variables                      # variables     : List[V]
        self.domains:Dict[V, List[D]] = domains                 # domains       : { V : List[D] }

        # 2. 제약 조건 컬렉션을 초기화한다.
        self.constraints:Dict[V, List[Constraint[V, D]]] = {}   # constraints   : { V : List[Constraint[V, D]] }
        for variable in self.variables:                         # {}
            self.constraints[variable] = []                     # { 변수1 : [], 변수2: [], ... }
            if variable not in self.domains:
                raise LookupError("모든 변수에 도메인이 할당되어야 합니다.")

    # 3. 제약 조건을 저장한다.
    def add_constraint(self, constraint:Constraint[V, D]) -> None:
        for variable in constraint.variables:                   
            if variable not in self.variables:
                raise LookupError("제약 조건 변수가 아닙니다.")
            else:
                self.constraints[variable].append(constraint)   # { 변수1 : [제약 조건], 변수 2: [제약 조건], ... }

    # 주어진 변수의 모든 제약 조건을 검사하며 assignment 값이 일관적인지 확인한다.
    def consistent(self, variable:V, assignment:Dict[V, D]) -> bool:
        for constraint in self.constraints[variable]:
            if not constraint.satisfied(assignment):
                return False    # 제약 조건을 충족하지 않음    -> False
        return True         # 할당이 모든 제약 조건을 충족 -> True

    # 백트래킹(backtracking): 깊이 우선 탐색(DFS)과 유사한 방식
    def backtracking_search(self, assignment:Dict[V, D] = {}) -> Optional[Dict[V, D]]:

        # assignment는 모든 변수가 할당될 때 완료된다(기저 조건).
        if len(assignment) == len(self.variables):
            return assignment

        # 할당되지 않은 모든 변수를 가져온다.
        unsigned:List[V] = [v for v in self.variables if v not in assignment]
        
        # 할당되지 않은 첫 번째 변수의 가능한 모든 도메인 값을 가져온다.
        first:V = unsigned[0]
        for value in self.domains[first]:
            local_assignment = assignment.copy()
            local_assignment[first] = value
            
            # local_assignment 값이 일치하면 재귀 호출한다.
            if self.consistent(first, local_assignment):
                result:Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
                if result is not None:
                    return result   # 솔루션 반환
        return None                 # 솔루션 없음

CSP 클래스는 인스턴스 생성 시 변수와 도메인을 저장하며, add_constraint() 메서드를 통해 제약 조건을 저장한다.

assignment는 변수(key)에 대한 유효한 도메인(value)을 갖는 사전 자료형으로, 모든 변수가 할당될 때 솔루션으로 반환된다.

consistent() 메서드는 할당된 값이 제약 조건을 만족시키는 유효한 값인지 확인한다.

backtracking_search() 메서드는 깊이 우선 탐색(DFS)과 유사한 방식을 사용해 값을 할당한다. 모든 변수가 할당될 때까지 재귀 호출을 시행하며, 특정 깊이에서의 할당이 전부 실패할 경우 이전 재귀 스택으로 돌아간다.

1. 호주 지도 색칠 문제

위 호주 지도를 색칠한다고 가정한다. 3가지 색만 사용해야 하며, 인접한 두 지역은 같은 색을 사용할 수 없다.

변수, 도메인, 제약 조건을 정의하고, 이를 바탕으로 코드를 작성한다.

	타입	설명
변수(V)	str	지역 이름
도메인(D)	str	색상 이름
제약 조건	Constraint[str, str]	인접한 두 지역은 같은 색으로 칠할 수 없다.

제약 조건 설정

from csp import Constraint, CSP
from typing import Dict, List, Optional


class MapColoringConstraint(Constraint[str, str]):
    def __init__(self, place1:str, place2:str) -> None:
        super().__init__([place1, place2])
        self.place1:str = place1
        self.place2:str = place2

    def satisfied(self, assignment:Dict[str, str]) -> bool:
        if self.place1 not in assignment or self.place2 not in assignment:
            return True
        return assignment[self.place1] != assignment[self.place2]

재정의한 satisfied() 메서드는 충돌이 발생한 경우 문제의 조건에 위배되므로 False를 반환하며, 그 이외의 경우 True를 반환한다.

두 지역 중 하나라도 할당이 이루어지지 않은 경우	두 지역 모두 할당이 이루어지고 충돌이 발생하지 않은 경우	두 지역 모두 할당이 이루어지고 충돌이 발생한 경우

True	True	False

Note

호주 지도 색칠 문제에서는 두 지역 중 하나라도 색상이 지정되지 않았다면 제약 조건이 충족되었다고 간주한다. 그 이유는 backtracking_search 메서드의 작동 알고리즘인 깊이 우선 탐색에서는 할당이 불가능할 때 None을 반환하고 재귀 체인을 다른 이전 할당이 이뤄진 지역으로 되돌아가게 한다. 특정 지역에 대해 제약 조건을 검사할 때, 그 지역은 이미 할당된 지역과 아직 할당되지 않은 지역 모두 인접하고 있다. 만약 아직 할당되지 않은 지역과의 조건 비교에서 False를 반환한다면 할당이 실패하므로 이전 재귀 스택으로 돌아가게 되며, 결국 최대 깊이까지 탐색하지 못해 솔루션을 찾을 수 없다.

main

if __name__ == "__main__":

    # V
    variables:List[str] = ["웨스턴 오스트레일리아", 
                           "노던 준주", 
                           "사우스 오스트레일리아",
                           "퀸즐랜드",
                           "뉴사우스웨일스",
                           "빅토리아",
                           "태즈메이니아"]

    # D
    domains:Dict[str, List[str]] = {}
    for variable in variables:
        domains[variable] = ["빨강", "초록", "파랑"]

    # constraint
    csp:CSP[str, str] = CSP(variables, domains)
    csp.add_constraint(MapColoringConstraint("웨스턴 오스트레일리아", "노던 준주"))
    csp.add_constraint(MapColoringConstraint("웨스턴 오스트레일리아", "사우스 오스트레일리아"))
    csp.add_constraint(MapColoringConstraint("사우스 오스트레일리아", "노던 준주"))
    csp.add_constraint(MapColoringConstraint("퀸즐랜드"             , "노던 준주"))
    csp.add_constraint(MapColoringConstraint("퀸즐랜드"             , "사우스 오스트레일리아"))
    csp.add_constraint(MapColoringConstraint("퀸즐랜드"             , "뉴사우스웨일스"))
    csp.add_constraint(MapColoringConstraint("뉴사우스웨일스"       , "사우스 오스트레일리아"))
    csp.add_constraint(MapColoringConstraint("빅토리아"             , "사우스 오스트레일리아"))
    csp.add_constraint(MapColoringConstraint("빅토리아"             , "뉴사우스웨일스"))
    csp.add_constraint(MapColoringConstraint("빅토리아"             , "태즈메이니아"))
    
    # solution
    solution:Optional[Dict[str, str]] = csp.backtracking_search()
    if solution is None:
        print("답을 찾을 수 없습니다!")
    else:
        print(solution)

앞서 정의한 내용을 바탕으로 변수, 도메인, 제약 조건을 추가한다. 이후 백트래킹을 통해 솔루션을 도출한다.

후술할 다른 모든 문제도 이와 같은 구조의 실행 과정을 가진다.

실행 결과

{'웨스턴 오스트레일리아': '빨강', '노던 준주': '초록', '사우스 오스트레일리아': '파랑', '퀸즐랜드': '빨강', '뉴사우스웨일스': '초록', '빅토리아': '빨강', '태즈메이니아': '초록'}

2. 여덟 퀸 문제

체스판에 8개의 퀸을 배치한다고 가정한다. 각 퀸은 서로의 공격 범위(같은 줄, 같은 대각선)에 위치할 수 없다.

변수, 도메인, 제약 조건을 정의하고, 이를 바탕으로 코드를 작성한다.

	타입	설명
변수(V)	int	퀸의 열(1 ~ 8)
도메인(D)	int	퀸의 행(1 ~ 8)
제약 조건	Constraint[int, int]	모든 퀸은 서로 다른 줄 및 대각선에 위치한다.

제약 조건 설정

class QueensConstraint(Constraint[int, int]):
    def __init__(self, columns:List[int]) -> None:
        super().__init__(columns)
        self.columns:List[int] = columns

    def satisfied(self, assignment:Dict[int, int]) -> bool:
        """
        q1c = 퀸1의 열, q1r = 퀸1의 행
        q2c = 퀸2의 열, q2r = 퀸2의 행
        """
        for q1c, q1r in assignment.items():                     # 모든 key와 value에 대해 반복
            for q2c in range(q1c + 1, len(self.columns) + 1):   # 1. 남은 열에 대해 반복(두 퀸은 같은 행에 위치할 수 없다)
                if q2c in assignment:
                    q2r:int = assignment[q2c]
                    if q1r == q2r:                              # 2. 두 퀸이 같은 행에 위치할 수 없다.
                        return False
                    if abs(q1r - q2r) == abs(q1c - q2c):        # 3. 두 퀸이 같은 대각선에 위치할 수 없다.
                        return False
        return True

퀸의 열을 변수로 사용하므로 제약 조건 설정 시 두 퀸은 자연스럽게 다른 열에 배치된다. 따라서 행의 위치만 비교하면 된다.

같은 대각선에 위치하는 모든 격자는 열과 행의 차가 일정하다. 이를 이용해 제약 조건 알고리즘을 작성할 수 있다.

main

if __name__ == "__main__":
    
    # V
    columns:List[int] = [1, 2, 3, 4, 5, 6, 7, 8]
    
    # D
    rows:Dict[int, List[int]] = {}
    for column in columns:
        rows[column] = [1, 2, 3, 4, 5, 6, 7, 8]
        
    # constraint
    csp:CSP[int, int] = CSP(columns, rows)
    csp.add_constraint(QueensConstraint(columns))
    
    # solution
    solution:Optional[Dict[int, int]] = csp.backtracking_search()
    if solution is None:
        print("답을 찾을 수 없습니다!")
    else:
        print(solution)

실행 결과

{1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4}

3. SEND+MORE=MONEY

복면산 퍼즐(cryptarithmetic puzzle의 일종으로, 문자로 암호화된 계산식을 복호화하는 알고리즘이다. 같은 문자는 같은 숫자를 나타낸다.

변수, 도메인, 제약 조건을 정의한다.

	타입	설명
변수(V)	str	문자
도메인(D)	int	문자가 의미하는 숫자(0 ~ 9)
제약 조건	Constraint[str, int]	서로 다른 문자는 같은 숫자를 나타낼 수 없다.

제약 조건 설정

from csp import Constraint, CSP
from typing import Dict, List, Optional


class SendMoreMoneyConstraint(Constraint[str, int]):
    def __init__(self, letters:List[str]) -> None:
        super().__init__(letters)
        self.letters:List[str] = letters

    def satisfied(self, assignment:Dict[str, int]) -> bool:
        if len(set(assignment.values())) < len(assignment):
            return False
    
        if len(assignment) == len(self.letters):
            s:int = assignment["S"]
            e:int = assignment["E"]
            n:int = assignment["N"]
            d:int = assignment["D"]
            m:int = assignment["M"]
            o:int = assignment["O"]
            r:int = assignment["R"]
            y:int = assignment["Y"]
            send:int = s * 1000 + e * 100 + n * 10 + d
            more:int = m * 1000 + o * 100 + r * 10 + e
            money:int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
            return send + more == money
        return True

main

if __name__ == "__main__":

    # V
    letters:List[str] = ["S", "E", "N", "D", "M", "O", "R", "Y"]

    # D
    possible_digits:Dict[str, List[int]] = {}
    for letter in letters:
        possible_digits[letter] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    possible_digits["M"] = [1]

    # constraint
    csp:CSP[str, int] = CSP(letters, possible_digits)
    csp.add_constraint(SendMoreMoneyConstraint(letters))
    
    # solution
    solution:Optional[Dict[str, int]] = csp.backtracking_search()
    if solution is None:
        print("답을 찾을 수 없습니다!")
    else:
        print(solution)

실행 결과

{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}

4. 단어 검색

영문자로 구성된 격자에서 행과 열, 대각선을 따라 배치된 특정 단어를 찾는다고 가정한다. 단어의 위치는 겹치거나 격자 범위를 벗어날 수 없다. 문제를 간단히 하기 위해 격자에 중복 단어의 사용을 배제한다.

변수, 도메인, 제약 조건을 정의한다.

	타입	설명
변수(V)	str	단어
도메인(D)	List[GridLocation]	단어의 위치
제약 조건	Constraint[str, List[GridLocation]]	단어는 겹칠 수 없다.

from typing import NamedTuple, Dict, List, Optional
from random import choice
from string import ascii_uppercase
from csp import Constraint, CSP

Grid = List[List[str]]


class GridLocation(NamedTuple):
    row:int
    column:int

GridLocation 클래스는 NamedTuple을 상속받아 격자 행렬에서의 알파벳 위치를 표시하는 역할을 수행한다.

def generate_grid(rows:int, columns:int) -> Grid:
    return [[choice(ascii_uppercase) for c in range(columns)] for r in range(rows)]

def display_grid(grid:Grid) -> None:
    for row in grid:
        print(" ".join(row))

generate_grid 함수는 무작위 알파벳 대문자로 채워진 격자인 2차원 리스트를 생성하며, display_grid 함수를 사용해 출력할 수 있다.

random.choice 함수는 입력받은 Sequence에서 무작위 항목을 반환한다. 이때 인자로 “ABCDEFGHIJKLMNOPQRSTUVWXYZ” 대신 string.ascii_uppercase를 사용해 간단하게 나타낼 수 있다.

도메인 설정

def generate_domain(word:str, grid:Grid) -> List[List[GridLocation]]:
    domain:List[List[GridLocation]] = []
    height:int = len(grid)
    width:int = len(grid[0])
    length:int = len(word)
    for row in range(height):
        for col in range(width):
            columns:range = range(col, col + length + 1)
            rows:range = range(row, row + length + 1)
            if col + length <= width:
                # 1. 왼쪽에서 오른쪽으로
                domain.append([GridLocation(row, c) for c in columns])
                if row + length <= height:
                    # 2. 대각선 오른쪽 아래로
                    domain.append([GridLocation(r, col + (r - row)) for r in rows])
            if row + length <= height:
                # 3. 위에서 아래로
                domain.append([GridLocation(r, col) for r in rows])
                if col - length >= 0:
                    # 4. 대각선 왼쪽 아래로
                    domain.append([GridLocation(r, col - (r - row)) for r in rows])
    return domain

generate_domain 함수를 사용해 도메인을 설정한다. 도메인(단어의 위치)는 격자를 벗어날 수 없으므로 격자의 크기와 단어의 길이에 영향을 받는다.

제약 조건 설정

class WordSearchConstraint(Constraint[str, List[GridLocation]]):
    def __init__(self, words:List[str]) -> None:
        super().__init__(words)
        self.words:List[str] = words

    def satisfied(self, assignment:Dict[str, List[GridLocation]]) -> bool:
        all_locations = [locs for values in assignment.values() for locs in values]
        return len(set(all_locations)) == len(all_locations)

할당된 단어 위치의 중복을 확인하기 위해 all_locations에 모든 위치를 저장한다. 리스트를 집합(set)으로 변환 시 모든 중복 항목이 제거되므로 비교를 통해 중복 여부를 검사할 수 있다.

main

if __name__ == "__main__":

    # V
    grid:Grid = generate_grid(9, 9)

    # D
    words:List[str] = ["MATTHEW", "JOE", "MARY", "SARAH", "SALLY"]
    locations:Dict[str, List[List[GridLocation]]] = {}
    for word in words:
        locations[word] = generate_domain(word, grid)

    # constraint
    csp:CSP[str, List[GridLocation]] = CSP(words, locations)
    csp.add_constraint(WordSearchConstraint(words))
    
    # solution
    solution:Optional[Dict[str, List[GridLocation]]] = csp.backtracking_search()
    if solution is None:
        print("답을 찾을 수 없습니다!")
    else:
        for word, grid_locations in solution.items():
            if choice([True, False]):
                grid_locations.reverse()
            for index, letter in enumerate(word):
                (row, col) = (grid_locations[index].row, grid_locations[index].column)
                grid[row][col] = letter
        display_grid(grid)

실행 결과

Y W E H T T A M J
M A R Y D S F Q O
R M B A F A Y A E
O S Y C Y R L R P
R I W Z P A L A Z
K T T H M H A P K
C T L X T I S C C
C E H C S E O R X
M I Z A H L G W Z

연습문제

📝 3-1

WordSearchConstraint 클래스를 수정하여 중복 단어를 허용하는 단어 검색을 구현하라.

…

📝 3-2

회로판 레이아웃 문제

단어 검색 문제 알고리즘을 응용하여 해결할 수 있다. 격자는 무작위 영문자 대신 빈 칸으로 채워진다. 경계를 명확히 표시하기 위해 특수문자를 사용한다.

def generate_grid(rows:int, columns:int) -> Grid:
    return [["□" for c in range(columns)] for r in range(rows)]

기존 알고리즘의 D는 문자열 타입으인덱스와 이에 대응하는 문자로 격자를 채울 수 있었다.

회로판 레이아웃 문제에서는 M x N 사각형의 칩을 사용한다. 사각형의 크기와, 격자판에 표시할 문자를 나타내기 위해 타입 D에 문자열 대신 튜플을 사용한다.

words:List[Tuple[str, int, int]] = [("A", 1, 6),
                                    ("B", 4, 4),
                                    ("C", 3, 3),
                                    ("D", 2, 2),
                                    ("E", 5, 2)]
locations:Dict[str, List[List[GridLocation]]] = {}
for word in words:
    locations[word] = generate_domain(word, grid)

solution을 화면에 표시하는 방법을 변경한다. 기존의 반전 요소 역시 삭제한다.

solution:Optional[Dict[str, List[GridLocation]]] = csp.backtracking_search()
if solution is None:
    print("답을 찾을 수 없습니다!")
else:
    for word, grid_locations in solution.items():
        for element in grid_locations:
            row, col = element.row, element.column
            grid[row][col] = word[0]
    display_grid(grid)

사각형의 배치는 단어의 배치보다 덜 복잡하다. 현재 좌표를 기준으로 두 개의 길이 변수를 활용해 계산하여, 사각형의 크기가 격자의 범위를 벗어나지 않는다면 도메인의 항목으로 추가한다.

def generate_domain(word:str, grid:Grid) -> List[List[GridLocation]]:
    domain:List[List[GridLocation]] = []
    height:int = len(grid)
    width:int = len(grid[0])
    length1:int = word[1]
    length2:int = word[2]
    for row in range(height):
        for col in range(width):
            columns:range = range(col, col + length1)
            rows:range = range(row, row + length2)
            if (col + length1 <= width) and (row + length2 <= height):
                domain.append([GridLocation(r, c) for c in columns for r in rows])
    return domain

전체 코드는 다음과 같다.

연습문제 3-2.py

from typing import NamedTuple, List, Dict, Optional, Tuple
from csp import Constraint, CSP

Grid = List[List[str]]


class GridLocation(NamedTuple):
    row:int
    column:int


def generate_grid(rows:int, columns:int) -> Grid:
    return [["□" for c in range(columns)] for r in range(rows)]

def display_grid(grid:Grid) -> None:
    for row in grid:
        print(" ".join(row))

def generate_domain(word:str, grid:Grid) -> List[List[GridLocation]]:
    domain:List[List[GridLocation]] = []
    height:int = len(grid)
    width:int = len(grid[0])
    length1:int = word[1]
    length2:int = word[2]
    for row in range(height):
        for col in range(width):
            columns:range = range(col, col + length1)
            rows:range = range(row, row + length2)
            if (col + length1 <= width) and (row + length2 <= height):
                domain.append([GridLocation(r, c) for c in columns for r in rows])
    return domain


class WordSearchConstraint(Constraint[str, List[GridLocation]]):
    def __init__(self, words:List[Tuple[str, int, int]]) -> None:
        super().__init__(words)
        self.words:List[Tuple[str, int, int]] = words

    def satisfied(self, assignment:Dict[str, List[GridLocation]]) -> bool:
        all_locations = [locs for values in assignment.values() for locs in values]
        return len(set(all_locations)) == len(all_locations)


if __name__ == "__main__":

    # V
    grid:Grid = generate_grid(9, 9)

    # D
    words:List[Tuple[str, int, int]] = [("A", 1, 6),
                                        ("B", 4, 4),
                                        ("C", 3, 3),
                                        ("D", 2, 2),
                                        ("E", 5, 2)]
    locations:Dict[str, List[List[GridLocation]]] = {}
    for word in words:
        locations[word] = generate_domain(word, grid)

    # constraint
    csp:CSP[str, List[GridLocation]] = CSP(words, locations)
    csp.add_constraint(WordSearchConstraint(words))
    
    # solution
    solution:Optional[Dict[str, List[GridLocation]]] = csp.backtracking_search()
    if solution is None:
        print("답을 찾을 수 없습니다!")
    else:
        for word, grid_locations in solution.items():
            for element in grid_locations:
                row, col = element.row, element.column
                grid[row][col] = word[0]
        display_grid(grid)

실행 결과

A B B B B C C C □
A B B B B C C C □
A B B B B C C C □
A B B B B D D □ □
A □ □ □ □ D D □ □
A E E E E E □ □ □
□ E E E E E □ □ □
□ □ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □ □

📝 3-3

스도쿠 문제

스도쿠 문제는 좌표 개념을 사용해 구현할 수 있다. 같은 행, 열, 구역은 중복을 허용하지 않는 1~9의 숫자로 이루어져 있다.

행: 0행 ~ 8행
열: 0열 ~ 8열
구역: 0구역 ~ 8구역

기존의 GridLocation을 변형한다.

class GridLocation(NamedTuple):
    row:int
    column:int
    realm:int = 3 * (row // 3) + column // 3

realm은 내부적으로 계산된다.

KEY: GridLocation, VALUE: int ok?

3 x 3 크기가 아닌 퍼즐에 대해서는 3, 9 대신 상수를 사용할 수 있다.

SIZE: 구역의 크기(= 3)
WIDTH: 스도쿠 퍼즐의 크기(= 9 = math.pow(SIZE, 2))

satisfied: 현재 GridLocation의 row, column에 대해

같은 row를 가지는 집합의 원소가 될 수 없다.
같은 column을 가지는 집합의 원소가 될 수 없다.
같은 구역에 속하는 집합의 원소가 될 수 없다.

예를 들어 row=3, column=5일 때 realm=4이다

if assignment[GridLocation[3][5]] in rows[GridLocation.row]: return False