디지털 컴퓨터에서, 정보의 최소 단위인 비트는 두 가지 상태만을 가진다.
즉, 컴퓨터로 “무엇인가를” 표현하기 위해서는 그것을 0과 1로만 나타낼 수 있어야 된다는 것이다.
예를 들어, 시각(時刻), 색, 사진, 음악은 보통 다음과 같이 기록된다.
시각은 특정 시점을 잡은 뒤, 그 시점부터 지난 시간을 세어 기록한다.
색은 적절한 색 공간을 잡은 뒤, 그 공간 상의 좌표를 이용해 기록한다.
사진은 작은 영역들(픽셀)로 나눈 뒤, 각 영역의 색을 이용해 기록한다.
소리는 일정한 시간마다 공기의 압력을 측정하고, 측정값을 일렬로 기록한다.
이 모든 것의 기본은 숫자, 그 중에서도 정수를 0과 1로 나타내는 것이다.
언뜻 보면 매우 간단해 보이는 일이다. 그냥 이진법으로 숫자를 나타내면 되는 거 아닌가?
하지만 여기에는 다음과 같은 세 가지 문제점이 숨겨져 있다.
숫자 하나를 나타내는 데 비트를 몇 개 써야 할까?
음수는 어떻게 나타내어야 할까?
비트(혹은 비트의 묶음인 바이트)의 순서는 어떻게 정할까?
이번 글에서는 1번과 2번에 초점을 두어, C++에서 정수를 다룰 때 어떤 점을 주의해야 할 지에 대해 이야기해 보자.
C++ 이외에도 러스트, 파이썬, 자바스크립트와 같은 다른 언어에 대해서도 간단히 다룰 것이지만,
C++에서 흥미로운 문제를 많이 다룰 수 있으므로(?) C++을 메인으로 삼는다.
3번의 경우 리틀 엔디언 / 빅 엔디언 등과 관련이 있는 문제로,
네트워크 프로그래밍이나 여러 CPU를 고려해야 되는 코드의 경우 추가적으로 고려해야 되는 점이다.
하지만 나는 빅 엔디언을 사용하는 프로그래밍을 해 본 경험이 거의 없기 때문에 이 글에서는 굳이 다루지 않기로 하자.
간단히 말해, 모든 코드는 x86 혹은 amd64 아키텍처 상에서 돌아간다고 가정하자.
오버플로우
메모리가 허락하는 한, 숫자 하나를 표현하는 데 필요한 비트의 수에는 제한이 없다.
예를 들어, 대략 10메가바이트의 메모리를 이용하면 현재까지 알려진 제일 큰 소수인 M82589933을 표현할 수 있다.
{ const solver = new SudokuSolver([ new LineConstraint, new GroupConstraint, new KnightConstraint, new VertexNeighborConstraint, new NoConsecutiveConstraint, new ThermoConstraint([[57, 56, 55], [24, 15]]), ]);
console.log("힌트 없는 스도쿠 해답:"); solver.solve().forEach((board) => { console.log(board.toString()); }); }
그 사실을 증명한 논문은 상당히 길었지만 읽을 만한 논문이였고, 대략적인 방법은 의외로 간단했다.
스도쿠 판을 채우는 모든 각각의 경우의 수에 대해,
힌트가 16개인 스도쿠 퍼즐을 만들고,
모든 퍼즐을 직접 풀어보아 해가 유일하지 않음을 증명한다.
위 작업을 하는데 대략 1년이 걸렸고, CPU 코어 하나로 모든 경우의 수를 살펴봤다면 대략 800년이 걸릴 정도의 연산을 했다고 한다.
또한, 스도쿠 판을 채우는 한 가지 경우에 대해 힌트가 16개인 모든 퍼즐을 살펴보는데 평균 3.6초가 걸렸다고 한다.
자연스럽게 두 가지 의문점이 생겼다.
스도쿠 판을 채우는 한 가지 경우에 대해, 대체 어떻게 3.6초만에 모든 퍼즐을 만들고 풀 수 있었을까?
단순히 모든 퍼즐을 생성하는 경우의 수는 \( {81 \choose 16} \simeq 3.4 \times 10^{16} \)가지로, 지나치게 많다.
대체 어떻게 스도쿠 판을 채우는 모든 경우에 대해 조사를 했을까?
첫 번째 질문에 대한 답은 유일해가 존재할 가능성이 있는 퍼즐만을 고려해, 생성된 퍼즐의 개수를 최소화했다는 것이다.
구체적인 개수는 논문에 적혀있지 않지만, 논문에 사용된 스도쿠 솔버가 1초에 5만개의 퍼즐을 처리할 수 있었다고 언급되어 있으므로,
한 가지 스도쿠 해답에 대해 겨우 20만개 정도의 퍼즐을 만들었다는 것을 알 수 있다.
어떻게 하면 효율적으로 퍼즐을 생성할 수 있는지에 대해서는 나중에 살펴보기로 하자.
두 번째 질문에 대한 답은 간단한데, 스도쿠 판을 채우는 경우의 수 중에서 “필수적으로 고려해야 되는” 경우의 수는 생각보다 적기 때문이다.
논문에는 다음과 같은 사실이 명시되어 있다.
스도쿠 판을 채우는 경우의 수는 총 \( 6,670,903,752,021,072,936,960 \simeq 6.7 \times 10^{21} \)가지이다.
하지만 이 경우를 모두 살펴볼 필요는 없다. 스도쿠 퍼즐의 최소 힌트의 개수는 다음과 같은 변환을 해도 유지되기 때문이다.
1-9의 숫자들을 다른 값으로 변경
퍼즐을 뒤집거나 돌림
3개씩 묶인 열/행에 대해, 묶음을 재배열
각 묶음 안의 줄을 재배열
이런 경우들을 제외하고, 필수로 살펴보아야 되는 스도쿠 해답의 경우의 수는 총 \( 5,472,730,538 \simeq 5.5 \times 10^{9} \)가지이다.
모든 경우의 수를 압축하지 않고 저장하면 418GB정도 된다.
적절한 압축을 하고 저장하면 6GB 미만의 공간을 차지한다.
저걸 보니, 저 숫자들은 또 어떻게 알아낸건지 궁금해졌고, 이 페이지에서 그 방법을 찾을 수 있었다.
이 블로그 포스트에서는 스도쿠 해답의 경우의 수인 \( 6.7 \times 10^{21} \)를 어떻게 계산할 수 있는지 알아보자.
(여담인데, 노가다가 아닌 방법으로 경우의 수를 구하는 건 언제나 흥미롭다고 생각한다.)
만약 1초에 1억개의 스도쿠 해답을 본다면, 모든 스도쿠 해답을 보는 데에는 대략 210만년의 시간이 걸린다.
즉, 단순히 모든 해답을 살펴보는 방식으로는 스도쿠 해답의 경우의 수를 계산하는 것은 불가능하다는 뜻이다.
맨 왼쪽 위 블록을 고정한다고 해도, 6년이라는 시간이 걸리므로 이보다는 더 나은 방법이 사용했을 것이다.
논문에서 서술한, 스도쿠 판을 채우는 모든 경우의 수를 세는 방법은 생각보다는 의외로 간단했다.
맨 왼쪽 위 블록(3x3 칸 묶음)의 숫자를 고정한다. (경우의 수가 9!배 줄어든다.)
첫 세 줄을 채우는 경우의 수에 대해,
나머지 여섯 줄을 채우는 경우의 수를 구한다.
여기서 2번 과정과 3번 과정을 무식하게 바로 진행하면 사실상 (맨 왼쪽 위 블록이 고정된) 모든 경우의 수를 세어 보는 것과 같은데,
실제로는 조금 머리를 굴려 직접 세야 될 경우의 수를 줄일 수 있다.
첫 세 줄 채우기
우선 맨 왼쪽 위 블록을 다음과 같이 고정하자.
123|...|...
456|...|...
789|...|...
첫 세 줄을 채우는 경우의 수는, 다음과 같이 계산할 수 있다.
가운데 블록의 첫 줄 세 숫자와, 오른쪽 블록의 첫 줄 세 숫자를 (순서 고려하지 않고) 정하는 경우의 수는 \( {6 \choose 3} = 20 \)가지이다.
가운데 블록의 첫 줄 세 숫자가 456인 경우, 나머지 칸의 숫자는 (같은 블록과 줄 안에서는 순서를 고려하지 않고) 다음과 같이 정해진다.
가운데 블록의 마지막 줄은 123이며, 가운데 줄은 789이다.
오른쪽 블록의 세 줄의 숫자들은 위부터 789, 123, 456이다.
순서를 고려하게 되면,두 블록을 채워넣는 경우의 수는 \( (3!)^6 \)가지이다.
가운데 블록의 첫 줄 세 숫자가 789인 경우에도 경우의 수는 동일하다.
가운데 블록의 첫 줄 세 숫자가 457인 경우, 나머지 칸의 숫자는 (역시 같은 블록과 줄 안에서는 순서를 고려하지 않고) 다음과 같이 정해진다.
가운데 블록에서 6은 마지막 줄에, 8과 9는 가운데 줄에 들어갈 수 있다.
가운데 블록 가운데 줄의 나머지 숫자를 a라고 하자. (a는 1, 2, 3 중 하나가 될 수 있다.)
가운데 블록의 가운데 줄은 89a, 마지막 줄은 6bc이다. (b, c는 1, 2, 3중 a가 아닌 다른 두 숫자이다.)
오른쪽 블록의 세 줄의 숫자들은 위부터 689, 7bc, 45a이다.
순서를 고려하게 되면, a가 정해져 있을 때 두 블록을 채워넣는 경우의 수는 \( (3!)^6 \)가지이다.
a를 고르는 경우의 수는 3이므로, 두 블록을 채워놓는 총 경우의 수는 \( 3 \times (3!)^6 \)가지이다.
이 경우의 수는 가운데 블록의 첫 줄 세 숫자중 한 개 혹은 두 개가 456 중에 있고, 나머지 숫자가 789 중에 있을 때에는 같다.
즉, 왼쪽 위 블록을 고정한 상태로 스도쿠 퍼즐의 첫 세 줄을 채우는 총 경우의 수는 다음과 같다.
\[ 2 \times (3!)^6 + 18 \times (3 \times (3!)^6) = 2612736 \]
왼쪽 위 블록이 고정되지 않았다면, 위 숫자에 9!을 곱한 948109639680가지 경우의 수가 가능하다.
260여만 가지 경우의 수를 단순히 돌아보는 것은 쉽게 가능하지만, 각각의 경우에 대해 나머지 여섯 줄을 채우는 경우의 수를 구하기에는 너무 많다.
다만, 다음과 같은 경우 나머지 여섯 줄을 채우는 경우의 수가 변하지 않기 때문에 이런 경우 굳이 다시 셀 필요는 없다는 것을 알 수 있다.
가운데 블록과 오른쪽 블록을 바꾼다.
가운데 블록, 또는 오른쪽 블록의 각 세 열을 교환한다.
이런 식으로 경우의 수를 굳이 다시 고려하지 않아도 되는 경우를 추려내보자.
첫 번째 줄 정렬하기
우선 방금 언급한 것을 고려하여 다음과 같은 경우만 고려한다 해 보자.
가운데 블록의 왼쪽 위 숫자가 오른쪽 블록의 왼쪽 위 숫자보다 작아야 된다. (그렇지 않다면 두 블록을 바꾼다.)
각 블록에 대해, 첫 줄은 오름차순으로 정렬되어 있어야 한다. (그렇지 않다면 열들을 재배열한다.)
이렇게 정렬하는 경우, 총 경우의 수는 \( 2\times(3!)^2 = 72 \)배만큼 줄어들어 36288가지가 된다.
이 정도면 각 경우에 대해 스도쿠 판을 채우는 경우의 수를 구해볼 수도 있을 것 같다.
한 번, 36288가지 경우를 나열하고 그 중 한 가지 경우에 대해 스도쿠 판을 채우는 경우의 수를 구해보자.
/// 간단히 세 숫자를 배열하는 모든 경우의 수를 반환한다. function* permute3([x, y, z]) { yield [x, y, z]; yield [x, z, y]; yield [y, x, z]; yield [y, z, x]; yield [z, x, y]; yield [z, y, x]; } /// 세 숫자들의 묶음 네 개를 배열하는 모든 경우의 수를 반환한다. function* permute3x4(x, y, z, w) { for(let xx of permute3(x)) for(let yy of permute3(y)) for(let zz of permute3(z)) for(let ww of permute3(w)) yield [xx, yy, zz, ww]; } /// 첫 세 줄을 1차원 배열에 저장한 결과들을 나열한다. function* firstThreeRows() { let arr = []; for(let i=0; i<27; ++i) { // 가운데 블록의 맨 왼쪽 위 숫자는 4여야 한다. // 첫 줄의 첫 네 숫자는 1234로 고정 if(i < 4) arr[i] = i+1; // 두 번째 줄과 세 번째 줄의 첫 세 숫자를 456, 789로 고정 elseif(9 <= i && i < 12) arr[i] = i-5; elseif(18 <= i && i < 21) arr[i] = i-11; else arr[i] = 0; } for(let j=5; j<=8; ++j) for(let k=j+1; k<=9; ++k) { // 가운데 블록의 윗 줄을 채운다. [arr[4], arr[5]] = [j, k];
/// 오른쪽 아래 6x6를 채워넣는 경우의 수 구하기 functioncount6x6(stack, rows, columns, groups) { let i = 0; let [row, col, grp] = [0, 0, 0]; let count = 0; let v = 2;
while(true) { // 마지막 칸까지 다 채웠거나, 현재 칸에 가능한 값을 다 넣었을 때 if(i === 36 || v === 1024) { if(i === 0) return count; if(i === 36) ++count; // 이전 칸으로 되돌아가고, 플래그도 다시 되돌린다. v = stack[--i]; if(--col < 0) [row, col] = [row-1, 5]; grp = (0|row/3)*2 + (0|col/3);
for(let leftCols of firstThreeRows()) { // 왼쪽 위 블록이 1-9가 되게 숫자를 다시 적는다. let numberMapCount = 0; for(let i=0; i<3; ++i) for(let j=0; j<3; ++j) { numberMaps[leftCols[coord2ind(j, i)]] = ++numberMapCount; }
/// 스도쿠의 첫 세 행을 채우는 방법을 iterate한다. /// yield되는 값: [중복도, 첫 세 행] function* reducedFirstThreeRows() { const disjointSets = {}; for(let arr of firstThreeRows()) { const key = arr.join(''); if(!(key in disjointSets)) disjointSets[key] = new DisjointSetElem(); // 동등한 경우를 찾아 파티션을 합치자. for(let equivArr of generateEquivPermutations(arr)) { normalizeThreeRows(equivArr);
const equivKey = equivArr.join(''); if(equivKey === key) continue; if(!(equivKey in disjointSets)) disjointSets[equivKey] = new DisjointSetElem(); disjointSets[key].union(disjointSets[equivKey]); } }
{ let reduced = 0; let total = 0; for(let [dup, arr] of reducedFirstThreeRows()) { ++reduced; total += dup; }
console.log(`줄어든 경우의 수: ${total} => ${reduced}`); }
generateEquivPermutations 함수에서…
행을 재배열하는 경우와, 열을 재배열하는 경우를 독립적으로 고려하였다.
열을 재배열하는 경우는, 첫 번째 블록을 다른 블록으로 바꾸는 경우만 고려하였다.
다른 방식으로 해당 함수를 구현해도 결과에는 차이가 없다.
이렇게 하면 고려할 경우의 수가 줄어드는 것을 확인할 수 있는데, 논문과 일치하지 않는 숫자가 출력된다.
블록 재배열을 고려하는 경우, 논문에서는 2051가지 경우의 수로 줄어든다고 적혀 있지만, 실제로 계산된 값은 2081이다.
행 재배열까지 고려하는 경우, 논문에서는 416가지 경우의 수로 줄어든다고 적혀 있지만, 실제로 계산된 값은 426이다.
논문의 오타거나 코드가 잘못됐거나 둘 중 한 가지일텐데, 우선 스도쿠 판을 채울 수 있는 총 경우의 수에는 영향이 없다 가정해 보자.
426가지 경우 각각에 대해 스도쿠를 채울 수 있는 경우의 수를 모두 구하면 대략 하루하고도 반나절 정도 걸린다.
이 시간을 더 줄일 수 있을까?
각 숫자의 열 분포 고려하기
스도쿠의 위 세 줄을 채웠을 때, 아래 여섯 줄을 채우는 경우의 수는 단순히 말하면 단 한가지에 달려 있다.
“각 열에 어떤 숫자들이 있는가?”
그렇다면, 다음과 같은 알고리즘으로 해답의 개수가 동일한 경우를 더 찾을 수 있을 것이다.
위에서 구한 426가지 경우 각각에 대해,
블록 및 블록 안의 열들을 재배치하고,
숫자들을 다른 숫자들로 치환하여,
다른 425가지 경우와 각 열에 오는 수가 같은 경우가 존재하는지 확인한다.
2번 과정의 경우의 수는 \( (3!)^4 = 1296 \)가지밖에 되지 않지만, 3번 과정의 경우의 수는 \( 9! = 362880 \)가지로 조금 많은 듯 하다.
이 때문인지, 논문에서는 이렇게 하는 대신 특정한 직사각형 패턴을 찾아 변경하는 방식으로 동일한 경우를 찾았다.
하지만 조금만 생각해 보면 사실 3번 과정 대신 훨씬 간단한 방식으로 위 알고리즘을 만들 수 있다는 것을 알 수 있게 된다.
즉, 이론상으로도 구현상으로도 논문에서 언급된 방식보다 간단한 방식이 있는 셈이다.
3번 과정을 어떻게 하면 피할 수 있을까?
그 방법은 바로 “각 행에 어느 숫자가 있는지” 대신 “각 숫자가 어느 행에 있는지”를 고려하는 것이다.
예를 들어 다음 세 행에 대해 해답의 개수가 동일한 경우를 더 찾는다고 해 보자.
123|458|679
456|179|238
789|236|145
여기서 각 숫자가 어느 행에 있는지, 1부터 9까지의 숫자에 대해 적으면 다음과 같다.
147 247 358 148 259 367 158 269 369
여기서 첫 세 행의 1과 5를 바꿔 적는다고 하면, 위에서 147과 259가 뒤바뀌게 된다.
하지만 나머지에는 영향을 주지 않으며, 따라서 전체 집합에는 변화가 없다.
집합이 동일한 경우라면 나머지 6x9 칸을 채우는 경우의 수가 동일함을 쉽게 확인할 수 있다.
즉, 3x9를 채워넣는 두 경우의 수에 대해, “숫자를 치환했을 때 각 행에 오게 되는 숫자를 동일하게 만들 수 있는지”를 판단하기 위해서는,
단순히 두 경우에 대해 위와 같이 각 숫자가 어느 행에 있는지에 대한 집합을 만든 다음, 두 집합이 동일한지 판단하면 된다.
다만 블록이나 블록 안의 열들을 재배치 하는 경우에는 위 집합이 달라지지만 나머지 6x9를 채우는 경우의 수에는 변함이 없다.
즉, 위 알고리즘의 2번 과정은 유지한 채로 3번 과정 대신 위와 같은 집합을 만드는 과정을 넣어야 한다.
/// 위 함수에서 반환된 배열을 정렬한다. functionsortColumnConfigs(cols) { // 각 숫자별 행 배치를 정렬한 다음, 행 배치가 오름차순이 되게 정렬하자. // 사족: Array.prototype.sort는 숫자 정렬이 아닌 문자열 정렬이지만, // 한 자리 수에 대해서는 둘이 같으므로 신경 쓰지 말자. cols.forEach((a) => a.sort()); cols.sort(([x0, x1, x2], [y0, y1, y2]) => { if(x0 !== y0) return x0 - y0; if(x1 !== y1) return x1 - y1; return x2 - y2; }); }
/// 스도쿠의 첫 세 행을 채우는 방법을 iterate한다. /// yield되는 값: [중복도, 첫 세 행] function* reducedFirstThreeRows() { const disjointSets = {}; for(let arr of firstThreeRows()) { const key = arr.join(''); if(!(key in disjointSets)) disjointSets[key] = new DisjointSetElem(); // 동등한 경우를 찾아 파티션을 합치자. for(let equivArr of generateEquivPermutations(arr)) { normalizeThreeRows(equivArr);
const equivKey = equivArr.join(''); if(equivKey === key) continue; if(!(equivKey in disjointSets)) disjointSets[equivKey] = new DisjointSetElem(); disjointSets[key].union(disjointSets[equivKey]); } }
// 동등한 숫자 배치가 있는 경우를 찾아 파티션을 합치자. const columnConfigs = {}; for(let key in disjointSets) if(disjointSets[key].isRoot()) { const cols = getColumnConfigs(key.split(''));
각 44개 동치류의 크기는 이 페이지에 적혀 있다.
위 코드의 결과와 동일한지 확인해 보자.
1 2 3 4 5 6 7 8 9 10
// 위 코드의 마지막 블록 안에 추가 const answers = [].map.call( document.querySelectorAll("td b.green"), (node) => +node.innerText ).sort((x, y) => x-y);
if(answers.length === dupArr.length && answers.every((v, i) => v === dupArr[i])) console.info("계산 결과와 알려진 결과가 일치함."); else console.error("계산 결과와 알려진 결과가 일치하지 않음.");
구현 결과, 논문과 동일하게 경우의 수가 44가지로 줄어들고, 각 경우에 대응되는 원래 경우의 수들이 일치하는 것을 확인할 수 있다.
이 44가지 경우에 대해 스도쿠 판의 나머지를 채우는 경우의 수를 구하면 이제 4시간 좀 안 되는 시간이 걸리게 된다.
잠깐만, 그런데 이 아이디어를 6x9의 왼쪽 두 블록을 채울 때에도 적용할 수 있지 않을까?
아이디어는 괜찮지만, 불행히도 경우의 수가 단순히 44가지로 줄어들지는 않는다.
왼쪽 두 블록을 채우는 한 가지 경우에 대해 주대각선(왼쪽 위에서 오른쪽 아래로 향하는 대각선)을 따라 뒤집어 보자.
그 결과는 위쪽 세 블록을 채우는 한 가지 경우가 되지만, 왼쪽 세 열 전체(9x3)가 이미 채워져 있다는 중요한 차이가 있다.
즉, 다음과 같은 변환은 왼쪽 두 블록을 채우는 경우의 수를 줄일 때 적용할 수 없다.
숫자를 다른 숫자로 치환하기
왼쪽 블록을 건드리면서 열 또는 블록을 재배치하기
위 경우를 제외해도 왼쪽 두 블록을 채우는 경우의 수가 줄어들기는 하지만, 불행히도 많이 줄어들지는 못한다.
얼마나 줄어들게 되는지 직접 확인해 보자.
프로그램 코드
reducedFirstThreeRows에 첫 블록을 고정하는 플래그를 추가하고, 위에서 구현했던 count6x9를 다시 구현해 보자.
/// 스도쿠의 첫 세 행을 채우는 방법을 iterate한다. /// fixLeftBlock: true라면, 왼쪽 세 열은 이미 고정되었다고 가정한다. /// yield되는 값: [중복도, 첫 세 행] function* reducedFirstThreeRows(fixLeftBlock=false) { const disjointSets = {}; for(let arr of firstThreeRows()) { const key = arr.join(''); if(!(key in disjointSets)) disjointSets[key] = new DisjointSetElem(); if(fixLeftBlock) continue; // 동등한 경우를 찾아 파티션을 합치자. for(let equivArr of generateEquivPermutations(arr)) { normalizeThreeRows(equivArr);
const equivKey = equivArr.join(''); if(equivKey === key) continue; if(!(equivKey in disjointSets)) disjointSets[equivKey] = new DisjointSetElem(); disjointSets[key].union(disjointSets[equivKey]); } }
// 동등한 숫자 배치가 있는 경우를 찾아 파티션을 합치자. const columnConfigs = {}; for(let key in disjointSets) if(disjointSets[key].isRoot()) { const cols = getColumnConfigs(key.split('')); const process = (blocks, b0, b1, b2) => { const permutedCols = cols.map((a) => a.map((i) => blocks[0|i/3]*3 + [b0, b1, b2][0|i/3][i%3])); if(fixLeftBlock) permutedCols.forEach((a) => a.sort()); else sortColumnConfigs(permutedCols); const colKey = permutedCols.map((a) => a.join('')).join(''); if(colKey in columnConfigs) { const equivKey = columnConfigs[colKey]; disjointSets[key].union(disjointSets[equivKey]); } else { columnConfigs[colKey] = key; } };
/// 첫 세 행이 주어졌을 때, 나머지 6x9를 채워넣는 경우의 수 구하기 /// 가능한 왼쪽 세 열의 목록을 leftColsList로 주어야 한다. functioncount6x9(arr, leftColsList) { while(arr.length < 81) arr.push(0);
for(let [dup, leftCols] of leftColsList) { // 왼쪽 위 블록이 1-9가 되게 숫자를 다시 적는다. let numberMapCount = 0; for(let i=0; i<3; ++i) for(let j=0; j<3; ++j) { numberMaps[leftCols[coord2ind(j, i)]] = ++numberMapCount; }
console.log("Step 1: 위 3x9, 왼쪽 9x3 미리 계산하기"); console.time('Step 1'); const topRowsList = Array.from(reducedFirstThreeRows(false)); const leftColsList = Array.from(reducedFirstThreeRows(true)); console.timeEnd('Step 1');
console.log(`줄어든 경우의 수: 위쪽 ${topRowsList.length}가지, 왼쪽 ${leftColsList.length}가지`);
console.log("Step 2: 특정 케이스에 대해 스도쿠를 완성시키는 경우의 수 구하기"); console.time('Step 2'); // 논문에 의하면 이 경우 완성시키는 데 7053225408가지 경우의 수가 존재한다고 한다. const arr = '123478569456139278789256134'.split('').map((c) => +c); console.log(`스도쿠 판을 완성시키는 경우의 수: ${count6x9(arr, leftColsList)}`); console.timeEnd('Step 2');
Step 1의 경우, 위쪽 세 행을 채우는 데 44가지 경우의 수, 왼쪽 세 열을 채우는 데 22266가지 경우가 있음을 확인할 수 있다.
인내심을 가지고 Step 2를 기다리면, 대략 3분 정도 뒤에 이전과 같은 값이 출력되는 것을 확인할 수 있다.
즉, 왼쪽 두 블록을 채우는 경우의 수가 36288가지에서 22266가지로 조금 줄어들 뿐이다.
다만 스도쿠 퍼즐을 푸는 경우의 수를 구하는 데 걸리는 시간이 2시간에서 조금 더 되는 정도로 줄어들게 되긴 한다.
논문에서도 Guenter Stertenbrink, Kjell Fredrik Pettersen 두 사람이 전체 경우의 수를 1초 안에 셀 수 있는 방법을 개발했다고 서술되어 있다.
어떻게 하면 여기서 계산 시간을 더 줄일 수 있을까?
다섯 블록 한 번에 고려하기
위에서 언급한 숫자를 잘 생각해 보면, 다섯 블록을 채우는 경우의 수가 \( 44 \times 22266 = 979704 \)가지 있다는 사실을 깨달을 수 있다.
간단하게 얻을 수 있는 경우의 수인 \( 36288^2 = 1316818944 \)가지보다 훨씬 적은 값이 된 것이다.
여기서 한 가지 아이디어를 떠올릴 수 있다.
나머지 4개 블록을 채우는 경우의 수는, 6개 행과 열에서 사용된 숫자가 동일하다면 동일하다.
즉, 앞에서 행별 숫자를 고려했던 것처럼 5개 블록에 대해 행/열별 숫자 배치가 동일한 경우를 찾아 줄일 수 있지 않을까?
이렇게 바로 진행해 볼 수 있지만, 한 번 위에서 언급된 셈법도 같은 아이디어를 이용해 셌는지 궁금해서 찾아봤다.
조금 구글링을 해 보니 30ms만에 스도쿠 경우의 수를 구할 수 있는 방법에 대해 서술한
포스트를 찾을 수 있었다.
포스트에 적힌 방법을 요약하면 다음과 같다. 블록의 번호는 왼쪽 위부터 글을 읽는 순서대로 1, 2, 3…번이라고 하자.
2, 3번 블록의 열, 4, 7번 블록의 행에 어떤 숫자가 올지를 고정한다.
2, 3, 4, 7번 블록과 5, 6, 8, 9번 블록 배치를 독립적으로 생성한다.
생성된 두 배치를 합친다.
지금까지 진행한 방법에 어떻게 저 과정을 적용하면 될지 생각해보자.
1, 2, 3번 블록을 채우는 경우의 수 44가지를 찾는다.
1, 2, 3, 4, 7번 블록을 채우는 경우의 수 대략 백만 가지를 찾는다.
2에서 찾은 각 배치별로 4-9번째 행과 4-9번째 열에 어떤 숫자 조합이 올 수 있는지를 기록한다.
5, 6, 8, 9번 블록을 채우는 경우의 수 ??가지를 찾는다.
4에서 찾은 각 배치에 대해 2의 조합 중 남은 숫자 조합이 ‘호환되는’ 경우를 센다.
이 과정을 직접 구현해 볼 수도 있겠지만, 이것까지 구현하려면 블로그 글도 지나치게 길어질 것 같은데다가,
구현하는 데 걸리는 시간이 계산하는 데 걸리는 시간보다 더 길어질 것 같으므로 넘어가기로 하자.
console.log("Step 1: 위 3x9, 왼쪽 9x3 미리 계산하기"); console.time('Step 1'); const topRowsList = Array.from(reducedFirstThreeRows(false)); const leftColsList = Array.from(reducedFirstThreeRows(true)); console.timeEnd('Step 1');
console.log(`줄어든 경우의 수: 위쪽 ${topRowsList.length}가지, 왼쪽 ${leftColsList.length}가지`);
console.log("Step 2: 첫 세 행을 채우는 모든 경우에 대해 나머지를 완성시키는 경우의 수 구하기"); console.time('Step 2'); let count = BigInt(0); for(let [dup, arr] of topRowsList) { const partialCount = BigInt(count6x9(arr, leftColsList)); console.log(`- 크기가 ${dup}인 동치류: ${partialCount}`); count += BigInt(dup) * partialCount; }
// 위 세 줄을 채우는 동일한 72*9!가지 경우의 수를 고려해야 한다. count *= BigInt(72); for(let i=2; i<=9; ++i) count *= BigInt(i); console.timeEnd('Step 2');
console.log(`스도쿠 판을 완성시키는 경우의 수: ${count}`);
위 코드를 실행하면 대략 두 시간 뒤 스도쿠 판을 완성시키는 경우의 수가 6670903752021072936960가지라는 것을 계산할 수 있다.
나는 초등학생때부터 무료 웹 호스팅 업체를 통해 개인 홈페이지를 만들어 왔다.
하지만 무료에는 그만한 댓가가 따르기 마련이였다.
대부분의 무료 웹 호스팅 업체에서는 용량이나 총 트래픽 제한을 걸어놓는다.
제한이 널널한 외국 호스팅 업체들은 네트워크 속도가 느리기 일쑤였다.
웹 서버에서 구동할 수 있는 프로그램이나, 설정 가능한 요소들이 제한되어 있다.
그래서, 지난 2012년인가 2013년 즈음에, 집에서 쓰던 오래 된 컴퓨터를 동아리방에 가져다 놓았다.
그리고 그 컴퓨터에 Debian을 깔고, NGINX 및 MariaDB등을 이용해 개인 홈페이지를 구축했다.
원하는 대로 서버를 굴리면서도 유지비용이 없어서 좋기는 한데, 서버가 낡아 성능이 좋지 못한것이 흠이였다.
뭐, 웹 호스팅에 그다지 높은 성능이 필요한 건 아니니까 큰 문제는 아니였고, 계속 시간이 날 때마다 홈페이지에 기능을 추가했다.
그러던 와중, 심심해서 만들어 보았던 끝말잇기 게임이 많은 인기를 끌게 되었고, 덕분에 서버가 매일 바쁘게 돌아갔다.
거의 항상 1초에 10건 정도의 요청을 처리하던 수준이였는데, 다행히도 서버의 다른 기능에 큰 영향을 끼치는 부하는 아니였다…라고 생각했었는데, 문제가 하나 생겼다.
DB 데이터가 손상되어버린 것이다.
서버의 낡은 하드 디스크가 오랜 동작 끝에 수명을 다하기 시작했다는 신호였다.
비록 당장은 서버가 제 기능을 하더라도, 근 시일 내에 서버에 어떤 문제가 생길지도 모르는 것이였다.
하드디스크를 하나 사서 교체할 수도 있지만, 이왕 이렇게 된 거 새 컴퓨터를 하나 장만하기로 하고, 기존 서버를 내렸다.
… 그리고 새 서버를 어떻게 장만해야 할 지 고민하다 몇 년이 지났고, 결국 다시 호스팅 업체를 이용하기로 결정했다. 웹 호스팅이 아닌 클라우드 서버 호스팅을.
