1. 개요

이 기사에서는 스도쿠 퍼즐과이를 해결하는 데 사용되는 알고리즘을 살펴볼 것입니다.

다음으로 Java로 솔루션을 구현합니다. 첫 번째 해결책은 단순한 무차별 대입 공격입니다. 두 번째는 Dancing Links 기술을 활용합니다 .

OOP 디자인이 아닌 알고리즘에 초점을 맞출 것임을 명심합시다.

2. 스도쿠 퍼즐

간단히 말해, Sudoku는 9 x 9 셀 격자가 부분적으로 1부터 9까지의 숫자로 채워진 조합 숫자 배치 퍼즐입니다. 목표는 나머지 빈 필드를 나머지 숫자로 채워서 각 행과 열이 하나만 갖도록하는 것입니다. 각 종류의 수.

또한 그리드의 모든 3 x 3 하위 섹션은 중복 된 숫자를 가질 수 없습니다. 난이도는 각 보드의 빈 필드 수에 따라 자연스럽게 올라갑니다.

2.1. 테스트 보드

솔루션을 더 흥미롭게 만들고 알고리즘을 검증하기 위해 다음과 같은 "세계에서 가장 어려운 스도쿠" 보드를 사용할 것입니다.

8 . . . . . . . . 
. . 3 6 . . . . . 
. 7 . . 9 . 2 . . 
. 5 . . . 7 . . . 
. . . . 4 5 7 . . 
. . . 1 . . . 3 . 
. . 1 . . . . 6 8 
. . 8 5 . . . 1 . 
. 9 . . . . 4 . .

2.2. 해결 된 보드

그리고 신속하게 솔루션을 망칠 수 있습니다. 올바르게 해결 된 퍼즐은 다음과 같은 결과를 제공합니다.

8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

3. 역 추적 알고리즘

3.1. 소개

역 추적 알고리즘 은 유효한 솔루션에 대해 각 셀을 테스트하여 퍼즐을 풀려고합니다.

제약 조건 위반이없는 경우 알고리즘은 다음 셀로 이동하여 모든 잠재적 솔루션을 채우고 모든 검사를 반복합니다.

위반이있는 경우 셀 값을 증가시킵니다. 일단 셀의 값이 9에 도달하고 여전히 위반이있는 경우 알고리즘은 이전 셀로 다시 이동하여 해당 셀의 값을 증가시킵니다.

가능한 모든 솔루션을 시도합니다.

3.2. 해결책

우선 보드를 정수의 2 차원 배열로 정의합시다. 0을 빈 셀로 사용합니다.

int[][] board = {
  { 8, 0, 0, 0, 0, 0, 0, 0, 0 },
  { 0, 0, 3, 6, 0, 0, 0, 0, 0 },
  { 0, 7, 0, 0, 9, 0, 2, 0, 0 },
  { 0, 5, 0, 0, 0, 7, 0, 0, 0 },
  { 0, 0, 0, 0, 4, 5, 7, 0, 0 },
  { 0, 0, 0, 1, 0, 0, 0, 3, 0 },
  { 0, 0, 1, 0, 0, 0, 0, 6, 8 },
  { 0, 0, 8, 5, 0, 0, 0, 1, 0 },
  { 0, 9, 0, 0, 0, 0, 4, 0, 0 } 
};

보드 를 입력 매개 변수로 사용하고 유효한 솔루션을 위해 각 셀을 테스트하는 행, 열 및 값을 반복 하는 solve () 메서드를 만들어 보겠습니다 .

private boolean solve(int[][] board) {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            if (board[row][column] == NO_VALUE) {
                for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
                    board[row][column] = k;
                    if (isValid(board, row, column) && solve(board)) {
                        return true;
                    }
                    board[row][column] = NO_VALUE;
                }
                return false;
            }
        }
    }
    return true;
}

필요한 또 다른 방법은 isValid () 메서드로, 스도쿠 제약 조건을 확인합니다. 즉, 행, 열 및 3 x 3 그리드가 유효한지 확인합니다.

private boolean isValid(int[][] board, int row, int column) {
    return (rowConstraint(board, row)
      && columnConstraint(board, column) 
      && subsectionConstraint(board, row, column));
}

이 세 가지 검사는 비교적 유사합니다. 먼저 행 검사부터 시작하겠습니다.

private boolean rowConstraint(int[][] board, int row) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(column -> checkConstraint(board, row, constraint, column));
}

