使用JavaScript生成数独棋盘
Xplorist Lv6
  2021-12-28 11:50:00 2021-12-28 11:50      

使用JavaScript生成数独棋盘

reference-site-list

steps

  1. 初始化需要的数组

  2. 前进

  3. 回溯

problem

  • 核心问题在于回溯的规则，规则不能够满足所有情况

  • 找不到完美的回溯规则

  • 回溯判断出了问题，存储可能性这里判断出了问题，

  • 每个格子必须要有记忆，记忆错误值，下次不用相同的错误值就能够通过回溯递归找到正确的值，从宏观逻辑上来看就是这么个道理。

  • 每个格子记忆当前行的前面所有的格子，如果前进时发现下一个格子没有可能值了，说明当前行的现有排列是错误排列，
    再回到刚才的格子，已经进入回溯了，说明出现问题了，记录当前行已有的数字的排列到格子的错误数组中，下次取值时，要加上当前行的值，对比是否为错误数组中的值。

  • 回溯的哲学逻辑：记录犯过的错，下次不再犯，这就是回溯法。

  • 当前格子可能值和当前行当前格子前面的所有格子进行组合，所有可能的组合集合，然后和记录的错误集合对比，如果在错误集合中的，都删除，留下的集合进行随机选择。

  • 哲学逻辑上的清楚，我最终实现了完美的回溯法生成数独。

code

  • html - FinalSudoku.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>FinalSudoku</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.val === 0 ? 'red' : 'black'}">
            {{ col.val }}
        </div>
    </div>
</div>
</body>
<script src="https://cdn.jsdelivr.net/npm/vue@2.6.14"></script>
<script type="text/javascript" src="./FinalSudoku.js"></script>
</html>
  • css - sudoku.css
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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 - FinalSudoku.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
var app = new Vue({
    el: '#app',
    data: {
        rows: [],
        cols: [],
        zones: [],
    },
    created: function () {
        this.init();
    },
    methods: {
        init: function () {
            this.initEmptyArr(this.rows, 'obj');
            this.initEmptyArr(this.cols);
            this.initEmptyArr(this.zones);
            this.rows[0] = this.getRandomRow('obj');
            // 初始化第1行的列，宫数据
            for (let i = 0; i < 9; i++) {
                let num = this.rows[0][i].val;
                let zoneName = this.getZoneName(0, i);
                let zoneOrder = this.getZoneOrder(0, i);
                this.cols[i][0] = num;
                this.zones[zoneName][zoneOrder] = num;
            }
            this.forward(0, 8);
        },
        // 前进
        forward: function (row, col) {
            let curRow = 0;
            let curCol = 0;
            if (col === 8) {
                curRow = row + 1;
                curCol = 0;
            } else {
                curRow = row;
                curCol = col + 1;
            }
            if (curRow < 1 || curRow > 8 || curCol < 0 || curCol > 8) {
                return;
            }

            let possible = this.getPossible(curRow, curCol);
            if (possible.length === 0) {
                // 回溯
                this.gridReset(curRow, curCol);
                this.backward(curRow, curCol);
            } else {
                // 前进
                let randomVal = this.getRandomOne(possible);
                this.gridSet(curRow, curCol, randomVal);
                this.forward(curRow, curCol);
            }
        },
        // 回溯
        backward: function (row, col) {
            let curRow = 0;
            let curCol = 0;
            if (col === 0) {
                curRow = row - 1;
                curCol = 8;
            } else {
                curRow = row;
                curCol = col - 1;
            }
            if (curRow < 1 || curRow > 8 || curCol < 0 || curCol > 8) {
                return;
            }
            // 把当前值加入error中
            this.addCurIntoError(curRow, curCol);
            // 从可能值中随机一个当前值
            this.setCurInPossible(curRow, curCol);
        },
        // 从可能值中随机一个当前值
        setCurInPossible: function (row, col) {
            let curGrid = this.rows[row][col];
            let possible = this.getPossible(row, col);
            let beforeStr = this.getBeforeStr(row, col);
            let arr = [];
            for (let i = 0; i < possible.length; i++) {
                arr.push(beforeStr + '' + possible[i]);
            }
            let errorArr = curGrid.error;
            for (let i = 0; i < arr.length; i++) {
                let str = arr[i];
                if (errorArr.includes(str)) {
                    arr.splice(i, 1);
                    i--;
                }
            }
            if (arr.length === 0) {
                // 回溯
                this.gridReset(row, col);
                this.backward(row, col);
            } else {
                // 前进
                let randomStr = this.getRandomOne(arr);
                let char = randomStr[randomStr.length - 1];
                let num = parseInt(char);
                this.gridSet(row, col, num);
                this.forward(row, col);
            }
        },
        // 把当前值加入error中
        addCurIntoError: function (row, col) {
            let curGrid = this.rows[row][col];
            let errorStr = this.getBeforeStr(row, col) + curGrid.val;
            curGrid.error.push(errorStr);
        },
        // 获取当前格子前面所有的格子记录
        getBeforeStr: function (row, col) {
            let str = '';
            for (let i = 0; i < col; i++) {
                str += '' + this.rows[row][i].val;
            }
            return str;
        },
        test: function (row, col, val) {
            let obj = {val: val, error: []};
            this.rows[row].splice(col, 1, obj);
        },
        gridSet: function (row, col, val) {
            let obj = this.rows[row][col];
            obj.val = val;
            this.rows[row].splice(col, 1, obj);
            this.cols[col].splice(row, 1, val);

            //this.rows[row][col] = val;
            //this.cols[col][row] = val;
            let zoneName = this.getZoneName(row, col);
            let zoneOrder = this.getZoneOrder(row, col);
            //this.zones[zoneName][zoneOrder] = val;
            this.zones[zoneName].splice(zoneOrder, 1, val);
        },
        gridReset: function (row, col) {
            this.gridSet(row, col, 0);
        },
        initEmptyArr: function (arr, type) {
            for (var i = 0; i < 9; i++) {
                var row = [];
                for (var j = 0; j < 9; j++) {
                    if (type === 'obj') {
                        let obj = {val: 0, error: []};
                        row.push(obj);
                    } else {
                        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);
        },
        // 根据坐标获取可能集合中的一个随机值
        getRandomInPossible: function (row, col) {
            var possible = this.getPossible(row, col);
            if (possible.length === 0) {
                return 0;
            }
            return this.getRandomOne(possible);
        },
        // 根据坐标获取可能集合
        getPossible: function (row, col) {
            var zone = this.getZoneName(row, col);

            var rowTemp = this.pushToArr(this.rows[row], 'obj');
            var colTemp = this.pushToArr(this.cols[col]);
            var zoneTemp = this.pushToArr(this.zones[zone]);

            // 去0
            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, type) {
            var result = [];
            for (var i = 0; i < arr.length; i++) {
                if (type === 'obj') {
                    result.push(arr[i].val);
                } else {
                    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 (type) {
            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);
                if (type === 'obj') {
                    let obj = {val: temp[random], error: []};
                    row.push(obj);
                } else {
                    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;
        },
    },
});
  • 本文标题：使用JavaScript生成数独棋盘
  • 本文作者：Xplorist
  • 创建时间：2021-12-28 11:50:00
  • 本文链接：https://xplorist.tech/2021/12/28/5a5639f49cdb/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论