בזמנו שלמדתי היינו בונים קצת משחקי לוח פשוטים.
לאחר הלימודים הגיע הסודוקו, ויצא לי לחשוב קצת תאורטית על האלגוריתם שפותר אותו. השיטות לפתירת סודוקו מגוונות יחסית ולכן יש כמה בדיקות.
המשימה אומרת כך: האלגוריתם מקבל מטריצה 9X9 של סודוקו סטנדרטי(בכל תא יש מספר 1-9 או מקום ריק). מקום ריק מוגדר כ-"0"(לצורך נוחיות) ומחזיר את הפיתרון של המטריצה.
יש כמה סוגי בדיקות שלפיהן אפשר להתקדם:
1. שלילת ספרות אחרות עבור משבצת\תא (אלימינציה). לדעתי נצטרך לשלב כאן מערך 1-9 עבור כל תא, לנפות ממנו מספרים שלא ייתכנו עבור תא, יהיה משתנה לאורך כל הפיתרון עד קביעת המספר עבור אותו תא. נצטרך להשתמש במערך 1-9 עבור עוד בדיקות. זאת בדיקה חזקה יחסית שצריכה לכלול השוואה לטור, שורה ומטריצה פנימית 3X3.
1.2 בדיקה עבור כל מערך 1-9 של כל תא אשר אומרת: אם יש רק מספר אחד במערך, אז המספר נכנס לתא. (אם זה לא 1,2,3,4,5,6,7,8 אז ערך התא 9).
2. השוואה בין מערכים 1-9 של כל תא במטריצה 3X3 עבור כל המספרים החוקיים (1-9). אם יש מספר כלשהו שלא יימצא באף מערך פרט לאחד, אז נכנס המספר אל התא. עבור תא שקיים בו מספר שונה מאפס אין צורך במערך 1-9. זאת תהיה פונקציה שמקבלת את כל ה-9 מטריצות 3X3 שיש בלוח.
3. תנאי העצירה יגיד כמובן שאם אין אפסים במטריצה(תא ריק)-החזר פתרון (מטריצה פתורה).
4. לגבי מטריצה לא חוקית, לאחר כל הבדיקות האלה להריץ בדיקה נוספת לגבי מספר אפסים (0). אם הוא לא ישתנה (קטן כמובן) אחרי כל הבדיקות אז הרי המטריצה שהתקבלה לא חוקית. עדיף שיהיה כפונקציה ראשונה האמת.
אני לא נזכר בעוד בדיקות נוספות כרגע, במידה ויש תרשמו את אופי הבדיקה והרעיון.
אפשר להריץ בדיקה עבור כל אחד מהדברים האלה בשפות הנ"ל בלי בעייה יחסית.
אני רוצה רק אלגוריתם בשביל לראות איך זה מתבצע ולא את התוכנה כתובה. יש עדיפות לשפת C אם כבר.