計算機プログラミングI

全ての組み合わせを試すプログラム

// 覆面算: SEND+MORE=MONEY となる S,E,N,D,M,O,R,Y を見つける
// プログラム中では文字S〜Yを整数の配列の0〜7番目の要素に対応させる
class Alphametics {
  // 組み合わせnが上の式を満たしているかを調べ、満たしていれば表示
  static void checkExpression(int[] n) {
    int S=n[0], E=n[1], N=n[2], D=n[3], M=n[4], O=n[5], R=n[6], Y=n[7];
    int SEND =          S*1000+E*100+N*10+D,
	MORE =          M*1000+O*100+R*10+E,
        MONEY = M*10000+O*1000+N*100+E*10+Y;
    if (S!=0 && M!=0		// 各最上位桁は非零
	&& SEND+MORE == MONEY)  // 式のチェック
      System.out.println(SEND+ "+" + MORE + "=" + MONEY);
  }

  // 組み合わせnumbersの0〜index-1要素にxが含まれているかを調べる
  static boolean used(int[] numbers, int index, int x) {
    // 0からindex-1桁目までの要素について調べる
    for (int i = 0; i < index; i=i+1)
      if (numbers[i] == x) // xはnumbersに含まれているのでtrueを返す
        return true;
    // 繰り返しが終了した場合、xはnumbersに含まれていなかったのでfalse
    return false;
  }

  // numbers[0]..numbers[index-1] に1桁の数の重複のない組み合わせが
  // があるとき、index桁目以降の数を決める
  static void combination(int[] numbers, int index) {
    if (index == numbers.length) // 全ての桁が決った場合
      checkExpression(numbers);  // その数が条件を満たしているかを調べる
    else {
      // 次の1桁(nextNumber)として 0 から 9 を全て試す
      for (int nextNumber = 0; nextNumber < 10; nextNumber=nextNumber+1) {
	// numbers[0]..numbers[index-1]にnextNumberが含まれているかを調べ
	if (!used(numbers,index,nextNumber)) { // 含まれていなければ
	  numbers[index] = nextNumber;   // index桁目にセットして
	  combination(numbers, index+1); // index+1桁目以降を決める
	}
      }
    }
  }

  public static void main(String[] args) {
    int[] numbers = new int[8]; // 8桁の数を覚える配列を作る
    combination(numbers,0);     // 最初の桁から決めてゆく
  }
}

Hidehiko Masuhara, November 2000