Constraint Programming Using Choco
1. 개요
이 튜토리얼에서는 인기 있는 Java 제약 프로그래밍(CP) 프레임워크인 Choco-solver에 대해 배웁니다.
전반적으로 CP의 기본 개념을 간략하게 이해하고 Choco-solver 라이브러리의 주요 개념을 살펴보겠습니다. 마지막으로 이 라이브러리를 사용하여 스도쿠 퍼즐을 해결하는 작은 프로그램을 만들어 볼 것입니다.
2. 제약 프로그래밍 개념
CP는 조합 문제를 해결하는 데 도움이 되는 전통적인 결정론적 또는 명령형 프로그래밍과는 다른 패러다임입니다. 제약 프로그래밍 관련 몇 가지 사용 사례로는 스케줄링, 계획 수립, 경로 설정, 포장, 자원 할당, 스도쿠 퍼즐 해결 등이 있습니다.
- 변수: X1, X2, X3,…, Xn의 집합
- 영역: 미지수의 가능한 값으로 D1, D2, D3,…, Dk로 표현됨
- 제약 조건: 변수에 영역 값이 할당될 때 충족해야 하는 규칙 또는 기준으로 C1, C2, C3,…, Cm로 표현됨
- 일반적으로 P = (X, D, C)로 표현되며, 여기서 P는 문제를 의미합니다.
3. 필수 조건
Choco-solver를 사용하기 전에 필요한 Maven 의존성을 가져오도록 하겠습니다:
<dependency>
<groupId>org.choco-solver</groupId>
<artifactId>choco-solver</artifactId>
<version>4.10.14</version>
</dependency>
4. Choco-solver의 주요 구성 요소
Choco-solver 프레임워크의 주요 구성 요소를 살펴보겠습니다. 이 라이브러리에서 Model 클래스는 변수와 제약 조건을 보유하는 컨테이너 또는 컨텍스트입니다.
Variable 및 Constraint 클래스는 CP 프로그래밍 패러다임에서 변수와 제약 조건을 나타냅니다. Model 클래스는 변수와 해당 도메인 값을 효율적으로 정의하는 메서드를 포함한 IVariableFactory 인터페이스를 구현합니다. 또한 단일 및 다차원 배열의 도메인 값을 생성할 수 있는 기능은 복잡한 문제를 모델링하는 데 뛰어난 유연성과 편리함을 제공합니다.
또한 Model 클래스는 IIntConstraintFactory와 같은 제약 공장 인터페이스를 구현합니다. 따라서 arithm(), sum(), allDifferent() 등과 같은 메서드는 변수 간의 산술 관계 정의에 도움을 줍니다. 이 라이브러리는 더 복잡한 제약 조건을 설정하기 위한 수많은 다른 메서드를 제공합니다.
변수 및 제약 조건을 정의한 후, 우리는 Model#getSolver() 메서드를 호출하여 Solver 클래스를 가져올 수 있습니다. 다음으로, Solver#solve() 및 Solver#findSolution()과 같은 메서드는 해결책을 찾는 데 도움을 줍니다.
또한 이 기사는 Choco-solver 라이브러리의 더 넓은 기능에 대한 미리보기에 불과합니다. 이 라이브러리의 더 복잡한 기능을 탐색할 수 있는 추진력을 제공합니다.
다음 섹션에서는 스도쿠 보드의 솔루션을 구현할 때 더 많은 것을 배울 것입니다.
5. 빈 스도쿠 보드 해결하기
스도쿠 보드는 1에서 9까지의 고유 값을 가진 아홉 개의 3 x 3 행렬로 구성된 9 x 9 행렬입니다.
빈 스도쿠 보드는 여러 솔루션을 가질 수 있습니다. 각 셀을 1에서 9 까지의 도메인 값을 가진 변수로 표현하고 Choco-solver 라이브러리를 사용하여 SudokuSolver 클래스를 구현할 것입니다.
5.1. 여러 솔루션 찾기
SudokuSolver#findSolutions() 메서드를 살펴보겠습니다:
List<Integer[][]> findSolutions(final int MAX_SOLUTIONS) {
IntVar[][] sudokuCells = createModelAndVariables();
setConstraints(sudokuCells);
List<Integer[][]> solvedSudokuBoards = getSolutions(MAX_SOLUTIONS);
return solvedSudokuBoards;
}
이 메서드는 모델과 해당 변수를 sudokuCells에 생성합니다. 그런 다음, 변수에 대해 제약 조건을 설정하고 마지막으로 솔루션을 가져옵니다.
5.2. 모델 및 변수 생성
createModelAndVariables() 메서드는 Model을 인스턴스화하고 9 x 9 행렬을 반환합니다:
IntVar[][] createModelAndVariables() {
sudokuModel = new Model("Sudoku Solver");
IntVar[][] sudokuCells = sudokuModel.intVarMatrix("board", 9, 9, 1, 9);
return sudokuCells;
}
먼저, Sudoku Solver라는 식별자로 Model 객체를 생성합니다. 다음으로, 새로 생성된 Model 객체에 대해 Model#intVarMatrix()를 호출하여 9 x 9의 2차원 행렬을 생성합니다. 이 행렬에는 1에서 9까지의 도메인 값을 가진 IntVar 변수가 포함됩니다.
5.3. 변수에 제약 조건 설정
다음 단계에서는 Model 객체의 도메인 변수에 제약 조건을 설정합니다:
void setConstraints(IntVar[][] sudokuCells) {
for (int i = 0; i < 9; i++) {
IntVar[] rowCells = getRowCells(sudokuCells, i);
sudokuModel.allDifferent(rowCells).post();
IntVar[] columnCells = getColumnCells(sudokuCells, i);
sudokuModel.allDifferent(columnCells).post();
}
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
IntVar[] cellsInRange = getCellsInRange(j, j + 2, i, i + 2, sudokuCells);
sudokuModel.allDifferent(cellsInRange).post();
}
}
}
getRowCells() 및 getColumnCells() 메서드는 각각 ith 행 및 열의 모든 셀을 반환합니다. 그런 다음, Model#allDifferent()는 스도쿠 보드의 아홉 개 행과 열 각각에서 검색된 셀 변수를 제약하도록 설정합니다. 이로써 1-9의 도메인 값이 어떤 행이나 열에서도 반복되지 않도록 보장합니다.
또한 모든 3 x 3 그리드의 셀을 검색하고 해당 셀에 고유한 값을 보장하기 위해 제약 조건을 적용합니다.
5.4. 솔루션 가져오기
마지막으로 제약 조건을 설정한 후 getSolutions() 메서드를 호출합니다:
List<Integer[][]> getSolutions(int MAX_SOLUTIONS) {
List<Integer[][]> solvedSudokuBoards = new ArrayList<>();
int solutionCount = 0;
while (sudokuModel.getSolver().solve()) {
if (solutionCount++ > MAX_SOLUTIONS - 1) {
break;
}
IntVar[] solvedSudokuCells = sudokuModel.retrieveIntVars(true);
solvedSudokuBoards.add(getNineByNineMatrix(solvedSudokuCells));
sudokuModel.getSolver().reset();
}
return solvedSudokuBoards;
}
이 메서드는 솔루션을 포함하는 여러 2차원 배열을 List로 반환합니다. Model#getSolver()는 Solver 객체를 가져와, 그 위에서 Solver#solve()를 호출하여 Model의 IntVar 변수를 솔루션으로 채웁니다.
나중에 Model#retrieveIntVars()를 호출하여 배열에서 모든 셀 값을 검색합니다. 루프의 끝에서 Solver#reset()을 호출하여 변수 값을 초기화합니다. 이후 라이브러리는 다음 반복에서 변수에 새 솔루션을 채웁니다.
5.5. 결과
이제 SudokuSolver#findSolutions() 메서드를 실행하여 결과를 확인해보겠습니다:
void whenSudokuBoardIsEmpty_thenFindTwoSolutions() {
SudokuSolver sudokuSolver = new SudokuSolver();
List<Integer[][]> sudokuSolutionMatrices = sudokuSolver.findSolutions(2);
sudokuSolutionMatrices.forEach(e -> checkValidity(e));
sudokuSolutionMatrices.forEach(sudokuSolver::printSolution);
}
이 프로그램은 빈 스도쿠 보드에 대한 두 가지 가능한 솔루션을 찾는 데 도움을 줍니다. 솔루션을 찾은 후에는 checkValidity()를 호출하여 결과를 검증합니다. 마지막으로 SudokuSolver#printSolution() 메서드를 사용하여 9 x 9 스도쿠 보드를 출력합니다:
3 7 2 | 1 5 6 | 4 9 8
8 4 5 | 2 3 9 | 6 7 1
1 9 6 | 8 7 4 | 3 2 5
---------------------
5 3 1 | 6 2 7 | 8 4 9
4 2 9 | 3 8 5 | 7 1 6
7 6 8 | 4 9 1 | 2 5 3
---------------------
9 1 4 | 7 6 3 | 5 8 2
6 8 7 | 5 1 2 | 9 3 4
2 5 3 | 9 4 8 | 1 6 7
유사하게 여러 솔루션을 검색하고 출력할 수 있습니다.
6. 부분적으로 해결된 스도쿠 보드 해결하기
스도쿠 퍼즐에서는 일반적으로 보드가 부분적으로 채워져 있습니다. 이번에는 문제를 이전 섹션과 유사하게 접근할 것이며, 그러나 이번에는 단일 솔루션이 있을 것입니다.
6.1. 단일 솔루션 찾기
이런 경우를 위해 SudokuSolver 클래스에 findSolution() 메서드를 구현합니다:
Integer[][] findSolution(int[][] preSolvedSudokuMatrix) {
IntVar[][] sudokuCells = createModelAndVariables();
setConstraints(sudokuCells, preSolvedSudokuMatrix);
Solution solution = sudokuModel.getSolver().findSolution();
IntVar[] solvedSudokuCells = solution.retrieveIntVars(true).toArray(new IntVar[0]);
return getNineByNineMatrix(solvedSudokuCells);
}
이 프로그램은 변수를 선언하고 제약 조건을 설정하는 것은 이전과 같지만, 이전 예제와는 달리 기능이 오버로딩된 setConstraints() 메서드를 두 번째 이차원 배열 인수와 함께 호출합니다. 미해결 셀은 이차원 preSolvedSudokuMatrix 배열에서 0 값으로 표현됩니다.
이제 setConstraints() 메서드를 살펴보겠습니다:
void setConstraints(IntVar[][] sudokuCells, int[][] preSolvedSudokuMatrix) {
setConstraints(sudokuCells);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (preSolvedSudokuMatrix[i][j] != 0) {
sudokuCells[i][j].eq(preSolvedSudokuMatrix[i][j])
.post();
}
}
}
}
첫째, setConstraints()에 대한 호출은 이전과 같이 기본 제약 조건을 설정하는 데 도움을 줍니다. 그런 다음,
eq() 메서드는 ArExpression 인터페이스에서 상속받아, preSolvedSudokuMatrix에서 미리 입력된 셀 값을 할당하는 제약 조건을 적용합니다.
마지막으로 SudokuSolver#findSolution() 메서드에서는 Solver#findSolution()을 호출하여 Solution 객체를 얻습니다. 결국 Solution#retrieveIntVars()는 채워진 셀을 검색하는 데 도움을 줍니다.
6.2. 결과
부분적으로 채워진 스도쿠 보드를 고려해 보겠습니다:
이제 SudokuSolver#findSolution() 메서드를 실행하여 나머지 필드를 채워보겠습니다:
void whenSudokuPartiallySolved_thenFindSolution() {
SudokuSolver sudokuSolver = new SudokuSolver();
Integer[][] solvedSudokuBoard = sudokuSolver.findSolution(initialValues);
checkValidity(solvedSudokuBoard);
sudokuSolver.printSolution(solvedSudokuBoard);
}
SudokuSolver#findSolution()의 결과를 checkValidity() 메서드를 사용하여 검증합니다. 그 후, 솔루션을 출력합니다:
9 8 4 | 7 5 1 | 2 6 3
5 7 3 | 4 6 2 | 8 9 1
1 6 2 | 9 3 8 | 5 4 7
---------------------
2 4 5 | 8 1 3 | 9 7 6
7 9 8 | 6 2 4 | 3 1 5
6 3 1 | 5 9 7 | 4 2 8
---------------------
8 1 6 | 3 4 9 | 7 5 2
3 5 9 | 2 7 6 | 1 8 4
4 2 7 | 1 8 5 | 6 3 9
7. 결론
이 기사에서는 조합 문제를 해결하기 위한 다재다능하고 표현력이 풍부한 오픈 소스 라이브러리인 Choco-solver에 대해 살펴보았습니다.
이 라이브러리는 변수, 도메인 값 및 제약 조건을 정의함으로써 문제를 거의 선언적으로 모델링하는 데 도움을 줍니다. 따라서 도메인 특정 논리를 작성하지 않고도 여러 솔루션을 얻을 수 있습니다.
일반적으로 이 기사에서 사용된 소스 코드는 GitHub에서 확인할 수 있습니다.
![POE(패스오브엑자일) 인벤 자동 정리 !!! [1]](http://13.209.78.165/wp-content/uploads/2019/06/PoE-Inven-Organize.png)
