בעיה בתכנית לפתירת סודוקו

[Jaman]

בתור תרגול עצמי החלטתי לכתוב תכנית שתפתור סודוקו.

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

הרעיון הוא להתחיל מזה שבכל משבצת ריקה יכולים להיות הערכים 1..9.

א"כ עוברים על הלוח, וכל פעם שמגיעים למשבצת מסויימת שידועה לבטח - לעבור על כל השורה, הטור, והריבוע שמכיל אותה, ולמחוק את האפשרות בכל המשבצות האחרות לקבלת אותו ערך כמו שלה. אם במהלך מחיקות הערכים מתקבלת משבצת בטוחה - להפעיל רקורסיבית את פונקצית המחיקה.

הכל טוב ויפה, אבל משום מה, מה שכתבתי לא עובד בפועל .

אשמח אם מישהו יעבור על התוכנית ויעזור לי למצוא את הבעיה.

הצלחתי לצמצם את מקור הבעיה לפונקצית העזר remove_options, כך שאין צורך להתעמק בפונקציות שמעליה.

תודה לעוזרים .

[attachment deleted by admin]

[שניצל]

נראה לי שיש לך באג כאן:

for (int i = BigSquareX*board_size_sqrt; i < board_size_sqrt*x; i++)
{
	for (int j = BigSquareY*board_size_sqrt; j < board_size_sqrt*y; j++)
	{

נניח, אתה צריך לכפול ב-BigSquareY+1 במקום ב-y.

חוץ מזה, תהייה לגבי הפונקציה two_to_the_power_of_n - למה לא עשית פשוט

1<<n

וזהו?

[Jaman]

חוץ מזה, תהייה לגבי הפונקציה two_to_the_power_of_n - למה לא עשית פשוט

1<<n

וזהו?

לא יודע , זו בערך הפעם הראשונה שאני שימוש ב bitwise operations, כך שאין לי הרבה נסיון עם זה.

נראה לי שיש לך באג כאן:

for (int i = BigSquareX*board_size_sqrt; i < board_size_sqrt*x; i++)
{
	for (int j = BigSquareY*board_size_sqrt; j < board_size_sqrt*y; j++)
	{

נניח, אתה צריך לכפול ב-BigSquareY+1 במקום ב-y.

צודק, זו בדיוק הבעיה. בגללה גם הקומפילר הודיע לי בסיום התוכנית שה stack around the array "board" is corrupted.

עכשיו כפי שחששתי - עושה רושם שהאלגוריתם הזה לא יכול לפתור את כל הלוח, וגם כשאני מריץ אותו בלולאה 100 פעמים הוא מגיע לגבול מסויים של משבצות שהוא יכול למצוא.

ככל הנראה אצטרך לכתוב בנוסף לו אלגוריתם שבודק עבור כל משבצת אם היא היחידה שיכולה להיות מספר מסויים מכל השורה/טור/ריבוע שלה, ולשלב בינהם בצורה חכמה (בסה"כ אני משתמש בשילוב של שתי הדרכים האלו לפתירת סודוקו באמת, כך שזה צריך לעבוד לפחות בשביל סודוקו בינוני וקל).

תודה על העזרה , אני אעלה את התוכנית מחדש כשהיא תהיה מוכנה ותעבוד טוב.