עזרה | אלגוריתם ליצירת סודוקו ב C שלא עובד

[yosefor]

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

האלגוריתם:

1. בחר משבצת במבוך באופן אקראי.

2. אם המשבצת ריקה - בחר מספר באופן אקראי. אחרת - חזור על פעולה מס' 1.

3. נסה להציב את המספר האקראי במשבצת האקראית שנבחרה. אם לא חוקי להציב את המספר במשבצת שנבחרה, חזור על פעולה מספר 2.

4. אם הלוח לא למלא, חזור לפעולה מס' 1.

הנה קטע הקוד שאחראי על יצירת הסודוקו באופן אקראי:

typedef struct
{
  int number;
  int color;
}  square;

int legal(int x, int y, int number)
{
  int i, j;

  for(i = 0 ; i<9 ; i++)
    if(table[y][i].number == number)
      return 1;

  for(i = 0 ; i<9 ; i++)
    if(table[i][x].number == number)
      return 1;

  int squarex = x/3;
  int squarey = y/3;

  for(i = 0 ; i<3 ; i++)
    for(j = 0 ; j<3 ; j++)
      if(table[squarey*3+i][squarex*3+j].number == number)
        return 1;

  table[y][x].number = number;

  return 0;  
}

int full()
{
  int i, j;

  for(i = 0 ; i<9 ; i++)
    for(j = 0 ; j<9 ; j++)
      if(table[i][j].number == 0)
        return 1;

  return 0;
}

void empty()
{
  int x, y, result;

  for(y = 0 ; y<9 ; y++)
    for(x = 0 ; x<9 ; x++)
    {
      table[y][x].number = 0;
      table[y][x].color = 0;
    }

  do
  {
    do
    {
      x = rand()%9;
      y = rand()%9;
    }
    while(table[y][x].number != 0);

    do
      result = legal(x, y, rand()%9+1);
    while(result != 0);
  }
  while(full() != 0);
}

המבנה square מייצג משבצת אחת. השדה number מייצג את המספר שבמשבצת, והשדה color מייצג אם המספר נכתב מהמחשב או מהמשתמש (0 - שחור, מהמחשב, 1 - אדום, המשתמש הזין את המספר והוא יכול למחוק אותו בהמשך).

יש מערך של 9 על 9 מבני square שמייצג את הסודוקו עצמו.

לאחר שהסודוקו יושלם, אני אריץ פונקציה שתמחק חלק מהמספרים (ותהפוך את השדה color שלהם ל 1) וככה יווצר לי סודוקו מושלם ואקראי מריצה לריצה שהמשתמש יוכל לפתור.

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

יכול להיות שהאלגוריתם לא עובד טוב ואני עלול להגיע לשגיאה וללולאה אין-סופית ?

יש איזה סבירות שאני אגיע למצב הבא ?

אני אשמח מאוד לעזרה.

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

תודה על כל עזרה,

יוסף אור

[Zelig]

זה יעזור לך.

http://norvig.com/sudoku.html

[שניצל]

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

כשחושבים על נכונות/יעילות של אלגוריתמים, חושבים על ה-worst case scenario - מה הקלט הכי גרוע שאני יכול לקבל. אם אני לא מסוגל להתמודד איתו - אז הקוד לא טוב. כמובן, אני יכול להניח שה-worst case scenario הזה לא סביר (לדוגמה, שהפונקציה rand תמיד תחזיר 0) ואז אפשר להחליט מראש לא להתמודד עם מקרה כזה.

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

חוץ מזה, כמה טיפים קטנים לגבי הקוד שלך:

1. מומלץ תמיד לעטוף את הגוף של if/for/while בסוגריים מסולסלים, גם אם התוכן הוא רק שורה אחת. זה יכול למנוע טעויות בעתיד, ולפעמים יותר קריא (לדוגמה, קצת קשה להבין את לולאת ה-do/while בסוף של הפונקציה empty).

