ABA


"אלגוריתם לפתירת SUDOKU, תהנו :)"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #12277 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 12277
Ice Cold  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק
   10:17   07.07.05   
אל הפורום  
  אלגוריתם לפתירת SUDOKU, תהנו :)  
 
עכשיו נראה כמה SOLVERS יוציאו

http://www.eddaardvark.co.uk/sudokusolver.html


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

  האשכול     מחבר     תאריך כתיבה     מספר  
  תודה :) Zvikadori 07.07.05 11:56 1
  תודה Tamirrr 07.07.05 14:39 2
  תודה רבה... jossepe_4u  07.07.05 18:15 3
  תודה רבה, אבל מה שאני מחפש עכשיו זה אלגוריתם ליצירה של לוח. יש לך? bizho 07.07.05 20:00 4
     בבקשה: Ice Cold  08.07.05 01:44 5
         תודה. :) bizho 08.07.05 12:44 7
  תתפלא, אבל כשקיבלתי לוח קשה במיוחד kobituashi 08.07.05 11:52 6
     באלגוריתם יש גם שלב שלישי boynet 09.07.05 09:23 8
     זה לא קשור למזל - זה קשור לניחושים למציאה אם יש סתירה ScOrPiOn-m1  10.07.05 13:16 12
  כמה מחשבות על סודוקו dryice 09.07.05 18:19 9
     תאכלס אם לא אכפת לך ממש מיעילות של המחשב ScOrPiOn-m1  10.07.05 13:15 11
         במימוש זהיר זה יוצא ממש מהיר. dryice 10.07.05 21:53 13
             איזה משהו קצר? bizho 10.07.05 22:48 14
             סתם שאלה ... איך אתה עומד את הזמן שלוקח לו לבצע את ScOrPiOn-m1  11.07.05 12:08 15
                 אתה פשוט bizho 11.07.05 13:51 16
  זה התוכנה שבניתי עם שינויים קלים : (SODUKO SOLVER 1.0 ) ScOrPiOn-m1  10.07.05 13:11 10
  תודה! uriguron 14.07.05 01:00 17
  כתבתי את כל התוכנה +חלק 1 +חלק 2!!! ttak 14.07.05 14:07 18

       
Zvikadori
חבר מתאריך 3.8.02
5369 הודעות
   11:56   07.07.05   
אל הפורום  
  1. תודה :)  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Tamirrr

   14:39   07.07.05   
אל הפורום  
  2. תודה  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
jossepe_4u 
חבר מתאריך 18.3.02
258 הודעות
   18:15   07.07.05   
אל הפורום  
  3. תודה רבה...  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   20:00   07.07.05   
אל הפורום  
  4. תודה רבה, אבל מה שאני מחפש עכשיו זה אלגוריתם ליצירה של לוח. יש לך?  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Ice Cold  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק
   01:44   08.07.05   
אל הפורום  
  5. בבקשה:  
בתגובה להודעה מספר 4
 
http://www.pro.or.jp/~fuji/java/puzzle/numplace/makesudoku/sudoku01.html.en


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   12:44   08.07.05   
אל הפורום  
  7. תודה. :)  
בתגובה להודעה מספר 5
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
kobituashi לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 18.3.02
6186 הודעות, 1 פידבק
   11:52   08.07.05   
אל הפורום  
  6. תתפלא, אבל כשקיבלתי לוח קשה במיוחד  
בתגובה להודעה מספר 0
 
   של סודוקו, הלכתי לאקסל ובניתי כזה דבר.

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
boynet

   09:23   09.07.05   
אל הפורום  
  8. באלגוריתם יש גם שלב שלישי  
בתגובה להודעה מספר 6
 
   הוא אמר שאת רוב הלוחות תצליח לפתור בשלב השני
אבל יש כאלה לוחות שחייבים להמר
הוא הסביר שם


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ScOrPiOn-m1 
חבר מתאריך 26.11.10
7 הודעות
   13:16   10.07.05   
אל הפורום  
  12. זה לא קשור למזל - זה קשור לניחושים למציאה אם יש סתירה  
בתגובה להודעה מספר 6
 
   ולחזרה למקום של ההצבה

המילה ניחוש לא מתאימה


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   18:19   09.07.05   
אל הפורום  
  9. כמה מחשבות על סודוקו  
