N queens, X by Y board keputusan pertanyaan wawancara masalah

Saya ditanya pertanyaan berikut dalam wawancara hari ini dan saya sudah memikirkannya sejak saat itu. Saya tidak dapat menjawabnya dan belum dapat menemukan solusi online.

Diberi papan catur dengan dimensi X oleh ratu Y dan N, tentukan apakah mungkin untuk mengatur ratu-ratu ini di papan sehingga mereka tidak dapat saling menyerang.

Papan 2 x 3 dengan 2 ratu memang memiliki solusi sehingga algoritma akan mengembalikan true:

Q . .
. . Q

Saya mencari pendekatan pemrograman untuk puzzle ini, bukan hanya cara untuk menyelesaikannya di atas kertas, misalnya.

Ini bukan (IMO) masalah yang sangat menarik dari sudut pandang pemrograman. Anda bisa membuat algoritma rekursif yang mencoba setiap pengaturan, seperti ini:

bool try_queens(Board board, int n)
{
    if (n == 0) {
        // no queens left to place, so we're done
        return true
    }
    // try each open position until we find one that works
    for each position on the board {
        if (is_empty(board, position) and not is_attacked(board, position)) {
            place_queen(board, position)
            if (try_queens(board, n-1)) {
                return true
            }
            remove_queen(board, position)
        }
    }
    // if we get this far, there's no available position
    return false
}

main()
{
    initialize board(X,Y)
    return try_queens(board, N)
}

Jika Anda sedikit memikirkan masalah ini, Anda akan menyadari bahwa tidak ada cara untuk menyesuaikan N queens di papan tulis di mana X <N atau Y <N karena itu akan mengharuskan setidaknya dua queens berakhir di peringkat atau file yang sama, dan karena itu mereka akan saling menyerang. Jika Anda membaca tentang masalah n-queens, Anda akan segera mengetahui bahwa selalu memungkinkan untuk menempatkan N queens pada papan NxN untuk N> 3. Sekarang kita tahu bahwa jawabannya adalah TIDAK untuk (X <N atau Y <N) dan YA untuk (X> = N dan Y> = N, N> 3). Yang tersisa hanyalah kasing khusus:

• N = 1 (YA)
• N = 2 (YA untuk X> = 2 dan Y> 2 atau sebaliknya)
• N = 3 (YA untuk X> = 3 dan Y> 3 atau sebaliknya)

Jadi sekarang fungsi rekursif kami yang bagus menjadi fungsi sederhana yang hanya membandingkan N ke X dan Y dan mengembalikan hasil kalengan. Itu bagus dari sudut pandang kinerja, karena Anda bisa mendapatkan jawaban dalam waktu yang konstan. Tidak terlalu bagus dari sudut pandang pemrograman karena Anda menyadari, pada titik ini, bahwa pertanyaannya sebenarnya lebih tentang seberapa baik Anda dapat memecahkan teka-teki daripada tentang kemampuan Anda untuk menulis fungsi rekursif.

(Dan bocah oh bocah, aku benar-benar berharap aku tidak membuat kesalahan bodoh dalam jawaban celana cerdasku; ;-)

Jika pewawancara meminta Anda untuk menulis kode untuk masalah tersebut, maka saya pikir itu tidak adil. Algoritma membutuhkan kerja. Namun, jika idenya adalah untuk menunjukkan kepada pewawancara tentang kelas, metode, atau beberapa konsep yang perlu Anda gunakan atau yang serupa, maka itu mungkin pertanyaan yang adil.

Masalahnya adalah masalah Ilmu Komputer klasik dan dibahas dalam banyak buku seperti itu. Penjelasan yang sangat baik, dengan animasi dan 12 solusi berbeda bersama dengan beberapa kode dapat ditemukan di sini:

http://en.wikipedia.org/wiki/Eight_queens_puzzle

Kode juga dapat ditemukan di sini: http://www.codeproject.com/KB/java/EightQueen.aspx

Jangan merasa buruk tentang ini, seperti yang saya katakan, itu tidak mudah.

Ini lebih dari sekadar komentar, tetapi tidak cocok di sana ...

Papan catur memiliki kotak 8x8, tidak lebih tidak kurang (pertanyaan-pertanyaan ini selalu mengganggu saya dengan pendekatan papan catur yang disesuaikan).

Tapi bagaimanapun, jika Anda memiliki papan catur x * y, dan n ratu dan menganggap bahwa ratu "mengambil" bidang ini