2. ב-C (ובהרבה שפות תכנות אחרות, כולל שפת מכונה) ערך 0 מייצגת שקר, וכל ערך אחר (ובפרט 1) מייצג אמת. אתה עשית בדיוק ההיפך. אחת הסיבות לעשות ככה היא שאז אתה יכול להשתמש באופרטורים לוגיים בצורה נכונה, לדוגמה בשביל להמשיך לעבוד כל עוד הלוח אינו מלא, אפשר לעשות ככה:

while (!full())

וזה יותר ברור למי שקורא את הקוד.

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

4. עדיף להימנע ממשתנים גלובליים (table). היה עדיף אם היית מעביר את המשתנה כפרמטר נוסף לכל הפונקציות.

[yosefor]

תודה רבה על התגובה :-)

באמת אני רואה שטעיתי - ובגדול. האלגוריתמים האלו אף פעם לא פשוטים.

בנוגע לטיפים שהבאת לי:

1. באמת רעיון טוב, אפילו יישמתי אותו. אני מעריך שהקוד שלי קצת יותר קריא עכשיו...

2. בדרך כלל ב main ערך מוחזר 0 אומר שהתוכנית פעלה כשורה, ו 1 אומר שארעה תקלה. זה מה שמבלבל אותי, אני פשוט לא מצליח לשנות את זה. התרגלתי לכתוב בצורה לא נכונה, וקצת קשה לי לשנות הרגל זה.

3. אני לא דובר אנגלית. תרגום גוגל לא תמיד מספיק טוב ;-)

4. במקרה הזה באמת לא הייתי צריך משתנה גלובלי, כיוון שאני לא צריך להעביר ממש מצביעים. בד"כ אני משתמש למבנים בתור משתנים גלובליים.

תודה רבה על העזרה.

אני מקווה שאצליח לפתור את האלגוריתם...

צהריים טובים,

יוסף אור

[שניצל]

2. בדרך כלל ב main ערך מוחזר 0 אומר שהתוכנית פעלה כשורה, ו 1 אומר שארעה תקלה. זה מה שמבלבל אותי, אני פשוט לא מצליח לשנות את זה. התרגלתי לכתוב בצורה לא נכונה, וקצת קשה לי לשנות הרגל זה.

צודק, ובאמת יש פה בעיה עם הקונבנציה.

הקדמה קצרה: במחשבים, יש טיפוס נתונים שנקרא בוליאן (boolean). לטיפוס הזה יש בדיוק שני ערכים - "אמת" ו"שקר". יש שפות תכנות שבהן זהו טיפוס נתונים בפני עצמו (כמו שיש int/char/float), ויש שפות (כמו C ושפת מכונה) שבהן הוא מיוצג ע"י int, באופן שציינתי קודם - 0 מייצג "שקר", וכל ערך אחר (כולל 1, אבל לא רק) מייצג אמת. הדבר הזה מאפשר לנו להשתמש בפעולות לוגיות על משתנים מטיפוס int - פעולות ! ("לא"), && ("וגם)" ו-|| ("או").

