csp.js

// A代表1，B代表2，C代表3，D代表4
domain = Array.from({length:10}).map(i => [1,2,3,4]);
value = [];
choice = [
    [1,2,3,4],
    [5,6,7,8],
    [4,9,8,2],
    [5,4,3,2],
    [1,2,3,4],
    ['nothing','c','c','d'],
    [3,2,1,0],
    [0,1,2,3],
    ['heshu','zhishu','<5','pingfangshu'],
    [1,2,3,4]
]
constraints = {};
firstAUpdate = (num) => {
    let ans = choice[0][num - 1];
    // 约束传播, 答案之前的题目都不能选A（值域去掉A），该题值域为A取交集
    for(let i = 0;i < ans - 1;i++) {
        domain[i] = domain[i].filter(i => i !== 1);
    }
    domain[ans - 1] = domain[ans - 1].filter(i => i === 1);
}
sameIndexUpdate = (num) => {
    let ans = choice[1][num - 1];
    // 全局约束
    constraints.sameIndex = ans;
}
sameAnswerWithTwoUpdate = (num) => {
    let ans = choice[2][num - 1];
    // 约束传播， 答案对应的该题值域为该题选项（取交集），题目中的其他题目不能取该题选项
    domain[ans - 1] = domain[ans - 1].filter(i => i === num);
    const twoValue = domain[2][0];
    for(i = 0;i < 4;i++){
        let t = choice[2][i] - 1;
        if(t != ans - 1){
            domain[t] = domain[t].filter(i => i !== twoValue);
        }
    }
}
aNumBerUpdate = (num) => {
    let ans = choice[3][num - 1];
    // 约束传播，注意到A的数量和非A的数量和为10，同时影响8，9两题的值域（元音的数量即为A的数量），这里稍微有点暴力
    // 更好的方法可以是 domain[8] = domain[8].filter(x => IsXNum(10-x)); 
    domain[7] = domain[7].filter(i => choice[7][i-1] === ans);
    if(ans === 5) domain[8] = domain[8].filter(x => x === 2);
    if(ans === 4) domain[8] = domain[8].filter(x => x === 1);
    if(ans === 3) domain[8] = domain[8].filter(x => x === 2);
    if(ans === 2) domain[8] = domain[8].filter(x => x === 1);
    // 全局约束
    constraints.aNumber = ans;
}
sameAnswerWithFourUpdate = (num) => {
    let ans = choice[4][num - 1];
    // 约束传播， 答案对应的该题值域为该题选项（取交集），题目中的其他题目不能取该题选项
    domain[ans - 1] = domain[ans - 1].filter(i => i === num);
    const fourValue = domain[4][0];
    for(i = 0;i < 4;i++){
        let t = choice[4][i] - 1;
        if(t != ans - 1){
            domain[t] = domain[t].filter(i => i !== fourValue);
        }
    }
}
aNumberSameWithUpdate = (num) => {
    let ans = choice[5][num - 1];
    // 全局约束
    constraints.aNumberSameW = ans;
}
sevenDiffUpdate = (num) => {
    let ans = choice[6][num - 1];
    // 约束传播，下一题和本题的差固定
    let proAns = [];
    if(num - ans >= 1) proAns.push(num - ans);
    if(num + ans <= 4) proAns.push(num + ans);
    domain[7] = domain[7].filter(x => proAns.includes(x));
}
aNumBerUpdate2 = (num) => {
    let ans = choice[7][num - 1];
    // 约束传播，注意到A的数量和非A的数量和为10，同时影响3，9两题的值域（元音的数量即为A的数量），这里稍微有点暴力
    domain[3] = domain[3].filter(i => choice[3][i-1] === ans);
    if(ans === 0) domain[8] = domain[8].filter(x => x === 1);
    if(ans === 1) domain[8] = domain[8].filter(x => x === 1 || x === 4);
    if(ans === 2) domain[8] = domain[8].filter(x => x === 1);
    if(ans === 3) domain[8] = domain[8].filter(x => x === 2);
    constraints.aNumber = ans;
}
fuYinNumUpdate = (num) => {
    let ans = choice[8][num - 1];
    // 约束传播，注意到A的数量和非A的数量和为10
    if(ans === 'heshu') {
        domain[7] = domain[7].filter(x => x !== 4);
        domain[3] = domain[3].filter(x => x === 2 || x === 4);
    }
    if(ans === 'zhishu'){
        domain[7] = domain[7].filter(x => x === 4);
        domain[3] = domain[3].filter(x => x === 1 || x === 3);
    }
    if(ans === '<5'){
        domain[7] = [];
        domain[3] = [];
    }
    if(ans === 'pingfangshu'){
        domain[7] = domain[7].filter(x => x == 2);
        domain[3] = [];
    }
}
zero = () => {}
// 当某个值域被我们改变时，所执行的约束传播函数
UpdatFunc = [
    firstAUpdate,
    sameIndexUpdate,
    sameAnswerWithTwoUpdate,
    aNumBerUpdate,
    sameAnswerWithFourUpdate,
    aNumberSameWithUpdate,
    sevenDiffUpdate,
    aNumBerUpdate2,
    fuYinNumUpdate,
    zero
]
checkDomain = () => {
    for(i = 0;i < 10;i++) {
        if(domain[i].length === 0) return false;
    }
    return true;
}
checkConstraint = () => {
    if(constraints.sameIndex) {
        for(i = 0;i < 9;i++) {
            if(domain[i].length === 1 && domain[i+1].length === 1 && domain[i][0] === domain[i+1][0]) {
                if(i !== constraints.sameIndex - 1) return false;
            }
            if(i === constraints.sameIndex - 1) {
                if(domain[i].length === 1 && domain[i+1].length === 1 && domain[i][0] !== domain[i+1][0]) return false;
            }
        }
    }
    if(constraints.aNumber) {
        let haveA = 0;
        for(i = 0;i < 10;i++) {
            if(domain[i].length === 1 && domain[i][0] === 1) haveA++;
        }
        if(haveA > constraints.aNumber) return false;
        if(isFinal && haveA !== constraints.aNumber)  return false;
    }
    if(constraints.aNumberSameW) {
        if(isFinal) {
            let have = {a:0,b:0,c:0,d:0}
            for(i = 0;i < 10;i++) {
                if(domain[i][0] === 1) have.a++;
                if(domain[i][0] === 2) have.b++;
                if(domain[i][0] === 3) have.c++;
                if(domain[i][0] === 4) have.d++;
            }        
            if(constraints.aNumberSameW === 'nothing') {
                if(have.a === have.b || have.a === have.c || have.a === have.d) return false;
            }
            else {
                if(have.a !== have[constraints.aNumberSameW]) return false;
            }
        }
    }
    return true;
}
checkIsFinal = () => {
    for(i = 0;i < 10;i++){
        if(domain[i].length !== 1) return false;
    }
    return true;
}

