Algorithmus für die Überprüfung der Diagonale in N Königinnen Algorithmus

Question

Ich versuche, N-Queens Problem in Python zu implementieren. Ich brauche eine kleine Hilfe beim Entwerfen des Algorithmus, um zu überprüfen, ob bei einer Position von Königin überprüft wird, ob eine andere Dame auf dem Spielbrett auf seiner Diagonale vorhanden ist oder nicht.

Ich versuche, eine Funktion diagonal_check(board, row, col) zu entwerfen, wo Board ist N * N-Matrix von Arrays, wo "1" Anwesenheit von Königin und "0" Abwesenheit darstellt. Ich werde Array und Position von Königin (row, col) an die Funktion übergeben. Meine Funktion muss false zurückgeben, wenn eine andere Dame auf ihrer Diagonale vorhanden ist oder sonst wahr ist.

Wenn mir jemand mit Algorithmus für diagonal_check Funktion helfen könnte. Ich suche keinen bestimmten Sprachcode.

Answer 1

Lassen Sie die obere linke Ecke (0,0)

den Abwärts rechts für ein Quadrat (Row, Col) orientiert ist diagonal col-row+7

Der Aufwärts rechts für ein Quadrat (row diagonal orientierte (col) ist row+col

Überprüfen Sie einfach, ob 2 Königinnen die gleichen haben col-row+7 oder row+col sollte Ihnen sagen, ob 2 Königinnen auf der gleichen Diagonale sind. Wenn Sie immer noch etwas verwirrt sind, suchen Sie in Google nach einem Schachbrettbild.

Answer 2

boolean diagonalCheck(board, row, col) { 

    int tempRow ; 
    int tempCol ; 

    //algorithm to check left diagonal 
    if (row >= col) { 
     tempRow = row-col; 
     tempCol = 0; 
    } else { 
     tempRow = 0; 
     tempCol = col-row; 
    } 

    while (tempRow != N-1 && tempCol != N-1) { 
     if (tempRow == row && tempCol ==col){ 
      //no need to check 
     } else if(queen(tempRow,tempCol) == 1) { 
      return true; 
     } 
     tempRow++; 
     tempCol++; 
    } 

    //algorithm to check right diagonal 
    if (row + col >= N-1) { 
     tempCol = N-1; 
     tempRow = (row + col) -(N-1) 
    } else { 
     tempRow = 0; 
     tempCol = row + col; 
    } 


    while (tempRow != N-1 && tempCol != 0) { 
     if (tempRow == row && tempCol ==col) { 
      //no need to check 
     } else if(queen(tempRow,tempCol) == 1) { 
      return true; 
     } 
     tempRow++; 
     tempCol--; 
    } 
    return false; 
}