다음으로 거의 동일한 코드를 사용하여 열의 유효성을 검사합니다.

private boolean columnConstraint(int[][] board, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(row -> checkConstraint(board, row, constraint, column));
}

또한 3 x 3 하위 섹션의 유효성을 검사해야합니다.

private boolean subsectionConstraint(int[][] board, int row, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;

    int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;

    for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
        for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
            if (!checkConstraint(board, r, constraint, c)) return false;
        }
    }
    return true;
}

마지막으로 checkConstraint () 메서드 가 필요합니다 .

boolean checkConstraint(
  int[][] board, 
  int row, 
  boolean[] constraint, 
  int column) {
    if (board[row][column] != NO_VALUE) {
        if (!constraint[board[row][column] - 1]) {
            constraint[board[row][column] - 1] = true;
        } else {
            return false;
        }
    }
    return true;
}

일단 완료되면 isValid () 메서드는 단순히 true 를 반환 할 수 있습니다 .

이제 솔루션을 테스트 할 준비가 거의되었습니다. 알고리즘이 완료되었습니다. 그러나 true 또는 false 만 반환 합니다 .

따라서 보드를 시각적으로 확인하려면 결과를 인쇄하기 만하면됩니다. 분명히 이것은 알고리즘의 일부가 아닙니다.

private void printBoard() {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            System.out.print(board[row][column] + " ");
        }
        System.out.println();
    }
}

스도쿠 퍼즐을 해결하는 역 추적 알고리즘을 성공적으로 구현했습니다!

분명히 알고리즘이 가능한 각 조합을 순진하게 반복해서 확인하므로 개선의 여지가 있습니다 (특정 솔루션이 유효하지 않음을 알고 있음에도 불구하고).

4. 춤추는 링크

4.1. 정확한 커버

다른 솔루션을 살펴 보겠습니다. 스도쿠는 정확한 커버 문제 로 설명 할 수 있으며 두 개체 간의 관계를 나타내는 발생 행렬로 나타낼 수 있습니다.

예를 들어 1에서 7까지의 숫자와 집합 S = {A, B, C, D, E, F}를 취하면 다음과 같습니다.

  • A = {1, 4, 7}
  • B = {1, 4}
  • C = {4, 5, 7}
  • D = {3, 5, 6}
  • E = {2, 3, 6, 7}
  • F = {2, 7}

우리의 목표는 각 숫자가 한 번만 있고 반복되지 않는 하위 집합을 선택하는 것입니다.

열은 숫자이고 행은 집합 인 행렬을 사용하여 문제를 나타낼 수 있습니다.

  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

하위 컬렉션 S * = {B, D, F}는 정확한 표지입니다.

  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

각 열에는 선택한 모든 행에 정확히 하나의 1이 있습니다.

4.2. 알고리즘 X

알고리즘 X는 정확한 커버 문제에 대한 모든 솔루션을 찾기 위한 "시행 및 오류 접근 방식"입니다 . 즉, 예제 컬렉션 S = {A, B, C, D, E, F} , find subcollection S * = { B, D, F}.

알고리즘 X는 다음과 같이 작동합니다.

  1. 행렬 A 에 열이 없으면 현재 부분 솔루션이 유효한 솔루션입니다.
    성공적으로 종료됩니다. 그렇지 않으면 열 c (결정적)를 선택합니다.
  2. A r , c = 1이 되도록 행 r을 선택합니다 (비 결정적, 즉 모든 가능성 시도).
  3. 부분 솔루션에 행 r 포함
  4. 각 칼럼 용 J 그러한 경우 → R , J 각 행 = 1, I 되도록 I , J = 1, 삭제 행 I 행렬에서 및 삭제 열 J 매트릭스로부터
  5. 축소 된 행렬 A 에서이 알고리즘을 재귀 적으로 반복합니다 .

알고리즘 X의 효율적인 구현은 Donald Knuth 박사가 제안한 Dancing Links 알고리즘 (줄여서 DLX)입니다.

다음 솔루션은 이 Java 구현 에서 크게 영감을 받았습니다 .

4.3. 정확한 커버 문제

먼저 스도쿠 퍼즐을 정확한 커버 문제로 나타내는 행렬을 만들어야합니다. 행렬은 9 ^ 3 개의 행, 즉 가능한 모든 숫자 (9 개 숫자)의 모든 단일 위치 (9 행 x 9 열)에 대해 하나의 행을 갖습니다.

