<div id="readability-page-1" class="page"><div aria-label="Content">
 <article itemscope="" itemtype="http://schema.org/BlogPosting">

 

 <div itemprop="articleBody">
 Reference: <a href="https://youtu.be/Zq4upTEaQyM">Back to Back SWE - The Backtracking Blueprint</a>

<h2 id="개요">개요</h2>

Sudoku를 통해 알아보는 Backtracking

핵심: Choice / Constraints / Goal

<ul>
 <li>Choice: You have a decision</li>
 <li>Constraints: Your decisions are restricted</li>
 <li>Goal: Your goal</li>
</ul>

어떻게 이것을 풀 것인가?

<ol>
 <li>Choice: 문제가 주어졌을 때 어떻게 풀 것인가?</li>
</ol>

<ul>
 <li>Sudoku board의 경우 board의 cell을 채워야 한다.</li>
 <li>여기서 cell을 주목하자.</li>
 <li>cell은 row와 column에 있다. &lt;- 이 부분이 우리의 리드다</li>
</ul>



자 이제 어떻게 문제를 어떻게 진행할까?

<ol>
 <li>
 전체 Sudoku 보드를 전부 접근하지 말고, 가장 첫번째 row부터 집중하는 것으로 narrow down 해보자.
 </li>
 <li>
 이제 cell에 뭘 채울 수 있는지를 생각해보자. 1 ~ 9 사이의 숫자를 채울 수 있다.
 </li>
</ol>

<ul>
 <li>이제 빈 cell에 대해서 반복문을 넣어보자.</li>
</ul>

<div><pre><code>solve(row, col ...) {

 for (int value = 1; value &lt;= 9; value++) {
 board[row][col] = value;
 }

}
</code></pre></div>

<ol>
 <li>이제 모든 항목을 넣을 수는 없으니까, Constraint를 결정하자.</li>
</ol>

<ul>
 <li>여기서 validation에 해당하는 항목이 들어간다.
 <ul>
 <li>row를 break하는가?</li>
 <li>column을 break하는가?</li>
 <li>sub-group을 break하는가?</li>
 </ul>
 </li>
</ul>

<div><pre><code>solve(row, col ...) {

 for (int value = 1; value &lt;= 9; value++) {
 board[row][col] = value;

 if (validPlacement(row, col, ...)) {
 if (solve(row, col + 1, board)) {
 return true;
 }
 }

 }

}
</code></pre></div>

<ol>
 <li>검증 과정을 거치고 다음번 solve로 넘어간다.</li>
</ol>

<ul>
 <li>그런데 왜 <code>col</code>일까? 왜냐면, 하나를 해결하면 다음으로 넘어가고, 그 다음으로 넘어가기 때문이다.</li>
 <li><code>col</code>을 다 했는데, 아직 <code>row</code>가 끝이 아니라면 어떻게 될까?
 <ul>
 <li>자연스럽게 다음 번 <code>row</code>로 넘어간 후, 첫 번째 cell부터 작업을 다시 하면 된다.</li>
 </ul>
 </li>
</ul>

<ol>
 <li>여기서 base case가 생긴다.</li>
</ol>

<div><pre><code>solve(row, col ...) { // Sub problem
 if (col == board[row].length) {
 // ...base case question
 }

 for (int value = 1; value &lt;= 9; value++) { // Decision space
 board[row][col] = value;

 if (validPlacement(row, col, ...)) { // Converge to a base case
 if (solve(row, col + 1, board)) {
 return true;
 }
 }
 }

 board[row][col] = EMPTY_ENTRY; // undo our decision when it fails

}
</code></pre></div>

 </div>
 
 
</article>

 </div></div>

immigration9

Reference: Back to Back SWE - The Backtracking Blueprint
개요
Sudoku를 통해 알아보는 Backtracking
핵심: Choice / Constraints / Goal
Choice: You have a decision
Constraints: Your decisions are restricted
Goal: Your goal
어떻게 이것을 풀 것인가?
Choice: 문제가 주어졌을 때 어떻게 풀 것인가?
Sudoku board의 경우 board의 cell을 채워야 한다.
여기서 cell을 주목하자.
cell은 row와 column에 있다. <- 이 부분이 우리의 리드다
solve(row, col ...) {
}
자 이제 어떻게 문제를 어떻게 진행할까?
전체 Sudoku 보드를 전부 접근하지 말고, 가장 첫번째 row부터 집중하는 것으로 narrow down 해보자.
이제 cell에 뭘 채울 수 있는지를 생각해보자. 1 ~ 9 사이의 숫자를 채울 수 있다.
이제 빈 cell에 대해서 반복문을 넣어보자.
solve(row, col ...) {
 for (int value = 1; value <= 9; value++) {
 board[row][col] = value;
 }
}
이제 모든 항목을 넣을 수는 없으니까, Constraint를 결정하자.
여기서 validation에 해당하는 항목이 들어간다.
 
row를 break하는가?
column을 break하는가?
sub-group을 break하는가?
solve(row, col ...) {
 for (int value = 1; value <= 9; value++) {
 board[row][col] = value;
 if (validPlacement(row, col, ...)) {
 if (solve(row, col + 1, board)) {
 return true;
 }
 }
 }
}
검증 과정을 거치고 다음번 solve로 넘어간다.
그런데 왜 col일까? 왜냐면, 하나를 해결하면 다음으로 넘어가고, 그 다음으로 넘어가기 때문이다.
col을 다 했는데, 아직 row가 끝이 아니라면 어떻게 될까?
 
자연스럽게 다음 번 row로 넘어간 후, 첫 번째 cell부터 작업을 다시 하면 된다.
여기서 base case가 생긴다.
solve(row, col ...) { // Sub problem
 if (col == board[row].length) {
 // ...base case question
 }
 for (int value = 1; value <= 9; value++) { // Decision space
 board[row][col] = value;
 if (validPlacement(row, col, ...)) { // Converge to a base case
 if (solve(row, col + 1, board)) {
 return true;
 }
 }
 }
 board[row][col] = EMPTY_ENTRY; // undo our decision when it fails
}

Backtracking Programming Problems

댓글