기술 칼럼

MathWorks 인사이트

MATLAB으로 스도쿠 풀기


저자:

  • Cleve Moler, MathWorks

읽는 시간: 7분

요약

  • MATLAB에서는 재귀적 백트래킹에 기반한 무차별 대입 방식을 사용하여 프로그래밍 방식으로 스도쿠를 풀 수 있습니다.
  • 퍼즐을 제약 조건 문제로 모델링하고, 후보 값을 행, 열, 하위 격자 규칙에 비추어 평가합니다.
  • 재귀적 탐색에 싱글톤 식별과 같은 휴리스틱을 결합하여 탐색 공간을 줄입니다.
  • 더 작은 격자를 사용한 예제를 통해 후보 평가와 백트래킹으로 완전해를 구하는 과정을 살펴봅니다.

사람이 퍼즐을 푸는 방법과 컴퓨터 프로그램이 스도쿠를 푸는 기법은 매우 다릅니다. 손으로 스도쿠를 푸는 재미는 최종 해답의 실마리가 되는 수많은 미묘한 조합과 패턴을 발견하고 익히는 데서 나옵니다. 사람의 이러한 패턴 인식 능력을 컴퓨터가 그대로 재현하도록 프로그래밍하기는 쉽지 않습니다. 그래서 대부분의 스도쿠 풀이 프로그램은 무차별 대입 방식의 시행착오를 거의 무한히 수행할 수 있는 컴퓨터의 능력에 의존하는, 매우 다른 접근 방식을 취합니다. 제가 작성한 MATLAB® 프로그램에서도 이 접근 방식을 사용했습니다.

스도쿠라는 문제

아시다시피 스도쿠는 9×9 격자를 채우는 퍼즐로, 각 행과 열, 그리고 큰 3×3 블록마다 1부터 9까지의 숫자가 모두 들어가야 합니다. 처음 주어지는 격자에는 단서라고 하는 숫자가 몇 개 채워져 있습니다. 마방진이나 다른 숫자 퍼즐과 달리 스도쿠에는 계산이 전혀 필요하지 않습니다. 그래서 격자에 숫자 대신 알파벳이나 다른 기호를 넣어도 아무 문제가 없습니다.

그림 1은 초기 격자를 보여 줍니다. 저는 이 예제의 대칭성이 특히 마음에 드는데, 이 예제는 University of Western Australia의 Gordon Royle이 만든 것입니다. 그림 2는 해답을 보여 줍니다.

sudoku_fig1_w.gif
그림 1. 단서가 파란색으로 표시된 예제 퍼즐. 이 예제는 대칭성이 특히 보기 좋습니다.
sudoku_fig2_w.gif
그림 2. 완성된 퍼즐. 각 행, 열, 큰 3×3 블록에 1부터 9까지의 숫자가 모두 들어가도록 나머지 숫자를 채웠습니다.

재귀적 백트래킹으로 스도쿠 풀기

저희 MATLAB 프로그램은 싱글톤라는 단 하나의 패턴과 기본적인 컴퓨터과학 기법인 재귀적 백트래킹만 사용합니다.

프로그램의 작동 방식을 알아보기 위해 2×2 블록으로 구성된 더 간단한 4×4 격자를 사용해 보겠습니다. 이러한 퍼즐은 스도쿠가 아니라 시도쿠라고 부르는데, “시”가 일본어로 “4”를 뜻하기 때문입니다.

그림 3은 첫 번째 시도쿠 퍼즐을 보여 줍니다. 그림 4~6은 이 퍼즐의 해답을 보여 줍니다. 그림 4에서는 들어갈 수 있는 값, 즉 후보가 작은 숫자로 표시되어 있습니다. 예를 들어 두 번째 행에는 “3”이 있고 첫 번째 열에는 “1”이 있으므로 (2,1) 위치의 후보는 “2”와 “4”입니다. 네 개의 셀에는 후보가 하나만 있습니다. 이러한 셀이 싱글톤입니다. 이 첫 번째 예제는 싱글톤을 채우기만 하면 쉽게 풀 수 있습니다. 그림 5에서는 싱글톤 중 하나를 채우고 후보를 다시 계산했습니다. 그림 6에서는 나머지 싱글톤을 나타나는 대로 채워 해답을 완성했습니다.

sudoku_fig3_w.gif
그림 3. 시도쿠는 4×4 격자에서 하는 스도쿠입니다.
sudoku_fig4_w.gif
그림 4. 후보. 빨간색 후보가 싱글톤입니다.
sudoku_fig5_w.gif
그림 5. 싱글톤 “3”을 채우고 후보를 다시 계산합니다.
sudoku_fig6_w.gif
그림 6. 나머지 싱글톤을 채워 퍼즐을 완성합니다.

쉬운 퍼즐이란 싱글톤을 채우기만 해도 풀 수 있는 퍼즐이라고 정의할 수 있습니다. 이 정의에 따르면 첫 번째 예제는 쉬운 퍼즐이지만, 다음 예제는 그렇지 않습니다.

