Javascript: Stuck on diagonal validation of two queens and if they can attack each other

Question: What is the total number of positions that two queens can exist on a chess board where they cannot attack each other?

Approach: My logic in this is to create variables of two queens which provides the coordinates of where they exist on the chess board. From there, move one queen (white queen) through every open position on the board and in each new position loop through the validation on whether or not the other queen (black queen) can attack it by using first confirming if they're on the same column or row. Then for the diagonal attack starting with diagonally down and to the right, use attack coordinate variables (the vx and vy values) to move down and to the right each time it checks to see if as it diagonally moves, if the black queen ends up with the same coordinates as the white queen before it runs off the board. The variables vx and vy are purposely set to a -1 after each validation path to be "off the board" so it doesn't accidently trigger a validation based on the number it left off at when the loop is completed.

Where The Problem Is: The code works all the way up until the else if line for the //validates diagonal down/right attack section (line 39+). It doesn't seem to matter what I put in there as the true statement, the result freezes the application and forces me to use the break command to get out of it. If I comment out the diagonal attack section, the program (as is) will run and return a value of 49. I'm trying to get to the answer of 42. The difference of 7 being the diagonal down/right attack pattern when the black queen is in the top left (0,0) position.

Once Solved: I know arrays would be easier, but at this point, I know there is change that would unblock this and if someone could show me what I'm missing, then the other three diagonal attack patterns is a matter of copy/paste the diagonal attack section and then change the + and - signs of the variables to change the diagonal movement of the attacking queen. From there would add in the while loop of the black queens movement across the board and down every time the white queen has iterated through the board on the black queen's new coordinates.

Your help would be greatly appreciated. Thank you so much for your time!

<!DOCTYPE html>
<html>
<body>

<h2>Answer To Two Queens Question</h2>    

<p id="demo"></p>

<script>
//total number of positions the two queens cannot attack each other
var n = 0;

//white queen
var x1 = 0;
var y1 = 0;

//black queen
var x2 = 0;
var y2 = 0;

//validation attack path
var vx = -1;
var vy = -1;

//moves white queen down one row after iterating through all available options
while (y1 <= 7) {

//moves white queen across an entire row
while (x1 <= 7) {
    //skips validation of attack patterns if queens are on the same square on the board (invalid scenario)
    if (x1==x2 && y1==y2){
        x1 = x1 + 1;
    //validates horizontal attack (left & right)
    } else if (x1 == x2) {
        x1 = x1 + 1;
    //validates vertical attack (up & down)
    } else if (y1 == y2){
        x1 = x1 + 1; 
    //validates diagonal down/right attack
    } else if (1 == 1) {
        //sets validation coordinates to be the same as the black queen
        vx = x2;
        vy = y2; 
        //iterates through diagonal down/right attack coordinates to see if it matches same coordinates of white queen
        while(vx <= 7 && vy <= 7){
            if (x2 + vx == x1 && y2 + vy == y1) {
                x1 = x1 + 1;
            } else {
                vx = vx + 1;
                vy = vy + 1;
            }
        }
        vx = -1;
        vy = -1;
    //if all validations fail, count towards total count where they cannot attack
    } else {
        n = n + 1;
        x1 = x1 + 1;
    }
}
y1 = y1 + 1;
x1 = 0;
}

document.getElementById("demo").innerHTML = "The number positions where two queens cannot attack each other is " + n;
</script>

</body>
</html>

Upvotes: 1

Answers (2)

Trentium

Reputation: 3719

For the fun of it, here's another take on the problem..

In this case, the standard means of using bitboards for chess programming is employed to represent the possible movement of the pieces. That is, a Uint64 number is used as a bit mask to represent the possible moves of a rook, bishop, or queen. Since there are 64 squares on the board, there is a need for 64 of these Uint64 bit masks, to represent the possible moves for the piece on each square.

To help visualize this, the script below prints out the rook, bishop, and queen bitboard for square 'd3' (which is the 19th of the 64 squares in the piece array).

Once the bit boards are built, the effort to determine whether two queens attack each other is trivial, as it is simply a matter of logically ANDing the first queen's movement bitboard with the bitboard representing the square that the second queen sits on, and if the result is 0, then they are not attacking each other.

As an aside, this method arrives at 2576 combinations of a pair of queens not attacking each other...

// Establish array with each bitboard representing the square on the board
// that the bitboard index represents.
let squares = new BigUint64Array( 64 ).map( ( v , i ) => 1n << BigInt( i ) );

// Generate possible moves for Rooks and Bishops for each square
// that they can occupy.
let rookMoves = new BigUint64Array( 64 );
let bishopMoves = new BigUint64Array( 64 );

