AOJ1122 What is the Number in my Mind ?

問題リンク What is the Number in my Mind ?

• 概要

L桁のヒットアンドブローゲームを行う。H個のヒントが与えられるので、正解の数列を求めよ。そのような数列が無かったり、2つ以上存在する場合は"NO"とせよ。
H個のヒントにはL桁の数列tryとそれに対するhit数、blow数がある。
4 <= L <= 10

• 解法

10桁までしかないので深さ優先探索で全探索します。ただ、並べ方が10!あり、ヒントの数の分だけ照合を行うとなると枝刈りがないと厳しいと思います。
そこで、H個のtryに対して、今組み立てている数列とのヒット数ブロー数をカウントしていきます。もし、ヒット数、ブロー数のいずれかが、ヒントにあるヒット数ブロー数を超えたら、その数列が解となる可能性は絶対にないとわかるので刈れます。そして、解が2個以上見つかったら探索を終了するようにすれば速く解けます。

• ソース

import java.util.Scanner;

//What is the Number in my Mind ?
public class AOJ1122 {

	char[][] t;
	int[] hit, blow;
	boolean[][] appear;
	int n, m;

	int[] temph, tempb;
	char[] s;
	
	boolean[] u;
	String ans;
	int c;
	
	void dfs(int k){
		if(c>1)return;
		if(k==n){
			boolean ok = true;
			for(int j=0;j<m;j++){
				if(temph[j]!=hit[j]||tempb[j]!=blow[j])ok = false;
			}
			if(!ok)return;
			c++;
			ans = new String(s);
			return;
		}
		for(int i=0;i<10;i++){
			if(u[i])continue;
			boolean ok = true;
			//各ヒントに対してhit数, blow数更新
			for(int j=0;j<m;j++){
				if(appear[j][i]){
					if(t[j][k]-'0'==i)temph[j]++;
					else tempb[j]++;
					if(hit[j]<temph[j]||blow[j]<tempb[j])ok = false;
				}
			}
			if(ok){
				u[i] = true;
				s[k] = (char)(i+'0');
				dfs(k+1);
				u[i] = false;
			}
			//hit, blowを更新前に戻す
			for(int j=0;j<m;j++){
				if(appear[j][i]){
					if(t[j][k]-'0'==i)temph[j]--;
					else tempb[j]--;
				}
			}
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			m = sc.nextInt();
			if((n|m)==0)break;
			t = new char[m][n];
			hit = new int[m];
			blow = new int[m];
			appear = new boolean[m][10];
			for(int i=0;i<m;i++){
				t[i] = sc.next().toCharArray();
				for(char ch:t[i]){
					appear[i][ch-'0'] = true;
				}
				hit[i] = sc.nextInt();
				blow[i] = sc.nextInt();
			}
			temph = new int[m];
			tempb = new int[m];
			ans = "NO";
			c = 0;
			u = new boolean[10];
			s = new char[n];
			dfs(0);
			System.out.println(c>1?"NO":ans);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1122().run();
	}
}