N-Vezir

Geri İzleme O(N!) O(N)

N×N tahtaya, hiçbiri birbirine saldırmayacak şekilde N vezir yerleştirir; çakışma çıktığı an yerleştirmeleri geri alır.

Tahta boyutu

1/229

6×6 tahtada 0. satırdan çözmeye başlanıyor.

DeğişmezTahtadaki her vezir diğerlerinden güvendedir. Kısmi bir tahta asla kuraldışı değil, yalnızca eksiktir.

deneniyoryerleştiçakışmageri izleme

n-queens.c

int safe(int board[], int row, int col) {
    for (int r = 0; r < row; r++) {
        if (board[r] == col) return 0;
        if (r - board[r] == row - col) return 0;
        if (r + board[r] == row + col) return 0;
    }
    return 1;
}
 
int solve(int board[], int row, int n) {
    if (row == n) return 1;   /* all queens placed */
    for (int col = 0; col < n; col++) {
        if (safe(board, row, col)) {
            board[row] = col;
            if (solve(board, row + 1, n)) return 1;
            board[row] = -1;   /* backtrack */
        }
    }
    return 0;
}

N-Vezir nasıl çalışır?

Vezirleri satır satır yerleştir. Sütun/köşegen çakışması çıkarsa son yerleştirmeyi geri al ve sonraki sütunu dene — her seferinde mahkûm bir alt ağacın tamamı budanır.

Ne zaman kullanılır?

Kısıt sağlama probleminin klasiği: ikili çakışmalı yerleştirme problemleri.