解决倒水小游戏的dfs方法。

WaterPouringPuzzleSolver.js

// gameinfo
// n, target, capacity, result
function perform(state, src, dst, info) {
    state[dst] += state[src]
    if (state[dst] > info.capacity[dst]) {
        state[src] = state[dst] - info.capacity[dst]
        state[dst] = info.capacity[dst]
    } else {
        state[src] = 0
    }
}

function check_same(a1, a2, n) {
    for (let i = 0; i < n; i++) {
        if (a1[i] !== a2[i]) return false
    }
    return true
}

// 返回给定列表里是否存在此状态。
function search_same(state, chain, n) {
    for (let c of chain) {
        if (check_same(state, c.state, n)) return true
    }
    return false
}

function find_target(state, info) {
    for (let i = 0; i < info.n; i++) {
        if (state[i] === info.target) return true
    }
    return false
}

// woker dfs. chain: [{state, route}]
function dfs(chain, info) {
    let current_state = chain[chain.length - 1].state;
    if (find_target(current_state, info)) {
        // 找到了合理的解。
        info.result.push(structuredClone(chain))
        // return// 是否愿意获取更长的解？如果是的话，注释这个return.
    }
    for (let src = 0; src < info.n; src++) {
        if (current_state[src] === 0) {
            // 容器里没有水，什么也倒不出来。
            continue
        } else {
            for (let dst = 0; dst < info.n; dst++) {
                // 如果接受方已满，或者接受方就是倒出方，则不倒。
                if (info.capacity[dst] === current_state[dst] || dst == src) {
                    continue;
                } else {
                    // 否则，可以倒。
                    let copy_state = structuredClone(current_state)
                    perform(copy_state, src, dst, info)
                    if (search_same(copy_state, chain, info.n)) {// 如果存在一样的状态，则不倒。
                        continue
                    } else {
                        // 之前没有过这个状态！这就很有意思了，说明我们发现了一个新的状态。
                        chain.push({ state: structuredClone(copy_state), route: [src, dst] })
                        dfs(chain, info)
                        chain.pop() // 把插入动作的pop出来，防止破坏记录
                    }
                }
            }
        }
    }
}

function solve(state, capacity, target) {
    let info = {
        n: state.length,
        target,
        capacity,
        result: []
    }

    dfs([{ state: state }], info)
    let result_str = ""
    info.result.sort((a, b) =>( (a.length > b.length) - 0.5))
    for (result_chain of info.result) {
        for (chain_item of result_chain) {
            if (chain_item.route) {
                result_str += `${chain_item.route[0]}->${chain_item.route[1]} `
            }
        }
        result_str += "\n"
    }
    console.log(result_str)
}

solve([5, 6, 0], [5, 6, 10], 8)