for ( pieceRank = 0; pieceRank < 8; pieceRank++ ) {
  for ( pieceFile = 0; pieceFile < 8; pieceFile++ ) {
    let squareIndex = pieceRank * 8 + pieceFile;
    let rookMap = 0n;
    let bishopMap = 0n;
    for ( let r = 0; r < 8; r++ ) {
      for ( let f = 0; f < 8; f++ ) {
        let rf = r * 8 + f;
        if ( ( r === pieceRank || f === pieceFile ) && rf !== squareIndex ) {
          rookMap |= squares[ rf ];
        }
        if ( ( Math.abs( r - pieceRank ) === Math.abs( f - pieceFile ) ) && rf !== squareIndex ) {
          bishopMap |= squares[ rf ];
        }
      }
    }
    rookMoves[ squareIndex ] = rookMap;
    bishopMoves[ squareIndex ] = bishopMap;
  }
}  
 
// Generate the possible moves for Queens for each square that
// they can occupy.  This is done my looping through the Rook
// moves and simply ORing with the bishop moves.
let queenMoves = rookMoves.map( ( v, i ) => v | bishopMoves[ i ] );

// Helper function to print out the bitmap as a board, where 'X' 
// represents a bit that is set to 1 and '-' a bit that is set to '0'.
function printBitMap( bitBoard ) {
  let bm = '';
  for ( rank = 7; 0 <= rank; rank-- ) {
    for ( file = 0; file < 8; file++ ) {
      bm += bitBoard & squares[ rank * 8 + file ] ? ' X ' : ' - ';
    }
    bm += '\n';
  }
  return bm + '\n';
}

// Let's print the bitmaps for the rook, bishop, and queen at square d3,
// which is rank 2 ( range 0 - 7 ) file 3, or 2 * 8 + 3 which is square
// index 19.
console.log( 'Rook, Bishop, and Queen moves from square d3:' );
console.log( printBitMap( rookMoves[ 19 ] ) );
console.log( printBitMap( bishopMoves[ 19 ] ) );
console.log( printBitMap( queenMoves[ 19 ] ) );

// Now that the bitmaps are set up, the effort is simple... Loop through
// all combinations of two queens on the board...
let nonIntersectCount = 0;
for ( let Q1square = 0; Q1square < 64; Q1square++ ) {
  for ( let Q2square = 0; Q2square < 64; Q2square++ ) {
    // ...and if the queens are not on the same square and the intersection of
    // the possible moves for Q1 with the Q2 square is 0 bits, then we have
    // a situation where the queens are not attacking each other... 
    if ( Q1square !== Q2square && ( queenMoves[ Q1square ] & squares[ Q2square ] ) === 0n ) {
      nonIntersectCount++;
    }
  }
}

console.log( 'For every combination of 2 queens on a board, the number of combinations where they do not attack each other is:' );
console.log( nonIntersectCount );

Note also that BigUint64Array as of Jan 2021 has wide browser support, except for Safari. That being the case, and if Safari support is critical to the problem at hand, then one might want to consider reworking this solution using Uint32Array...

Upvotes: 0

GetSet

Reputation: 1577

In continuation from comments, this solution treats "position" as an integer between 0 and 63, where row and column can be derived from that using "arithmetic progression" logic. A row can be derived by the floor part on division by 8. A column can be derived from modulus on 8.

In this way only two loops are needed. A double loop is used so that each Queen1 (Q1) position is compared to Q2's position. Like your alg specifies, a condition is there to exclude when both Q1 and Q2 occupies the same square. The rest of the logic is explained in code comments.

On notable difference from your algorithm, is that this solution tries to solve for when an attack can be made. The return value must handle when positions can't be made, by deduction.

Disclaimer: This may not be the solution since OP doesn't know the correct return value beforehand. This is just a code attempt.

// What is the total number of positions that two queens can exist on a chess board where they cannot attack each other?
function answer() {

    var Q1;
    var Q2;
    var cnt = 0; // count of when they can attack each other
    
    for (Q1 = 0; Q1 < 64; Q1++) {
        //console.log(Q1);
        
        
        let Q1_y = Math.floor(Q1 / 8); // 0..7 ~ 0, 8..15 ~ 1, and so on
        let Q1_x = Q1 % 8;
        
        // console.log(Q1_x + ", " + Q1_y);
        
        for (Q2 = 0; Q2 < 64; Q2++) {
            
            let Q2_y = Math.floor(Q2 / 8); // 0..7 ~ 0, 8..15 ~ 1, and so on
            let Q2_x = Q2 % 8;
            
            if (Q1 != Q2) {
                // rule out both on same square
            
                let canAttack = false;
                // Now determine if on same X
                if (Q1_x == Q2_x) {
                    canAttack = true;
                }
                
                // Now determine if on same Y
                if (Q1_y == Q2_y) {
                    canAttack = true;
                }
                
                // Now determine if on same diagnoal
                let diag = (Math.abs(Q1_x - Q2_x) / Math.abs(Q1_y - Q2_y)) == 1;
                
                if (diag) {
                    canAttack = true;
                }
                
                // Update count for this square combo
                
                if (canAttack) {
                    cnt++;
                }
                
            }
            
        }
    }
    
    // console.log (cnt);
    
    return ((64 * 64) - 64) - cnt; // 64*64 total space pairs, minus the 64 times they are on same square, minus the number of times they *can* attack
    
    
    
}

console.log (answer());

Upvotes: 0

Javascript: Stuck on diagonal validation of two queens and if they can attack each other

Answers (2)

Related Questions