그림 7에 표시된 퍼즐의 입력 배열은 다음 MATLAB 문으로 생성됩니다.

 X = diag(1:4) 
sudoku_fig7_w.gif
그림 7. shidoku(diag(1:4))

이 퍼즐에는 싱글톤이 없으므로(그림 8) 재귀적 백트래킹을 사용합니다. 빈 셀 중 하나를 선택하고 해당 셀의 후보 중 하나를 임시로 채웁니다. 여기서는 MATLAB의 1차원 첨자 X(:)가 나타내는 순서대로 셀을 살펴보고, 후보를 숫자 순서대로 시도하기로 했습니다. 따라서 (2,1) 셀에 “3”을 채워 새로운 퍼즐을 만듭니다(그림 9). 그런 다음 프로그램을 재귀적으로 호출합니다.

sudoku_fig8_w.gif
그림 8. 후보. 싱글톤이 없습니다.
sudoku_fig9_w.gif
그림 9. 임시로 “3”을 채워 새로운 퍼즐을 만듭니다. 그런 다음 백트래킹합니다.

새 퍼즐은 쉬운 퍼즐이며, 결과는 그림 10에 나와 있습니다. 하지만 이 해답은 재귀 호출 전에 내린 선택에 따라 달라집니다. 다른 선택을 하면 다른 해답이 나올 수 있습니다. 이 간단한 대각 초기 조건에는 두 가지 해답이 있는데, 공교롭게도 두 해답은 서로의 전치 행렬입니다. 해답이 유일하지 않으므로 그림 7의 격자는 올바른 퍼즐이 아닙니다.

sudoku_fig10_w.gif
그림 10. 결과로 얻은 해답. 이 해답은 유일하지 않으며, 이 해답의 전치 행렬도 또 다른 해답입니다.

존재성과 유일성

수학자로서 우리는 문제의 해답이 존재하며 그 해답이 유일하다는 것을 증명하고자 합니다. 스도쿠에서는 초기 단서만으로 존재성과 유일성을 쉽게 판단할 수 없습니다. 예를 들어 그림 1의 퍼즐에서 (1,1) 셀에 “1”, “5” 또는 “7”을 채우면 행, 열, 블록 조건은 충족되지만 그 결과로 얻은 퍼즐에는 해답이 없습니다. 이런 퍼즐이 신문에 실린다면 무척 답답할 것입니다.

백트래킹을 하면 불가능한 배치가 많이 생성됩니다. 저희 프로그램은 후보가 없는 셀을 만나면 재귀를 종료합니다. 이러한 퍼즐에는 해답이 없습니다.

유일성은 파악하기 까다로운 속성입니다. 대부분의 스도쿠 설명에는 해답이 하나뿐이어야 한다는 조건이 명시되어 있지 않습니다. 이 경우에도 주어진 해답과 다른 해답을 발견한다면 답답할 것입니다. MATLAB Central에 있는 일부 퍼즐 생성 프로그램은 유일성을 확인하지 않습니다. 제가 아는 한, 유일성을 확인하는 유일한 방법은 가능한 모든 해답을 빠짐없이 열거하는 것입니다.

스도쿠 풀이 알고리즘

저희 MATLAB 프로그램은 단 네 단계로 구성됩니다.
1. 모든 싱글톤을 채웁니다.
2. 후보가 없는 셀이 있으면 종료합니다.
3. 빈 셀에 임시 값을 채웁니다.
4. 프로그램을 재귀적으로 호출합니다.

핵심 내부 함수는 candidates입니다. 각 빈 셀은 z = 1:9로 시작하며, 해당 행, 열, 블록에 있는 숫자 값을 사용하여 z의 요소를 0으로 만듭니다. 남은 0이 아닌 값이 후보입니다. 예를 들어 그림 1의 (1,1) 셀을 살펴보겠습니다. 다음 값으로 시작합니다.

 z = 1 2 3 4 5 6 7 8 9 

첫 번째 행의 값에 따라 z는 다음과 같이 바뀝니다.

 z = 1 0 0 0 5 6 7 8 9 

이어서 첫 번째 열에 따라 z는 다음과 같이 바뀝니다.

 z = 1 0 0 0 5 0 7 0 9 

(1,1) 블록에서는 더 이상 바뀌는 값이 없으므로 이 셀의 후보는 다음과 같습니다.

 C{1,1} = [1 5 7 9] 

어려운 퍼즐

그림 1의 퍼즐은 사실 손으로 풀든 컴퓨터로 풀든 매우 어렵습니다. 그림 11과 12는 계산 과정의 스냅샷입니다. 처음에는 싱글톤이 없으므로 바로 첫 번째 재귀 단계가 실행됩니다. (1,1) 셀에 “1”을 시도합니다. 그림 11은 22단계까지 첫 번째 열이 어떻게 채워지는지 보여 줍니다. 하지만 해답까지는 아직 갈 길이 멉니다. 3,114단계 후에 재귀는 (1,1) 셀에 “5”를 넣고, 8,172단계 후에는 “7”을 시도합니다.

