מחפש אלגוריתם מסוים

[Answer3]

מחפש אלגוריתם מסוים

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

 

[tamarhp]

מנסה לחשוב על רעיון

נחליט על מספר הספרות שנכניס ללוח = N. ניצור לולאה עם מונה שמאותחל ל-0. נבחר רנדומלית תא [j] בלוח, ונבחר רנדומלית ספרה בין 1 ל-9. נפעיל פונקציית חיפוש בשורה, בעמודה ובריבוע. אם הספרה לא מופיעה - נכניס ונעלה את המונה ב-1. אחרת - נפעיל שוב את הבחירה הרנדומלית וכו'. נמשיך עד שהמונה מגיע לN. אני בטוחה שיש דברים יותר יעילים... אבל זה הדבר הראשון שעלה לי לראש...

 

[Answer3]

לא רק את חשבת על זה ...

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

 

[tamarhp]

למה לא עובד?

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

 

[tamarhp]

אם אתה רוצה לוח שלם אז

123456789 456789123 789123456 234567891 567891234 891234567 345678912 678912345 912345678 קלי קלות.

 

[ailag]

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

אם נבחרו רק הספרות 1-7, קחי פתרון חוקי ללוח, החליפי בו כל מופע של 8 ב 9 ולהפך וקיבלת עוד פתרון חוקי ללוח.

 

[tamarhp]

נו? ללוח סודוקו אין פתרון אחד ויחיד.

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

 

[orishal]

יצירת לוח סודוקו

תרשה לי להציע לך דרך אחרת..במקום לחשוב על אלגוריתם שמנסה ליצור סודוקו מכלום תחשוב קודם על דרכים לפתור סודוקו. נניח שיש לך אלגוריתם שכזה שמסוגל לפתור לוח סודוקו, והוא עושה זאת ע"י בדיקת העמודות, השורות, התאים 3X3 וכל תא בפני עצמו.. עכשיו נניח שאתה מנסה לפתור לוח סודוקו, אבל הבעיה שאין בו מספיק נתונים, בשלב מסויים לא תוכל לפתור יותר את הלוח לדוגמה בלוח הזה 000080030 300700100 080006000 006000010 409000508 020000700 000160050 002003009 040050000 גם אם תנסה את כל הדרכים הנ"ל תגלה שבסוף הלוח עדיין לא נפתר זה השלב להתחיל לנחש ערכים, אם תעשה זאת בצורה שיטתית, תראה שהלוח נפתר בצורה מאד מאד מהירה עכשיו ברגע שיש לך אלגוריתם שמסוגל לפתור לוח גם ע"י נסיון של ניחושים, אתה יכול לבחור מספר בודד של ערכים בצורה רנדומילית בצורה שלא תעבור חלילה על כללי הסודוקו, ולתת לתוכנה שלך לפתור את הלוח, ולמעשה גם אם תשאיר לוח ריק אלגוריתם שכזה עדיין אמור לפתור את הלוח שוב דוגמה נניח שהתחלת מלוח ריק ובחרת רנדומלית 5 ערכים ( זה חסר חשיבות כמה ערכים תבחר ) 001000000 000000000 000900000 000000000 500000300 000000000 000000000 000070000 000000000 כל שנותר לך זה להפעיל את האלגוריתם שלך ולפתור את הלוח 371526489 489137256 256948137 142359768 567812394 893764512 714693825 638275941 925481673 בהצלחה

 

[Answer3]

לtamarhp ולorishal

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

 

[orishal]

בעיית סודוקו

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

 

[Answer3]

תודה.

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

 

[tamarhp]

אני נתקלתי בלא מעט סודוקו

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

 

[orishal]

סודוקו

חבל שנתקלת בלוחות כאלו, לסודוקו בהגדרה חייב להיות רק פיתרון אחד http://en.wikipedia.org/wiki/Sudoku תנסי את החלק על בניית סודוקו.. כל הקושי בבנית לוח סודוקו קשה לפתירה זה לדאוג שמצד אחד הוא יהיה קשה מבחינה לוגית , ומצד שני שהיה בעל פיתרון אחד בלבד, וזה דבר שלא קל להשיג..

 

[Answer3]

אוקיי

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