-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
grid.js
109 lines (91 loc) · 2.67 KB
/
grid.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
class Grid {
constructor() {
this.cells = [];
this.solutions;
}
getCell(row, col) {
return this.cells[row * 9 + col];
}
setCell(row, col, value) {
this.cells[row * 9 + col] = new Cell(value);
return this;
}
generate() {
for(let i = 0; i < 81; i++) {
if(this.cells[i].value === 0) {
let values = shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9]);
for(let value of values) {
if(this.possible(Math.floor(i / 9), i % 9, value)) {
this.cells[i].value = value;
if(this.generate()) {
return true;
}
this.cells[i].value = 0;
}
}
return false;
}
}
return true;
}
solve() {
for(let i = 0; i < 81; i++) {
if(this.cells[i].value === 0) {
for(let value = 1; value <= 9; value++) {
if(this.possible(Math.floor(i / 9), i % 9, value)) {
this.cells[i].value = value;
if(this.countEmptyCells() === 0) {
this.solutions++;
break;
} else if(this.solve()) {
return true;
}
this.cells[i].value = 0;
}
}
return false;
}
}
return true;
}
possible(row, col, value) {
for(let i = 0; i < 9; i++) {
if(this.getCell(row, i).value === value || this.getCell(i, col).value === value) {
return false;
}
}
let x = Math.floor(col / 3) * 3;
let y = Math.floor(row / 3) * 3;
for(let i = 0; i < 3; i++) {
for(let j = 0; j < 3; j++) {
if(this.getCell(y + i, x + j).value === value) {
return false;
}
}
}
return true;
}
countEmptyCells() {
let num = 0;
for(let i = 0; i < 81; i++) {
if(this.cells[i].value === 0) {
num++;
}
}
return num;
}
clone() {
let clone = new Grid();
for(let i = 0; i < 81; i++) {
clone.cells[i] = new Cell(this.cells[i].value, this.cells[i].stored);
}
return clone;
}
static init() {
let grid = new Grid();
for(let i = 0; i < 81; i++) {
grid.cells[i] = new Cell(0);
}
return grid;
}
}