שאלה

[Pharell]

שאלה

יש לי לבנות מבני נתונים כדי לטפל בסודוקו הוא צריך לתמוך בפונקצית init בסיבוכיות זמן של 0(1) ובפונקציות Insert בסיבוכיות זמן משוערכת!! של 0(1) חשבתי להשתמש במערך לשורות, מערך לעמודות, מערך לבוקסות האלה ועוד מערך דו מימדי בשביל הכל, וכמו כן להשתמש ב HASH TABLES אבל אני צריך פונקצית ערבול בקיצור הסתבכתי מישהו יכול להדריך אותי קצת?

 

[neko]

מה יעזור לך HASH TABLE?

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

 

[yonyl]

סודוקו הוא בגודל קבוע

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