javascript解三阶幻方(九宫格)
谜题:三阶幻方,试将1~9这9个不同整数填入一个3×3的表格,使得每行、每列以及每条对角线上的数字之和相同。
策略:穷举搜索。列出所有的整数填充方案,然后进行过滤。
亮点为递归函数getPermutation的设计,文章最后给出了几个非递归算法
//递归算法,很巧妙,但太费资源 functiongetPermutation(arr){ if(arr.length==1){ return[arr]; } varpermutation=[]; for(vari=0;i<arr.length;i++){ varfirstEle=arr[i];//取第一个元素 vararrClone=arr.slice(0);//复制数组 arrClone.splice(i,1);//删除第一个元素,减少数组规模 varchildPermutation=getPermutation(arrClone);//递归 for(varj=0;j<childPermutation.length;j++){ childPermutation[j].unshift(firstEle);//将取出元素插入回去 } permutation=permutation.concat(childPermutation); } returnpermutation; } functionvalidateCandidate(candidate){ varsum=candidate[0]+candidate[1]+candidate[2]; for(vari=0;i<3;i++){ if(!(sumOfLine(candidate,i)==sum&&sumOfColumn(candidate,i)==sum)){ returnfalse; } } if(sumOfDiagonal(candidate,true)==sum&&sumOfDiagonal(candidate,false)==sum){ returntrue; } returnfalse; } functionsumOfLine(candidate,line){ returncandidate[line*3]+candidate[line*3+1]+candidate[line*3+2]; } functionsumOfColumn(candidate,col){ returncandidate[col]+candidate[col+3]+candidate[col+6]; } functionsumOfDiagonal(candidate,isForwardSlash){ returnisForwardSlash?candidate[2]+candidate[4]+candidate[6]:candidate[0]+candidate[4]+candidate[8]; } varpermutation=getPermutation([1,2,3,4,5,6,7,8,9]); varcandidate; for(vari=0;i<permutation.length;i++){ candidate=permutation[i]; if(validateCandidate(candidate)){ break; }else{ candidate=null; } } if(candidate){ console.log(candidate); }else{ console.log('Novalidresultfound'); } //求模(非递归)全排列算法 /* 算法的具体示例: *求4个元素["a","b","c","d"]的全排列,共循环4!=24次,可从任意>=0的整数index开始循环,每次累加1,直到循环完index+23后结束; *假设index=13(或13+24,13+224,13+3*24…),因为共4个元素,故迭代4次,则得到的这一个排列的过程为: *第1次迭代,13/1,商=13,余数=0,故第1个元素插入第0个位置(即下标为0),得["a"]; *第2次迭代,13/2,商=6,余数=1,故第2个元素插入第1个位置(即下标为1),得["a","b"]; *第3次迭代,6/3,商=2,余数=0,故第3个元素插入第0个位置(即下标为0),得["c","a","b"]; *第4次迭代,2/4,商=0,余数=2,故第4个元素插入第2个位置(即下标为2),得["c","a","d","b"]; */ functionperm(arr){ varresult=newArray(arr.length); varfac=1; for(vari=2;i<=arr.length;i++)//根据数组长度计算出排列个数 fac*=i; for(varindex=0;index<fac;index++){//每一个index对应一个排列 vart=index; for(i=1;i<=arr.length;i++){//确定每个数的位置 varw=t%i; for(varj=i-1;j>w;j--)//移位,为result[w]留出空间 result[j]=result[j-1]; result[w]=arr[i-1]; t=Math.floor(t/i); } if(validateCandidate(result)){ console.log(result); break; } } } perm([1,2,3,4,5,6,7,8,9]); //很巧妙的回溯算法,非递归解决全排列 functionseek(index,n){ varflag=false,m=n;//flag为找到位置排列的标志,m保存正在搜索哪个位置,index[n]为元素(位置编码) do{ index[n]++;//设置当前位置元素 if(index[n]==index.length)//已无位置可用 index[n--]=-1;//重置当前位置,回退到上一个位置 elseif(!(function(){ for(vari=0;i<n;i++)//判断当前位置的设置是否与前面位置冲突 if(index[i]==index[n])returntrue;//冲突,直接回到循环前面重新设置元素值 returnfalse;//不冲突,看当前位置是否是队列尾,是,找到一个排列;否,当前位置后移 })())//该位置未被选择 if(m==n)//当前位置搜索完成 flag=true; else n++;//当前及以前的位置元素已经排好,位置后移 }while(!flag&&n>=0) returnflag; } functionperm(arr){ varindex=newArray(arr.length); for(vari=0;i<index.length;i++) index[i]=-1; for(i=0;i<index.length-1;i++) seek(index,i);//初始化为1,2,3,...,-1,最后一位元素为-1;注意是从小到大的,若元素不为数字,可以理解为其位置下标 while(seek(index,index.length-1)){ vartemp=[]; for(i=0;i<index.length;i++) temp.push(arr[index[i]]); if(validateCandidate(temp)){ console.log(temp); break; } } } perm([1,2,3,4,5,6,7,8,9]);
/*
全排列(非递归求顺序)算法
1、建立位置数组,即对位置进行排列,排列成功后转换为元素的排列;
2、按如下算法求全排列:
设P是1~n(位置编号)的一个全排列:p=p1,p2...pn=p1,p2...pj-1,pj,pj+1...pk-1,pk,pk+1...pn
(1)从排列的尾部开始,找出第一个比右边位置编号小的索引j(j从首部开始计算),即j=max{i|pi<pi+1}
(2)在pj的右边的位置编号中,找出所有比pj大的位置编号中最小的位置编号的索引k,即k=max{i|pi>pj}
pj右边的位置编号是从右至左递增的,因此k是所有大于pj的位置编号中索引最大的
(3)交换pj与pk
(4)再将pj+1...pk-1,pk,pk+1...pn翻转得到排列p'=p1,p2...pj-1,pj,pn...pk+1,pk,pk-1...pj+1
(5)p'便是排列p的下一个排列
例如:
24310是位置编号0~4的一个排列,求它下一个排列的步骤如下:
(1)从右至左找出排列中第一个比右边数字小的数字2;
(2)在该数字后的数字中找出比2大的数中最小的一个3;
(3)将2与3交换得到34210;
(4)将原来2(当前3)后面的所有数字翻转,即翻转4210,得30124;
(5)求得24310的下一个排列为30124。
*/
functionswap(arr,i,j){ vart=arr[i]; arr[i]=arr[j]; arr[j]=t; } functionsort(index){ for(varj=index.length-2;j>=0&&index[j]>index[j+1];j--) ;//本循环从位置数组的末尾开始,找到第一个左边小于右边的位置,即j if(j<0)returnfalse;//已完成全部排列 for(vark=index.length-1;index[k]<index[j];k--) ;//本循环从位置数组的末尾开始,找到比j位置大的位置中最小的,即k swap(index,j,k); for(j=j+1,k=index.length-1;j<k;j++,k--) swap(index,j,k);//本循环翻转j+1到末尾的所有位置 returntrue; } functionperm(arr){ varindex=newArray(arr.length); for(vari=0;i<index.length;i++) index[i]=i; do{ vartemp=[]; for(i=0;i<index.length;i++) temp.push(arr[index[i]]); if(validateCandidate(temp)){ console.log(temp); break; } }while(sort(index)); } perm([1,2,3,4,5,6,7,8,9]);
以上所述就是本文的全部内容了,希望大家能够喜欢。