Ahli120 XPUnit 9: Fungsi dan Rekursi, soal 9 dari 9
N Ratu
Hitung banyaknya cara menempatkan N ratu catur yang tidak saling menyerang.
Ratu catur menyerang ke segala arah: mendatar, menurun, dan diagonal. Berapa banyak cara menempatkan N ratu di papan N × N sehingga tidak ada dua ratu yang saling menyerang? Soal ini terkenal sejak abad ke-19 dan menjadi latihan wajib backtracking.
Masukan
Satu bilangan bulat N dari 1 sampai 10.
Keluaran
Banyaknya susunan yang sah.
Contoh masukan dan keluaran
Contoh 1
Masukan
4
Keluaran
2
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Setiap baris pasti berisi tepat satu ratu. Tempatkan ratu baris demi baris, dan di setiap baris coba setiap kolom.
Petunjuk 2
Catat kolom dan diagonal yang sudah terancam. Diagonal turun dikenali dari baris - kolom yang sama, diagonal naik dari baris + kolom yang sama.