문제 풀기(서로 다른 숫자를 사용해서 연산해 내기, 순열이용) in Java

어느날 우리애가 풀어보라면 들고 왔습니다. 선생님이 내줬다는 문제인데요....

과연 풀려면 어떻게 할까 생각해보다가, 오랜만에 PC로 풀어볼려고 마음먹었습니다.  정리하자면 아래와 같은 문제입니다.

문제) 1~9까지 서로 다른 숫자를 사용해 들어갈 숫자를 완성하세요.

   A B
X    C
--------
   D E
+ F G
--------
   H I

이중에 힌트로 B=7,I=3가 주어졌다고 합니다.
힌트 없이 풀어보도록 하겠습니다.

각각의 값은 중복이 되지 않으므로 순열이라고 보면됩니다.
방법은 A=1...9까지 선택하고 B=1....9 까지 선택하고... 이런식으로 I까지 선택한 후 이전에 선택된 값이라면 무시하고 식이 맞는지 확인하는 방법으로 구해보았습니다.
여러개의 루프를 사용하면서 안쪽에서 다시 루프를 사용하고 아래와 같은 코드에 의해 이미 선택된 값이라면 선택이 되지 않도록 합니다.

if(usedflag[b])continue;

여러개의 루프를 사용하는 방법:

package testProject;

public class Test3 {

 public static void main(String[] args) {
  
  test1();
  
 }
 

 private static void test1() {
  boolean usedflag[]={false,false,false,false,false,false,false,false,false,false};
  
  for(int a=1;a<=9;a++){
   usedflag[a]=true;
   for(int b=1;b<=9;b++){
    if(usedflag[b])continue;
    usedflag[b]=true;
    for(int c=1;c<=9;c++){
     if(usedflag[c])continue;
     usedflag[c]=true;
     for(int d=1;d<=9;d++){
      if(usedflag[d])continue;
      usedflag[d]=true;
      for(int e=1;e<=9;e++){
       if(usedflag[e])continue;
       usedflag[e]=true;
       for(int f=1;f<=9;f++){
        if(usedflag[f])continue;
        usedflag[f]=true;
        for(int g=1;g<=9;g++){
         if(usedflag[g])continue;
         usedflag[g]=true;
         for(int h=1;h<=9;h++){
          if(usedflag[h])continue;
          usedflag[h]=true;
          for(int i=1;i<=9;i++){
           if(usedflag[i])continue;
           usedflag[i]=true;
           if(((a*10+b)*c)==((d*10)+e)){
            if(((d*10)+e)+((f*10)+g)==(h*10)+i){
             System.out.println("a="+a+",b="+b+",c="+c+",d="+d+",e="+e+",f="+f+",g="+g+",h="+h+",i="+i);
            }
           }
           usedflag[i]=false;
          }
          usedflag[h]=false;
         }
         usedflag[g]=false;
        }
        usedflag[f]=false;
       }
       usedflag[e]=false;
      }
      usedflag[d]=false;
     }
     usedflag[c]=false;
    }
    usedflag[b]=false;
   }
   usedflag[a]=false;
  }
 }
 
 
}

결과:

a=1,b=7,c=4,d=6,e=8,f=2,g=5,h=9,i=3

위 방법대로 할경우 문제가 있습니다. 많은 변수를 사용하게 되면 굉장히 코드도 길어지고 그러다보면 실 수 할 수도 있게 됩니다.
그렇다면 코드의 중복되는 부분을 함수로 만들어서 호출해주는 방법을 고민하게 됩니다.

기본적으로 구현은 자기자신을 호출해주는 재귀부와 조건이 맞으면 더이상 재귀를 동작 안하게 하는 두 부분으로 구성됩니다.
재귀부:

  for(int i=1;i<=9;i++){
   test2(depth+1,usedflag,selected);
  }

더 이상 재귀를 동작 안하게 하는 부분:

  if(depth == 9) {

   return;
  }

재귀를 동작 안하게 하려면 얼마나 호출되었는지 관리가 필요합니다. 여기에서는 depth 변수를 이용하여 관리를 하고(자신을 호출시 depth+1 사용) 특정 조건에 맞으면 더 이상의 재귀 동작을 멈추게 합니다. (if(depth==XX) return 조건 사용)

아래는 구현한 내용입니다.

재귀 호출을 이용한 방법:

package testProject;

public class Test3 {

 public static void main(String[] args) {

  boolean usedflag[]={false,false,false,false,false,false,false,false,false,false};
  int selected[]={-1,-1,-1,-1,-1,-1,-1,-1,-1};
  test2(0, usedflag, selected);
  
 }
 
 private static void test2(int depth, boolean usedflag[], int selected[])
 {
  if(depth == 9) {
   if(((selected[0]*10+selected[1])*selected[2])==((selected[3]*10)+selected[4])){
    if(((selected[3]*10)+selected[4])+((selected[5]*10)+selected[6])==(selected[7]*10)+selected[8]){
     System.out.println("a="+selected[0]+",b="+selected[1]+",c="+selected[2]+",d="+selected[3]+",e="+selected[4]+",f="+selected[5]+",g="+selected[6]+",h="+selected[7]+",i="+selected[8]);
    }
   }
   return;
  }
  for(int i=1;i<=9;i++){
   if( usedflag[i] ) continue;
   usedflag[i]=true;
   selected[depth]=i;
   test2(depth+1,usedflag,selected);
   usedflag[i]=false;
  }
 }
 
}

순열에 대한 자세한 내용은 아래 링크를 확인해보세요.
http://swlock.blogspot.kr/2016/11/permutation-combination-algorithm_13.html