isFinal = false;

// searchWeight = [3,1,3,3,3,0,3,3,3,0];这个权重可以降低搜索次数到27
searchWeight = [0,0,0,0,0,0,0,0,0,0];

findNextSearch = () => {
    let n_i = 0;
    let max_w = 0;
    let min_l = 5;
    for(let i = 0;i < 10;i++) {
        if(!searchList.includes(i)) {
            if(domain[i].length === 1) return i;
            if(searchWeight[i] > max_w || (searchWeight[i] === max_w && domain[i].length < min_l)) {
                n_i = i;
                max_w = searchWeight[i];
                min_l = domain[i].length;
            }
        }
    }
    return n_i;
}

searchList = [];

printAnswer = () => {
    const anslist = ['A','B','C','D'];
    const a = domain.reduce((x,y) => x + ' '+ anslist[y-1],'');
    console.log(a);
}

searchNum = 0;

searchFunc = (index) => {
    isFinal = false;
    // 保存当前值域和约束
    let old_domain = Array.from({length:10}).map((item,i) => [...domain[i]]);
    let old_constraints = {...constraints};
    let now_domain = [...domain[index]];
    for (i of now_domain) {
        // 搜索当前节点
        searchList.push(index);
        searchNum++;
        domain[index] = [i];
        // 改变当前节点后，做一次因为当前节点产生的约束传播，更新值域以及一些全局约束
        UpdatFunc[index](i);
        isFinal = checkIsFinal();
        if(checkDomain() && checkConstraint()) {
            if( isFinal ) {
                console.log('搜到答案的次数', searchNum);
                printAnswer();
            }
            else {
                // 
                let x = findNextSearch();
                searchFunc(x);
            }
        }
        // 递归回溯
        searchList.pop(index);
        domain = Array.from({length:10}).map((item,i) => [...old_domain[i]]);
        constraints = {...old_constraints};
    }
}

searchFunc(0);
console.log('最终搜索的次数', searchNum);