backtracking algoritma(sudoku)

ringkasan
Sudoku adalah permainan puzzle dimainkan pada grid yang terdiri dari 9 x 9
sel masing-masing milik tiga kelompok : satu dari sembilan baris , salah satu
sembilan kolom dan salah satu dari sembilan sub grid ( kadang-kadang disebut
daerah ) . Permainan Sudoku pada dasarnya didasarkan pada Latin
kuadrat . Sudoku adalah Lembaga yang dibentuk pada tahun 1979 dan pertama kali
dipublikasikan dalam Majalah Dell sebagai " Number Place " pada tahun
1984. Istilah Sudoku berarti satu nomor . Permainan dimulai
dengan nomor yang sudah dicetak dalam beberapa sel . Pemain harus mengisi
dalam sel-sel kosong dengan angka 1 sampai 9 sehingga setiap kolom ,
baris dan wilayah berisi nomor yang tepat sekali . ada
beberapa aplikasi Sudoku yang telah dikembangkan oleh
banyak programmer di seluruh dunia . Dalam tulisan ini , kami memberikan
gambaran pekerjaan yang telah kita dilakukan pada
pengembangan permainan Sudoku yang menghasilkan 9 x 9 teka-teki
grid dengan berbagai tingkat kesulitan . Aplikasi ini juga memungkinkan
pengguna untuk memasukkan puzzle mereka sendiri dan harus diselesaikan oleh komputer .
Aplikasi yang dikembangkan juga mencakup fitur canggih seperti
seperti menyimpan, beban dan validasi input cepat. Algoritma pemecahan
aplikasi Sudoku dikembangkan juga telah dibandingkan dengan
beberapa aplikasi Sudoku yang ada untuk analisis .

1 . pengantar
" Sudoku " adalah teka-teki menantang numerik yang melatih kami
Pikiran logis ! Tidak ada matematika terlibat di dalamnya - kita hanya perlu
memecahkan teka-teki numerik dengan penalaran dan logika . sekarang
permainan yang satu menemukan dirinya kecanduan dalam .
Memecahkan teka-teki Sudoku tidak memerlukan matematika , bahkan tidak
aritmatika [ 1 ] - [ 9 ] . Meski begitu , permainan ini menimbulkan beberapa
masalah matematika menarik .
Ironisnya , meskipun permainan angka , Sudoku
menuntut tidak ada sedikitpun matematika pemecah nya . Bahkan ,
tidak ada operasi - termasuk penambahan atau perkalian - membantu
dalam menyelesaikan grid , yang dalam teori bisa diisi dengan
setiap set sembilan simbol yang berbeda ( huruf , warna , ikon dan
sebagainya ) .
Namun demikian , Sudoku menyajikan matematikawan dan
ilmuwan komputer dengan sejumlah masalah yang menantang .
Teka-teki Sudoku , dan varian mereka , telah menjadi
sangat populer dalam dekade terakhir , dan sekarang dapat
ditemukan setiap hari di surat kabar yang paling utama . Selain buku-buku yang tak terhitung jumlahnya dari teka-teki Sudoku , ada banyak panduan
strategi Sudoku dan logika .
Tidak seperti kubus tiga dimensi Rubik , Sudoku
teka-teki adalah datar , kotak persegi . Biasanya mengandung 81 sel
( sembilan baris dan kolom sembilan ) dan dibagi menjadi sembilan
kotak kecil yang berisi sembilan sel masing-masing, menyebut mereka sub
grid atau wilayah . Permainan dimulai dengan nomor yang sudah
dicetak dalam beberapa sel . Pemain harus mengisi kosong
sel dengan angka 1 sampai 9 bahwa setiap kolom , baris dan
wilayah berisi nomor yang tepat sekali . Dengan demikian pengulangan
dari nomor secara ketat ditinggalkan . Setiap teka-teki memiliki satu
solusi yang unik .

2. definisi
Tabel 1 menggambarkan arti dari istilah yang berbeda digunakan dalam
kertas diberikan dalam makalah ini adalah
Tabel 1: Definisi
istilah dan Definisi
Sebuah sel tunggal persegi di teka-teki
Kotak Sekelompok sel 3X3
Grid Sekelompok kotak 3X3
Kolom Sebuah kolom 9 sel
Row Sederet 9 sel
mengingat
nilai
Sebuah nilai (antara 1-9) yang sudah
ditugaskan ke sel pada awal permainan, yang
tidak dapat diubah
sah
masukan
Sebuah nilai yang dapat dimasukkan ke dalam sel
tanpa melanggar aturan main saat
ketika nilai dimasukkan. Tidak berarti
nilai yang disisipkan adalah nilai yang benar untuk
permainan
mungkin
Daftar nilai input berlaku untuk sel

3.input berlaku untuk sel
3. pendekatan Diambil
3.1 Menghasilkan Teka-teki Sudoku
Membangkitkan teka-teki Sudoku adalah tugas memilih
subset sel dari grid Sudoku mengandung petunjuk untuk memungkinkan solver untuk menghitung solusi untuk teka-teki. untuk
memuaskan untuk pemecah manusia, solusi tersirat oleh
petunjuk harus unik, sehingga sangat diinginkan untuk menghasilkan
teka-teki yang tepat. Pada dasarnya, ada dua metode yang berbeda
untuk membuat teka-teki Sudoku tepat: generasi Incremental,
yang memberikan angka untuk satu sel demi satu sampai
petunjuk yang cukup diberikan untuk teka-teki untuk memiliki unik
solusi. Generasi decremental menghapus angka dari
sel-sel grid Sudoku penuh selama yang diinginkan atau
mungkin agar solusi untuk tetap unik. Gambar 1
dan 3 menunjukkan diagram alir dan algoritma masing-masing
yang merupakan prosedur untuk menghasilkan teka-teki.