열은 보드 (다시 9 x 9)에 제약 수를 곱한 값을 나타냅니다.

이미 세 가지 제약 조건을 정의했습니다.

  • 각 행에는 각 종류의 숫자가 하나만 있습니다.
  • 각 열에는 각 종류의 숫자가 하나만 있습니다.
  • 각 하위 섹션에는 각 종류의 번호가 하나만 있습니다.

또한 암시 적 네 번째 제약 조건이 있습니다.

  • 셀에는 하나의 숫자 만있을 수 있습니다.

이는 총 4 개의 제약 조건을 제공하므로 정확한 커버 매트릭스에 9 x 9 x 4 열이 있습니다.

private static int BOARD_SIZE = 9;
private static int SUBSECTION_SIZE = 3;
private static int NO_VALUE = 0;
private static int CONSTRAINTS = 4;
private static int MIN_VALUE = 1;
private static int MAX_VALUE = 9;
private static int COVER_START_INDEX = 1;
private int getIndex(int row, int column, int num) {
    return (row - 1) * BOARD_SIZE * BOARD_SIZE 
      + (column - 1) * BOARD_SIZE + (num - 1);
}
private boolean[][] createExactCoverBoard() {
    boolean[][] coverBoard = new boolean
      [BOARD_SIZE * BOARD_SIZE * MAX_VALUE]
      [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS];

    int hBase = 0;
    hBase = checkCellConstraint(coverBoard, hBase);
    hBase = checkRowConstraint(coverBoard, hBase);
    hBase = checkColumnConstraint(coverBoard, hBase);
    checkSubsectionConstraint(coverBoard, hBase);
    
    return coverBoard;
}

private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
                for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) {
                    for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) {
                        int index = getIndex(row + rowDelta, column + columnDelta, n);
                        coverBoard[index][hBase] = true;
                    }
                }
            }
        }
    }
    return hBase;
}

private int checkColumnConstraint(boolean[][] coverBoard, int hBase) {
    for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}

private int checkRowConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}

private int checkCellConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}

다음으로, 새로 생성 된 보드를 초기 퍼즐 레이아웃으로 업데이트해야합니다.

private boolean[][] initializeExactCoverBoard(int[][] board) {
    boolean[][] coverBoard = createExactCoverBoard();
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
            int n = board[row - 1][column - 1];
            if (n != NO_VALUE) {
                for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
                    if (num != n) {
                        Arrays.fill(coverBoard[getIndex(row, column, num)], false);
                    }
                }
            }
        }
    }
    return coverBoard;
}

이제 다음 단계로 넘어갈 준비가되었습니다. 세포를 서로 연결하는 두 개의 클래스를 만들어 보겠습니다.

4.4. 춤추는 노드

Dancing Links 알고리즘은 노드의 이중 연결 List에 대한 다음 작업에 대한 기본 관찰에 따라 작동합니다.

node.prev.next = node.next
node.next.prev = node.prev

노드를 제거하는 동안 :

node.prev = node
node.next = node

노드를 복원합니다.

DLX의 각 노드는 왼쪽, 오른쪽, 위쪽 및 아래쪽의 노드에 연결됩니다.

DancingNode 클래스에는 노드를 추가하거나 제거하는 데 필요한 모든 작업이 있습니다.

class DancingNode {
    DancingNode L, R, U, D;
    ColumnNode C;

    DancingNode hookDown(DancingNode node) {
        assert (this.C == node.C);
        node.D = this.D;
        node.D.U = node;
        node.U = this;
        this.D = node;
        return node;
    }

    DancingNode hookRight(DancingNode node) {
        node.R = this.R;
        node.R.L = node;
        node.L = this;
        this.R = node;
        return node;
    }

    void unlinkLR() {
        this.L.R = this.R;
        this.R.L = this.L;
    }

    void relinkLR() {
        this.L.R = this.R.L = this;
    }

    void unlinkUD() {
        this.U.D = this.D;
        this.D.U = this.U;
    }

    void relinkUD() {
        this.U.D = this.D.U = this;
    }

    DancingNode() {
        L = R = U = D = this;
    }

    DancingNode(ColumnNode c) {
        this();
        C = c;
    }
}

4.5. 기둥 노드

ColumnNode 클래스는 열을 함께 연결합니다.

