javascriptmatrix

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


I am supposed to solve 8 queens problem for college, and one of the steps I am trying to do right now is to solve how to get all queens right and diagonal up and down from the current element. Can anyone help me with that. What I have so far is this:

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) is empty, and kraljica (K) is queen. By the way This is how it should look:

[ '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' ]

Trying to do addition of all queens diagonally from the current or right from it. I tried diagonally, but soon figured I can only do those on the point where two meet, using this code:

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;
 };

But sadly this is only for diagonal again where both i and j match, I need this for the current element, and not the whole array as well.


Solution

  • Sorry, had to change to "Q" & "E" (the example is smaller), also added some queens, so all diagonals (starting from 3,3) hold at least one queen:

    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)

    The algorithm (thinking) in steps:

    This is all that's in the snippet above.