בתגובה להודעה מספר 0
 
   אם פותרים בעזרת מחשב אני לא רואה צורך בחוקי היסק לוגי רציניים,
משום שהעלות של ניחוש היא מאוד מצומצמת.
אפשר לפשט את השיטה המתוארת לעיל, להכיל רק את השלב הראשון
ולהשתמש בניחושים וback-tracking ונקבל תוצאות ללא קושי.
מחשבים לכל משבצת את כל האפשרויות ומנסים לנחש איפה שיש הכי מעט אפשרויות
(בפרט אפשרות אחת זה מצוין). בסתירה חוזרים אחורנית. אני לא רואה צורך
בחוקי היקש מסובכים יותר.

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

ודוגמא למקרה יותר מורכב, אם יש לנו בשורה אחת תאים עם הערכים האפשריים:
1,5
5,3
1,5,3
אזי הערכים 1,5,3 לא יכולים להופיע בשום מקום אחר באותה שורה וניתן לסלקם.

אם משתמשים גם בכלל זה בנוסף ל2 שהוצגו במסמך לעיל אפשר לפתור גם לוחות
קשים למדיי ללא ניחושים, אבל כאמור זה ממש לא הכרחי במימוש בעזרת מחשב,
אלגוריתם דיי נאיבי של best-first-search פותר גם לוחות קשים בשבריר שנייה על מחשב בייתי.

DRYICE


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ScOrPiOn-m1 
חבר מתאריך 26.11.10
7 הודעות
   13:15   10.07.05   
אל הפורום  
  11. תאכלס אם לא אכפת לך ממש מיעילות של המחשב  
בתגובה להודעה מספר 9
 
   מספיק להשתמש בשלב ראשון ובניחושים (באק-טראק) - שלב שלישי...


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   21:53   10.07.05   
אל הפורום  
  13. במימוש זהיר זה יוצא ממש מהיר.  
בתגובה להודעה מספר 11
 
   אני כתבתי משהוא קצר בC ועל הlap top שלי זה פותר לוח בבין 3 ל 7 מילישניות. ואני מניח שחלק גדול מזה זה הזמן שלוקח לקלט פלט של הלוח/תוצאה.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:48   10.07.05   
אל הפורום  
  14. איזה משהו קצר?  
בתגובה להודעה מספר 13
 
   השלב של הניחושים, או הפתרון הלוגי?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ScOrPiOn-m1 
חבר מתאריך 26.11.10
7 הודעות
   12:08   11.07.05   
אל הפורום  
  15. סתם שאלה ... איך אתה עומד את הזמן שלוקח לו לבצע את  
בתגובה להודעה מספר 13
 
   העיבוד עד לפלט ... יש פונקציה כזאת במהדר ?
או שזה סתם ניחוש שלך ?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   13:51   11.07.05   
אל הפורום  
  16. אתה פשוט  
בתגובה להודעה מספר 15
 
   מוצא את הזמן שבו התוכנית התחילה (יש API של וינדוס שעושה את זה, אני מניח שיש גם ספרייה סטנדרטית ב++C/C שעושה את זה). מחשב הכל, ובסוף התוכנית אתה לוקח את הזמן הנוכחי ומחסר.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ScOrPiOn-m1 
חבר מתאריך 26.11.10
7 הודעות
   13:11   10.07.05   
אל הפורום  
  10. זה התוכנה שבניתי עם שינויים קלים : (SODUKO SOLVER 1.0 )  
בתגובה להודעה מספר 0
 
   לא הכרתי את האתר שפירסמת, אז מחשיבה אישית שלי :
עשיתי את השלב הראשון ואת השלב השני, אבל עשיתי קצת שונה ( בלי רישומים של כל המספרים באותה משבצת) ושלב ראשון ושני פותרים אותו הדבר כמו כאן

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
uriguron

   01:00   14.07.05   
אל הפורום  
  17. תודה!  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ttak

   14:07   14.07.05   
אל הפורום  
  18. כתבתי את כל התוכנה +חלק 1 +חלק 2!!!  
בתגובה להודעה מספר 0
 
   בערב אני יכתוב את חלק 3 ויפרסם פה את התוכנה!
נ.ב.הכול עובד פרפקט עד עכשיו ואין בגים


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net