春风博客

春天里,百花香...

导航

<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

使用全排列方法解九宫格问题

下面的方法能解出九宫格,但对于更高阶只有理论可能性,因为耗时太长,不能作为通用解决方案。

输出:
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);
    }
}

posted on 2008-04-08 22:16 sitinspring 阅读(2082) 评论(1)  编辑  收藏 所属分类: 算法数据结构

评论

# re: 使用全排列方法解九宫格问题 2008-11-19 19:27 杨鞠孝

好   回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.