Cube Solver

حل مكعب روبيك

عرض الفيديو: https://www.youtube.com/watch?v=A6JyElruhwE

العرض التوضيحي: http://d4m4s74.pythonanywhere.com/

وصف:

مشروعي الأخير لـ CS50 هو "الطريقة البشرية" لحل مكعبات روبيك.
وهذا يعني أن مكعب روبيك الذي تم إدخاله قد تم حله باستخدام طريقة يمكن للإنسان استخدامها (CFOP)، بخطوات واضحة: Cross وF2L وOLL وPLL.
يتكون المنتج النهائي من تطبيق Shell، ومكتبة C لاستخدامها في مشاريع أخرى، وواجهة ويب مكتوبة بلغات Flask وHTML وCSS وJavascript.

قررت إنشاء حل لمكعب روبيك لأنني قمت بإنشاء حل سودوكو من قبل في لغة C++، وكان المكعب بمثابة خطوة للأمام.
بدلاً من المستوى ثنائي الأبعاد، لدي مستوى شبه ثلاثي الأبعاد، مع حواف وزوايا.
نظرًا لأن حلول الذكاء الاصطناعي قد تم إنجازها، ولست واثقًا بدرجة كافية من قدراتي في الكتابة باستخدام الذكاء الاصطناعي، فقد قررت أن أجعل البرنامج يحل المكعب بالطريقة التي أفعلها:
كروس، F2L، OLL وPLL

كيفية الاستخدام

حلالا

لينكس

قم بتنزيل الملف القابل للتنفيذ bin/solver أو أنشئ من المصدر باستخدام make solver

نظام التشغيل العاشر

قم بتنزيل الملفات من هذا المستودع أو استنساخها ثم قم بالإنشاء باستخدام make solver

ويندوز

قم بتنزيل الملفات أو استنساخها باستخدام هذا المستودع وتجميع جميع ملفات .c في src باستثناء Solver_library

الجميع

قم بتنفيذ الحل باستخدام أحد الأوامر التالية:

 ./solver "Algorithm"
./solver [Up] [Front] [Right] [Back] [Left] [Down]

