-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver.js
116 lines (104 loc) · 2.74 KB
/
solver.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
var boardSize
var pieces
var board
var placed
exports.init = function (size, basePieces) {
boardSize = size
pieces = basePieces
board = []
for (var x = 0; x < size; x++) {
board[x] = []
for (var y = 0; y < size; y++) {
board[x][y] = 0
}
}
placed = []
for (var i = 0; i < pieces.length; i++) {
placed[i] = false
}
}
exports.findSolution = function (progress, done) {
fillBoard(0, 0, 0, progress, done)
}
function fillBoard (piecesIndex, x, y, progress, done) {
for (var i = 0; i < pieces.length; i++) {
if (!placed[i] && checkAndPlaceBothWays(i, x, y, progress, done)) {
return true
}
}
return false
}
function checkAndPlaceBothWays (piecesIndex, x, y, progress, done) {
return checkAndPlaceOneWay(piecesIndex, false, x, y, progress, done) ||
checkAndPlaceOneWay(piecesIndex, true, x, y, progress, done)
}
function checkAndPlaceOneWay (piecesIndex, rotated, x, y, progress, done) {
var piece = pieces[piecesIndex]
var width = rotated ? piece[1] : piece[0]
var height = rotated ? piece[0] : piece[1]
if (checkAndPlace(x, y, width, height, piecesIndex + 1)) {
placed[piecesIndex] = true
if (allPlaced()) {
if (done(pieces, board)) {
return true
}
} else {
if (findNextCorner(x, y, done, function (x, y) {
return fillBoard(piecesIndex + 1, x, y, progress, done)
})) {
return true
}
}
unPlace(x, y, width, height)
placed[piecesIndex] = false
} else {
progress(pieces, board)
}
return false
}
function findNextCorner (startX, startY, done, callback) {
for (var y = startY; y < boardSize; y++) {
for (var x = (y === startY ? startX : 0); x < boardSize; x++) {
if (!board[x][y]) {
return callback(x, y)
}
}
}
return false
}
function checkAndPlace (x, y, width, height, value) {
if (x + width > boardSize || y + height > boardSize) return false
// check the corners first
if (board[x + width - 1][y] || board[x][y + height - 1] || board[x + width - 1][y + height - 1]) return false
for (var i = x; i < x + width; i++) {
for (var j = y; j < y + height; j++) {
if (!board[i][j]) {
board[i][j] = value
} else {
// oops! something's here; better clean up our mess...
for (var l = x; l <= i; l++) {
for (var m = y; m < (i === l ? j : y + height); m++) {
board[l][m] = 0
}
}
return false
}
}
}
return true
}
function unPlace (x, y, width, height) {
for (var i = x; i < x + width; i++) {
for (var j = y; j < y + height; j++) {
board[i][j] = 0
}
}
}
function allPlaced () {
for (var i = 0; i < placed.length; i++) {
if (!placed[i]) {
return false
}
}
return true
}