javascript设计模式交流（2）

javascript设计模式交流（2）2010-02-04 csdn博客挨踢老人最后是finish函数在beam的基础上修改一下就可以了我们可以通过finish检查，来决定求一个可行解、求所有解、还是对解计数，下面的finish是求出并打印所有解。

Code:

function finishQueen（）{
if（this.depth<this.size）return false;
x=this.pos;y=this.depth-1;
while（--x>=0&&--y>=0）
if（this[y][x]！=0）return false;
x=this.pos;y=this.depth-1;
while（--y>=0）
if（this[y][x]！=0）return false;
x=this.pos;y=this.depth-1;
while（--y>=0&&++x<this.size）
{
if（this[y][x]！=0）return false;
}
document.write（this+"
"）;
return false;
}

有了这三个函数之后，就可以定义一个BFSQueen类，使它继承Queen类并实现 BreadthFirstSearch接口定义如下

Code:

function BFSQueen（n）
{
var ret=new Queen（n）;
var BFS=new BreadthFirstSearch（extendQueen,beamQueen,finishQueen）;
BFS.apply（ret）;
return ret;
}

下面是完整的八皇后问题代码，在我的电脑上大约跑了30秒用FF的话只需要一半的时间

<pre style="font-family:宋体;">
<script>
function Queen（n）{
var ret=new Array（）;
ret.size=n;//皇后问题的规模
ret.depth=0;//搜索的深度
ret.pos=0;//新皇后的水平位置
for（var y=0;y<n;y++）
{
ret.push（[]）;
for（var x=0;x<n;x++）
ret[ret.length-1].push（0）;
}
function objectPrototypeClone（）
{
var tmp=function（）{};
tmp.prototype=this;
return new tmp;
}
ret.clone=function（）{
var r=objectPrototypeClone.call（this）;
for（var i=0;i<n;i++）
{
r[i]=objectPrototypeClone.call（this[i]）
}
return r;
}
ret.toString=function（）{
var str="";
for（var y=0;y<n;y++）
{
for（var x=0;x<n;x++）
str+=this[y][x]==0？"○":"★";
str+="
";
}
return str;
}
return ret;
}
function extendQueen（）
{
var ret=new Array（）;
if（this.depth==this.size）return ret;
for（var i=0;i<this.size;i++）
{
var current=this.clone（）;
//alert（current.depth）;
current[current.depth][i]=1;
current.pos=i;
current.depth++;
ret.push（current）;
}
return ret;
}
function beamQueen（）
{
var x,y;
if（this.depth==0）return false;
if（this.depth==this.size）return true;
x=this.pos;y=this.depth-1;
while（--x>=0&&--y>=0）
if（this[y][x]！=0）return true;
x=this.pos;y=this.depth-1;
while（--y>=0）
if（this[y][x]！=0）return true;
x=this.pos;y=this.depth-1;
while（--y>=0&&++x<this.size）
{
if（this[y][x]！=0）return true;
}
return false;
}
function finishQueen（）{
if（this.depth<this.size）return false;
x=this.pos;y=this.depth-1;
while（--x>=0&&--y>=0）
if（this[y][x]！=0）return false;
x=this.pos;y=this.depth-1;
while（--y>=0）
if（this[y][x]！=0）return false;
x=this.pos;y=this.depth-1;
while（--y>=0&&++x<this.size）
{
if（this[y][x]！=0）return false;
}
document.write（++count+".
"+this）;
return false;
}
function BreadthFirstSearch（extend,beam,finish）
{
return function（）{
this.finish=finish;
this.extend=extend;
this.beam=beam;
this.search=function（）{
var queue=[this];
while（queue.length）
{
var current=queue.shift（）;
if（！current.beam（））{
var extended=current.extend（）;
for（var i=0;i<extended.length;i++）
{
if（extended[i].finish（））return extended[i];
queue.push（extended[i]）;
}
}
}
return null;
}
}
}
function BFSQueen（n）
{
var ret=new Queen（n）;
var BFS=new BreadthFirstSearch（extendQueen,beamQueen,finishQueen）;
BFS.apply（ret）;
return ret;
}
var queen=new BFSQueen（8）;
var count=0;
queen.search（）;
</script>
</pre>