class Constraint {
constructor(cells, total) {
this.cells = cells;
this.total = total;
}
get length() {
return this.cells.length;
}
isSubsetOf(constraint) {
return this.cells.every(cell => constraint.indexOf(...cell) !== -1);
}
indexOf(row, col) {
return this.cells.findIndex(cell => cell[0] === row && cell[1] === col);
}
remove(row, col, flag = false) {
const index = this.indexOf(row, col);
if (index !== -1) {
this.cells.splice(index, 1);
if (flag) {
this.total--;
}
}
}
removeCells(cells) {
cells.forEach(cell => this.remove(...cell));
}
}
// constraints
class Constraints {
constructor(grid, totalMines) {
this.constraints = [];
const covered = [];
console.log(grid)
grid.forEach((row, col) => {
if (grid.isOpened(row, col)) {
console.log("this :", this)
this.addFromCell(grid, row, col);
}
if (grid.isCovered(row, col)) {
covered.push([row, col]);
}
});
this.add(covered, totalMines);
this.reduce();
}
get length() {
return this.constraints.length;
}
add(cells, value) {
if (cells.length > 0) {
this.constraints.push(new Constraint(cells, value));
}
}
addFromCell(grid, row, col) {
let value = grid.valueAt(row, col);
let cells = [];
grid.forEachNeighbor(row, col, (i, j) => {
if (grid.isCovered(i, j)) {
cells.push([i, j]);
}
if (grid.isFlagged(i, j)) {
value--;
}
});
this.add(cells, value);
}
reduce() {
for (let i = 0; i < this.constraints.length; i++) {
for (let j = 0; j < this.constraints.length; j++) {
if (i === j) continue;
const a = this.constraints[i];
const b = this.constraints[j];
if (a.isSubsetOf(b)) {
b.removeCells(a.cells);
b.total -= a.total;
}
}
}
this.constraints = this.constraints.filter(c => c.length > 0);
}
removeCell(row, col, flag = false) {
this.forEach(c => c.remove(row, col, flag));
}
flagCell(row, col) {
this.removeCell(row, col, true);
}
forEach(cb) {
this.constraints.forEach((c) => cb(c));
}
}
// Grid
class Grid {
constructor(map) {
this.grid = map.split('\n').map(row => {
return row.split(' ').map(value => value === '?' ? this.COVERED : +value);
});
}
get FLAGGED() { return 9; }
get COVERED() { return -1; }
toString() {
return this.grid.map((row, i) => {
return row.map((value, j) => {
if (this.isFlagged(i, j)) return 'x';
if (this.isCovered(i, j)) return '?';
return value;
}).join(' ');
}).join('\n');
}
_open_(row, col) {
const e = open(row, col)
console.log("before :", this.grid[row][col], row, col, typeof +e)
this.grid[row][col] = parseInt(e);
console.log("after :", this.grid[row][col], open(row, col))
}
flag(row, col) {
this.grid[row][col] = this.FLAGGED;
}
isFlagged(row, col) {
return this.valueAt(row, col) === this.FLAGGED;
}
isCovered(row, col) {
return this.valueAt(row, col) === this.COVERED;
}
isOpened(row, col) {
return !this.isFlagged(row, col) && !this.isCovered(row, col);
}
isFringe(row, col) {
if (!this.isCovered(row, col)) return false;
let isFringe = false;
this.forEachNeighbor(row, col, (i, j) => {
isFringe = isFringe || this.isOpened(i, j);
});
return isFringe;
}
valueAt(row, col) {
return this.grid[row][col];
}
forEach(cb) {
console.log("cb :", cb)
this.grid.forEach((row, i) => {
row.forEach((value, j) => cb(i, j));
});
}
forEachNeighbor(row, col, cb) {
for (let i = -1; i < 2; i++) {
for (let j = -1; j < 2; j++) {
if (i === 0 && j === 0) continue;
if (this.inGrid(row + i, col + j)) {
cb(row + i, col + j);
}
}
}
}
inGrid(row, col) {
return row >= 0 && row < this.grid.length
&& col >= 0 && col < this.grid[0].length;
}
}
// Fringe
class Fringe {
constructor(cells = []) {
this.cells = {};
cells.forEach(c => {
this.cells[c] = null;
});
}
static create(grid) {
const cells = [];
grid.forEach((row, col) => {
if (grid.isFringe(row, col)) {
cells.push([row, col]);
}
});
return new Fringe(cells);
}
clone() {
const fringe = new Fringe();
fringe.cells = Object.assign({}, this.cells);
return fringe;
}
meetsConstraints(constraints) {
let valid = true;
constraints.forEach(c => {
valid = valid && this.meetsConstraint(c);
});
return valid;
}
meetsConstraint(constraint) {
let total = 0;
let found = 0;
for (let cell in this.cells) {
const [row, col] = cell.split(',').map(Number);
const value = this.cells[cell];
if (value !== null && constraint.indexOf(row, col) > -1) {
found++;
total += value;
if (total > constraint.total) {
return false;
}
}
}
if (found === constraint.length && total !== constraint.total) {
return false;
}
return true;
}
set(cell, value) {
this.cells[cell] = value;
}
get unsolvedCell() {
let unsolvedCell = null;
for (let cell in this.cells) {
if (this.cells[cell] === null) {
unsolvedCell = cell;
break;
}
}
return unsolvedCell;
}
}
class Solutions {
constructor() {
this.fringes = [];
this.empty = {};
this.mines = {};
}
get length() {
return this.fringes.length;
}
get knownMines() {
const mines = [];
for (let key in this.mines) {
const cell = key.split(',').map(Number);
if (this.mines[key] === 1) {
mines.push(cell);
}
}
return mines;
}
get knownEmpty() {
const empty = [];
for (let key in this.empty) {
const cell = key.split(',').map(Number);
if (this.empty[key] === 0) {
empty.push(cell);
}
}
return empty;
}
push(fringe) {
this.fringes.push(fringe);
if (this.fringes.length === 1) {
for (let cell in fringe.cells) {
this.empty[cell] = 0;
this.mines[cell] = 1;
}
}
for (let cell in fringe.cells) {
this.empty[cell] |= fringe.cells[cell];
this.mines[cell] &= fringe.cells[cell];
}
}
}
class Solver {
constructor(map, totalMines) {
this.totalMines = totalMines;
this.grid = new Grid(map);
this.constraints = new Constraints(this.grid, totalMines);
}
solve() {
this.solveBasic();
if (this.constraints.length === 0) {
return this.grid.toString();
}
const solutions = this.findAllSolutions();
if (solutions.length > 0) {
this.flag(solutions.knownMines);
this._open_(solutions.knownEmpty);
if (solutions.knownMines.length > 0 || solutions.knownEmpty.length > 0) {
return this.solve();
}
}
return '?';
}
solveBasic() {
let changed = false;
this.constraints.forEach(c => {
if (c.total === 0) {
this._open_(c.cells);
changed = true;
}
if (c.total === c.length) {
this.flag(c.cells);
changed = true;
}
});
if (changed) {
this.constraints.reduce();
this.solveBasic();
}
}
findAllSolutions() {
let solutions = new Solutions();
const search = (fringe) => {
const solution = fringe.clone();
const unsolvedCell = fringe.unsolvedCell;
if (!unsolvedCell) {
solutions.push(solution);
return;
}
for (let i = 0; i <= 1; i++) {
solution.set(unsolvedCell, i);
if (!solution.meetsConstraints(this.constraints)) {
continue;
}
search(solution);
}
};
search(Fringe.create(this.grid));
return solutions;
}
_open_(cells) {
cells.slice().forEach(cell => {
const [row, col] = cell;
this.grid._open_(row, col);
this.constraints.removeCell(row, col);
this.constraints.addFromCell(this.grid, row, col);
});
}
flag(cells) {
cells.slice().forEach(cell => {
const [row, col] = cell;
this.grid.flag(row, col);
this.constraints.flagCell(row, col);
});
}
}
function solveMine(map, n) {
const solver = new Solver(map, n);
return solver.solve();
}
tests = [
[
`? ? ? ? ? ?
? ? ? ? ? ?
? ? ? 0 ? ?
? ? ? ? ? ?
? ? ? ? ? ?
0 0 0 ? ? ?`,
`1 x 1 1 x 1
2 2 2 1 2 2
2 x 2 0 1 x
2 x 2 1 2 2
1 1 1 1 x 1
0 0 0 1 1 1`
,6],
[
`0 ? ?
0 ? ?`,
`0 2 x
0 2 x`,2],
[`? ? ? ? 0 0 0
? ? ? ? 0 ? ?
? ? ? 0 0 ? ?
? ? ? 0 0 ? ?
0 ? ? ? 0 0 0
0 ? ? ? 0 0 0
0 ? ? ? 0 ? ?
0 0 0 0 0 ? ?
0 0 0 0 0 ? ?`,
`1 x x 1 0 0 0
2 3 3 1 0 1 1
1 x 1 0 0 1 x
1 1 1 0 0 1 1
0 1 1 1 0 0 0
0 1 x 1 0 0 0
0 1 1 1 0 1 1
0 0 0 0 0 1 x
0 0 0 0 0 1 1`,6]
]
for(let [a, b, n] of xs){
let r = solveMine(a, n)
console.log(r == b)
}
To embed this program on your website, copy the following code and paste it into your website's HTML: