package com.lyk.exercise;
 /**
  * 九宫格算法实现类
  * 我现在的思路是将3*3个数字进行全排列
  * 在全排列的过程中进行检索满足条件的排列
  * 然后在显示出来
  * 可能这个算法还有待优化
  * 将数字存放到数组里面然后再递归回溯
  * 目前只能实现3*3的魔方更大的话就太耗时间了
  * @author LYk
  *
  */
  public class NineCell {
	  
	  /**
	   * 判断每行每列以及对角线的值是否满足条件
	   * 
	   * @param number 检索的数组
	   * @return true is 满足条件 否则false不满足条件
	   */
	  private boolean right(int []number){
		  int size=(int) Math.sqrt(number.length);
		  int [][]ary=new int[size][size];
		  int index=0;
		  int check=stand(number);
		  //将一维数组转化为二维数组
		  for(int row=0;row<size;row++){
		  for(int column=0;column<size;column++){
			  ary[row][column]=number[index];
			  index++;
		  }
		  }
		  int result=0;
		  //检测每一行的值是否相等
		  for(int row=0;row<size;row++){
			  for(int column=0;column<size;column++){
				  result+=ary[row][column];
			  }
			  if(result!=check){
				  return false;
			  }
			  result=0;
			  
			  }
		  //判断每列的值是否相等
		  for(int row=0;row<size;row++){
			  for(int column=0;column<size;column++){
				  result+=ary[column][row];
			  }
			  if(result!=check){
				  return false;
			  }
			  result=0;
			  
			  }
		  //判断对角线的值是否相等
		  for(int i=0;i<size;i++){
			  
			  result+=ary[i][i];
		  }
		  if(result!=check){
			  return false;
		  }
		  result=0;
		  for(int column=size-1,row=0;column>=0&&row<size;column--,row++){
			  result+=ary[row][column];
		  }
		  if(result!=check){
			  return false;
		  }
		  
		  
		  return true;
		  
	  }
	  /**
	   * 打印满足九宫格条件的数组
	   * @param number
	   */
	  private void printResults(int []number){
		   int row=(int) Math.sqrt(number.length);
		   for(int i=0;i<number.length;i++){
			   System.out.print(number[i]+"\t");
			   if((i+1)%row==0){
				   System.out.println();
			   }
		   }
		    System.out.println();
		  
	  }
	  /**
	   * 计算出满足N*N使每行每列及对角线都相等的值
	   * 比如3*3的格子每行每列的值都及对角线的值都等于15
	   * @param number
	   * @return
	   */
	  private int stand(int []number){
		  int size=number.length;
		  int row=(int) Math.sqrt(size);
		  return (int) ((1+size)*size*Math.pow(2, -1))/row;
	  }
	
	  /**
	   * 将N*N个数字进行全排列
	   * @param n数字
	   */
	  private void coreCode(int []number,int begin,int end){
		  int row=(int) Math.sqrt(number.length);
		  //如果是偶数阶则返回
		  if(row%2==0){
			  return;
		  }


		  else if (begin == end) {// 如果begin等于end说明，数组中的元素交换完毕，可以进行打印输出
			  if(number[end/2]==(number.length+1)/2&&right(number))//判断是否为奇数阶魔方如果是就打印输出
			 printResults(number);

				}

			 else {// 如果元素还没有交换完毕，继续进行递归

				for (int i = begin; i <= end; i++) {

					int temp = number[begin];// 将首元素与其后的第i个元素进行交换
					number[begin] = number[i];
					number[i] = temp;

					// 判断中间那个数是否是N*N正阶魔方的长度的一半
				

					coreCode(number, begin + 1, end);
				
					// 还原数组

					number[i] = number[begin];

					number[begin] = temp;

				}

			}

		
		  
	  }
	

	  
	
	
	 
	  public static void main(String[] args) {
		
		  int []number={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
		  int []number1={1,2,3,4,5,6,7,8,9};
		
	
	  new NineCell().coreCode(number1, 0, 8);
	  System.out.println(222);
	}

	
	  
	 
	  
	  
	  
	  
}