javascript - Processing of two-dimensional arrays, somewhat similar to Solitaire

Question

var arr = [["A", "B"], ["C", "D"], ["E", "F"], ["G", "H"], ["C", "A"],["C","Q"] ["F", "D"], ["E", "G"],["H", "A"]];
var point = "A";//根据arr二维数组进行接龙，point这个是接龙的起点和终点
//要求输出:output_arr=[["A", "C"],["C", "D"],["D", "F"],["F", "E"],["E", "G"],["G", "H"],["H", "A"]]
//如上，起点和终点都为"A"
//用不到的元素舍弃了：["A", "B"]中"A"以后的"B"再接不下去，所以没用，同理["C","Q"]中的"Q"也接不下去，也不用了
//注意顺序:["C", "A"]，因为从"A"开始，所以这个元素变为["A","C"]

I am not engaged in this field of work. I write programs myself. When I encounter the above problem, it has been bothering me for several days. Please help me.

Answer 1

Provide a single solution idea.

First find the array whose first element is A, take it out and name it the candidate array

Then select one of the candidate arrays, and then define a current array and a result array to store the current head and tail sum results, such as [A,B] and [[A,B], [B,C]], Of course, the current array does not need to be used. Here is a convenient explanation.

Then loop arr until you know the array whose first letter is A, such as [B,C]. This result array can be collapsed into [A,C]. Then of course you need to save [B, C] into the result array, and delete [B, C] from arr.

Then if the current array is folded to length 0 after grouping, it means that a dragon has been found, and the result can be output.

But if it cannot be found, it means that [B, C] has no solution, then the result array and the current array will be returned to the previous stage, and [B, C] will no longer be added to arr, because It can't be one of the answers. Then keep repeating this process.

The description of the image point is that we find that [A, B, B, C, C, D] cannot find the result, fall back to [A, B, B, C], and then cannot find it, then continue to fall back to [ A,B]. And so on.

Find out until the end.

If there are multiple interpretations, it is exactly the same solution. Too troublesome.

Answer 2

This is an exhaustive exercise...
The idea I can think of is to select two ends and exhaustively search towards the middle.
Record each pair of possibilities (note that they are locked and cannot be selected repeatedly), and the end of the possibilities can be If you can catch it, it’s ok.
Since the length of the results is uncertain, and the order is also uncertain, this is much more complicated...

Answer 3

It took me some time to write a recursion and used a pruning logic. If a letter only appears once, then the corresponding letter pair will be removed from the original data.

let map = {};   // 计算字母出现次数使用
let result = [];

// 计算字母出现次数
arr.forEach(item => {
    map[item[0]] ? map[item[0]]++ : (map[item[0]] = 1);
    map[item[1]] ? map[item[1]]++ : (map[item[1]] = 1);
});

// 淘汰包含出现小于1字母的数组, 避免无用递归
arr = arr.filter(item => {
    return (map[item[0]] > 1 && map[item[1]] > 1);
});

let dfs = (_point, _arr) => {
    for(let i = _arr.length; i--; ) {
        let item = _arr[i];
        if(item[0] === _point || item[1] === _point) {

            if(result.length === 0 && item[1] === _point) {
                [item[0], item[1]] = [item[1], item[0]];
            }

            let tempArr = Object.assign(_arr);  // 复制一个数组副本，方便回溯
            tempArr.splice(i, 1);   // 从临时数组中删去当前组，进一步递归

            if(item[1] === point || dfs(item[1], tempArr)) {
                // 如果找到答案，一层层往上返回
                // 不带下划线的point是全局的目标point
                result.unshift(item);
                return true;
            }
        }
    }
    return false;
};

if(dfs(point, arr)){
    console.log(result);
} else {
    console.log('no result');
}