3.2 . Memecahkan teka-teki Sudoku
Meskipun tujuan awal untuk pekerjaan itu hanya untuk
menerapkan pena sederhana dan versi kertas Sudoku pada
komputer tanpa komputer benar-benar memecahkan
teka-teki bagi pengguna . Akan menyenangkan untuk memiliki pemecah dalam kasus
pengguna terjebak dan ingin menemukan jawaban meskipun
sekarang-a - hari ada banyak online kiat pemecahan masalah dan pemecah
[ 10 ] - [ 19 ] tersedia . Hal ini juga menarik untuk mengetahui
apa algoritma bekerja dengan baik dengan berbagai jenis
teka-teki .
Di sini kita telah mengikuti algoritma backtracking untuk memecahkan
teka-teki . Namun, ada dua alasan utama mengapa hal ini
tidak diinginkan : Mengulangi pada umumnya membutuhkan waktu terlalu banyak
waktu dan tidak pas untuk menilai kesulitan Sudoku
teka-teki . Namun, kami telah mengikuti proses ini didasarkan pada
fakta bahwa lebih mudah daripada metode lainnya (seperti
pemrograman kendala , brute-force dll ) dan ada
hanya aplikasi Sudoku beberapa yang didasarkan pada
backtracking algoritma . Gambar 2 dan 4 menunjukkan diagram alir dan algoritma masing-masing untuk pendekatan yang kita miliki
digunakan untuk memecahkan teka-teki Sudoku .

Figure 2: Flow Chart for solving Sudoku Grid

1. Initialize String s[ ], mark[ ][ ], mark_row[ ][ ],

mark_col[ ], maze[ ][ ]

2. Initialize genpuzzle(level){

1. String ans=null;

2. Intialize count=0, cells=13, min=0,

max=cells+(24-10*level);

3. While(true)

1. Initialize all arrays to 0

2. While (count<=cells)

1. Generate random values for val, row,

col, through Random() function.

2. Decide region through row, col

3. Insert value into grid according to

the rule and mark corresponding

row, col and region

4. If (solvable)

1. String ret[ ]=getstrings(ans, level)

2. Return ret;

5. Else backtrack

6. End if

3. End while

4. Return array;

4. End while

1. initialize getanswer (string s[ ])

2. define variables mark_row[ ][ ], mark_col[ ][ ],

mark[ ][ ], maze[ ][ ], top, rr, cc, val, region;

3. for (i=0;i<=81;i++)

1. if (cell is not empty)

1. copy and store the val in maze and set the

corresponding flags in other row, col, mark and

set the corresponding flags;

2. end if

4. end for

5. while(true)

1. if(cell is empty)

1. while(++val!=10 && val is not conflicting)

1. insert the val

2. end while

2. end if

3. if (val<10)

1.val=0;

4. if (cc!=9){cc++;}

5. elseif (rr!=9){rr++;}

6. else{ top--; reset top and corresponding value;}

7. end if

6. end while

3 . Pelaksanaan dan Hasil Analisis
Hal ini diketahui bahwa Sudoku adalah kelas NP - lengkap
masalah dan apalagi semua aplikasinya dari heuristik
di alam . Algoritma disebutkan dalam bagian terakhir adalah
diimplementasikan dengan menggunakan java ayunan UI komponen dan java
[ 20 ] - [ 23 ] sebagai bahasa pemrograman dasar pada windows7
Platform . Percobaan dilakukan untuk menghitung waktu
diperlukan untuk memecahkan teka-teki Sudoku yang diberikan mempertimbangkan
sampel teka-teki . Sama set teka-teki sampel juga
diselesaikan dengan menggunakan Sudoku solver v 2.0 dan Sudoku solver v
1.01 [ 24 ] dan waktu penyelesaian yang dibutuhkan juga dicatat .
Kami membandingkan algoritma kami dengan yang disebutkan di atas
pemecah sehubungan dengan waktu yang dibutuhkan untuk memecahkan teka-teki .
Di sini kita melihat bahwa pemecah dikembangkan oleh kami membutuhkan
waktu secara signifikan lebih rendah dibandingkan dengan dua lainnya
pemecah . Perbandingan antara ketiga algoritma
terhadap waktu ditunjukkan dalam bentuk kinerja
grafik pada gambar 5 . Berikut aplikasi yang diuji selama komputer memiliki Intel Pentium Core 2 Duo processor dan
2GB RAM .

4. Kesimpulan dan Masa Depan kerja
Dalam tulisan ini kita disajikan algoritma backtracking untuk
menghasilkan dan memecahkan teka-teki Sudoku. Kami memiliki
menerapkan algoritma menggunakan java dan juga dibandingkan
dengan dua software aplikasi lainnya yang ada. itu
Hasil perbandingan menunjukkan bahwa program aplikasi
dikembangkan oleh kami melakukan lebih baik daripada Sudoku solver v 2.0
dan Sudoku solver v 1.01.
Pekerjaan di masa depan akan menjadi peningkatan solver Sudoku
algoritma untuk meningkatkan efisiensi. Juga perbandingan
program aplikasi dengan Sudoku lain yang ada
solver tetap sebagai pekerjaan di masa depan.

mengakui
Kami menyajikan pengakuan yang tulus kepada semua fakultas
anggota, staf non-mengajar dan semua siswa
Departemen Teknologi Informasi, Universitas Assam,
Silchar untuk inspirasi dan dukungan mereka.