【20140423】【jQuery】8クイーン問題アプリ
お題
8クイーン問題を解くアプリを開発する
プログラム概要
ボタンを押すと8クイーン問題の解析が始まる。
最終的にクイーンを置いた箇所が赤になり、
盤上にクイーンを置いた回数を表示させる。
ソース
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>8クイーン体験アプリ</title>
<script src="http://code.jquery.com/jquery-1.8.2.min.js"></script>
<style>
img {
width: 100px;
height: 100px;
margin: 0px;
}
body {
background-color: yellow;
}
td {
width: 50px;
height: 50px;
background-color: yellow;
}
</style>
</head>
<body background="">
<h3>8クイーン問題</h3>
<input type="button" id="button" value="開始">
<table border="1">
<tr id="tr0">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr1">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr2">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr3">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr4">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr5">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr6">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr id="tr7">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
</table>
<br>
<script>
$(function() {
var SUCCESS = 1; // 成功
var FAIL = 0; // 失敗
var FREE = 1; // この場所は利き筋になっていない
var NOT_FREE = 0; // この場所は利き筋になっている
var N = 8; // クイーンの数
// 各行におかれたクイーンの位置
var pos = new Array(N);
// クイーンが垂直方向に利いているかを示す配列
var col = new Array(N);
// クイーンが右斜め下向きに利いているかを示す配列
var down = new Array(2 * N - 1);
// クイーンが右斜め上向きに利いているかを示す配列
var up = new Array(2 * N - 1);
// クイーンを置いた数を示す配列
var count = new Array(N * N);
// スリープ関数
function sleep(t){
var d1 = new Date().getTime();
var d2 = new Date().getTime();
while( d2 < d1+1000*t ){ //T秒待つ
d2=new Date().getTime();
}
return;
}
// クイーンの位置と聞き筋を初期化する
function init_board() {
var i;
for(i = 0; i < N; i++)
pos[i] = -1;
for (i = 0; i < N; i++)
col[i] = FREE;
for (i = 0; i < 2 * N - 1; i++)
down[i] = FREE;
for (i = 0; i < 2 * N - 1; i++)
up[i] = FREE;
for (i = 0; i < N * N; i++) {
count[i] = 0;
}
}
// a行目以降すべての行にクイーンを置いてみる
function execute(a) {
var b;
// 左から右に向かって順番にクイーンがおけるかどうかを調べる
for(b = 0; b < N; b++) {
// a行目のb番目に置けるかどうかを調べる
if (col[b] == FREE && up[a+b] == FREE && down[a-b+(N-1)] == FREE) {
// 置くことができた。場所を記録して、利き筋をセットする
pos[a] = b;
target_tds = '#tr' + a + ' > td';
$(target_tds).eq(b).css("background-color", "red");
count[a * N + b]++;
col[b] = NOT_FREE;
up[a+b] = NOT_FREE;
down[a-b+(N-1)] = NOT_FREE;
// N個のクイーンをすべておくことができれば成功である
if (a + 1 >= N)
return SUCCESS;
else {
// a+1行目以降のすべての行に置けたら成功である
if (execute(a + 1) == SUCCESS)
return SUCCESS;
else {
// 失敗した。クイーンを取り除く
pos[a] = -1;
target_tds = '#tr' + a + ' > td';
$(target_tds).eq(b).css("background-color", "yellow");
col[b] = FREE;
up[a + b] = FREE;
down[a - b + (N-1)] = FREE;
}
}
}
}
// 結局この行には置ける場所がなかった
return FAIL;
}
function main() {
init_board();
if(execute(0) == SUCCESS) {
alert('成功');
} else {
alert('失敗');
}
for(var i = 0; i < N; i++) {
target_tds = '#tr' + i + ' > td';
for(var j = 0; j < N; j++) {
$(target_tds).eq(j).text(count[i * N + j]);
}
}
$('table').after($('<p>テーブルの中の数字はクイーンが置かれた回数です</p>'));
}
$('#button').click(function() {
main();
});
});
</script>
</body>
</html>