ועכשיו לנושא: full היא פונקציה שעונה על השאלה "האם הלוח מלא?". לשאלה כזו יש רק שתי תשובות אפשריות - "אמת" או "שקר". לכן, ערך ההחזרה שלה הוא בוליאני. כיוון שכאמור ב-C אין כזה טיפוס, אז אנחנו משתמשים ב-int, עם הקונבנציות של שקר=0, ואמת=כל דבר אחר. אם היינו משתמשים בשפה שבה קיים טיפוס boolean (לדוגמה ++C#, C או Java) אז ערך ההחזרה של full היה מהטיפוס הזה.

main, לעומת זאת, לא מחזירה תשובה לשאלה "האם התוכנית הצליחה" (שהיא תשובה בוליאנית), אלא היא מחזירה תשובה לשאלה "איזו שגיאה קרתה במהלך ריצת התוכנית". כקונבנציה, ערך 0 מציין "לא קרתה שום שגיאה", בעוד ששאר הערכים האפשריים מציינים סוגי שגיאות אפשריים (שהם נתונים להחלטתך). לדוגמה, אתה יכול להחליט שאם המשתמש הזין קלט לא נכון אז main תחזיר 1, אם המשתמש היה צריך להזין שם של קובץ אבל הקובץ לא קיים אז main תחזיר 2, וכן הלאה.

כשאתה כותב פונקציה, אתה צריך לחשוב - האם הפונקציה מחזירה תשובה בוליאנית או לא, והאם אתה מתכנן להשתמש בתוצאה של הפונקציה כביטוי לוגי (כלומר, אתה מתכנן להזין אותה ל-if/while/for או להפעיל עליה פעולות לוגיות). בכל מקרה, הכי חשוב הוא לתעד דבר כזה (לרשום בהערות בתחילת הפונקציה בדיוק מה מציינים ערכי ההחזרה שלה).

[yosefor]

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

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

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

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

הפונקציה שאחראית על יצירת האלגוריתם פשוטה במיוחד:

typedef struct
{
  int number; /* >= 1 && <= 9 */
  int color; /* (אפס מודיע שהמספר נכתב באלגוריתם ולא הוכנס מהמשתמש, ואחד מודיע שהמשתמש הזין את המספר (המשתמש יוכל למחוק את המספר */
}  square;

void CreateSudoku(square table[9][9])
{
  int i, j, result;

  /* איפוס המערך מערכי 'זבל' לאפס */
  for(i = 0 ; i<9 ; i++)
  {
    for(j = 0 ; j<9 ; j++)
    {
      table[i][j].number = 0;
      table[i][j].color = 0;
    }
  }

   /* מאפשר מספרים אקראיים מריצה לריצה */
  srand(time(NULL));

  /* אתחול השורה הראשונה, שתועתק בצורה קבועה לשאר הלוח */
  for(i = 1 ; i<10 ; i++)
  {
    do
    {
      result = rand()%9;
    }
    while(table[0][result].number != 0);

    table[0][result].number = i;
  }

  for(i = 0 ; i<3 ; i++)
  {
    /* אתחול שלושת השורות הראשונות */

    table[2][i] = table[1][6+i] = table[0][3+i];
    table[2][6+i] = table[1][3+i] = table[0][i];
    table[2][3+i] = table[1][i] = table[0][6+i];
  }

  for(i = 0 ; i<3 ; i++)
  {
    /* אתחול ששת השורות הנותרות */

    table[i+6][0].number = table[i+3][2].number = table[i][1].number;
    table[i+6][3].number = table[i+3][5].number = table[i][4].number;
    table[i+6][6].number = table[i+3][8].number = table[i][7].number;

    table[i+6][1].number = table[i+3][0].number = table[i][2].number;
    table[i+6][4].number = table[i+3][3].number = table[i][5].number;
    table[i+6][7].number = table[i+3][6].number = table[i][8].number;

    table[i+6][2].number = table[i+3][1].number = table[i][0].number;
    table[i+6][5].number = table[i+3][4].number = table[i][3].number;
    table[i+6][8].number = table[i+3][7].number = table[i][6].number;
  }

  /* מחיקת 50 תאים ממערך הסודוקו */
  for(result = 0 ; result<45 ; result++)
  {
    do
    {
      i = rand()%9;
      j = rand()%9;
    }
    while(table[i][j].number == 0);

    table[i][j].number = 0;
    table[i][j].color = 1;
  }
}

אני מניח שדרך ההערות אפשר להבין פחות או יותר את האלגוריתם, למרות זאת:

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

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

ד.א

הקוד המלא של הסודוקו נמצא אצלי (ב SDL), למקרה (שלא יקרה מן הסתם) שמישהו יתעניין בו.

בכל מקרה, תודה רבה על כל העזרה :-)

שבת שלום ומבורך,

יוסף אור