JavaでBASE+BALL=GAMESの覆面算を縦型探索で解くプログラムを完成させたい

Question

Nodeクラスのexpandの部分がなにを書いていいのか全くわかりません。。。
他の部分はかけたので、expandの部分をなにを書けばいいのかコードを教えていただきたいです。
下にコードを添付するので、//の部分を教えていただきたいです。

import java.util.*;

class Node {
int [] s = new int [7];
int p;

Node(int p) { this.p = p; }

boolean goalp () {
    if ((s[0] == 0) || (s[5] == 0)) return false;
    int base  =  1000 * s[0] + 100 * s[1] + 10 * s[2] + s[3];
    int ball  =  1000 * s[0] + 100 * s[1] + 10 * s[4] + s[4];
    int games =  10000 * s[5] + 1000 * s[1]  + 100 * s[6] + 10 * s[3] + s[2];
    if (games == base + ball) return true;
    return false;
}

ArrayList<Node> expand() {
    ArrayList<Node> al = new ArrayList<Node>();

    // ここがわからない

    return al;
 }

void show() {
    System.out.println("B = " + s[0] + ", A = " + s[1] + ", S = " + s[2] + 
          ", E = " + s[3] + ", L = " + s[4] + ", G = " + s[5] + ", M = " + s[6]);
}

}

class Fukumen {
public static void main(String [] args) {
Stack<Node> st = new Stack<Node>();
st.push(new Node(0));
while(! st.isEmpty()) {
Node a = st.pop();
ArrayList<Node> en = a.expand();
for(int i = 0;i < en.size();i++) {
Node b = en.get(i);
if (b.p == b.s.length) {
if (b.goalp()) {
b.show(); // return;
}
} else {
st.push(b);
}
}
}
}
}

Comments

[xebme]

プログラムを組まずに解いていませんが、B≠0,G≠0は制約としますか。

[xebme]

しつれいしました。B≠0,G≠0はコードに含まれていますね。
(やることは順列10P7を作ることですが、b.p == b.s.lengthを調べる必要があるのかと思います。)
Stackを使い、expand()でsに含まれない数字を末尾に追加してArrayListの要素を増やすやりかたですね。

Answer 1

ヒント

ArrayListに追加される(複数の)Nodeは次のコンストラクターを使って生成します。Nodeの中身をコピーして、 sの末尾にsで使われていない数字を1つだけ追加します。

	Node(Node that, int x) {
		s = that.s.clone();
		p = that.p;
		s[p++]=x;
	}

expand()のなかで配列sで使われていない数字を調べなければなりません。

解説

覆面算に使用する数字は7種類。expand()を使って0から9までの10個の数字から7個をとり並べる。
expand()1回分のルールは

• 配列sに含まれない数字を1つだけ末尾に追加したNodeを作成する
• 配列sに含まれない数字はもれなく使 って複数のNodeを作成する
• 作成したNodeはArrayListに追加する

配列sの初期値は空[]。expand()を実行すると0-9までの数字を末尾に追加した10個のNodeが作られる。

[0],[1],...,[9]

これらのNodeのれぞれにexpand()が適用される。例えばsが[0]のときexpand()するとNodeは9個に増える。

[01],[02],[03],[04],...,[09]

[1]-[9]もそれぞれ9個に増える。以下同様。Nodeの数が増えてゆきます。expand()を7回実行すると求める順列が完成します。

Javaコード(追記)

import java.util.ArrayList;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
class Node {
  int[] s = new int[7];
  int p;
  Node(int p) {
    this.p = p;
  }
  protected Node(Node that, int x) {
    this.s = that.s.clone();
    this.p = that.p;
    this.s[p++] = x;
  }
  boolean goalp() {
    // if ((s[0] == 0) || (s[5] == 0)) return false;
    int base = 1000 * s[0] + 100 * s[1] + 10 * s[2] + s[3];
    int ball = 1000 * s[0] + 100 * s[1] + 10 * s[4] + s[4];
    int games = 10000 * s[5] + 1000 * s[1] + 100 * s[6] + 10 * s[3] + s[2];
    return (games == base + ball);
  }
  ArrayList<Node> expand() {
    ArrayList<Node> al = new ArrayList<>();
    // ここがわからない
    boolean[] b = new boolean[10]; // 数字: 0 - 9 の除外対象
    for (int i=0; i < p; ++i) {
      b[s[i]] = true; // 既に数字s[i]が存在する。
    }
    if (p == 0 || p == 5) b[0] = true; // B != 0, G != 0
    for (int i=0; i < b.length; ++i) { // 残りの数字を全て使う
      if (!b[i]) al.add(new Node(this,i));
    }
    return al;
  }
  //B = 7, A = 4, S = 8, E = 3, L = 5, G = 1, M = 9
  void show() { 
    System.out.println("B = " + s[0] + ", A = " + s[1] + ", S = " + s[2] + ", E = " + s[3] + ", L = " + s[4] + ", G = "
        + s[5] + ", M = " + s[6]);
  }
//  ArrayList<Node> expand() {
//    Set<Integer> set = IntStream.of(s).limit(p).mapToObj(Integer::valueOf).collect(Collectors.toSet());
//    return IntStream.range((p == 0 || p == 5) ? 1 : 0, 10).filter(x -> !set.contains(x)).mapToObj(x -> new Node(this, x)).collect(Collectors.toCollection(ArrayList::new));
//  }
}

Comments

[xebme]

なぜStackを使うのかがわかりませんでした
ArrayListは幅優先ですが、Stackを使って深さ優先にするため( タイトルは縦型探索と言っています)
幅優先ならStackの代わりにQueueを使うと思います
また、深さ優先ならまず再帰を試すでしょうね

[xebme]

expand()で、B≠0,G≠0制約をかければ、順列の生成を節約できます。

[mt0503xx]

めちゃめちゃ参考になって助かりました！！
本当にありがとうございます！