Implementasi pemecah untuk permainan kata Boggle klasik! Pernah berkompetisi dalam permainan Boggle yang intens sambil berpikir Anda telah kehabisan semua kemungkinan kata di papan? Jangan berpikir lagi!
Dengan file kamus pilihan Anda dan papan dengan dimensi khusus, Anda akan mendapatkan semua kata bahasa Inggris yang ada di papan Boggle Anda dalam waktu singkat! (Di komputer saya, algoritme berjalan dalam <3 detik pada papan 50x50!!) Jika Anda ingin menggunakan kamus selain yang saya sediakan, itu tidak masalah- pastikan setiap kata dipisahkan dengan baris baru.
Setelah menavigasi ke direktori proyek root, gunakan perintah berikut di terminal:
Gradlew Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Dengan asumsi file Boggle.java belum diubah, program ini akan menemukan semua kata yang terdapat di board berikut:
Solving:
a r m
b e s
n i m
arsine
rabies
bismer
bersim
barmen
miners
minbar
abime
abies
abner
resin
bines
bisme
biers
benim
besin
besra
berms
bears
bearm
braes
barse
bares
barms
smear
serab
smear
nears
inerm
mines
miner
miser
arse
aren
ares
arms
rems
reim
rein
reis
rems
rabi
mems
mein
mear
mrem
bine
bise
bien
bier
beni
berm
bear
brei
bren
bars
bare
barm
ears
sime
sine
sier
semi
serb
sera
sear
nims
nies
near
inbe
mise
mien
mems
mear
aes
aer
abn
abr
ars
are
arb
arm
rem
rei
ren
res
reb
rem
rea
rms
rab
mem
men
mer
mea
mrs
bim
bin
bis
ben
bes
ber
bra
bae
bar
ems
ems
ers
era
ear
sim
sin
sie
sib
sem
sei
sen
sem
ser
sea
nim
nis
nib
nei
neb
nea
ism
ise
ism
iba
min
mis
mib
men
mem
mer
mea
Seperti yang dapat Anda bayangkan, mencari di kamus untuk memeriksa apakah setiap rangkaian huruf yang mungkin merupakan kata dalam bahasa Inggris akan menjadi tugas yang cukup sulit. Ternyata untuk papan berukuran apa pun nxn , ada maksimum n^2 x (n^2)! kemungkinan urutan huruf yang perlu diperiksa keabsahannya. Ini jelas rusak dengan sangat cepat - papan sederhana berukuran 3 x 3 memerlukan paling banyak 3265920 validasi, dan ini bahkan bukan ukuran papan Boggle yang sebenarnya! Jadi bagaimana saya melakukannya? Maksud saya, bahkan menyelesaikan papan berukuran 8 x 8 akan membutuhkan maksimal sekitar 10^90 komputasi! Aku pasti telah melakukan sesuatu yang sangat pintar di sini. Ternyata ada pendekatan yang jauh lebih efisien. Inti dari algoritma penyelesaian berkisar pada struktur data tertentu yang dikenal sebagai Trie. Mengingat string yang panjangnya n , Trie dapat memberi tahu kita apakah string yang kita cari ada dalam kamus kita dalam waktu O(n) (linier) atau tidak! Ini merupakan kemajuan besar dalam menjalankan pencarian biner untuk setiap kemungkinan kata dalam file kamus. Faktanya, Trie dapat memeriksa apakah menambahkan huruf ke string yang ada akan menghasilkan kata lain yang valid dalam waktu yang konstan! Inilah yang menjadikan algoritma ini secepat itu: kita melakukan pencarian mendalam pertama dari setiap huruf di papan, menambahkan huruf yang berdekatan ke kata yang sedang kita buat dan menambahkannya ke hasil kita jika menghasilkan kata yang terkandung dalam kamus kami. Jika suatu saat kita mencapai string yang bukan merupakan awalan dari kata lain, kita mundur ke awalan terdekat yang valid dan melanjutkan. Barang yang cukup keren!
Namun efisiensi waktu proses memerlukan biaya. File kamus yang saya gunakan kira-kira berukuran 5 megabyte teks, sehingga kebutuhan ruang untuk menyusun setiap kata ke dalam kamus Trie cukup besar. Membuat Trie dari kamus sebenarnya membutuhkan waktu paling lama untuk menyelesaikannya, dengan rata-rata kecepatan eksekusi ~2,2 detik di komputer saya. Jika kita melihat sisi baiknya, pembuatan kamus Trie membutuhkan waktu dan ruang yang konstan sehubungan dengan dimensi papan yang kita pecahkan. Oleh karena itu, satu-satunya elemen yang menjadi perhatian adalah waktu proses algoritme penyelesaian kami, yang telah terbukti efisien dalam menyelesaikan papan dengan dimensi hingga 50 x 50 dalam waktu kurang dari 3 detik. Jika Anda tertarik dengan batasan ekstrem, algoritme memerlukan waktu sekitar 77 detik di sistem saya untuk menemukan solusi pada papan 250 x 250 .
