8-Queen
8queen.jsfunction setup(){
col = [];
qpos = [];
up = {};
down = {};
nqueens = 8;
var i;
for(i=0;i<nqueens;i++){
col[i] = qpos[i] = 0;
}
for(i= -nqueens;i<nqueens;i++){
up[i+nqueens] = 0;
down[i+nqueens] = 0;
}
expand(0);
}
function output(){
var i;
var s = '';
for(i=0;i<nqueens;i++){
s += qpos[i];
}
console.log(s);
}
function expand(n){
for(var c=0;c<nqueens;c++){
if(col[c] == 0 && up[n+c] == 0 && down[n-c+nqueens] == 0){
qpos[n] = c;
if(n+1 >= nqueens){
output();
}
else {
col[c] = up[n+c] = down[n-c+nqueens] = 1;
expand(n+1);
col[c] = up[n+c] = down[n-c+nqueens] = 0;
}
}
}
}Generatorの使い方がおかしくて動かない
8queen2.jsfunction setup(){
col = [];
qpos = [];
up = {};
down = {};
nqueens = 8;
var i;
for(i=0;i<nqueens;i++){
col[i] = qpos[i] = 0;
}
for(i= -nqueens;i<nqueens;i++){
up[i+nqueens] = 0;
down[i+nqueens] = 0;
}
gen = expand(0);
}
function mouseClicked(){ // クリックすると次々と値を表示する
background('#ff8')
//clear()
value = gen.next().value
text(value.join(' '), 30, 40)
}
function* expand(n){
for(var c=0;c<nqueens;c++){
if(col[c] == 0 && up[n+c] == 0 && down[n-c+nqueens] == 0){
qpos[n] = c;
if(n+1 >= nqueens){
yield qpos; // これは無理か?
}
else {
col[c] = up[n+c] = down[n-c+nqueens] = 1;
expand(n+1);
col[c] = up[n+c] = down[n-c+nqueens] = 0;
}
}
}
}ruby#
# Generate and Testで8-Queenを解く
#
(0..7).to_a.permutation { |a|
h = {}
collision = false
(0..7).each { |x|
y = a[x]
collision = true if h[x+y]
break if collision
h[x+y] = true
}
next if collision
h = {}
collision = false
(0..7).each { |x|
y = a[x]
collision = true if h[x-y]
break if collision
h[x-y] = true
}
next if collision
puts a.join('-')
}再帰を使うのが一般的だと思うがこの程度なら力技でも大丈夫なようだ
魔方陣でも大丈夫かも
解を生成するプログラムと表示するプログラムを別プロセスにしたい