JavaScript实现生成数独

reference-site-list

steps

code

html

sudoku.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>sudoku</title>
    <link rel="stylesheet" type="text/css" href="./sudoku.css">
</head>
<body>
<div id="app">
    <div class="row" v-for="(row, rowIndex) in rows">
        <div class="col" v-for="(col, colIndex) in row"
             v-bind:style="{borderTop: rowIndex === 0 ? '2px black solid' : '0px',
             borderLeft: colIndex ===0 ? '2px black solid' : '0px',
             borderRight: (colIndex + 1) % 3 === 0 ? '2px black solid' : '1px gainsboro solid',
             borderBottom: (rowIndex + 1) % 3 === 0 ? '2px black solid' : '1px gainsboro solid',
             color: col === 0 ? 'red' : 'black'}">
            {{ col }}
        </div>
    </div>
</div>
</body>
<script src="https://cdn.jsdelivr.net/npm/vue@2.6.14"></script>
<script type="text/javascript" src="./sudoku.js"></script>
</html>

sudoku.css

#app {
    /*border: 1px gainsboro solid;*/
    width: 100%;
    height: 98vh;
    display: flex;
    flex-direction: column;
}

div {
    /*border: 1px gainsboro solid;*/
}

.row {
    display: flex;
    flex-direction: row;
    height: 11vh;
}

.col {
    width: 12%;
    border-right: 1px gainsboro solid;
    border-bottom: 1px gainsboro solid;
    display: flex;
    flex-direction: row;
    justify-content: center;
    align-items: center;
    font-size:2.5em;
}

JavaScript

sudoku.js

