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.

CodePudding user response：

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:

• let's have x and y as the starting coordinates
• let's choose the easiest diagonal: down and right (easiest, because that's just a 1 for x and y). Let's call them xNext & yNext, respectively
• how do you check if there's a queen one step away? Simple: arr[y 1][x 1] -> arr[yNext][xNext] and look there if it's a queeny (isQeen())
• how do you check if there's a queen two steps away? Simple: arr[y 2][x 2] -> arr[yNext 1][xNext 1] It looks the same as in the beginning, only the x and y changed to xNext and yNext... hmmm... can this pattern be used? Of course! Create a recursive function that automatically change xNext & yNext based on a rule of adding 1 to them AND check isQueen; then repeat. When should it stop? On the "edge of the chessboard" (if the arr[yNext][xNext] is undefined, the algorithm reached the end of the chessboard.)
• how to generalize this, so we can use it for the different diagonals? The other diagonals are nothing else (to this function) only a different set of changes in the x and y coordinates.

This is all that's in the snippet above.

CodePudding user response：

You identified the challenges correctly. Your current code only works on the big diagonal, and only counts the amount of queens there.

You need to split the problem down to smaller challenges. Writing a few helper functions would make it possible to tackle some of the bigger challenges.

A function that checks if there are any queens to the right of the current element position, so a helper function like this

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

Writing a function like this should be a smaller challenge and thus easier to accomplish

Then another helper function would be

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

And same for the other diagonal direction, another helper function would be

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

Does this help? Are these helper functions something that you can implement? Let me know in the comments.