アルゴリズム設計と分析:5-28虫食演算式問題

5-28虫食い演算式の問題
問題の説明
虫食い算式とは古書の算式の一部が虫食いになったことを指す.虫食い算式問題は,虫食い算式の残りの数字から,虫食いされた数字を論理的に推定することである.たとえば、
43?98650?45+8468?663344445506978 43 ? 98650 ? 45 + 8468 ? 6633 44445506978
その中で「?」虫食いを表す数字.この虫食い演算式により,1行目の2個の虫食い数はそれぞれ5と3,2行目の虫食い数は5と推定される.一般に,虫食い演算式の問題は,演算式のすべての数字が虫食いになったと仮定するが,虫食い演算式のどの数字が同じであるかを知っている.また,虫食い演算式はn進数加算式であることも知られている.虫食い演算式の3つの数はいずれもnビット数であり,先頭0を許容する.
与えられた虫食い演算式について、演算式中の虫食い数字をプログラミングして計算する.
データ入力:1行目に正の整数n(n<=26)が1つあり、与えられた虫食い演算式がn進数加算式であることを示す.その後の3行には,各行にn個の大文字英字からなる文字列が1個あり,それぞれ虫食い演算式の2個の加算数とその和を表す.同じ英字は同じ数字を表す.
Java

package Chapter5HuiSuFa;

import java.util.Scanner;

public class ChongShiSuanShi {

    private static class Node{
        int a,b,c;
        Node next;
    }

    private static int n;
    private static int[][] B;
    private static int[] x;
    private static Node[] cut;

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);

        while (true){
            n = input.nextInt();

            B = new int[n][3];
            x = new int[n];
            cut = new Node[n];


            for(int j=0; j<3; j++){
                String a = input.next();
                for(int i=0; i'A';
            }

            for(int i=0; i0);
        }
    }

    private static boolean backtrack(int i){
        if(i == n-1){
            if(oka()){
                for(int j=0; j" ");
                return true;
            }else
                return false;
        }else
            for(int j=i; jif(constrain(i) && backtrack(i+1))
                    return true;
                swap(x,i,j);
            }

        return false;
    }

    private static void swap(int[] x, int i, int j){
        int tmp = x[i];
        x[i] = x[j];
        x[j] = tmp;
    }

    private static boolean oka(){
        int carr = 0;
        for(int i=n-1; i>=0; i--){
            int sum = x[B[i][0]]+x[B[i][1]]+carr;
            if(sum%n != x[B[i][2]]) return false;
            carr = sum/n;
        }

        return true;
    }

    private static boolean constrain(int i){
        for(int j=0; j<=i; j++){
            if(vio(cut[j]))
                return false;
        }

        return true;
    }

    private static boolean vio(Node p){
        while (p != null){
            if((x[p.a]+x[p.b])%n != x[p.c] && (x[p.a]+x[p.b]+1)%n != x[p.c])
                return true;
            p = p.next;
        }

        return false;
    }

    private static void construct(){
        Node p;
        for(int i=0; inull;
        for(int i=0; iint maxi = B[i][0];
            for(int j=1; j<3; j++)
                if(maxi < B[i][j])
                    maxi = B[i][j];
            p = new Node();
            p.a = B[i][0];
            p.b = B[i][1];
            p.c = B[i][2];
            p.next = cut[maxi];
            cut[maxi] = p;
        }
    }
}

Input & Output

5
ABCED
BDACE
EBBAA
1 0 3 4 2 



7
BCEFDAG
CABGEDF
GDGFAGG
1 2 4 5 3 0 6 

Reference
王暁東「コンピュータアルゴリズム設計と分析」