var app = new Vue({
    el: '#app',
    data: {
        rows: [],
        cols: [],
        zones: [],
    },
    methods: {
        init: function () {
            this.initEmptyArr(this.rows);
            this.initEmptyArr(this.cols);
            this.initEmptyArr(this.zones);
            this.rows[0] = this.getRandomRow();
            for (var i = 0; i < this.rows.length; i++) {
                for (var j = 0; j < this.rows[i].length; j++) {
                    var num = this.rows[i][j];
                    var zoneName = this.getZoneName(i, j);
                    var zoneOrder = this.getZoneOrder(i, j);
                    if (i === 0) {
                        this.cols[j][i] = num;
                        this.zones[zoneName][zoneOrder] = num;
                    } else {
                        /*
                        if (newNum === 0) {
                            this.lineReset(i);
                            i--;
                            break;
                        } else {
                            this.rows[i][j] = newNum;
                            this.cols[j][i] = newNum;
                            this.zones[zoneName][zoneOrder] = newNum;
                        }
                        */
                        this.generateSpecial(i, j, zoneName);
                        num = this.rows[i][j];
                        if (num === 0) {
                            var newNum = this.getRandomInPossible(i, j, zoneName);
                            this.rows[i][j] = newNum;
                            this.cols[j][i] = newNum;
                            this.zones[zoneName][zoneOrder] = newNum;
                        }
                    }
                }
                window.console.log("i = " + i + " : " + this.rows[i]);
            }
        },
        // 整行数据重置
        lineReset: function (row) {
            for (var i = 0; i < this.rows[row].length; i++) {
                this.rows[row][i] = 0;
                this.cols[i][row] = 0;
                var zoneName = this.getZoneName(row, i);
                var zoneOrder = this.getZoneOrder(row, i);
                this.zones[zoneName][zoneOrder] = 0;
            }
        },
        initEmptyArr: function (arr) {
            for (var i = 0; i < 9; i++) {
                var row = [];
                for (var j = 0; j < 9; j++) {
                    row.push(0);
                }
                arr.push(row);
            }
        },
        // 获取宫序号
        getZoneOrder: function (row, col) {
            return row % 3 * 3 + col % 3;
        },
        // 获取宫名
        getZoneName: function (row, col) {
            return Math.floor(row / 3) * 3 + Math.floor(col / 3);
        },
        // 当在中宫列的第2行进行生成关键的三个数的组合
        generateSpecial: function (row, col, zone) {
            if (row % 3 === 1 && Math.floor(col / 3) === 1) {
                var rowSet = [];
                var zoneSet = [];
                var rightSet = []; // 上一行最右边的3个数的集合
                for (var i = 0; i < 3; i++) {
                    rowSet.push(this.rows[row][i]);
                    zoneSet.push(this.zones[zone][i]);
                    rightSet.push(this.rows[row - 1][i + 6]);
                }
                var sameSet = [];
                for (var i = 0; i < rowSet.length; i++) {
                    if (rightSet.includes(rowSet[i])) {
                        sameSet.push(rowSet[i]);
                    }
                }

                var sameNum = sameSet.length;
                if (sameNum === 0) {
                    // 上右3中的数，进行随机排列
                    // var result = this.getRandomArr(rightSet);
                    var align = this.getRandomLegalAlign(rightSet);
                    this.rows[row][col] = align[0];
                    this.rows[row][col + 1] = align[1];
                    this.rows[row][col + 2] = align[2];
                } else if (sameNum === 1) {
                    // 上右3中不同的两个数，再从上左3中随机出一个数，组成排列，从有效排列中随机出一个排列

                } else if (sameNum === 2) {
                    // 上右3中不同的一个数，在从上左3中随机出两个数，组成排列，从有效排列中随机出一个排列

                }
            }
        },
        // 从有效的排列中随机选一个
        getRandomLegalAlign: function (arr) {
            var aligns = this.findLegalArr(arr);
            var random = this.getRandomNum(0, aligns.length - 1);
            return aligns[random];
        },
        // 找出有效的排列
        findLegalArr: function (arr) {
            var result = [];
            var aligns = this.listAlign(arr);
            for (var i = 0; i < aligns.length; i++) {
                var align = aligns[i];
                if (this.checkCenter(align)) {
                    result.push(align);
                }
            }
            return result;
        },
        // 列举出3个数字所有的排列
        listAlign: function (arr) {
            var trees = [];
            for (var i = 0; i < arr.length; i++) {
                var num = arr[i];
                var tree = {
                    val: num,
                    parent: null,
                    children: []
                };
                this.generateTree(arr, num, tree);
                trees.push(tree);
            }
            var result = [];
            // 树转数组
            for (var i = 0; i < trees.length; i++) {
                var tree = trees[i];
                var temp = [];
                this.recurseTree(tree, temp, result);
            }
            return result;
        },
        // 遍历树
        recurseTree: function (node, arr, result) {
            var temp = arr.slice();
            temp.push(node.val);
            var children = node.children;
            if (children.length === 0) {
                result.push(temp);
            } else {
                for (var i = 0; i < children.length; i++) {
                    var child = children[i];
                    this.recurseTree(child, temp, result);
                }
            }
        },
        // 生成以该数字开头的树
        generateTree: function (arr, num, tree) {
            var temp = arr.slice();
            // 移除数组中该该数字，获得该节点的子节点数
            for (var i = 0; i < temp.length; i++) {
                if (temp[i] === num) {
                    temp.splice(i, 1);
                    i--;
                }
            }
            for (var i = 0; i < temp.length; i++) {
                var item = {
                    val: temp[i],
                    parent: num,
                    children: []
                };
                tree.children.push(item);
                this.generateTree(temp, temp[i], item);
            }
        },
        // 检查中宫列的中行3个数字是否合规
        checkCenter: function (arr) {
            if (this.cols[3].includes(arr[0]) || this.cols[4].includes(arr[1]) || this.cols[5].includes(arr[2])) {
                return false;
            }
            return true;
        },
        // 根据坐标获取可能集合中的一个随机值
        getRandomInPossible: function (row, col, zone) {
            var possible = this.getPossible(row, col, zone);
            if (possible.length === 0) {
                return 0;
            }
            return this.getRandomOne(possible);
        },
        // 根据坐标获取可能集合
        getPossible: function (row, col, zone) {
            var rowTemp = this.pushToArr(this.rows[row]);
            var colTemp = this.pushToArr(this.cols[col]);
            var zoneTemp = this.pushToArr(this.zones[zone]);

            var rowArr = this.getNotZeroSet(rowTemp);
            var colArr = this.getNotZeroSet(colTemp);
            var zoneArr = this.getNotZeroSet(zoneTemp);
            var subAll = [];
            subAll = this.addToSubSet(rowArr, subAll);
            subAll = this.addToSubSet(colArr, subAll);
            subAll = this.addToSubSet(zoneArr, subAll);
            var total = this.getTotalSet();
            var result = [];
            for (var i = 0; i < total.length; i++) {
                var item = total[i];
                if (!subAll.includes(item)) {
                    result.push(item);
                }
            }
            if (result.length === 0) {
                window.console.log( 'row: ' + row + ' col: ' + col + ' zon: ' + zone
                    + '\nrowTemp: ' + rowTemp + '\ncolTemp: ' + colTemp + '\nzoneTemp: ' + zoneTemp
                    + '\nsubAll : ' + subAll);
            }
            return result;
        },
        // 将一个数组中的所有元素添加到另外一个数组中
        pushToArr: function (arr) {
            var result = [];
            for (var i = 0; i < arr.length; i++) {
                result.push(arr[i]);
            }
            return result;
        },
        // 将集合去重添加到目标集合中
        addToSubSet: function (arr, subAll) {
            for (var i = 0; i < arr.length; i++) {
                var item = arr[i];
                if (!subAll.includes(item)) {
                    subAll.push(item);
                }
            }
            return subAll;
        },
        // 获取非0集合
        getNotZeroSet: function (arr) {
            for (var i = 0; i < arr.length; i++) {
                if (arr[i] === 0) {
                    arr.splice(i, 1);
                    i--;
                }
            }
            return arr;
        },
        // 获取全集
        getTotalSet: function () {
            var total = [];
            for (var i = 0; i < 9; i++) {
                total.push(i + 1);
            }
            return total;
        },
        // 获取1-9的随机不重复数组
        getRandomRow: function () {
            var row = [];
            var temp = [];
            for (var i = 0; i < 9; i++) {
                temp.push(i + 1);
            }
            for (var i = 0; i < 9; i++) {
                var random = this.getRandomNum(0, temp.length - 1);
                row.push(temp[random]);
                temp.splice(random, 1);
            }
            return row;
        },
        // 将数组变成随机数组
        getRandomArr: function (arr) {
            var result = [];
            var temp = arr.slice();
            while (temp.length > 0) {
                var random = this.getRandomNum(0, temp.length - 1);
                result.push(temp[random]);
                temp.splice(random, 1);
            }
            return result;
        },
        // 从数组中随机取出一个数
        getRandomOne: function (arr) {
            var random = this.getRandomNum(0, arr.length - 1);
            return arr[random];
        },
        // 获取[min, max]之间的一个随机数
        getRandomNum: function (min, max) {
            min = Math.floor(min);
            max = Math.ceil(max);
            return Math.floor(Math.random() * (max + 1 - min)) + min;
        },
    },
    created: function () {
        this.init();
    }
});