NQueens package

Ringkasan

Masalah N-Queens adalah tantangan klasik yang sering ditemui dalam wawancara pemrograman dan pengaturan akademik. Tantangannya adalah menempatkan N Queens di papan catur N × N sehingga tidak ada dua ratu yang saling mengancam. Ini berarti bahwa tidak ada dua ratu yang dapat berbagi baris, kolom, atau diagonal yang sama.

Pernyataan masalah

Diberi integer n, kembalikan semua solusi berbeda ke teka-teki N-Queens. Anda dapat mengembalikan jawaban dalam urutan apa pun.

Setiap solusi berisi konfigurasi papan yang berbeda dari penempatan N-Queens, di mana 'Q' menunjukkan seorang ratu dan '.' menunjukkan ruang kosong.

Contoh

Untuk n = 4, solusi yang mungkin adalah:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Pendekatan dan Algoritma

Algoritma backtracking

Pendekatan yang paling umum untuk menyelesaikan masalah N-Queens adalah menggunakan backtracking. Algoritma backtracking secara bertahap membangun kandidat untuk solusi dan meninggalkan kandidat segera setelah menentukan bahwa kandidat tidak mungkin mengarah pada solusi yang valid.

Tangga:

1. Initialize the Board : Mulailah dengan papan N × N yang kosong.
2. Place the Queen : Cobalah menempatkan ratu di baris pertama dan melanjutkan untuk menempatkan ratu berikutnya.
3. Check Validity : Untuk setiap penempatan ratu, periksa apakah itu bertentangan dengan ratu yang sudah ditempatkan.
4. Backtrack if Necessary : Jika menempatkan ratu mengarah ke tidak ada solusi, lepaskan ratu (backtrack) dan coba posisi berikutnya.
5. Store the Solution : Jika konfigurasi yang valid ditemukan (N Queens ditempatkan), simpan konfigurasi papan.
6. Repeat : Lanjutkan proses ini sampai semua konfigurasi yang mungkin telah dicoba.

Tantangan

Representasi Dewan

Papan dapat diwakili menggunakan daftar 2D di mana setiap sel adalah 'q' atau '.'.

Memeriksa konflik

Memeriksa konflik secara efisien sangat penting:

1. Row Check : Memastikan tidak ada ratu lain yang berada di baris yang sama.
2. Column Check : Memastikan tidak ada ratu lain yang ada di kolom yang sama.
3. Diagonal Check : Memastikan tidak ada ratu lain yang menggunakan diagonal yang sama.

Optimasi

Menggunakan set untuk melacak kolom yang ditempati dan diagonal dapat mempercepat proses pemeriksaan konflik.

Konkurensi dengan threadpoolexecutor

Untuk mengoptimalkan pemecahan masalah untuk N yang lebih besar, solusi memanfaatkan konkurensi dengan threadpoolexecutor:

• Setiap utas mulai memecahkan masalah untuk kolom yang berbeda di baris pertama.
• Pendekatan paralel ini dapat secara signifikan mengurangi waktu untuk menemukan semua solusi.

Solusi kami

Solusi ini datang dari salah satu tantangan Jumat gratis kami, di mana kami memilih tantangan wawancara acak selama downtime kami untuk menulis solusi.

Instalasi

 pip install wolfsoftware.NQueens

Penggunaan

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

Ringkasan

Masalah N-Queens adalah tantangan yang menarik dan kompleks yang membutuhkan pemahaman yang mendalam tentang rekursi, backtracking, dan teknik optimisasi. Dengan memanfaatkan multi-threading, implementasi ini secara efisien menemukan semua solusi yang mungkin untuk ukuran papan tertentu. Memahami dan menerapkan masalah N-Queens adalah latihan yang berharga untuk meningkatkan keterampilan pemecahan masalah dan pemikiran algoritmik.