class ColumnNode extends DancingNode {
    int size;
    String name;

    ColumnNode(String n) {
        super();
        size = 0;
        name = n;
        C = this;
    }

    void cover() {
        unlinkLR();
        for (DancingNode i = this.D; i != this; i = i.D) {
            for (DancingNode j = i.R; j != i; j = j.R) {
                j.unlinkUD();
                j.C.size--;
            }
        }
    }

    void uncover() {
        for (DancingNode i = this.U; i != this; i = i.U) {
            for (DancingNode j = i.L; j != i; j = j.L) {
                j.C.size++;
                j.relinkUD();
            }
        }
        relinkLR();
    }
}

4.6. 솔버

다음으로 DancingNode 및 ColumnNode 개체 로 구성된 그리드를 만들어야 합니다.

private ColumnNode makeDLXBoard(boolean[][] grid) {
    int COLS = grid[0].length;

    ColumnNode headerNode = new ColumnNode("header");
    List<ColumnNode> columnNodes = new ArrayList<>();

    for (int i = 0; i < COLS; i++) {
        ColumnNode n = new ColumnNode(Integer.toString(i));
        columnNodes.add(n);
        headerNode = (ColumnNode) headerNode.hookRight(n);
    }
    headerNode = headerNode.R.C;

    for (boolean[] aGrid : grid) {
        DancingNode prev = null;
        for (int j = 0; j < COLS; j++) {
            if (aGrid[j]) {
                ColumnNode col = columnNodes.get(j);
                DancingNode newNode = new DancingNode(col);
                if (prev == null) prev = newNode;
                col.U.hookDown(newNode);
                prev = prev.hookRight(newNode);
                col.size++;
            }
        }
    }

    headerNode.size = COLS;

    return headerNode;
}

휴리스틱 검색을 사용하여 열을 찾고 행렬의 하위 집합을 반환합니다.

private ColumnNode selectColumnNodeHeuristic() {
    int min = Integer.MAX_VALUE;
    ColumnNode ret = null;
    for (
      ColumnNode c = (ColumnNode) header.R; 
      c != header; 
      c = (ColumnNode) c.R) {
        if (c.size < min) {
            min = c.size;
            ret = c;
        }
    }
    return ret;
}

마지막으로 답을 재귀 적으로 검색 할 수 있습니다.

private void search(int k) {
    if (header.R == header) {
        handleSolution(answer);
    } else {
        ColumnNode c = selectColumnNodeHeuristic();
        c.cover();

        for (DancingNode r = c.D; r != c; r = r.D) {
            answer.add(r);

            for (DancingNode j = r.R; j != r; j = j.R) {
                j.C.cover();
            }

            search(k + 1);

            r = answer.remove(answer.size() - 1);
            c = r.C;

            for (DancingNode j = r.L; j != r; j = j.L) {
                j.C.uncover();
            }
        }
        c.uncover();
    }
}

더 이상 열이 없으면 해결 된 스도쿠 보드를 인쇄 할 수 있습니다.

5. 벤치 마크

이 두 가지 알고리즘을 같은 컴퓨터에서 실행하여 비교할 수 있습니다 (이렇게하면 구성 요소, CPU 또는 RAM 속도 등의 차이를 피할 수 있습니다). 실제 시간은 컴퓨터마다 다릅니다.

그러나 상대적인 결과를 볼 수 있어야하며 이는 어떤 알고리즘이 더 빠르게 실행되는지 알려줍니다.

Backtracking Algorithm은 보드를 해결하는 데 약 250ms가 걸립니다.

약 50ms가 걸리는 Dancing Links와 비교해 보면 확실한 승자를 볼 수 있습니다. Dancing Links는이 특정 예제를 해결할 때 약 5 배 더 빠릅니다.

6. 결론

이 예제에서는 핵심 Java를 사용하여 스도쿠 퍼즐에 대한 두 가지 솔루션을 논의했습니다. 무차별 대입 알고리즘 인 역 추적 알고리즘은 표준 9x9 퍼즐을 쉽게 풀 수 있습니다.

약간 더 복잡한 Dancing Links 알고리즘도 논의되었습니다. 둘 다 몇 초 안에 가장 어려운 퍼즐을 해결합니다.

마지막으로 항상 그렇듯이 토론 중에 사용 된 코드 는 GitHub 에서 찾을 수 있습니다 .