تطبيق حلال للعبة الكلمات الكلاسيكية Boggle! هل سبق لك أن تنافست في لعبة مكثفة من لعبة Boggle معتقدًا أنك استنفدت كل الكلمات الممكنة على اللوحة؟ لا تفكر أكثر!
من خلال ملف قاموس من اختيارك ولوحة ذات أبعاد مخصصة، سيكون لديك كل الكلمات الإنجليزية الموجودة داخل لوحة Boggle الخاصة بك في وقت قصير جدًا! (على جهاز الكمبيوتر الخاص بي، تعمل الخوارزمية في أقل من 3 ثوانٍ على لوحة مقاس 50 × 50!!) إذا كنت ترغب في استخدام قاموس آخر غير القاموس الذي قدمته، فلا توجد مشكلة - فقط تأكد من فصل كل كلمة بسطر جديد.
بمجرد الانتقال إلى دليل المشروع الجذر، استخدم الأوامر التالية في الوحدة الطرفية:
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
بافتراض أن ملف Boggle.java لم يتم تعديله، سيجد هذا البرنامج جميع الكلمات الموجودة في اللوحة التالية:
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
كما يمكنك أن تتخيل، فإن البحث في القاموس للتحقق مما إذا كان كل تسلسل ممكن من الحروف هو كلمة إنجليزية سيكون مهمة شاقة للغاية. اتضح أنه بالنسبة لأي لوحة بحجم nxn ، يوجد حد أقصى لـ n^2 x (n^2)! التسلسلات المحتملة للأحرف التي تحتاج إلى التحقق من صحتها. من الواضح أن هذا يتحلل بسرعة كبيرة - تتطلب اللوحة البسيطة 3 × 3 3265920 عملية تحقق على الأكثر، وهذا ليس حتى بحجم لوحة Boggle الحقيقية! فكيف فعلت ذلك؟ أعني أنه حتى حل لوحة مقاس 8 × 8 سيستغرق ما يقرب من 10^90 عملية حسابية كحد أقصى! لا بد وأنني فعلت شيئًا ذكيًا حقًا هنا. اتضح أن هناك نهجًا أكثر كفاءة بشكل لا يصدق. يدور جوهر خوارزمية الحل حول بنية بيانات معينة تُعرف باسم Trie. بالنظر إلى سلسلة بطول n ، فإن Trie قادر على إخبارنا ما إذا كانت السلسلة التي نبحث عنها موجودة في قاموسنا في زمن O(n) (خطي) أم لا! يعد هذا تحسنًا كبيرًا في إجراء بحث ثنائي لكل كلمة محتملة في ملف القاموس. في الواقع، يمكن لـ Trie التحقق مما إذا كانت إضافة حرف إلى سلسلة موجودة أم لا ستؤدي إلى كلمة صالحة أخرى في وقت ثابت! وهذا ما يجعل الخوارزمية سريعة كما هي: نقوم بإجراء بحث متعمق أولًا من كل حرف على اللوحة، ونضيف حرفًا مجاورًا للكلمة الحالية التي أنشأناها ونلحقه بنتائجنا إذا أسفرت عن كلمة موجودة في قاموسنا. إذا وصلنا في مرحلة ما إلى سلسلة ليست بادئة لأي كلمة أخرى، فإننا نتراجع إلى أقرب بادئة صالحة ونستمر. أشياء رائعة جدًا!
ومع ذلك، فإن كفاءة وقت التشغيل تأتي بتكلفة. يبلغ حجم ملف القاموس الذي أستخدمه حوالي 5 ميغابايت من النص، وبالتالي فإن متطلبات المساحة اللازمة لتجميع كل كلمة في قاموس Trie هائلة جدًا. إن إنشاء محاولة من القاموس هو في الواقع ما يستغرق وقتًا أطول لإنجازه، بمتوسط سرعة تنفيذ تصل إلى 2.2 ثانية تقريبًا على جهاز الكمبيوتر الخاص بي. إذا نظرنا إلى الجانب المشرق، فإن إنشاء قاموس Trie يتطلب وقتًا ومكانًا ثابتين فيما يتعلق بأبعاد اللوحة التي نقوم بحلها. ويترتب على ذلك أن العنصر الوحيد الذي يثير الاهتمام هو وقت تشغيل خوارزمية الحل لدينا، والتي أثبتت كفاءتها في حل اللوحات ذات الأبعاد التي تصل إلى 50 × 50 في أقل من 3 ثوانٍ. إذا كنت مهتمًا بالحدود القصوى، فقد استغرقت الخوارزمية حوالي 77 ثانية على نظامي لإيجاد حلول للوحة مقاس 250 × 250 .
