حل مسئله رمز نگاری در CSP

[soroushp]

x3 x2 x1
T W O
T W O +
ـــــــــــــــــــــــــ ــــــــــــــــــــ
F O U R

O+O=R+10X1
X1+W+W=U+10X2
X2+T+T=O+10X3
X3=F

سوال من اینه که چطوری باید مقدار عددی برای T,W,O,R,U,F در بازه ی {0...9} پیدا کنیم ؟
x1,x2,x3=0,1

نمی خواد کلش رو حل کنید ، روشش رو بگید کافیه !
:تشویق:

[soroushp]

شاید اگر ما حروف رو به صورت گره در نظر بگیریم یک گراف بشه اما اگر مقداردهی بکنیم و بخواهیم با backtracking حل کنیم ، نمایی میشه - من احتمال می دم یک روش جبری داشته باشه !!! یا با Forward checking

[amin1softco]

این معما های کتاب هوش قبلاً حل شده بهتره سرچ کنید فقط :
این سورسش به زبان سی :
http://bach.istc.kobe-u.ac.jp/puzzle/crypt/crypt14.tgz
و اینم نمونه آنلاینش تست کنید:
http://bach.istc.kobe-u.ac.jp/llp/crypt.html

لینک های مفید :
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/first_steps.html
http://en.wikipedia.org/wiki/Brute-force_search
http://cboard.cprogramming.com/cplusplus-programming/119017-cryptarithmetic-puzzle.html

یا در گوگل سرچ کنید:
cryptarithmetic puzzle

[soroushp]

شاید سوال رو بد پرسیدم من نمی خوام برنامه اش رو بنویسم می خوام به صورت دستی حلش کنم ،
اگر با brute-force بخوایم حل کنیم n^6 زمان می خواد فکرشو بکن اگر بخوایم n حرف رو رمز کنیم !
تو این مسئله ها ، x1 , x2 , x3 نمی دهند ؟ برای حلش باید چه کرد ؟

[amin1softco]

خوب شوما به صورت دستی می خواهی n تا متغیر در نظر بگیری؟
والا تا جایی که ما در هوش مصنوعی خوندیم این مسائل را با روش های زیادی می شه حل کرد که یکیش به قول شوما Forward checking است یکیش BackTrack و Arc Consistency است که آرک با پیچیدگی ( O(n^2*d^3 به نظرم بهترین روش باشه یک سری جستجوی دیگه ام بود با نام جستجوی محلی که Hill-climbing, simulated annealing رو شامل می شد با تمام این ها می شه مسئله رو حل کرد شما می خواهید با کدوم روش برید محدودیت ها اینجا اینهاست :
O+O=R+10X1
X1+W+W=U+10X2
X2+T+T=O+10X3
X3=F
که می تونید از c1 تا c4 نام گذاری کنید . و x1 , x2 , x3 متغیر کمکی هستند

[soroushp]

شوما یعنی چی ؟:چشمک: - ببین با backtracking میشه اما برات مثال میزنم : مثلا O رو از دامنه 2 رو انتخاب می کنی 2+2=4 ، بعد می ری جلو می بینی به تناقض رسیدی بعد دوباره برمی گردی عدد 2 رو عوض می کنی و همینطور تا آخر - با simulate anealing چطوری می خای شبیه سازی کنی ؟ دما رو چی درنظر می گیری در صورتی که کل دامنه توزیع یکنواخت دارند ! شاید با پرتو محلی بشه که حتما میشه حالا بگذریم ، سوال چون تو csp بوده با forward checking نمایی کمتری داره اما سوال ام اینه که روش جبری داره ؟ اگر نداشته باشه باید همون روشی که تو پست قبلی اشاره کردی رو دنبال کرد .

[amin1softco]

عزیز دلم فک کنم شما درک درستی از مسئله ندارید :http://en.wikipedia.org/wiki/Cryptarithmetic
اینجا فایل رو ببنید : http://uilab.kaist.ac.kr/course/CS570_2009_Spring/assignment2_solution.pdf

[soroushp]

عزیز دلم فک کنم شما درک درستی از مسئله ندارید


اگر من مسئله رو درک کرده بودم که دیگه وقت شما رو نمی گرفتم !
تعریف مسئله از نظره من : حروف مذکور باید با استفاده از دامنه که در فاصله 0 تا 9 هست عدد دهی شود به طوری که به تناقض نرسیم (در صورت اضافه شدن حروف دیگه) - x هم نماد 10 بر یک هستند که دامنه 0و1 داره
حالا اگر تعریف من اشتباه هست بگید ؟
فکر می کنم pdf که لینک کردین جواب سوالم باشه

[amin1softco]

نه عزیز دلم کاملاً درست
بله در هر دو تا لینک روش بدست آوردن راه حل ذکر شده در ویکی پدیا به روش دستی در لینک دوم هم حل تمرین 6 فصل 5 کتاب راسل نرویگ است. فایل ضمیمه هم مرحله به مرحله forward checking است.
ولی خوب شاید من اشتباه فکر می کردم شوما می خواهید تعداد راه حل ها را بدست بیارید یعنی به چند طریق مثل اون سایته :

two+two=four (6 variables)
938+938=1876
928+928=1856
867+867=1734
846+846=1692
836+836=1672
765+765=1530
734+734=1468
CPU time = 0 msec

7 solution(s)

88564