数独ソルバー
上記のやり方でそのままJavaScriptで書いてみた。メモ程度に全文残しておく。
<html>
<head>
<script language="JavaScript">
//<!--
Array.prototype.indexOf = function (value) {
for (var i = 0; i < this.length; i += 1) {
if (this[i] == value) return i;
}
return -1;
};
Array.prototype.remove = function (value) {
var index = this.indexOf(value);
if (index < 0) return false;
this.splice(index, 1);
return true;
};
Array.prototype.deepcopy = function () {
var other = [];
for (var i = 0; i < this.length; i += 1) {
var v = this[i];
if (v.constructor == Array) {
other[i] = v.deepcopy();
} else {
other[i] = v;
}
}
return other;
};
var div = function (a, b) {
return (a - (a % b)) / b;
};
var init = function () {
initInput();
initSample();
};
var initInput = function () {
var sourceDiv = document.getElementById("source");
var questionId = "question";
var questionTable = createSudokuTable(questionId);
sourceDiv.appendChild(questionTable);
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
var cid = questionId + i + "" + j;
var cell = document.getElementById(cid);
var iid = "source" + i + "" + j;
var input = document.createElement("input");
input.id = iid;
input.size = 1;
cell.appendChild(input);
}
}
};
var initSample = function () {
var sample = [
[8,0,7,
0,6,0,
5,0,1],
[0,0,1,
0,0,0,
2,7,0],
[0,0,3,
0,9,0,
6,0,0],
[0,0,3,
6,0,2,
1,5,0],
[5,0,0,
0,0,8,
3,0,0],
[0,0,0,
0,1,0,
2,0,0],
[9,0,0,
0,0,0,
4,7,0],
[1,3,0,
0,0,4,
0,8,5],
[8,0,6,
9,5,7,
0,0,2]
];
setSample(sample);
};
var clearSample = function () {
var sample = [
[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,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,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]
];
setSample(sample);
};
var setSample = function (sample) {
var id = "source";
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
var value = sample[i][j];
var iid = id + i + "" + j;
var input = document.getElementById(iid);
if (value == 0) {
input.value = "";
} else {
input.value = "" + value;
}
}
}
};
var createSudokuTable = function (id) {
var outTable = document.createElement("table");
outTable.id = id;
outTable.border = "1";
var indexO = 0;
for (var oRow = 0; oRow < 3; oRow += 1) {
var outRow = outTable.insertRow(oRow);
for (var oCol = 0; oCol < 3; oCol += 1) {
var outCol = outRow.insertCell(oCol);
var inTable = document.createElement("table");
inTable.id = id + indexO;
inTable.border = "1";
var indexI = 0;
for (var iRow = 0; iRow < 3; iRow += 1) {
var inRow = inTable.insertRow(iRow);
for (var iCol = 0; iCol < 3; iCol += 1) {
var inCol = inRow.insertCell(iCol);
var inDiv = document.createElement("div");
inCol.appendChild(inDiv);
inDiv.id = id + indexO + "" + indexI;
//inDiv.innerHTML = "0";
indexI += 1;
}
}
outCol.appendChild(inTable);
indexO += 1;
}
}
return outTable;
};
var solve = function () {
clearResult();
var data = createData();
try {
var id = "source";
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
var iid = id + i + "" + j;
var input = document.getElementById(iid);
if (input.value.length == 0) continue;
var value = parseInt(input.value);
if (value == 0) continue;
fixValue(data, i, j, value);
}
}
//showResult(data);
detect(data);
} catch (ex) {
alert(ex);
}
};
var isSolution = function (data) {
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
if (data[i][j].length != 1) return false;
}
}
return true;
};
var detect = function (data) {
if (isSolution(data)) {
showResult(data);
return true;
}
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
var values = data[i][j];
if (values.length == 1) continue;
var v = values.deepcopy();
for (var k = 0; k < v.length; k += 1) {
var value = v[k];
var newData = data.deepcopy();
try {
fixValue(newData, i, j, value);
} catch (ex) {
values.remove(value);
continue;
}
var detected = detect(newData);
if (detected) return true;
}
}
}
return false;
};
var createData = function () {
var data = [];
for (var i = 0; i < 9; i += 1) {
var inner = [];
data.push(inner);
for (var j = 0; j < 9; j += 1) {
var values = [];
inner.push(values);
for (var v = 1; v <= 9; v += 1) {
values.push(v);
}
}
}
return data;
};
var fixValue = function (data, x, y, value) {
data[x][y] = [value];
checkValue(data, x, y, value);
};
var checkValue = function (data, x, y, value) {
// group check
for (var i = 0; i < 9; i += 1) {
if (i == y) continue;
removeValue(data, x, i, value);
}
//row check
var xdiv3 = div(x,3);
var ydiv3 = div(y,3);
for (var i = 0; i < 9; i += 1) {
if (i == x) continue;
if (div(i, 3) != xdiv3) continue;
for (var j = 0; j < 9; j += 1) {
if (div(j, 3) != ydiv3) continue;
removeValue(data, i, j, value);
}
}
// col check
var xmod3 = x % 3;
var ymod3 = y % 3;
for (var i = 0; i < 9; i += 1) {
if (i == x) continue;
if (i % 3 != xmod3) continue;
for (var j = 0; j < 9; j += 1) {
if (j % 3 != ymod3) continue;
removeValue(data, i, j, value);
}
}
};
var removeValue = function (data, x, y, value) {
var removed = data[x][y].remove(value);
if (data[x][y].length == 0) throw "input data has no solutions.";
if (removed && data[x][y].length == 1) {
checkValue(data, x, y, data[x][y][0]);
}
};
var showResult = function (data) {
var resultDiv = document.getElementById("result");
var resultId = "solution";
var resultTable = createSudokuTable(resultId);
resultDiv.appendChild(resultTable);
for (var i = 0; i < 9; i += 1) {
for (var j = 0; j < 9; j += 1) {
var cid = resultId + i + "" + j;
var cell = document.getElementById(cid);
var cellDiv = document.createElement("div");
cellDiv.innerHTML = "" + data[i][j];
cell.appendChild(cellDiv);
}
}
};
var clearResult = function () {
var resultDiv = document.getElementById("result");
resultDiv.innerHTML = "";
};
//-->
</script>
</head>
<body onload="init()">
<form id="input">
<div id="source">
</div>
<input type="button" id="" value="solve" onclick="solve()" />
<input type="button" id="" value="clear" onclick="clearSample()" />
</form>
<div id="result">
</div>
</body>
</html>ACMのプログラミングコンテストとかでも思うけど、こういうクイズ解決タイプのプログラミング、とりわけ解法を試行錯誤していく面では、クラスとか使うオブジェクト指向プログラミングは合わない。汎用のデータ型(リストやタプル、マップなど)がしっかりしていて、それに対する強力な機能が用意されていることが重要だ。
中身があまりよくわからないうちは、いろいろ操作できることが重要となり、オブジェクトモデリングのような先に関連付けを決めるようなものとは逆のアプローチになるからだろう。そのため、こういう状況での選択は、関数型言語 > C++(STL) > Javaとなりそうだ。
JavaScriptはというと、言語的にはいいせんいっているんだけど、デフォルト環境での、数値演算の貧弱さ、Arrayの貧弱さなどで、少し躊躇するところである。
