Program Solusi 8 ratu

Program untuk menemukan solusi dimulai dengan meletakkan ratu di pojok kiri atas dari papan catur. Kemudian ratu ke 2 diletakkan di kolom ke 2 yang nantinya tidak dapat diserang oleh ratu di kolom pertama. Begitu juga ratu ke 3 juga diletakkan di kom 3 yang tidak dapat diserang oleh ratu 1 maupun ratu 2. Kemudian peruses tu berlanjut hingga maring-masing ratu tidak dapatt diserang atapun menyerang ratu lainnya. Jika tidak ada tempat untuk ratu di kolom yang tepat, program akan kembali ke awal untk memprediksi kolom dan menempatkan ratu di kolom yang tepat. Jika ratu telah sampai pada akhir kolom, kita harus menemukan dan meletakkan ratu pada tempat yang tepat. Jika kolom yng dimaksud adalah kolom terakhir dan tempat yang aman telah ditemukan untuk ratu terakhir, maka solusi telah ditemukan. Jika kolom yang benar dari kolom pertama pemindahan ratu kemudian semua kemungkinan susunan sudah diperiksa,maka semua solusi telah ditemukan dan algoritma berakhir.

Ketika solusi telah ditemukan akan dapat ditampilkan di layar. Tetapi tidak akan muncul di layar jika program tidak dapat mendapatkan solusi yang dapat diperoleh dari sebelumnya dengn perputaran atau pemikiran.

Tingkat kesulitan dai permasalahan tergantung dari banyaknya perpindahan atas algoritma pengambilan solusi yang pertama. Jumlah jalan keluar sebanding degan kenaikan N, tetapi N tidak bertambah secara monoton. Tabel terdekat memberikan banyaknya langkah yang diperlukan. Hal itu ditentukan dengan menaikkan tingkat kesulitan. Jadi papan termudah untuk menemukan solusinya adalah dengan papan 5×5.

n = 7, y = 3x + 1
6					X
5							X
4		X
3				X
2						X
1	X
0			X
	0	1	2	3	4	5	6

Misal N adalah nomor utama, solusi dengan mudah ditemukan dengan menggambar garis lurus yang melewati ratu pada bidang yang sesuai batasnya. Idak ada garis lurus yang memotong pada garis lain dari ratu yang lain., garis lurus y=ax+b dimana tidak sama dengan 1 atau -1 dapat memberikan solusi. Coordinat mulai dari 0.

Contoh : N=7, y=2x

6				X
5							X
4			X
3						X
2		X
1					X
0	X
	0	1	2	3	4	5	6

Kita dapat dengan mudah menemukan 28 solusi dengan a=2,3,4,5, dan b=0,1,2,3,4,5,6..

RAsio Solusi analitis untuk solusi total untuk beberapa p kecil, sbb:

P=5, 10/10, 100%

P=7, 28/40, 70%

P=11, 99/2680, 4%

Untuk nomor gabungan N=pq, kita dapat membuat keluaran yang tepat untuk masalah p-ratu dan q-ratu. Setiap posisi masalah ratu dipandang sebagai solusi dari masalah q-ratu. Kita dapat mengubah peraturan p dan q. Untuk 35=5*7, kita dapat menghasilkan 10*(40)^5+40^7 solusi.

Untuk menghasilkan solusi umum N, misalkan koordinat papan i=0,…,n-1 dan j=0,…,n-1.

5			X
4						X
3		X
2					X
1	X
0				X
	0	1	2	3	4	5

Anggap N genap. Untuk semua k,

(1) Jika N bukan 6k+2,

J= 2i+1,untuk 0<=i<N/2

J=2i mod n, untuk n/2<=i<N

Contoh: N=6

(2) jika N bukan 6k

7			X
6					X
5		X
4								X
3	X
2							X
1				X
0						X
	0	1	2	3	4	5	6	7

j = (n/2 + 2i -1) mod n, untuk 0 <= i < n/2
j = (n/2 + 2i + 2) mod n, untuk n/2 <= i

Contoh: n=8

Untuk nilai yang ganjil, kita dapat meletakkan ratu pada (N-1,N-1)

Contoh: N=9

8									X
7			X
6					X
5		X
4								X
3	X
2							X
1				X
0						X
	0	1	2	3	4	5	6	7 8

Masalah 8 ratu sering kali digunakan sebagai contoh pelajaran Artificial Intelegence. Objek yang menempatkan 8 ratu pada papan catur kosong tak satupun dari mereka dapat menyerang satu samalain.