javascript设计模式交流(2)

最后是finish函数 在beam的基础上修改一下就可以了 我们可以通过finish检查，来决定求一个可行解、求所有解、还是对解计数，下面的finish是求出并打印所有解。

Code:

functionfinishQueen(){
　　if(this.depth<this.size)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--x>=0&&--y>=0)
　　　　if(this[y][x]!=0)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0)
　　　　if(this[y][x]!=0)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0&&++x<this.size)
　　{
　　　　if(this[y][x]!=0)returnfalse;
　　}
　　document.write(this+"n");
　　returnfalse;
}　

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

Code:

functionBFSQueen(n)
{
　　varret=newQueen(n);
　　varBFS=newBreadthFirstSearch(extendQueen,beamQueen,finishQueen);
　　BFS.apply(ret);
　　returnret;
}

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

<prestyle="font-family:宋体;">
<script>
functionQueen(n){
　　varret=newArray();
　　ret.size=n;　　　　　　　　　　　　　　　　//皇后问题的规模
　　ret.depth=0;　　　　　　　　　　　　　　　　//搜索的深度
　　ret.pos=0;　　　　　　　　　　　　　　　　//新皇后的水平位置
　　for(vary=0;y<n;y++)
　　{
　　　　ret.push([]);
　　　　for(varx=0;x<n;x++)
　　　　　　ret[ret.length-1].push(0);
　　}
　　functionobjectPrototypeClone()
　　{
　　　　vartmp=function(){};
　　　　tmp.prototype=this;
　　　　returnnewtmp;
　　}
　　ret.clone=function(){
　　　　varr=objectPrototypeClone.call(this);
　　　　for(vari=0;i<n;i++)
　　　　{
　　　　　　r[i]=objectPrototypeClone.call(this[i])
　　　　}
　　　　returnr;
　　}
　　ret.toString=function(){
　　　　varstr="";
　　　　for(vary=0;y<n;y++)
　　　　{
　　　　　　for(varx=0;x<n;x++)
　　　　　　　　str+=this[y][x]==0?"○":"★";
　　　　　　str+=" ";
　　　　}
　　　　returnstr;
　　}
　　returnret;
}
functionextendQueen()
{
　　varret=newArray();
　　if(this.depth==this.size)returnret;
　　for(vari=0;i<this.size;i++)
　　{
　　　　varcurrent=this.clone();
　　　　//alert(current.depth);
　　　　current[current.depth][i]=1;
　　　　current.pos=i;
　　　　current.depth++;
　　　　ret.push(current);
　　}
　　returnret;
}
functionbeamQueen()
{
　　varx,y;
　　if(this.depth==0)returnfalse;
　　if(this.depth==this.size)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--x>=0&&--y>=0)
　　　　if(this[y][x]!=0)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0)
　　　　if(this[y][x]!=0)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0&&++x<this.size)
　　{
　　　　if(this[y][x]!=0)returntrue;
　　}
　　returnfalse;
}
functionfinishQueen(){
　　if(this.depth<this.size)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--x>=0&&--y>=0)
　　　　if(this[y][x]!=0)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0)
　　　　if(this[y][x]!=0)returnfalse;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0&&++x<this.size)
　　{
　　　　if(this[y][x]!=0)returnfalse;
　　}
　　document.write(++count+". "+this);
　　returnfalse;
}
functionBreadthFirstSearch(extend,beam,finish)
{
　　returnfunction(){
　　　　this.finish=finish;
　　　　this.extend=extend;
　　　　this.beam=beam;
　　　　this.search=function(){
　　　　　　
　　　　　　varqueue=[this];
　　　　　　while(queue.length)
　　　　　　{
　　　　　　　　varcurrent=queue.shift();
　　　　　　　　if(!current.beam()){
　　　　　　　　　　varextended=current.extend();
　　　　　　　　　　for(vari=0;i<extended.length;i++)
　　　　　　　　　　{
　　　　　　　　　　　　if(extended[i].finish())returnextended[i];
　　　　　　　　　　　　queue.push(extended[i]);
　　　　　　　　　　}
　　　　　　　　}　　　　
　　　　　　}
　　　　　　returnnull;
　　　　}
　　}
}
functionBFSQueen(n)
{
　　varret=newQueen(n);
　　varBFS=newBreadthFirstSearch(extendQueen,beamQueen,finishQueen);
　　BFS.apply(ret);
　　returnret;
}
varqueen=newBFSQueen(8);
varcount=0;
queen.search();
</script>
</pre>