Anda bisa membuat array dua dimensi dan "menandai" semua bidang yang diserang oleh satu ratu. Kemudian tempat yang lain (dari tengah papan), tandai bidang yang tersisa, dan seterusnya ... sampai Anda menjalankan salah satu bidang atau ratu.

Ini tentu saja merupakan pendekatan yang sangat disederhanakan, karena jika diposisikan dengan cara yang buruk, saya mengumpulkan jumlah maksimum ratu akan bervariasi.

Hmm, baru saja menemukan ini - 8 masalah ratu.

Pada dasarnya, algoritma backtrack berfungsi seperti ini:

1. Buat array X oleh Y. Setel semua kotak menjadi kosong.

2. Atur jumlah ratu menjadi nol.

3. Atur posisi Anda saat ini menjadi (1,1)

4. Lihat apakah Anda dapat menempatkan ratu di posisi saat ini.

5. Jika Anda bisa, atur Array (X, Y) ke ratu, tambahkan ratu. Jika Anda menempatkan semua ratu, berhenti , Anda punya solusi.

6. Jika posisi saat ini tidak (X, Y), naikkan posisi saat ini dan lanjutkan ke langkah 4.

7. Temukan ratu di posisi terakhir (yang ada di urutan terakhir sesuai urutan kenaikan Anda). Atur posisi saat ini ke posisi ratu itu, hapus, dan kurangi jumlah ratu.

8. Jika jumlah ratu nol, berhenti , tidak ada solusi.

9. Tingkatkan posisi saat ini.

10. Lanjutkan ke langkah 4.

Menambah jawaban lain: membuat array dua dimensi hanya mempersulit kode.

Anda hanya perlu vektor ukuran 8 untuk papan catur biasa. Atau 8 + 1 jika suka posisi C 1 adalah 0, hanya untuk menyederhanakan kode, dan berurusan dengan 1-8 dan bukan 0-7.

Jika Anda berpikir tentang x menjadi posisi Anda dalam array, dan y menjadi konten posisi. misalnya papan [1] = 8 berarti ratu pertama berada di [1,8].

Dengan cara itu, Anda hanya perlu memeriksa validasi kolom.

Pada waktu di fakultas, saya menemukan buku yang sangat tua (60-an?), Tentang algoritma yang diterapkan di Dartmouth BASIC, yang mengimplementasikan masalah 8 ratu menggunakan memori yang lebih sedikit (karena setua itu, masuk akal).

Sejauh yang saya ingat, itu menggunakan ide vektor, dan pada dasarnya kasar memaksa semua posisi di papan dengan dua siklus FOR. Untuk memeriksa validitas posisi, ia menggunakan loop ketiga, siklus WHILE di setiap posisi kembali dalam vektor, dan memeriksa angka yang sama, atau untuk formula menggunakan operasi tangen untuk memeriksa diagonal.

Sayangnya, saya kehilangan jejak buku itu ...

Algoritma Said menemukan semua solusi untuk masalah n-queen.

Jika Anda hanya perlu menulis algoritma untuk menentukan apakah pengaturan seperti itu ada, maka lihat penelitian yang ada:
Eight queens puzzle di Wikipedia .

Anda dapat dengan sepele mengembalikan false jika N> min (X, Y).
Setelah membaca halaman itu, Anda tahu untuk mengembalikan true jika N <= min (X, Y) dan 2, 3! = Min (X, Y).

Yang tersisa 2, 3 == min (X, Y) dan N <= min (X, Y).

Nah, jika N <min (X, Y), mencari solusinya adalah sepele.
Jika N == min (X, Y), hanya ada solusi jika max (X, Y)> N.

f(X, Y, N)
    if X < Y => f(Y, X, N)
    if Y > N => false
    => (Y < N) or (Y != 2 and Y != 3) or (X > N)

Jelas tidak ada solusi jika N> min (X, Y). Kalau tidak, Anda dapat dengan mudah menunjukkan bahwa tidak ada solusi untuk N = X = Y = 2, N = X = Y = 3. Untuk semua kasus lain sepertinya ada solusi. Jumlah solusi tampaknya meningkat ketika N tumbuh.

Anda dapat menemukan solusi melalui pencarian lengkap dengan menelusuri kembali: Letakkan ratu di baris pertama, kolom 1. Letakkan ratu di baris kedua, di kolom pertama yang ratu di baris 1 tidak dapat dijangkau. Masukkan seorang ratu di baris kedua dll. Jika seorang ratu tidak dapat dimasukkan ke dalam baris k, maka Anda menghapusnya dan memindahkan ratu di baris k-1 di posisi kosong berikutnya.