数独生成プログラムを作成→未使用数列の概念で再帰的アルゴリズムを使用する。

はじめに

数独とは 数独とは9X9の穴あきマスに1〜9の値を入力し、穴を埋めるゲームです。 値を入力する際のルールとして、入力するマスの列・行・3X3の四角に存在する数字を使用してはいけない。

こんな感じです。

スキルアップのために、数独生成プログラム作成に取り掛かりました。
まず全ての数字をランダムに生成するプログラムを構築してしまえば穴を開ける作業は軽いと判断し、まず答えを生成するにはどうしたら良いかを考えました。

意外と日本語の記事が少なく主に海外の記事を参考にしていました。（余談ですが数独は日本発らしく海外でもSudokuとして扱われていました。なんか嬉しい。再帰的アルゴリズムはBackTracking。）

参考にした記事
https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
翻訳するのがめんどくさかったですが再帰的アルゴリズムの基礎がわかりやすく説明されています。

言語
今回は動的に値を共有できるようにしたかったので（最終的には５マス先取りの対戦ゲームを考えています。）javascriptを使用しました。

１マスに持たせる情報

まず数独の特徴である、”列・行・3X3の四角で数字が被らない”というルールに着目して、自身(マス)がどの列・行・3X3に属しているかの情報を持たせることにしました。 その次に入力した数値。 そして、もし先のマスで”列・行・3X3の四角で被らない数字がなかった場合”は、使用可能かつ未使用の数字が残っているマスまで戻って前回入力した数値とは別の数値を入力する。を完成するまで繰り返す為に、使用可能かつ未使用の数列を持たせました。

こんな感じです。

//変数の宣言

// 9×9のボード
var boardArray = []

// １マスの構造体
    // 値
var value = null
    // インデックス
var index = null
    // 列
var column = null
    // 行
var row = null
    // 3X3
var threeOnthree = null
    // 使用可能で未使用
var unuseNumbers = null

// インデックス
var i = 0
// for分のループで9X9を表現
    for (let x = 0; x < 9; ++x) {
        for (let y = 0; y < 9; ++y) {
            // ここで構造体のマスをインスタンス化
            let square = new squareStruct(x, y, i)
                // 9x9ボードにプッシュ
            boardArray.push(square)
            i += 1
        }
    }

// 1マスの構造体
function squareStruct(x, y, i) {
    // 表示される数値
    this.value = null
        // index
    this.index = i
        // 列
    this.column = x
        // 行
    this.row = y
        // 3X3マス
    this.threeOnThree = getThreeOnThreeObjectKey(x, y)
        // 使用可能な未使用の数列
    this.unuseNumbers = null
}

これで自分がどこに属しているかの情報を持った1マスのオブジェクトが81個とそれを格納するボードができました。
こうしてしまえば重複チェックは簡単です。

重複チェックの考え方としては自身の属する列・行・3X3マスに存在する全ての数値を取り出すことで、それ以外の1~9までの数値を使用可能な数列として保持することができます。

// 現在判定中のマスが該当する列・行・3X3を抽出
function getObjectNumbersNeedToBeCheck(square) {
    // 判定中のマスの列に存在する数値を抽出
    var columnsNumbers = boardArray.filter(x => x.column == square.column)
    columnsNumbers = columnsNumbers.map(x => x.value)
    // 数値だけ抽出
    columnsNumbers = columnsNumbers.filter(function(x) { return typeof x === 'number' })
        // 行
    var rowsNumbers = boardArray.filter(x => x.row == square.row)
    rowsNumbers = rowsNumbers.map(x => x.value)
    rowsNumbers = rowsNumbers.filter(function(x) { return typeof x === 'number' })
        // 3X3
    var threeOnThreesNumbers = boardArray.filter(x => x.threeOnThree == square.threeOnThree)
    threeOnThreesNumbers = threeOnThreesNumbers.map(x => x.value)
    threeOnThreesNumbers = threeOnThreesNumbers.filter(function(x) { return typeof x === 'number' })
        // 該当する列・行・3X3の全ての数列を合わせた数列を返す
    return columnsNumbers.concat(rowsNumbers.concat(threeOnThreesNumbers))
}

