如何从矩阵中的当前元素右上（对角线）和右下（对角线）获取所有元素

Question

我应该解决大学的 8 个皇后问题，我现在正在尝试做的步骤之一是解决如何使所有皇后正确并从当前元素上下对角线。任何人都可以帮助我。我到目前为止是这样的：

const prazno = "P";
const kraljica = "K";

let arr = [
    [prazno,prazno,prazno,prazno,prazno,prazno,prazno,prazno],
    [prazno,prazno,prazno,prazno,prazno,prazno,prazno,prazno],
    [prazno,prazno,prazno,prazno,prazno,prazno,prazno,prazno],
    [prazno,prazno,prazno,kraljica,prazno,prazno,prazno,prazno],
    [kraljica,prazno,prazno,prazno,kraljica,prazno,prazno,prazno],
    [prazno,kraljica,prazno,prazno,prazno,kraljica,prazno,kraljica],
    [prazno,prazno,kraljica,prazno,prazno,prazno,kraljica,prazno],
    [prazno,prazno,prazno,prazno,prazno,prazno,prazno,prazno]];

arr.forEach(a=>{console.log(a)});

prazno(P)为空，kraljica(K)为皇后。顺便一提它应该是这样的：

[ 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P' ]
[ 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P' ]
[ 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P' ]
[ 'P', 'P', 'P', 'K', 'P', 'P', 'P', 'P' ]
[ 'K', 'P', 'P', 'P', 'K', 'P', 'P', 'P' ]
[ 'P', 'K', 'P', 'P', 'P', 'K', 'P', 'K' ]
[ 'P', 'P', 'K', 'P', 'P', 'P', 'K', 'P' ]
[ 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P' ]

正在尝试对当前或右侧的所有皇后进行对角相加。我试过对角线，但很快发现我只能在两个相遇的地方做那些，使用这个代码：

const dijagonalniZbir = arr => {
    let dijagonalniZbir = 0;
    for(let i = 0; i < arr.length; i++){
       for(let j = 0; j < arr[i].length; j++){
          if(i === j && arr[i][j]=='K'){
            dijagonalniZbir++;
          };
       };
    };
    return dijagonalniZbir;
 };

但遗憾的是，这仅适用于 i 和 j 都匹配的对角线，我需要它用于当前元素，而不是整个数组。

Answer 1

您正确识别了挑战。您当前的代码仅适用于大对角线，并且仅计算那里的皇后数量。

您需要将问题分解为更小的挑战。编写一些辅助函数可以解决一些更大的挑战。

检查当前元素位置右侧是否有皇后的函数，所以像这样的辅助函数

const emptyToRight = (row, col, arr) => {
   // logic to check the same row to the right
   // and return false if a queen is found
   // ...
   return true;
}

编写这样的函数应该是一个较小的挑战，因此更容易完成

那么另一个辅助函数是

const emptyToUpRight = (row, col, arr) => {
   // logic to check the positions to up and right
   // and return false if a queen is found
   // ...
   return true;
}

同样对于另一个对角线方向，另一个辅助函数是

const emptyToDownRight = (row, col, arr) => {
   // logic to check the positions to down and right
   // and return false if a queen is found
   // ...
   return true;
}

这有帮助吗？这些辅助函数是您可以实现的吗？在评论中让我知道。

Answer 2

抱歉，只好改成“Q”&“E”（例子小了），还加了一些皇后，所以所有对角线（从3,3开始）都至少有一个皇后：

const e = "E"; // Empty
const q = "Q"; // Queen

let arr = [
  [q, e, e, e, e, e, e, e],
  [e, e, e, e, e, e, e, e],
  [e, e, e, e, q, e, e, e],
  [e, e, e, q, e, e, e, e],
  [q, e, e, e, q, e, e, e],
  [e, q, e, e, e, q, e, q],
  [e, e, q, e, e, e, q, e],
  [e, e, e, e, e, e, e, e]
];

// utility to check if there's a queen
// on the coordinates
const isQueen = ({ x, y, arr }) => {
  return arr[y][x] === q
}

// extracted functions to calculate diagonals
const getNext = {
  'downRight': ({ x, y }) => [x + 1, y + 1],
  'upLeft': ({ x, y }) => [x - 1, y - 1],
  'upRight': ({ x, y }) => [x + 1, y - 1],
  'downLeft': ({ x, y }) => [x - 1, y + 1],
}

// recursive function to gather all coordinates
// of queens in one diagonal direction (actually,
// this would work with any direction - only
// the getNext[something] function sets the
// pattern)
const getDiagonal = (direction) => {
  return ({ x, y, arr }) => {
    let ret = []
    const [xNext, yNext] = getNext[direction]({ x, y })
    
    // checking if next x, y coordinates are "in" the array
    if (arr[xNext] == null || arr[yNext] == null) {
      // if not, then recursion stops, an empty
      // array is returned
      return ret
    } else {
      // if yes, then check if they hold a queen
      if (isQueen({ x: xNext, y: yNext, arr })) {
        // if there's a queen on the next cordinates
        // then push those coordinates to the return array
        ret = [...ret, [xNext, yNext]]
      }
      
      // recursion goes: call the function with xNext, yNext -
      // and the checking starts from "let ret = []" again,
      // only with different x and y coordinates
      return [...ret, ...getDiagonal(direction)({ x: xNext, y: yNext, arr })]
    } 
  }
}

// creating the actual functions from the general
// getDiagonal
const getAllDownRight = getDiagonal('downRight')
const getAllUpLeft = getDiagonal('upLeft')
const getAllDownLeft = getDiagonal('downLeft')
const getAllUpRight = getDiagonal('upRight')

// setting starting position
const current = { x: 3, y: 3 }

// running the functions to see the queens
const downRight = getAllDownRight({ ...current, arr })
const upLeft = getAllUpLeft({ ...current, arr })
const upRight = getAllUpRight({ ...current, arr })
const downLeft = getAllDownLeft({ ...current, arr })

// output
console.log(downRight)
console.log(upLeft)
console.log(upRight)
console.log(downLeft)

算法（思路）步骤：

让我们以 x 和 y 作为起始坐标
让我们选择最简单的对角线：向下和向右（最简单，因为那只是 x 和 y 的 +1）。我们分别称它们为xNext & yNext
你如何检查一步之遥是否有女王？很简单：arr[y + 1][x + 1] -> arr[yNext][xNext] 然后看看那里是否是一个 queeny (isQeen())
你如何检查两步之外是否有女王？简单： arr[y + 2][x + 2] -> arr[yNext + 1][xNext + 1] 看起来和开始的一样，只是 x 和 y 变成了 xNext 和 yNext。 .. 嗯... 这个模式可以用吗？当然！创建一个递归函数，根据向它们加 1 并检查 isQueen 的规则自动更改 xNext 和 yNext；然后重复。什么时候应该停止？在“棋盘的边缘”（如果arr[yNext][xNext]是undefined，则算法到达棋盘的末端。）
如何概括这一点，以便我们可以将其用于不同的对角线？其他对角线（对于此函数）只是 x 和 y 坐标中的一组不同变化。

这就是上面代码片段中的全部内容。

如何从矩阵中的当前元素右上（对角线）和右下（对角线）获取所有元素

How to get a all elements right, right up (diagonal) and right down(diagonal) from the current element in matrix

javascript

matrix