Dado que solo necesita una ruta, se necesitaría demasiada memoria para generarlas todas. En cambio, considere que se sabe cuántos "movimientos" serán verticales, ya que solo pueden subir. Si hay n filas en la matriz, habrá n-1 movimientos hacia arriba.

Estos movimientos hacia arriba pueden ocurrir en cualquier columna, independientemente de la fila. Entonces, la aleatoriedad radica en la selección de la columna donde ocurrirá el movimiento ascendente. Si tenemos n números, cada uno de los cuales representa una columna, entonces hemos definido un camino de forma única. Se puede construir a partir de esa información.

Aquí hay una implementación, donde el punto de inicio siempre está en la fila inferior, en una coordenada X determinada, y el punto final siempre está en la fila superior, en una coordenada X determinada:

 function randint(range) { return Math.floor(Math.random() * range); } function randomPath(sizeX, sizeY, startX, endX) { let x = startX; let path = []; for (let y = sizeY - 1; y >= 0; y--) { let upX = y ? randint(sizeX) : endX; while (x != upX) { path.push([x, y]); if (x < upX) x++; else x--; } path.push([x, y]); } // Remove U-turns for (let i = path.length - 4; i >= 0; i--) { if (i+3 < path.length && path[i][1] === path[i+3][1] + 1 && path[i][0] === path[i+3][0]) { path.splice(i+1, 2); // Remove U } } return path; } function displayPath(sizeX, sizeY, path) { let grid = Array.from({length: sizeY}, () => Array(sizeX).fill(".")); for (let [x, y] of path) { grid[y][x] = "X"; } console.log(grid.map(row => row.join(" ")).join("\n")); } // Let's do this for a 7x7 matrix: let sizeX = 7, sizeY = 7; let path = randomPath(sizeX, sizeY, 2, 4); // Start at X=2 at bottom, end at X=4 at top console.log(JSON.stringify(path)); displayPath(sizeX, sizeY, path);

Cuando la primera parte del código genera un giro en U, será una secuencia de izquierda arriba derecha o derecha arriba izquierda. Entonces, por ejemplo: [3,0],[2,0],[2,1],[3,1] es un giro en U. Se puede ver que el primer y el último punto están separados por 1 unidad y. Estos puntos tienen otros 2 puntos entre ellos, por lo que en el camino tienen una distancia de 3.

La segunda parte del código buscará casos donde los puntos que están separados por 3 pasos en la ruta, tienen la misma coordenada X y 1 unidad de diferencia en la coordenada Y. Si se encuentra tal instancia, los dos puntos entre ellos (que representan el giro) se eliminan del camino.

ADVERTENCIA : esta respuesta puede no ser 100% precisa o completa

Utilice esto como referencia para construir y refinar aún más para obtener la solución adecuada para la pregunta.

 const n = 3; const getAllPaths = ({sr, sc, tr, tc, idx, arr, obj}) => { //console.log('sr, sc: ', sr, sc, '\narr: ', arr); if (sr > tr || sc > tc) return false; if (sr === tr && sc === tc) { return ({ obj: { ...obj, [idx + 1]: [...arr] }, idx: idx + 1 }) }; const rowRes = getAllPaths({ sr: sr + 1, sc, tr, tc, idx, arr: arr.concat([[sr+1, sc]]), obj: {...obj} }); //console.log('rowRes: ', rowRes); const colRes = getAllPaths({ sr, sc: sc + 1, tr, tc, arr: arr.concat([[sr, sc+1]]), idx: rowRes ? rowRes.idx : idx, obj: rowRes ? {...rowRes.obj} : {...obj} }); //console.log('colRes: ', colRes); return colRes ? {...colRes} : {idx, obj: {...obj}} }; const getAllPathsSrcDest = (rows = n, cols = n) => getAllPaths( {sr: 0, sc: 0, tr: rows - 1, tc: cols - 1, idx: -1, arr: [[0,0]], obj: {}} ); const allPaths = getAllPathsSrcDest()?.obj; const renderNicely = obj => Object .entries(obj || {}) .map( ([k,v]) => (`path num: ${+k+1} path: ${v.join(' - ')}`) ); console.log(renderNicely(allPaths)); const userInput = prompt('Enter matrix size 3, 4, 5, etc: '); console.log('userInput: ', userInput); console.log( renderNicely( getAllPathsSrcDest(userInput, userInput)?.obj ) );

Explicación

• Use un enfoque similar al que se muestra en la pregunta de OP
• En lugar de simplemente contar cada sentido, rastrea el camino exacto
• Las variables idx , arr y obj se utilizan para identificar y capturar rutas válidas.

Problemas conocidos

• La lista de rutas no está completa. Hay caminos que faltan.
• No hay una -ización random , por lo que se devuelve exactamente la misma lista de rutas
• Puede explorar opciones para memo la solución y asignar al random el valor que se devuelve en cada llamada