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.
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:
xNext
& yNext
, respectivelyarr[y + 1][x + 1]
-> arr[yNext][xNext]
and look there if it's a queeny (isQeen()
)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.)x
and y
coordinates.This is all that's in the snippet above.