Posted on 2008-04-08 22:16
博学精思慎言笃行 阅读(186)
评论(0) 编辑 收藏 所属分类:
算法数据结构
下面的方法能解出九宫格，但对于更高阶只有理论可能性，因为耗时太长，不能作为通用解决方案。
输出：
2 7 6
9 5 1
4 3 8
package com.sitinspring;
public class SquarePuzzle{
/**
* 阶数
*/
private int n;
/**
* 方阵数组
*/
private Integer[] arr;
/**
* 平均值
*/
private int average;
public SquarePuzzle(int n){
this.n=n;
// 建立数组并得到平均值
arr=new Integer[n*n];
average=0;
for(int i=1;i<=n*n;i++){
arr[i-1]=i;
average+=i;
}
average=average/n;
// 递归查看
permutation(arr,0,arr.length);
}
private void permutation(Integer[] arr,int start,int end){
if(start<end+1){
permutation(arr,start+1,end);
for(int i=start+1;i<end;i++){
Integer temp;
temp=arr[start];
arr[start]=arr[i];
arr[i]=temp;
permutation(arr,start+1,end);
temp=arr[i];
arr[i]=arr[start];
arr[start]=temp;
}
}
else{
/*for(int i=0;i<end;i++){
System.out.print(arr[i]);
}
System.out.print("\n");*/
int i,sum=0;
for(i=0;i<n;i++){
sum+=arr[i];
}
if(sum!=average){
return;
}
// 查看是否纵横对角线值都相等
checkAndPrint(arr);
}
}
private void checkAndPrint(Integer[] arr){
Integer[][] arr2=new Integer[n][n];
int i,j,sum;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
arr2[i][j]=arr[i*n+j];
}
}
// 横
for(i=0;i<n;i++){
sum=0;
for(j=0;j<n;j++){
sum+=arr2[i][j];
}
if(sum!=average){
return;
}
}
// 纵
for(i=0;i<n;i++){
sum=0;
for(j=0;j<n;j++){
sum+=arr2[j][i];
}
if(sum!=average){
return;
}
}
// 对角线
sum=0;
for(i=0;i<n;i++){
sum+=arr2[i][i];
}
if(sum!=average){
return;
}
// 对角线
sum=0;
for(i=0;i<n;i++){
sum+=arr2[i][n-i-1];
}
if(sum!=average){
return;
}
// 最终打印
for(i=0;i<n;i++){
for(j=0;j<n;j++){
System.out.print(arr2[i][j]+"\t");;
}
System.out.print("\n");;
}
System.out.print("\n");;
System.exit(0);
}
public static void main(String[] args){
new SquarePuzzle(3);
}
}