// 使用可能な数字を抽出
function getAvailableNumbers(square) {
    var number = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     // 自信が属する列・行・3X3の全ての数列
    var allredyUsedNumber = getObjectNumbersNeedToBeCheck(square)
     //自信が属する列・行・3X3の全ての数列と1~9までの数列との差分
    let arr = allredyUsedNumber.concat(number);
    return arr.filter((v, i) => {
        return !(allredyUsedNumber.indexOf(v) !== -1 && number.indexOf(v) !== -1);
    });
}

// 引数の数列からランダムで一つだけ数値を返す
function shuffle(arrayNumber) {
    var object = arrayNumber
    var i = object.length;
    while (--i) {
        var j = Math.floor(Math.random() * (i + 1));
        if (i == j) continue;
        var k = object[i];
        object[i] = object[j];
        object[j] = k;
    }
    return object[0];
}



// 使用例
var number = shuffle(getAvailableNumbers)

値挿入ロジック・バックトラッキング

ここが一番時間を取られたところでした。 最初は、「条件に合う場合だけ数値を挿入し、そうでない場合は数値を全リセットという流れでいつかゴールするだろう」と考えていたら大間違いでした笑 総当たりで探すと、とんでも無い処理量になり、スタックオバーフローになってしいました。(https://qiita.com/drken/items/23a4f604fa3f505dd5ad)参照

ということで、挿入する値が無くなった場合「全リセット」ではなく上記に記述している通り、"使用可能かつ未使用数列が存在するマスまで戻る。"方向に切り替えました。

(実はここで初めて、再帰的アルゴリズムの重要性やマスをオブジェクト化し、未使用数列を保持する方法に気づきました。)

先の反省を踏まえ出来るだけ軽い動きになるように、ゴールしない条件を洗い出してみました。
・全てのマスに数値が入力されている状況でない場合（ゴールノード）・・・重複チェックをパスした数列から値を挿入しているため全てのマスに数値が入力されていればゴールとなる。
・初めての挿入作業で、使用可能な数値がない場合。
・バックトラッキング中で、未使用数列・使用可能数列ともに存在しない場合

ここまでは割と簡単に思いついたのですが、これだと無限ループになりました。
使用可能な数値がなく一つ前のマスに戻る
↓
使用可能な数値を入力（例えば使用可能な数値が９のみだった場合９を入力）
↓
使用可能な数値がなく一つ前のマスに戻る
↓
使用可能な数値を入力（９を入力）
↓
以下無限ループ

ここで数値挿入時に更新される未使用数列に着目し以下の条件と処理を追加しました。

・バックトラッキング中で、未使用数列・使用可能数列ともに存在しない場合未使用の数列が存在するマスまで戻る、またその際その範囲までの挿入されている数値をnullに書き換える。
・バックトラッキングから戻ってきて、使用可能な数値がない場合かつ、一つ前の未使用数列が存在しない場合、未使用の数列が存在するマスまで戻る、またその際その範囲までの挿入されている数値をnullに書き換える。

これを踏まえた上で以下のような条件分岐ロジック

// 全てのマスに数値が挿入されるまでぐるぐる
while (!全てのマスに数値が入力されている場合){
if (数値挿入に成功(ボード[インデックス])){
インデックス　+= 1
} else {
// 一つ前のマスに戻る
インデックス　-= 1
}
}

こんな感じです。

// ゴールノードになるまでぐるぐる
    while (!isSolve()) {
        if (insertNumberOrBackTracking(boardArray[iTmp])) {
            iTmp += 1
        } else {
            iTmp -= 1
                // index <= iTmpのsquareのvalueをnullに書き換える
            rewriteForNull(iTmp)
        }
    }

// ゴールノードかどうか
function isSolve() {
    // 全マスから値がnullのマスのみフィルタリング
    let values = boardArray.filter(x => x.value == null)
    if (values == '') {
        return true
    }
    return false

// 使用可能な数字があれば挿入無ければ戻る
function insertNumberOrBackTracking(square) {
    // 使用可能な数列
    var availableNumbers = getAvailableNumbers(square)
        // このsquareにおいて初めての値挿入処理
    if ((square.unuseNumbers == null) && (availableNumbers != '')) {
        takeOutValueAndInsert(square, availableNumbers)
        return true
    }
    // バックトラッキング中で未使用数列に値がある場合挿入
    if ((square.unuseNumbers != null) && (square.unuseNumbers != '')) {
        takeOutValueAndInsert(square, square.unuseNumbers)
        return true
    }
    // バックトラッキング中で未使用数列に値が無く、使用可能数列に値がある場合挿入
    if ((square.unuseNumbers != null) && (square.unuseNumbers == '') && (availableNumbers != '')) {
        takeOutValueAndInsert(square, availableNumbers)
        return true
    }
    // バックトラッキングがダメだった場合,未使用数列が空でないノードまで遡る
    if ((square.unuseNumbers != null) && (square.unuseNumbers == '') && (availableNumbers == '')) {
        backTrackingForIsNotEmptyNode()
        return false
    }
    // バックトラッキング後使用可能数列が空かつ、一つ前の未使用数列がからの場合
    if ((square.unuseNumbers == null) && (availableNumbers == '') && (boardArray[square.index - 1].unuseNumbers == '')) {
        backTrackingForIsNotEmptyNode()
        return false
    }
    // それ以外
    return false
}

まとめ

今回のポイント ・マスを構造体としてオブジェクト化したこと。 ・未使用配列の概念を使用したことで、選択肢を狭めることができより ゴールに辿り着きやすくなったのではないか。

こんなところですが、当然他の選択肢もあるはずで、私自身これよりコード量も短く、正確なロジックも探していますのでこんな方法もあるよと教えていただけると幸いです！

ソース

// 9×9のボード
var boardArray = []
    // １マスの構造体
    // 値
var value = null
    // 名前
var name = null
    // インデックス
var index = null
    // 列
var column = null
    // 行
var row = null
    // 3X3
var threeOnthree = null
    // 使用可能で未使用
var unuseNumbers = null
    // 値挿入時に使用する添字
var iTmp = 0

// メインメソッド
function main() {
    createObjectSquareInTheBoard()
// ゴールノードになるまでぐるぐる
    while (!isSolve()) {
        if (insertNumberOrBackTracking(boardArray[iTmp])) {
            iTmp += 1
        } else {
            iTmp -= 1
                // index <= iTmpのsquareのvalueをnullに書き換える
            rewriteForNull(iTmp)
        }
    }
}

// ボードの中のマス構造体をインスタンス化
function createObjectSquareInTheBoard() {
    var i = 0
    for (let x = 0; x < 9; ++x) {
        for (let y = 0; y < 9; ++y) {
            // 1マス生成
            let square = new squareStruct(x, y, i)
                // 9x9ボードにプッシュ
            boardArray.push(square)
            i += 1
        }
    }
}

// index >= iTmpのsquareのvalueをnullに書き換える
function rewriteForNull(i) {
    boardArray.filter(function(x) {
        if (x.index >= i) {
            x.value = null
        }
    })
}

// ゴールノードかどうか
function isSolve() {
    let values = boardArray.filter(x => x.value == null)
    if (values == '') {
        return true
    }
    return false
}

// 使用可能な数字があれば挿入無ければ戻る
function insertNumberOrBackTracking(square) {
    // 使用可能な数列
    var availableNumbers = getAvailableNumbers(square)
        // このsquareにおいて初めての値挿入処理
    if ((square.unuseNumbers == null) && (availableNumbers != '')) {
        takeOutValueAndInsert(square, availableNumbers)
        return true
    }
    // バックトラッキング中で未使用数列に値がある場合挿入
    if ((square.unuseNumbers != null) && (square.unuseNumbers != '')) {
        takeOutValueAndInsert(square, square.unuseNumbers)
        return true
    }
    // バックトラッキング中で未使用数列に値が無く、使用可能数列に値がある場合挿入
    if ((square.unuseNumbers != null) && (square.unuseNumbers == '') && (availableNumbers != '')) {
        takeOutValueAndInsert(square, availableNumbers)
        return true
    }
    // バックトラッキングがダメだった場合,未使用数列が空でないノードまで遡る
    if ((square.unuseNumbers != null) && (square.unuseNumbers == '') && (availableNumbers == '')) {
        backTrackingForIsNotEmptyNode()
        return false
    }
    // バックトラッキング後使用可能数列が空かつ、一つ前の未使用数列がからの場合
    if ((square.unuseNumbers == null) && (availableNumbers == '') && (boardArray[square.index - 1].unuseNumbers == '')) {
        backTrackingForIsNotEmptyNode()
        return false
    }
    return false
}

// 使用可能な数列から値を取り出し挿入し、未使用数列を更新
function takeOutValueAndInsert(square, numbers) {
    var number = shuffle(numbers)
    square.value = number
    square.unuseNumbers = numbers.filter(x => x != number)
}

// 未使用数列が存在するノードまで戻る
function backTrackingForIsNotEmptyNode() {
    var backTrackArr = boardArray.filter(x => (x.unuseNumbers != null) && (x.unuseNumbers != ''))
    var backTrackSquare = backTrackArr[backTrackArr.length - 1]
    iTmp = backTrackSquare.index + 1
}

// 自身が属する3X3の場所を返す
function getThreeOnThreeObjectKey(x, y) {
    switch (true) {
        case ((x == 0 || x == 1 || x == 2) && (y == 0 || y == 1 || y == 2)):
            return 0;
        case ((x == 0 || x == 1 || x == 2) && (y == 3 || y == 4 || y == 5)):
            return 1;
        case ((x == 0 || x == 1 || x == 2) && (y == 6 || y == 7 || y == 8)):
            return 2;
        case ((x == 3 || x == 4 || x == 5) && (y == 0 || y == 1 || y == 2)):
            return 3;
        case ((x == 3 || x == 4 || x == 5) && (y == 3 || y == 4 || y == 5)):
            return 4;
        case ((x == 3 || x == 4 || x == 5) && (y == 6 || y == 7 || y == 8)):
            return 5;
        case ((x == 6 || x == 7 || x == 8) && (y == 0 || y == 1 || y == 2)):
            return 6;
        case ((x == 6 || x == 7 || x == 8) && (y == 3 || y == 4 || y == 5)):
            return 7;
        case ((x == 6 || x == 7 || x == 8) && (y == 6 || y == 7 || y == 8)):
            return 8;
    }
}

// 1から9の数字をランダムで返す
function shuffle(arrayNumber) {
    var object = arrayNumber
    var i = object.length;
    while (--i) {
        var j = Math.floor(Math.random() * (i + 1));
        if (i == j) continue;
        var k = object[i];
        object[i] = object[j];
        object[j] = k;
    }
    return object[0];
}

// 1マスの構造体
function squareStruct(x, y, i) {
    // 表示される数値
    this.value = null
        // index
    this.index = i
        // 座標
    this.name = "x" + x + "_" + "y" + y
        // 列
    this.column = x
        // 行
    this.row = y
        // 3X3マス
    this.threeOnThree = getThreeOnThreeObjectKey(x, y)
        // 使用可能な未使用の数列
    this.unuseNumbers = null
}

// 現在判定中の数字が該当する列・行・3X3を抽出
function getObjectNumbersNeedToBeCheck(square) {
    // 列
    var columnsNumbers = boardArray.filter(x => x.column == square.column)
    columnsNumbers = columnsNumbers.map(x => x.value)
    columnsNumbers = columnsNumbers.filter(function(x) { return typeof x === 'number' })
        // 行
    var rowsNumbers = boardArray.filter(x => x.row == square.row)
    rowsNumbers = rowsNumbers.map(x => x.value)
    rowsNumbers = rowsNumbers.filter(function(x) { return typeof x === 'number' })
        // 3X3
    var threeOnThreesNumbers = boardArray.filter(x => x.threeOnThree == square.threeOnThree)
    threeOnThreesNumbers = threeOnThreesNumbers.map(x => x.value)
    threeOnThreesNumbers = threeOnThreesNumbers.filter(function(x) { return typeof x === 'number' })
        // 該当する列・行・3X3の全ての数列を合わせた数列を返す
    return columnsNumbers.concat(rowsNumbers.concat(threeOnThreesNumbers))
}

// 使用可能な数字を抽出
function getAvailableNumbers(square) {
    var number = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        // 自信が属する列・行・3X3の全ての数列
    var allredyUsedNumber = getObjectNumbersNeedToBeCheck(square)
    let arr = allredyUsedNumber.concat(number);
    return arr.filter((v, i) => {
        return !(allredyUsedNumber.indexOf(v) !== -1 && number.indexOf(v) !== -1);
    });
}

最後に

今回の個人的な勉強の本筋は対戦ゲームのサーバー側の勉強ですので進捗があればまた記事をあげたいと思います。記事を見ていただきありがとうございます。

ちなみにはじめにの
項目で日本語の数独生成プログラムの記事が少ないと書きましたが、再起関数の記事はありました。
https://qiita.com/drken/items/23a4f604fa3f505dd5ad
この方の記事はとてもわかりやすく翻訳する必要もないのでおすすめです！