1概要

この記事では、数独パズルとそれを解くためのアルゴリズムについて説明します。

次に、Javaでソリューションを実装します。最初の解決策は単純な総当たり攻撃です。二つ目はhttps://en.wikipedia.org/wiki/Dancing__Links[Dancing Links]のテクニックを利用します。

OOPの設計ではなく、アルゴリズムに焦点を当てることになるので注意してください。


2数独パズル

簡単に言うと、数独は1から9までの数字で部分的に埋められた9×9セルのグリッドを持つ組み合わせの数字配置パズルです。各種類の番号。

さらに、グリッドの3 x 3サブセクションごとに重複した数を含めることはできません。各ボードの空白のフィールドの数が多いほど、難易度は上がります。


2.1. テストボード

このソリューションをより面白くし、アルゴリズムを検証するために、http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-youを使用します。 -crack-it.html[“世界最強数独”]ボードです。

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 }
};


board

を入力パラメーターとし、有効な解決策として各セルをテストする行、列、および値を反復処理する

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()

メソッドです。これは数独の制約をチェックします。

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

これら3つのチェックは比較的似ています。まず、行チェックから始めましょう。

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. 完全カバー

別の解決策を見てみましょう。数独はhttps://en.wikipedia.org/wiki/Exact__cover[Exact Cover]問題として記述することができ、これは2つのオブジェクト間の関係を示すインシデント行列によって表すことができます。

例えば、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}

からサブコレクションを見つけます。

S ** = \ {B、D、F} .

アルゴリズムXは次のように機能します。

  1. 行列

    A

    に列がない場合、現在の部分解は次のようになります.

有効な解決策
それ以外の場合は、列を選択してください。
(確定的に)



_A




r



c_

〜= 1(非決定的に、

すなわち、すべての可能性を試してください)
。部分解に行

r

を含める

  1. 各列

    j

    に対して


    _A




    r



    j

    〜= 1、各行に対して

    i_


__A




i



j

〜= 1、+のように
行列

A

から行

i

を削除し、行列

A

から列

j

を削除します。
。このアルゴリズムを縮小行列

A__で再帰的に繰り返します。

アルゴリズムXの効率的な実装は、Donald Knuth博士によって提案されたhttps://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf[資金リンク]アルゴリズム(略してDLX)です。

次の解決策はhttps://github.com/rafalio/dancing-links-java[この]Javaの実装に強く影響を受けています。


4.3. 正確なカバー問題

まず、数独パズルを正確なカバー問題として表す行列を作成する必要があります。マトリックスは9 ^ 3行、すなわち、あらゆる可能な数(9つの数)のあらゆる可能な位置(9行×9列)ごとに1行を有する。

列は、ボードの数(9 x 9)に制約の数を掛けたものを表します。

すでに3つの制約を定義しました。

  • 各行には各種類の番号が1つだけあります

  • 各列には各種類の番号が1つのみ

  • 各小区分には、それぞれの種類が1つだけあります

さらに、4番目の暗黙の制約があります。

  • 1つのセルに入れることができるのは1つの番号だけです

これにより、合計4つの制約が与えられ、したがってExact Cover行列の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;
}

私たちは今次の段階に進む準備ができています。セルをリンクする2つのクラスを作成しましょう。


4.4. ダンスノード

Dancing Linksアルゴリズムは、二重にリンクされたノードのリストに対する操作に従うという基本的な観察に基づいて動作します。

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ベンチマーク

これら2つの異なるアルゴリズムを同じコンピューター上で実行することで比較できます(これにより、コンポーネントの違い、CPUまたはRAMの速度などを回避できます)。実際の時間はコンピュータによって異なります。

しかし、相対的な結果を見ることができるはずです。これにより、どのアルゴリズムがより高速に実行されるかがわかります。

バックトラッキングアルゴリズムは、ボードを解くのに約250msかかります。

これをDancing Linksと比較すると(約50msかかります)、明らかに勝者になります。この特定の例を解くと、Dancing Linksは約5倍速くなります。


6. 結論

このチュートリアルでは、コアJavaを使った数独パズルの2つの解決策について説明しました。ブルートフォースアルゴリズムであるバックトラッキングアルゴリズムは、標準の9×9パズルを簡単に解くことができます。

もう少し複雑なDancing Linksアルゴリズムも議論されています。どちらも数秒以内に最も難しいパズルを解きます。

最後に、いつものように、議論の間に使われたコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[over on GitHub]で見つけることができます。