استبدال الخوارزمية بخوارزمية خلط (مثل U R2 FBR B2 R U2 L B2 RU' D' R2 FR' L B2 U2 F2 ) أو الوجوه ذات الألوان الموجودة على ذلك الوجه (على سبيل المثال wbwowrwgw gwgogrgyg rwrgrbryr bwbrbobyb owobogoyo ygyoyryby ).
الألوان المحتملة هي الأحرف الأولى من الأخضر والأحمر والأزرق والبرتقالي والأبيض والأصفر.
إذا لم تكن ملفات olls.txt وplls.txt موجودة في نفس المجلد مثل الملف الثنائي، فاستخدم الخيارات -o و-p أو -d للإشارة إلى الملفات

 bin/solver -d data/ "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2"
bin/solver -o data/olls.csv -p data/plls.csv "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2"

أضف الخيار -t لطباعة النص فقط بدون صور المكعب.

واجهة الويب

لينكس:

قم بتنزيل أو استنساخ الملفات من هذا المستودع.
قم بتثبيت Flask و Numpy باستخدام النقطة.

 python3 -m pip -r requirements.txt

استخدم إما flask run أو python3 app.py لتشغيل خادم الويب.
انتقل إلى https://127.0.0.1:5000/ لاستخدام الحل.

نظام التشغيل العاشر:

قم بتنزيل أو استنساخ الملفات من هذا المستودع.
قم بإزالة إصدار Linux من bin/libcubesolver.so يدويًا أو باستخدام make clean and recompile باستخدام make library .
تثبيت Flask و Numpy باستخدام النقطة:

 python3 -m pip -r requirements.txt

استخدم إما flask run أو python3 app.py لتشغيل خادم الويب.
انتقل إلى https://127.0.0.1:5000/ لاستخدام الحل.

ويندوز:

قم بتنزيل أو استنساخ الملفات من هذا المستودع. قم بإزالة إصدار Linux من bin/libcubesolver.so يدويًا.
قم بتجميع كافة ملفات .c في src باستثناء Solver.c إلى bin/libcubesolver.so. أو إذا كنت تستخدم اسمًا مختلفًا، فقم بتغيير السطر 19 في app.py ليعكس ذلك.
تثبيت Flask و Numpy باستخدام النقطة:

 python3 -m pip -r requirements.txt

استخدم إما flask run أو python3 app.py لتشغيل خادم الويب.
انتقل إلى https://127.0.0.1:5000/ لاستخدام الحل.

مكتبة الحلال

تثبيت للاستخدام مع C أو C++

قم بتجميع كافة الملفات في src باستثناء Solver.c إلى libcubesolver.so أو libcubesolver.dylib أو libcubesolver.dll واحفظها أينما تم حفظ المكتبات على جهاز الكمبيوتر الخاص بك.
على Linux، يمكنك استخدام make library
انسخ libcubesolver.h من src إلى أي مكان يتم حفظ الرؤوس فيه على جهاز الكمبيوتر الخاص بك (على سبيل المثال /usr/include/)

الاستخدام مع C أو C++

اربط بـ -lcubesolver أو قم بتجميعه في التطبيق كما لو كان ملفًا بتنسيق .o

 #include 
#include 
//Use either setup, or both load_olls and load_plls.
//Load all OLLs and PLLs into memory. Path is the folder where the olls.csv and plls.csv file are located.
//Returns indicating for succes or failure.
setup ( path );
//Loads the OLLs from a CSV file. Returns bool indicating success or failure.
load_olls ( filename );
//Loads the PLLs from a CSV file. Returns bool indicating success or failure.
load_plls ( filename );
//Create an array to hold the cube. 6 faces, 9 squares per face.
//The faces in order are Front, Right, Back, Left, Up and Down.
//The "Colors" are saved as the numbers 0 to 5.
int cube [ 6 ][ 9 ];
//Add the "colors" of the cube to the array as 9 character strings containing numbers 0 to 5.
color_cube ( cube , front , right , back , left , up , down );
//Run a multiple move algorithm on the cube, using standard cube notation. (Useful for scrambling)
run_algorithm ( cube , "Algorithm" );
/*
A function that prints the sides of the cube in an exploded fashion. Uses colors when in linux or OS X
Uses Green for 0, Red for 1, Blue for 2, Orange for 3, White for 4, Yellow for 5
    WWW
    WWW
    WWW

OOO GGG RRR BBB
OOO GGG RRR BBB
OOO GGG RRR BBB

    YYY
    YYY
    YYY
*/
print_cube ( cube );
//Validate the colors on the cube for impossible cubies. This does not check if the scramble is solvable.
//Returns bool.
if (! validate ( cube ))
{
    return "Invalid color combinaton" ;
}
//returns pointer to string containing all algorithms used to solve the cube, separated by newlines,
//and the names of the steps. (eg. Cross, F2L, OLL: Sune, PLL: Y perm)
//Modifies the array to its solved position
char * solution = solve ( cube );
// Returns:
/*
Cross
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)

F2L
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)

OLL: Kite
(y2) (R U R' U') R' F R2 U R' U' F'

PLL: G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
*/

//Generates a cube from an algorithm and returns pointer to its solution, or an error if unsolvable.
char * solution2 = solve_scramble ( "scramble" );
//Solves the (yellow) cross.
//Returns a pointer to a string containing the solve algorithm, with each solved edge separated by newlines.
//May also return an error if unsolvable.
//Modifies the cube array to have a solved cross.
char * cross = solve_cross ( cube );
//Solves the first two layers of the cube assuming a solved cross.
//Returns a string containing the solve algorithm, with each solved pair separated by newlines.
//Modifies the cube array to solve its f2l.
//Returns null if the cube is unsolvable.
char * f2l = solve_f2l ( cube );
//Looks up the right OLL algorithm and runs it, assuming a solved F2L.
//Returns the name of the OLL, and the algorithm, separated by a newline.
//Returns null if the cube is unsolvable.
char * oll = solve_oll ( cube );
//Looks up the right PLL algorithm and runs it, assuming a solved OLL.
//Returns the name of the PLL, and the algorithm, separated by a newline.
//Returns null if the cube is unsolvable.
char * pll = solve_pll ( cube );

الاستخدام مع بايثون

راجع الإصدار C لمعرفة ما تفعله كل وظيفة.
نظرًا لأنه من الصعب تحرير الذاكرة الصغيرة في لغة بايثون، استخدم إصدارات "آمنة" من وظائف الحل واستخدم free_strings() بعد الاستخدام.

 import numpy
import ctypes
# Most functions will need a c 2d int array. Let's give it a name so it's easy to use.
array_2d_int = numpy . ctypeslib . ndpointer (
    dtype = ctypes . c_int , ndim = 2 , flags = 'CONTIGUOUS' )
# First load the solver library using ctypes CDLL.
solver = ctypes . CDLL ( "/path/to/libcubesolver.so" )
# Then we set up all functions we might want to use.
# Setup, load_olls and load_plls require a string.
solver . setup . argtypes = [ ctypes . c_char_p ]
solver . load_olls . argtypes = [ ctypes . c_char_p ]
solver . load_olls . argtypes = [ ctypes . c_char_p ]
# Run_algorithm requires a 2d array for the cube, and a string.
solver . run_algorithm . argtypes = [ array_2d_int , ctypes . c_char_p ]
# All other functions require just the 2d array.
solver . print_cube . argtypes = [ array_2d_int ]
solver . validate . argtypes = [ array_2d_int ]
solver . solve_safe . argtypes = [ array_2d_int ]
solver . solve_cross_safe . argtypes = [ array_2d_int ]
solver . solve_f2l_safe . argtypes = [ array_2d_int ]
solver . solve_oll_safe . argtypes = [ array_2d_int ]
solver . solve_pll_safe . argtypes = [ array_2d_int ]
# For functions that return something other than an int (or bool) we also need to set the response type.
solver . solve_safe . restype = ctypes . c_char_p
solver . solve_cross_safe . restype = ctypes . c_char_p
solver . solve_f2l_safe . restype = ctypes . c_char_p
solver . solve_oll_safe . restype = ctypes . c_char_p
solver . solve_pll_safe . restype = ctypes . c_char_p
# Load the olls and plls csvs. in my case they're in the data folder.
# Use .encode('utf-8') to convert the python string to a c string.
solver . setup ( "data" . encode ( 'utf-8' ))
# Set up a cube. The inner lists, in order, are Front, Right, Back, Left, Up and Down.
# By default 0 = green, 1 = red, 2 = blue, 3 = orange, 4 = white, 5 = yellow.
solvedcube = [[ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ],
              [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ],
              [ 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ],
              [ 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 ],
              [ 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 ],
              [ 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 ]]
# Turn it into a C 2d array.
cube = numpy . array ( solvedcube ). astype ( ctypes . c_int )
# Run a scramble on the array. Use .encode('utf-8') to change the python string to a c string.
solver . run_algorithm (
    cube , "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2" . encode ( 'utf-8' ))
# Print the cube to the shell.
solver . print_cube ( cube )
# Validate the color comibinations on the cube.
if not validate ( cube ):
    return "Invalid color combinaton"
# Solve the cube using solver.solve.
# Note: running the function also modifies the cube array.
solution = solver . solve_safe ( cube ). decode ( "utf-8" )
# Returns:
"""
Cross
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)

F2L
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)

OLL: Kite
(y2) (R U R' U') R' F R2 U R' U' F'

PLL: G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
"""
# Or returns an error if the cube is unsolvable.

# You can also do the steps separately.
# solve the cross.
cross = solver . solve_cross_safe ( cube ). decode ( "utf-8" )
# returns
'''
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)
'''
# solve the F2L.
f2l = solver . solve_f2l_safe ( cube ). decode ( "utf-8" )
# returns
'''
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)
'''
# solve the OLL.
oll = solver . solve_oll_safe ( cube ). decode ( "utf-8" )
# returns
'''
Kite
(y2) (R U R' U') R' F R2 U R' U' F'
'''
# solve the PLL.
pll = solver . solve_pll_safe ( cube ). decode ( "utf-8" )
# returns
'''
G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
'''
# If a step is already solved, the functions return an empty string.
# With an unsolvable cube, these functions return NULL, which causes an
# AttributeError when trying to decode. You may want to verify before decoding. (or use try)

# Clean up the memory for the solution strings.
solver . free_strings ()
# Finally clean up the loaded OLLs or PLLs to prevent memory leaks
solver . cleanup_last_layer ()

بناء

يريد CS50 مني أن أشرح ما يفعله كل ملف وما هو موجود فيه. لذا فإن هذا الملف التمهيدي أطول من جميع ملفاتي باستثناء 3 منها.

 ├── app.py  
├── بن  
│ ├── libcubesolver.so  
│ └── حلالا  
├── البيانات  
│ ├── أخطاء.txt  
│ ├── olls.csv  
│ ├── أنماط.csv  
│ └── plls.csv  
├── ملف إنشاء  
├── README.md  
├── المتطلبات.txt  
├── سرك  
│ ├── cross.c  
│ ├── cross.h  
│ ├── cube.c  
│ ├── cube.h  
│ ├── cubesolver.h  
│ ├── f2l.c  
│ ├── f2l.h  
│ ├── lastlayer.c  
│ ├── lastlayer.h  
│ ├── حلالا.ج  
│ ├── Solver_library.c    
│ ├── utils.c  
│ └── utils.h  
├── اختبار  
│ ├── Randomtests.c  
│ └── اختبارات عشوائية   
├── ثابت  
│ ├── cube.css  
│ ├── cube.js  
│ ├── cubeinterface.js  
│ ├── favicon.ico  
│ ├── التالي.png  
│ ├──وقفة.png  
│ ├── play.png  
│ └── السابق.png  
├── القوالب  
│ ├── cube.html  
│ └── Solver.html  

src

cube.c و cube.h

يحتوي Cube.c وcube.h على كافة التعليمات البرمجية التي تتحكم في مكعب روبيك في الذاكرة.

مكعب روبيك، في الذاكرة، عبارة عن مصفوفة ثنائية الأبعاد مقاس 6 × 9. تحتوي المصفوفة الخارجية على الوجوه الستة: الأمامي، الأيمن، الخلفي، اليسار، الأعلى والأسفل.
لقد اخترت هذا الترتيب لأن الوجوه العلوية والسفلية هي نفسها دائمًا، لذا يمكنني ترميزها، لكن الجوانب تحتاج فقط إلى أن تكون صحيحة بالنسبة لبعضها البعض. هذا يعني أنه يمكنني استخدام علامة زائد أو ناقص بسيطة، بالإضافة إلى المعامل لترجمة الاختبارات والتحركات إلى كل جانب. وينطبق الشيء نفسه على الألوان، التي يتم حفظها كأرقام من 0 إلى 5، 0 هو اللون الأمامي، 1 هو اللون الصحيح، وما إلى ذلك.
اخترت أولاً ترتيب الألوان الذي أستخدمه: الأحمر في المقدمة، والأصفر في الأعلى، والأخضر على اليمين. ولكن لاحقًا عند كتابة كود Python والواجهة الخاصة بي، قمت بالتبديل إلى اللون الأخضر "الرسمي" في المقدمة، والأبيض في الأعلى، لذلك لا أحتاج إلى تدوير المكعب الذي أدخله المستخدم للحصول على اللون الأبيض في الأسفل.

color_cube()

أولاً قمت بإنشاء وظيفة color_cube(). يؤدي هذا إلى تطبيق نمط من اختيارك على المكعب باستخدام 6 سلاسل.
يستخدم رياضيات char بسيطة لتغيير char '0' و '1' وما إلى ذلك إلى ints وتخزينها في المصفوفة المحددة.
أنا أستخدم هذا مرة أو مرتين فقط كخط واحد لإعداد مكعب تم حله في سطر واحد، لأنه عند ترجمة إدخال المستخدم إلى شيء يفهمه الكمبيوتر، قد تقوم أيضًا بإدخال ints بشكل فردي بدلاً من ترجمته أولاً إلى سلسلة.

print_cube()

يقوم Print_cube() بإخراج المكعب المرفق إلى الجهاز. يتم استخدام هذا كثيرًا عند تصحيح الأخطاء وللتطبيق الطرفي. لقد بدأت بإخراج الأرقام من 0 إلى 5 فقط على شكل مكعب روبيك منفجر.

    444
    444
    444

333 000 111 222
333 000 111 222
333 000 111 222

    555
    555
    555

نظرًا لأنه سيؤدي إلى إنشاء المزيد من أسطر التعليمات البرمجية لأتمتة هذا، فأنا ببساطة أستخدم 9 عبارات طباعة تحتوي كل منها على ما يصل إلى 12 متغيرًا.
اكتشفت لاحقًا أنه يمكنني إضافة رموز الصدفة مثل e[42m لإعطاء هذه الأرقام لون الخلفية. إضافة تلك أعطاني 28 متغيرًا لكل طباعة.
أخيرًا، فكرت ببساطة في وضع الحرف أو الرقم للون في المصفوفة التي تحتوي على رموز الصدفة، وإعادتها إلى 12. ولسوء الحظ، لا يدعم Windows هذا النوع من رموز الصدفة، لذلك اضطررت إلى الاستمرار في استخدام الأرقام فقط، و رسائل لاحقة.

move_cube()

Move_cube() هي الوظيفة الأولى لتغيير المكعب فعليًا. هذه وظيفة متكررة تقوم بنقل المبلغ المطلوب من المرات. هناك 9 حركات محتملة، مرقمة من 0 إلى 8. الطبقة الأمامية واليمنى والخلفية الافتراضية، وما إلى ذلك، ولكن أيضًا الطبقة الوسطى وخط الاستواء والطبقة الدائمة. باستخدام وظيفة مساعدة كتبتها في utils.c تسمى Cycle، أقوم بتبديل قيم كل مربع على كل وجه يتوافق مع الحركة في اتجاه عقارب الساعة، مع التكرار إذا لزم الأمر.

تشغيل_الخوارزمية ()

نظرًا لأن الحركات عادةً لا تحدث من تلقاء نفسها، فقد كتبت بعد ذلك run_algorithm(). تستخدم هذه الوظيفة move_cube() لتشغيل خوارزمية على المكعب المتوفر في تدوين المكعب القياسي. يمنحني هذا القدرة على القيام بحركات متعددة في وقت واحد (أو بالترتيب فعليًا)، والقيام بحركات لها تأثير على طبقتين أو حتى ثلاث طبقات مثل x وy وz.

التحقق من صحة ()

وأخيرا، التحقق من صحة (). لقد أضفت هذه الوظيفة أثناء كتابة واجهة بايثون لأنه لا يجب أن تثق أبدًا في عدم قيام المستخدم بإدخال أشياء غريبة.
لا تتحقق هذه الوظيفة مما إذا كان مكعب روبيك قابلاً للحل. يتحقق مما إذا كانت الألوان صحيحة. على سبيل المثال، لا يمكن أن يحتوي المكعب الواحد على ملصقات بيضاء وصفراء. وبالتحرك في اتجاه عقارب الساعة من الممكن أن يكون لديك ملصقات خضراء وبيضاء وحمراء بهذا الترتيب، ولكن ليس العكس.
من أجل القيام بذلك، قمت جزئيًا بنسخ فكرة المصفوفة المقفلة في Tideman، باستخدام مصفوفة منطقية ثنائية الأبعاد للزوايا، ومصفوفة منطقية ثلاثية الأبعاد للحواف لمعرفة ما إذا كان من الممكن الجمع بين لونين أو ثلاثة ألوان. لقد مر هذا الرمز بتكرارات متعددة. قم أولاً بالتحقق من كل حافة وزاوية على حدة، ثم استخدم لاحقًا عددًا قليلًا من حلقات for.

cross.c و cross.h

يحتوي Cross.c على كافة التعليمات البرمجية اللازمة لحل تقاطع المكعب. لأنني أستخدم "الطريقة البشرية" (CFOP) لحل المكعب، فأنا مجبر نوعًا ما على استخدام أشجار قرارات ضخمة.
لقد قمت بإعادة كتابة هذا الملف بالكامل تقريبًا في اللحظة الأخيرة حتى لا يلزم محاذاة الحواف في كل خطوة على الطريق.

فايند زيرو ()

يبحث عن مكان وجود الحافة الصفراء والخضراء في الطبقة السفلية، أو ما قد تكون عليه إذا لم تكن موجودة بعد. وهذا يجعل من السهل محاذاة الحواف الأخرى في خطوات أقل لأنها يمكن أن تتم محاذاتها إلى "الصفر النسبي" بدلاً من الصفر الفعلي.

crossCase1() إلى 6

هذه الحالات الستة هي كل الطرق التي يمكن بها توجيه الحافة، والإشارة إلى الأسفل، والإشارة إلى الأعلى، والإشارة إلى الطبقات العلوية والسفلية، والإشارة إلى اليسار والإشارة إلى اليمين على الطبقة E.
تقوم الوظائف بشكل أساسي بمسح الوجوه بالترتيب من 0 إلى 3 للبحث عن القطع التي تنتمي إلى الصليب، وتدويرها في مكانها، وتخزين الحركات في مصفوفة char باستخدام وظيفة مساعدة أسميها append().

حل_كروس ()

يقوم Solve_cross أولاً بتوجيه المكعب بحيث يكون اللون الأصفر لأسفل. ثم يقوم بالحالات المتقاطعة الستة بالترتيب. إذا قام أحد بإرجاع شيء آخر غير null فإنه يعود إلى الحالة الأولى.
بمجرد حل جميع الحواف الأربعة، تقوم الدالة بإرجاع الخوارزميات. إذا تم اختبار جميع الحالات دون نجاح، أو بعد 4 حلقات، ترجع الدالة NULL.

f2l.c و f2l.h

نفس فكرة cross.c، باستثناء طريقة أكبر. 3600 سطر من التعليمات البرمجية لحل جميع الحالات.

f2lCase1() إلى 11

تتكون هذه الحالات الـ 11 من كل طريقة يمكن من خلالها توجيه الزاوية، وبعض مجموعات الزوايا والحواف.
لتوفير الوقت والخطوط، لا تحل معظم الوظائف مجموعة الزوايا/الحافة بشكل كامل، ولكنها توصلها إلى أقصر حالة معروفة وتستدعي الوظيفة الصحيحة.
الأرقام من 1 إلى 11 هي الترتيب الذي كتبت به، وليس دائمًا الترتيب الذي تم تشغيلها به.

حل_f2l()

يتحقق Solve_f2l أولاً من حل التقاطع. إذا لم يكن الأمر كذلك فإنه يعود فارغة.
بعد ذلك، يمرsolve_f2l بالحالات بالترتيب من أقصر خوارزمية متوسطة إلى الأطول، ويعود إلى 1 بمجرد أن تقوم الدالة بإرجاع خوارزمية. إذا تم اختبار جميع الحالات دون نجاح، أو بعد 4 حلقات، فسترجع الدالة NULL.

lastlayer.c و lastlayer.h

الملف الذي أفتخر به. لا توجد حلقات عملاقة، ولا أشجار القرار. مجرد الرياضيات الذكية وجداول البحث.

هيكل OL، و PLL

Oll و pll هما مبنيان مخصصان لتخزين OLL و PLLs. يقومون بتخزين الاسم والنمط الذي أستخدمه للتعرف عليهم والخوارزمية لحلها.
في ليلة بلا نوم، اكتشفت أنه يمكنني التعرف على PLL باستخدام ألوان الحلقة الخارجية فقط، وOLL من خلال 12 قيمة منطقية فقط تعني الأصفر، أو ليس الأصفر.

Load_olls() وload_plls()

يقوم Load_olls() وload_pllls() بتحميل الأسماء والأنماط والخوارزميات من ملف CSV. لقد مر هذا ببعض التكرارات.
لقد بدأت أولاً باستخدام getline() للحصول على كل سطر من ملفات CSV، وتقسيم السلسلة إلى 24 حرفًا و36 حرفًا، مع حشو الاسم بمسافات.
لم يكن هذا جميلًا لذا بدأت البحث عن الفواصل وتقسيم الأشياء هناك.
أخيرًا، وجهني أحد الأشخاص الموجودين على الخلاف إلى sscanf() مما سمح لي بتقسيم كل سلسلة بسهولة وسلاسة.
لقد قمت أيضًا بالتبديل إلى fgets() لجعل الخط أكثر توافقًا.
الأسطر التي تبدأ بـ # مرفوضة لأنها تعليقات. يتم التعرف على الخطوط التي لا يكون فيها النمط رقميًا بحتًا باستخدام وظيفة مساعدة تسمى isNumber() أو isBinary() ويتم رفضها، وأثناء كتابة هذا القسم أضفت اختبارًا لمعرفة ما إذا كان الاسم والنمط والخوارزمية بالطول الصحيح أم لا توقف عن القراءة والكتابة.
في مصفوفة olls وplls، يتم إنشاء مساحة للأسماء والخوارزميات باستخدام malloc ويتم نسخ المعلومات باستخدام strncpy. يتم تحويل النمط إلى مصفوفة مكونة من 12 قيمة منطقية أو قيمة منطقية.

find_oll() و find_pll()

Find_pll() هو فخري وسعادتي. كانت أول خوارزمية كتبتها لحل المكعب (قبل الصليب وf2l)، وجاءت لي في المنام. طريقة للتحقق من نمط oll لأي مجموعة ألوان مع بعض العمليات الحسابية البسيطة. لقد استيقظت حرفيًا وكتبت int case[12] containing the outer ring. if (front[0] == (front[1]-(case[0]-case[1])%4)) . وفي اليوم التالي قمت بتبسيطها إلى (faces[0][0] == (faces[0][1] - (plls[i].pattern[0] - plls[i].pattern[1])) % 4) (مرات 12). ثم (faces[j][0] - faces[j][1]) % 4 == (plls[i].pattern[0] - plls[i].pattern[1]) % 4 وأخيرًا بعد العديد من التكرارات انتهى بي الأمر بـ mod((cube[(j + i / 3) % 4][i % 3] + dif[j]), 4) مما يسمح لي بتشفير نمط الطبقة العليا من المكعب باستخدام 12 int مصفوفة, لسهولة المقارنة مع جميع القيم المعروفة.
كان بإمكاني ترميز النمط باعتباره int بحجم 4 بايت، لكنني قررت عدم القيام بذلك لأنني أعتقد أنه من الأفضل جعل الأنماط سهلة الفهم بدلاً من حفظ 44 بايت (إجمالي 3408 كيلو بايت للأنماط)
أخيرًا، تقوم الدالة بإرجاع زوج_int_int يحتوي على اتجاه الطبقة وOLL أو PLL الصحيح. أو رقمين سالبين إذا لم يتم العثور على شيء.

solve_oll() وsolve_pll()

تعتبر الدالتانsolve_oll() وsolve_pll() بسيطة نسبيًا. يسمون find_oll أو pll للحصول على الفهرس الصحيح والاتجاه (مقدار التحركات y). ثم تقوم الدالة بتدوير المكعب باستخدام حركة y، وتشغيل خوارزمية OLL أو PLL الصحيحة، وفي حالةsolve_pll() تقوم بتدوير الطبقة U لحل المكعب أخيرًا. تقوم الدالات بإرجاع الخوارزمية المستخدمة لحل المكعب بتدوين المكعب القياسي.

cleanup_last_layer()

يحرر الذاكرة المستخدمة لتخزين كافة OLLs وPLLs.

utils.c وutils.h

بعض الوظائف لتجعل حياتي أسهل قليلا.

وزارة الدفاع ()

نظرًا لأن % العادي لا يعمل مع الأرقام السالبة، فهذه "النسخة الخاصة بي" هي التي تعمل. مع شكر خاص للخلاف CS50.

make_pair_int_int()

بالنسبة لبعض الوظائف أريد إرجاع أكثر من متغير واحد. يعتمد هذا على زوج C++ وmake_pair(). يقوم بإنشاء بنية ذات مدخلين: الأول والثاني. في هذه الحالة يتم استخدامه لإرجاع رقم oll/pll وحركة U أو y السابقة.

دورة()

دالة تدور حول 4 أرقام. في الأساس خطوة للأعلى من المبادلة. يُستخدم في cube.c لتدوير الحواف والزوايا لتحركات المكعب. توجد نسخة من هذه الخطوة في cube.js

إلحاق ()

دالة تضيف سلسلة نصية إلى سلسلة أخرى، وتعيد تخصيصها إذا لزم الأمر. تستخدم في كل مكان في هذا التطبيق.

isNumber() و isBinary()

التحقق مما إذا كانت السلسلة تحتوي على أرقام فقط، أو أصفار وآحاد فقط. يُستخدم حاليًا فقط لتحميل OLLs وPLLs.

Solver_library.c و cubesolver.h

كتبت لأول مرة Solver.c كواجهة لبرنامج حل المكعبات الخاص بي، ولكن سرعان ما قررت أنني أريد واجهة مستخدم رسومية، وهو ما لست مستعدًا للقيام به بلغة C النقية.
ولهذا السبب بدأت في تحويل المكعبات الخاصة بي إلى مكتبة لاستخدامها مع أي شيء أريده.

يحل()

يجمع كل ذلك معًا لحل المكعب. يأخذ مكعبًا ويتحقق من صحته. ثم يحاول حل الصليب. إذا فشل فإنه يرجع خطأ، وإلا فإنه يخزن الإخراج. ثم يقوم بحل التقاطع أو إرجاع خطأ. ثم يقوم بحل OLL (أو الإرجاعات) وPLL. وأخيراً تقوم بإرجاع سلسلة تحتوي على الحل الكامل.

حل_التدافع ()

واجهة للحل. يُنشئ مكعبًا من التدافع المُدخل ويمرره للحل ()

يثبت()

فقط لجعل حياة الجميع أسهل قليلا. يأخذ مسارًا، ويقوم بتحميل ols وpls من هذا المسار. يُرجع صحيحًا إذا نجح، وينظف بعده ويعيد خطأ إذا لم ينجح.

store_string_pointer()

نظرًا لصعوبة تحرير الذاكرة من لغة Python، فقد قررت أن أفعل ذلك من لغة C. لدي إصدارات "آمنة" من كل وظيفة قد ترغب في استخدامها من خارج لغة C. وتقوم هذه الإصدارات بتخزين المؤشرات التي تم إنشاؤها والتي يجب تحريرها إلى مصفوفة عامة لتحرير الجميع مرة واحدة.

free_strings()

تحرير كافة trings المخزنة

solve_safe() وsolve_scramble_safe() وsolve_cross_safe() وsolve_f2l_safe() وsolve_oll_safe() وsolve_pll_safe()

تقوم الوظائف المتعددة بإرجاع السلاسل التي يجب تحريرها في النهاية. تقوم هذه الوظائف بتخزين المؤشرات إلى هذه السلاسل لحذفها لاحقًا.

حلالا.ج

للاختبار، وأولئك الذين يستخدمون لوحة المفاتيح بشكل أفضل من الماوس، لديهم واجهة طرفية.
لقد تمت إعادة كتابته عدة مرات، وأخيرًا تمت إعادة كتابته أثناء كتابة هذا الملف التمهيدي للعمل مع Solver_library بدلاً من العمل بمفرده.

رئيسي()

يفعل كل شيء! يقوم بتحميل OLLs وPLLs بناءً على الإدخال الافتراضي أو المستخدم. ثم يقوم بإنشاء مكعب بناءً على سطر الأوامر أو إدخال المستخدم، وأخيرًا يحل المكعب خطوة بخطوة، ويطبع المكعب على طول الطريق.

الحصول على دير ()

يحصل على الدليل من مسار ملف محدد (على سبيل المثال argv[0]). مكتوب للعمل مع أنظمة تشغيل Windows وUnix.

color_letter_to_number()

يغير حرف اللون إلى int المقابل. في بايثون استخدمت للتو قاموسًا. طريقة أسهل.

color_face_from_input()

اطلب من المستخدم الألوان التسعة لوجه مكعب روبيك، ويضعها على المكعب.

color_cube_interactive()

واجهة تفاعلية خطوة بخطوة لإدخال الألوان على المكعب.

نص المساعدة ()

طباعة اختبار المساعدة.

الاستخدام ()

يطبع الاستخدام.

امتحان

اختبارات عشوائية. ج

تطبيق قصير بسيط لاختبار الأخطاء. يولد الكثير من التدافع ويحلها. يطبع التدافع الأول الذي يفشل ويتوقف.
لقد استخدمت هذا للعثور على خطأ مطبعي واحد. كل شيء آخر قمت به يدويًا.

التحقق من الحل ()

يستخدم memcmp لمقارنة المكعب الذي تم إخراجه بواسطة خوارزمية الحل مع واحد من المكعبات الأربعة التي تم حلها (واحد لكل اتجاه).
يتاجر في القليل من الذاكرة من أجل السرعة.

إنشاء_التدافع ()

يولد حركات عشوائية لمكعب روبيك. بشكل سيء. لا يحمي من الحركة المزدوجة والحركات العكسية. لكن من الجيد أن يكون التدافع طويلاً بما فيه الكفاية.

رئيسي()

يقوم بتحميل OLLs وPLLs من إدخال المستخدم. يحل المكعب عدة مرات كما يريد المستخدم، حتى يفشل.

بيانات

olls.csv

يحتوي على قائمة بجميع حالات OLL الـ 58 (بما في ذلك التي تم حلها) للاستخدام مع مكتبة C الخاصة بي
خوارزميات من ذاكرتي الخاصة، ومن https://www.speedsolve.com/wiki/index.php/OLL

plls.csv

يحتوي على قائمة بجميع حالات PLL الـ 22 (بما في ذلك التي تم حلها) للاستخدام مع مكتبة C الخاصة بي
خوارزميات من ذاكرتي الخاصة، ومن https://www.speedsolve.com/wiki/index.php/PLL

أنماط.csv

يحتوي على بعض الأنماط لخلط المكعب بطرق جميلة. يُستخدم في الغالب لاختبار جافا سكريبت، ولكنه ميزة رائعة للمستخدم.

أخطاء.txt

نأمل أن لا يحتوي على أي شيء، ولكن المقصود منه تخزين أي وجميع الأخطاء في حل المكعب.

./

app.py

الجسر بين كود C الخاص بي وجافا سكريبت. يقوم بتحميل مكتبة C، ويقوم بتهيئة الوظيفة التي أحتاجها باستخدام أنواع الوسائط وإعادة الكتابة إذا لزم الأمر. استخدام numpy للتحويل من أنواع بايثون إلى أنواع ctypes

تعليق ()

وظيفة "استعرتها" من Stackoverflow. يستغرق دفق الإدخال ويخرج كل سطر يصل إلى #

خطوات ()

الحل الفعلي. فهو يأخذ مكعبًا مشوشًا ويحله خطوة بخطوة، ويعيد الخطوات على شكل مصفوفة من القواميس (تحتوي على مصفوفة تحتوي على خوارزميات). في حالة وجود استثناءات فإنه يخزن النمط في ملف data/errors.txt

واجهة الحل()

تستخدم فقط للاختبار. يأخذ خوارزمية التدافع من GET، ويحلها باستخدام getsteps() ويمررها إلى قالب الحل.

حلالاJSON()

يأخذ نمطًا ويتبارى من GET أو POST، ويحله باستخدام getsteps ويعيده بتنسيق JSON.

ValidatorJSON()

يأخذ نمطًا من GET أو POST ويحل المكعب، دون الاهتمام بالحل الفعلي، ولكن التحقق مما إذا كان قد فشل وأين فشل. إرجاع 0 للنجاح أو رقم الخطأ.

مكعب()

يعرض قالب cube.html: واجهة المستخدم الفعلية. أثناء قيامه بذلك، فإنه يأخذ أيضًا الأنماط من data/patterns.csv لإعطاءها للقالب، باستخدام dictreader وdecomment لإزالة تعليقاتي.

الأيقونة المفضلة ()

يمرر الرمز المفضل إلى المتصفح للحصول على رمز المكعب الجميل.

تنظيف()

يحرر كل الذاكرة من كود C الخاص بي: PLLs والسلاسل. تم التسجيل باستخدام atexit للتشغيل عند الخروج

com.makefile

جميع الأوامر الخاصة بتجميع كود C الخاص بي على Linux أو OS X. على الرغم من أنه يمكن استخدام مكتبتي كمكتبة، فقد قررت استخدام جميع الملفات للتجميع حتى أتمكن من تقديم ملف واحد قابل للتنفيذ.

المتطلبات.txt

يحتوي على المكتبتين اللتين استخدمتهما ويجب تثبيتهما بشكل منفصل. مجرد قارورة وnumpy. لا شيء خاص.

قوالب

Solver.html

يطلب التدافع، ويمرره إلى app.py لحل الحل وطباعته. يستخدم فقط للاختبار السريع.

cube.html

يحتوي على الكثير من divs الفارغة التي سيتم ملؤها بواسطة كود جافا سكريبت الخاص بي، وتشكيلها بواسطة CSS. يحتوي على 3 صور لضوابط التشغيل، ونموذج لإدخال التدافع، وشرح مختصر.
أخيرًا يقوم بتحميل جافا سكريبت لأنه لا شيء بدون dom. ليست جميلة جدًا، ولكنها عملية جدًا.

ثابت

باستثناء src يحتوي على الكود الأكثر واقعية. بعض CSS لجعل كل شيء يبدو قابلاً للاستخدام، وجافا سكريبت لجعله قابلاً للاستخدام بالفعل. وبعض الصور للنقر عليها.

cube.css

يغير رابط divs العشوائي إلى شيء يمكنك رؤيته.
يستخدم شبكات CSS بشكل افتراضي، وبطرق افتراضية أقل.
أستخدم حاوية خارجية لوضع عناصر التحكم على اليسار، والرسوم المتحركة للحل في أعلى اليمين، والحل في أسفل اليمين.
باستخدام الموضع المطلق أضع عناصر التحكم في التشغيل والطحالب الحالية فوق الرسوم المتحركة.
كل شيء آخر افتراضي تمامًا باستثناء منتقي الألوان. إذا نظرت إلى كود html، فإنك ترى فقط div يحتوي على 6 div، كل منها يحتوي على 9 div. باستخدام الشبكات، أقوم بتشكيل أقسام "الوجه" الستة لتبدو وكأنها مكعب غير مطوي، ويحتوي كل وجه على شبكة مكونة من 9 مربعات. يتيح لي هذا إنشاء حجم متغير بينما يظل الشكل كما هو، دون الحاجة إلى استخدام الصور.
لقد أمضيت أيضًا أسبوعًا أو أسبوعين في إنشاء عرض عبر الهاتف المحمول، لأن النص بدا وكأنه بحجم متغير. لقد اتصلت بالخلاف والفيسبوك وحتى Stackoverflow. أخيرًا وجدت سطر html في تدفق المكدس: والذي حل كل شيء في سطر واحد.

cube.js

يجلب الخوارزمية الخاصة بي إلى المستخدم. استنادا إلى three.js
هذه هي المرة الأولى التي أكتب فيها جافا سكريبت. لا يبدو الأمر جميلًا، وربما يخالف جميع القواعد، لكنه يعمل.

لقد قمت بإعادة كتابة هذا الملف عدة مرات. أولًا تكراري، كان ذلك قبل أن أبدأ في التحميل إلى github، ثم وظيفيًا، ثم أخيرًا نوعًا ما موجهًا للكائنات
أولاً، أعلن عن جميع المتغيرات التي يجب استخدامها من قبل أكثر من دالة: المواد والهندسة الخاصة بالكائنات three.js، ومصفوفات تخزين الكائنات، ومحاور الدوران، والمزيد.
يوجد أيضًا قاموس ضخم يحتوي على المتغيرات الضرورية لكل حركة مكعب قانوني: المكعبات المراد تدويرها أو تبديلها، ومحور ودرجات الدوران، وما يجب إظهاره. يمكن أن يتناسب كل هذا مع 72 سطرًا، لكن style50 يريد متغيرًا واحدًا لكل سطر، مما يجعله 649 سطرًا.

منشئ ()

يلتقط المشهد ويحفظ مرجعًا، وينشئ المكعبات والمخططات التفصيلية والمستويات في حلقة، ويضبط مواضع المكعبات والمخططات التفصيلية في الحلقة، والمستويات يدويًا.

دورة_التدوير ()

وظيفة مساعد. قم بتدوير دورات 4 مكعبات a > b > c > d > a باستخدام مكعب مؤقت.

Swap_rotations()

وظيفة مساعد. مبادلة دوران مكعبين باستخدام مكعب مؤقت.

إعادة تعيين_المكعب ()

أعد تعيين المكعبات إلى موضعها الافتراضي وأعد تعيين قسم الحل. هذا يحتاج إلى خطوات أكثر مما تعتقد. نحتاج أولاً إلى إعادة ضبط جميع الرسوم المتحركة وإنهاءها. قم بإعادة ضبط جميع التحركات المستقبلية والماضية، وأخيرًا إعادة ضبط دوران المكعبات.

is_moving()

إرجاع صحيح أو خطأ بناءً على ما إذا كان المكعب يتحرك.

do_move()

يقوم بإعداد الرسوم المتحركة للتحرك على المكعب.
كانت هذه الوظيفة في الأصل مكونة من 160 سطرًا من عبارات if/else، لكنني أعدت كتابتها لاحقًا للحصول على المكعبات والتحركات من قاموس ضخم. وهذا يجعل هذه الوظيفة والوظيفة التالية أسهل في القراءة، ويجعلها كذلك إذا كتبت نسخة 4x4 أو 5x5، فلا يتعين علي سوى تغيير القاموس.

Finish_move()

يكمل الرسوم المتحركة، ويحرك (يدور) المكعبات فعليًا.
نظرًا لأن المكعبات لا تتحرك فعليًا، فإن الفكرة الأساسية هي نسخ دوران المكعب الذي يتحرك في مكانه على المكعب الحقيقي، ثم تدوير كل شيء.
كانت هذه الوظيفة في الأصل عبارة عن 375 سطرًا ضخمًا من عبارات if/else التالية. تمت إعادة كتابته لاحقًا للعمل مع قاموس الحركات.

next_move()

هل الخطوة التالية في قائمة التحركات، أو الخوارزمية التالية في قائمة الخطوات، وتظهر الخوارزمية الحالية على الشاشة.

prev_move()

هل الحركة السابقة تقوم بتحريك القائمة في الاتجاه المعاكس أم الخوارزمية السابقة في قائمة الخطوات

Apply_pattern()

يطبق الألوان من منتقي الألوان (أو في الواقع مجموعة الوجوه) على المكعب عن طريق تدوير كل مكعب. يحتوي على بعض وظائفه الخاصة، كل مكعب لديه خط خاص به مع المعدلات اليدوية. بالنسبة لي، من العشوائي جدًا أتمتة الأمر. ولكن إذا كنت تريد أن تجرب، كن ضيفي.

معاكس_اللون()

يتغير اللون الأخضر إلى الأزرق، والأحمر إلى البرتقالي، والأبيض إلى الأصفر، والعكس. الآن أفكر في الأمر، كان من الممكن أن يكون هذا إملاءً، ولكن سطرًا واحدًا من الرياضيات و3 ifs يعمل أيضًا.

Apply_color()

يقوم بتدوير المكعب بناءً على اللون الأمامي والأيسر، أو اللون لأعلى. في الأساس هناك الكثير من عبارات if التي تحتوي على حركات مشفرة، ولكن هذا يكفي هنا.

run_alg()