잡담을 위한 소박한 장소

MathJax.Hub.Config({ jax: ["input/TeX","output/HTML-CSS"], tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], processEscapes: true }, "HTML-CSS": { availableFonts: ["STIX", "TeX"], // Add "STIX" for Word style formula preferredFont: "STIX" }, TeX: { equationNumbers: { autoNumber: "AMS" } } }); 이번 포스팅에서는, 대다수의 고급 전략들의 공통분모라 할 수 있는 XY-날개에 대하여 알아보고, 또 이 전략을 바라보는 여러 관점을 소개함으로써 앞으로 등장할 색칠 전략, 연쇄 고리 전..

MathJax.Hub.Config({ jax: ["input/TeX","output/HTML-CSS"], tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], processEscapes: true }, "HTML-CSS": { availableFonts: ["STIX", "TeX"], // Add "STIX" for Word style formula preferredFont: "STIX" }, TeX: { equationNumbers: { autoNumber: "AMS" } } }); 이번 포스팅에서는 가두기 전략에 대하여 설명하고자 합니다. 교차로 가두기 Strategy : Intersection Lock스도쿠에는 주어진 영역 내에서 숫자들이 특정한 조건을 만족시켜..

이번 포스팅에서는 기본적인 전략 바로 다음에 등장하는 전략들을 살펴보고자 합니다. 1. 드러난 부분집합 이전 포스팅에서 우리는 드러난 하나 전략에 대하여 알아본 바 있습니다. 드러난 하나 전략을 후보 숫자들을 셈하는 접근할 경우, 전략의 논리 자체는 칸 한에는 하나의 숫자가 들어가야 한다는 규칙 자체에서 곧바로 따라나왔었지요. 그리고 이 논리는 여러 칸을 동시에 생각하는 경우에도 비슷하게 확장됩니다. 우선 전략부터 살펴보기로 합시다. 이를 위하여, 용어를 하나 정의하고 넘어가겠습니다. 정의. 스도쿠 퍼즐에서 유닛(unit)이란 각각의 행, 열, 혹은 상자를 가리킨다. 이때, 드러난 하나 전략을 일반화한 드러난 부분집합(naked subset) 전략은 다음과 같이 서술할 수 있습니다. 전략 (드러난 부분집..

이번 포스팅에서는 가장 기본적인 전략에 대하여 살펴보려고 합니다. 1. 기본적인 후보 지우기 전략 서로 다른 두 칸이 같은 행이나 같은 열, 혹은 같은 상자 안에 들어있을 때, 서로를 볼 수 있다고 부릅니다. 스도쿠의 규칙에 의하면, 서로를 바라볼 수 있는 두 칸이 서로 같은 값으로 결정되서는 안됩니다. 그리고 이 간단한 관찰로부터 우리는 다음과 같이 아주 간단하면서도 강력한 전략인 기본적인 후보 지우기(obvious candidate removal) 전략을 얻게 됩니다. 전략 (기본적인 후보 지우기). 숫자가 n으로 결정된 각각의 칸에 대하여, 그 칸을 볼 수 있는 다른 모든 칸들에 포함된 후보 숫자(연필마크) n을 지울 수 있다. 아래는 예제입니다. 예제 1. 기본적인 후보 지우기 전략을 사용하여 후..

2022/11/06 에 포맷을 다듬고 수학 부분의 내용을 싹 갈아엎었습니다. 이번 포스팅 시리즈에서는 스도쿠의 다양한 전략들을 살펴보고 수학적으로 분석해보고자 합니다. 설명의 단계를 나누어, 일반인들을 위한 부분과 수학적인 부분을 최대한 분리하고 단계를 나누려고 노력하였습니다. 그리고 많은 예제도 소개할 예정입니다. 1. 스도쿠란? 스도쿠(数独; Sudoku)는 9×9 칸의 격자에 1 부터 9 까지의 숫자를 채워넣는 숫자 퍼즐 게임입니다. 특히 격자가 아래와 같이 3×3 짜리 상자들로 다시 나누어져 있어, 각 행, 열 그리고 상자마다 1 부터 9 까지의 숫자를 단 한 번만 들어가도록 채우는 게임입니다. 게임 자체가 등장한 지는 역사적으로 꽤 오래 되었지만, 결정적으로 1986년에 니코리라는 일본 퍼즐 게..