第48回:JavaScript講座予告編「数独を自動で解くプログラム」
どうも、シノです。
えー、すみません、今回は予告編となります。
次回やる内容が決定いたしました!!!
次回は、「再帰」という考え方を扱いたいと思います。
気になる方は自分で先に調べてください。いや、私の記事更新なんて待つ必要ないです。
で、これだけというのもアレなので、ちょっとサンプルプログラムの結果だけ載せておきます。
今回サンプルとして用意したのは、「数独を自動で解いてくれる」プログラムです。
元々入っているものは、「世界一難しい」と言われる問題です。
上が問題の入力部分、「解く」ボタンを押すと、答えが見つかれば下のグレーのところに答えが出力されます。見つからないと何も出力されません。
一応、「クリア」ボタンも用意しました。これを押すと答えの欄が空欄になります。
もちろん、問題の入力部分は変えれるようにしてあるので、どうしても答えが見たい問題がある方は、入力して解いてみてください。
あ、とりあえず動いたなくらいの確認しかできてないです。
見直し、テスト等一切なしで載せてるので、変な動作したらごめんなさい…
今回本編の書けなかった原因なんですが、まず一つはこのプログラムを組むだけで3時間くらいかかってること。
そしてもう一つが、この再帰の中で、私が予想していたものと異なる動きをした部分があったんです。
で、そこの理解がまだ追い付いてなく…申し訳ないですがちょっとお待ちください(´・ω・`)
更新情報はTwitterで垂れ流しています。よかったらチェックしてみてください。
それでは、次回をお楽しみに!
一応、サンプルのソースコードも載せておきます。
上にも書いたのですが、まだとりあえず動くくらいの確認しかしてないので、変な動作しても責任は負えません(´・ω・`)
ご了承の上、ご覧ください。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>数独解析</title>
<style type="text/css">
table{
margin-left: auto;
margin-right: auto;
border-collapse: collapse;
}
table *{
font-size: 1.5rem;
text-align: center;
}
input{
text-align: center;
width: 2rem;
}
td.verticalline{
border-right: 2px solid #000000;
}
tr.horizonline{
border-bottom: 2px solid #000000;
}
.button{
width: 3rem;
height: 3rem;
}
*{
text-align: center;
}
</style>
</head>
<body>
<script>
function inputNumber(){
document.getElementById("prob[0][2]").value = 5;
document.getElementById("prob[0][3]").value = 3;
document.getElementById("prob[1][0]").value = 8;
document.getElementById("prob[1][7]").value = 2;
document.getElementById("prob[2][1]").value = 7;
document.getElementById("prob[2][4]").value = 1;
document.getElementById("prob[2][6]").value = 5;
document.getElementById("prob[3][0]").value = 4;
document.getElementById("prob[3][5]").value = 5;
document.getElementById("prob[3][6]").value = 3;
document.getElementById("prob[4][1]").value = 1;
document.getElementById("prob[4][4]").value = 7;
document.getElementById("prob[4][8]").value = 6;
document.getElementById("prob[5][2]").value = 3;
document.getElementById("prob[5][3]").value = 2;
document.getElementById("prob[5][7]").value = 8;
document.getElementById("prob[6][1]").value = 6;
document.getElementById("prob[6][3]").value = 5;
document.getElementById("prob[6][8]").value = 9;
document.getElementById("prob[7][2]").value = 4;
document.getElementById("prob[7][7]").value = 3;
document.getElementById("prob[8][5]").value = 9;
document.getElementById("prob[8][6]").value = 7;
}
function getNumber(){
var result = new Array(9);
for(var i = 0; i < 9; i++){
result[i] = new Array(9);
for(var j = 0; j < 9; j++){
var input = document.getElementById("prob[" + i + "][" + j + "]").value;
if(input == ""){
result[i][j] = 0;
}else{
result[i][j] = parseInt(input);
}
}
}
return result;
}
function checkVH(prob, i, j, num){
for(var k = 0; k < 9; k++){
if(i != k && prob[k][j] == num){
return false;
}
if(j != k && prob[i][k] == num){
return false;
}
}
return true;
}
function checkSQ(prob, i, j, num){
for(var k = parseInt(i / 3) * 3; k < parseInt(i / 3) * 3 + 3; k++){
for(var l = parseInt(j / 3) * 3; l < parseInt(j / 3) * 3 + 3; l++){
if((k != i || l != j) && prob[k][l] == num){
return false;
}
}
}
return true;
}
function checkNum(prob, i, j, num){
return checkVH(prob, i, j, num) && checkSQ(prob, i, j, num);
}
function inputResult(result){
for(var i = 0; i < 9; i++){
for(var j = 0; j < 9; j++){
document.getElementById("result[" + i + "][" + j + "]").value = result[i][j];
}
}
}
function solveMain(prob, i, j){
if(i == 9){
inputResult(prob);
return true;
}
var next_i = i;
if(j == 8){
next_i += 1;
}
var next_j = (j + 1) % 9;
if(prob[i][j] > 0){
solveMain(prob, next_i, next_j);
}else{
for(var k = 1; k <= 9; k++){
if(!checkNum(prob, i, j, k)){
continue;
}
prob[i][j] = k;
if(solveMain(prob, next_i, next_j)){
return true;
}
prob[i][j] = 0;
}
}
return false;
}
function solve(){
var prob = getNumber();
solveMain(prob, 0, 0);
}
function clr(){
for(var i = 0; i < 9; i++){
for(var j = 0; j < 9; j++){
document.getElementById("result[" + i + "][" + j + "]").value = "";
}
}
}
</script>
<div>
<p>解きたい問題</p>
<script>
document.write('<table border="1">');
for(var i = 0; i < 9; i++){
document.write('<tr class="');
if(i % 3 == 2 && i < 8){
document.write('horizonline');
}
document.write('">');
for(var j = 0; j < 9; j++){
document.write('<td class="');
if(j % 3 == 2 && j < 8){
document.write('verticalline');
}
document.write('"><input type="number" id="prob[' + i + '][' + j + ']" name="prob" min="1" max="9"></td>');
}
document.write('</td>');
}
document.write('</table>');
inputNumber();
</script>
<br />
<input class="button" type="submit" id="solve" name="solve" value="解く" onclick="solve()">
<input class="button" type="submit" id="clear" name="clear" value="クリア" onclick="clr()">
<p>解答</p>
<script>
document.write('<table border="1">');
for(var i = 0; i < 9; i++){
document.write('<tr class="');
if(i % 3 == 2 && i < 8){
document.write('horizonline');
}
document.write('">');
for(var j = 0; j < 9; j++){
document.write('<td class="');
if(j % 3 == 2 && j < 8){
document.write('verticalline');
}
document.write('"><input type="number" id="result[' + i + '][' + j + ']" name="result" disabled></td>');
}
document.write('</td>');
}
document.write('</table>');
</script>
</div>
</body>
</html>