יום ראשון, 8 באוגוסט 2010

MATLAB - הדרך להימנע מהתמכרות ל-Sudoku!

"הרשו לי לפנות את הבמה בפוסט הזה לטובת בלוגר אורח – רוני פאר, אשר עובד יחד עמי בחברת סיסטמטיקס.  רוני מתמחה בכלי The MathWorks לתחומי מערכות הבקרה והמידול הפיסי, וכפי שתגלו – הוא גם חובב סודוקו לא קטן..."

הי אני רוני, ואני מכור לסודוקו.
 

עד לפני כחודש, הייתי משקיע שעות רבות ומאמצים בזמני החופשי, בכדי לפתור את תשבצי הסודוקו בעיתון סוף השבוע. זה היה סיוט. הגעתי למצב שבו עוד לפני הקפה של הבוקר, כבר הייתי שקוע בספרות אחת עד תשע, ומנסה לנחש עוד מיקום נוסף בלוח הזה. הצמחים שלי סבלו מחוסר השקייה, היו לי עיגולים אדומים סביב העיניים, ותזונה לקויה – סבלתי מכל הסממנים של התמכרות קשה.
 

לפני חודש חלה נקודת המפנה. כחלק מעבודתי בחברת סיסטמטיקס, נכנסתי לאתר ה-User Community של MathWorks, ובמקרה גיליתי קובץ MATLAB, אשר פותר את התשבץ! כמובן שהייתי כולי נסער – איך לא חשבתי על זה קודם? הרי MATLAB, מבוססת על מטריצות – כמובן תאפשר פתרון קל ומהיר של האלגוריתם הסבוך הזה. 

הפתרון הראשוני שמצאתי לקח כ-1,000 שניות (או 15 דקות) – כנראה שמי שכתב אותו לא שמע על דרכים להאיץ אלגוריתם של MATLAB. הגרסה השניה והשלישית היו טובות יותר וכותביהן היו מתכנתים טובים יותר, ואפילו תיעדו את הקוד כדי שאוכל להבין מה נעשה – ולשפר אותו. הגרסה הטובה ביותר שמצאתי, הייתה מבוססת על רקורסיה וארכה רק 100 שניות (או דקה וחצי) לפתרון – אכן פתרון מהיר.לא האמנתי – סופסוף אוכל להשקיע את זמני הפנוי בפעולות חיוביות יותר – כמו לטייל עם הכלב או לבלות עם בני הקטן. אגב, אתמול – מצאתי את הגרסה הטובה ביותר – אשר לוקח רק כ-2 שניות להגיע לפתרון, והוא כלל לא מבוסס על רקורסיה.
 


לאלו מכם שעדיין מבזבזים את זמנם - מצורף כאן קובץ הפתרון, אשר הורדתי בחינם מהאתר של MathWorks. תיהנו, ואל תשכחו – MATLAB היא הרבה מעבר לתוכנה שמקצרת את זמן הפיתוח – זו תוכנה שמאפשרת לכם לבלות זמן איכות עם המשפחה והחברים, ונלחמת עבורכם במפלצות יפניות.

נ.ב.
לאלו שלא שמעו על תשבץ זה, להלן עיקריו: דמיינו לוח של 9X9 משבצות. כל משבצת יכולה להכיל אחת מהספרות 1 - 9. המטרה היא למקם ספרות בכל אחת מהמשבצות. החלק הקשה הוא למקם את הספרות כך שלא ייווצר מצב שבו באותה השורה ובאותה עמודה מופיעה אותה הספרה. כמו כן, כל תת-ריבוע של 3X3 משבצות צריך להכיל את כל הספרות (1-9). ולבסוף, בכדי שיהיה מעניין – כל לוח סודוקו מתחיל בכך שישנן מספר משבצות שכבר שובצו בהן ספרות, ויש להשלים את כל היתר. אבל תקשיבו למי שכבר היה שם – אל תתקרבו לזה אם אין לכם רישיון של MATLAB.