sudoku_fig11_w.gif
그림 11. 그림 1의 해답을 향해 22단계만 진행한 후의 상황. 청록색 값은 백트래킹이 임시로 선택한 값이고, 녹색 값은 그 선택에 따라 결정된 싱글톤입니다. (1,1) 셀에 “1”을 넣은 것은 잘못된 선택입니다. 이미지를 클릭하면 확대해서 볼 수 있습니다.
sudoku_fig12_w.gif
그림 12. 14,781단계 후에는 해답에 가까워진 것처럼 보이지만, (1,9) 셀에 들어갈 후보가 없어 더 이상 진행할 수 없습니다. (1,1) 셀에 “7”을 넣은 것은 잘못된 선택입니다. 이미지를 클릭하면 확대해서 볼 수 있습니다.

그림 12는 14,781단계 후의 상황을 보여 줍니다. 81개의 셀 중 73개에 값이 할당되었으므로 해답에 가까워진 것처럼 보입니다. 하지만 첫 번째 행과 마지막 열에 1부터 9까지의 숫자가 모두 들어 있으므로 오른쪽 위 모서리에 있는 (1,9) 셀에 넣을 수 있는 값이 남아 있지 않습니다. 이 셀의 후보 목록이 비어 있으므로 재귀가 종료됩니다. 마침내 19,229단계 후에 첫 번째 셀에 “9”를 시도합니다. 이 “9”는 좋은 선택입니다. 200단계도 지나지 않은 19,422단계에서 프로그램이 그림 2에 표시된 해답에 도달하기 때문입니다. 이는 대부분의 퍼즐에 필요한 것보다 훨씬 많은 단계입니다.

재귀적 백트래킹으로 스도쿠 풀기

function X = sudoku(X) 
% SUDOKU  Solve Sudoku using recursive backtracking. 
%   sudoku(X), expects a 9-by-9 array X. 
 % Fill in all “singletons”. 
 % C is a cell array of candidate vectors for each cell. 
 % s is the first cell, if any, with one candidate. 
 % e is the first cell, if any, with no candidates. 
 [C,s,e] = candidates(X); 
 while ~isempty(s) && isempty(e) 
    X(s) = C{s}; 
    [C,s,e] = candidates(X); 
 end 
 % Return for impossible puzzles. 
 if ~isempty(e) 
    return 
 end 
 % Recursive backtracking. 
 if any(X(:) == 0) 
    Y = X; 
    z = find(X(:) == 0,1);    % The first unfilled cell. 
    for r = [C{z}]            % Iterate over candidates. 
       X = Y; 
       X(z) = r;              % Insert a tentative value. 
       X = sudoku(X);         % Recursive call. 
       if all(X(:) > 0)       % Found a solution. 
          return 
       end 
     end 
   end 
% ------------------------------ 
   function [C,s,e] = candidates(X) 
      C = cell(9,9); 
      tri = @(k) 3*ceil(k/3-1) + (1:3); 
      for j = 1:9 
         for i = 1:9 
            if X(i,j)==0 
               z = 1:9; 
               z(nonzeros(X(i,:))) = 0; 
               z(nonzeros(X(:,j))) = 0; 
               z(nonzeros(X(tri(i),tri(j)))) = 0; 
               C{i,j} = nonzeros(z)’; 
            end 
         end 
      end 
 L = cellfun(@length,C);   % Number of candidates. 
 s = find(X==0 & L==1,1); 
 e = find(X==0 & L==0,1); 
 end % candidates 
end % sudoku

스도쿠의 기원

대부분의 사람들은 스도쿠가 일본에서 유래했다고 생각합니다. 사실 스도쿠는 미국에서 발명되었습니다. 스도쿠는 1979년 Dell Puzzle Magazine에 Number Place라는 이름으로 처음 등장했습니다. 1984년 일본 출판사 Nikoli가 이 퍼즐을 일본에 소개하면서 스도쿠라는 이름을 붙였는데, 이는 “숫자는 하나여야 한다(독신이어야 한다)”라는 뜻의 한자 약어입니다. The Times of London이 2004년부터 이 퍼즐을 싣기 시작했고, 얼마 지나지 않아 미국과 전 세계로 퍼져 나갔습니다.

2009년 기고 - 91789v00


사용된 제품: MATLAB

저자 소개

Cleve Moler

Cleve Moler는 MathWorks의 공동 창립자로, 회장과 최고 과학 책임자를 역임했습니다. 그는 약 20년 동안 University of Michigan, Stanford University, 그리고 University of New Mexico에서 수학 및 컴퓨터과학 교수로 재직했습니다. 그는 MATLAB의 최초 버전을 개발했으며, 수치해석 분야의 핵심 과학 계산 서브루틴 라이브러리인 LINPACK과 EISPACK의 공동 개발자이기도 합니다. 또한 수치해석에 관한 교재 3권을 공동 집필했습니다.

심화 주제 탐색