שחור ופתור

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לפתרון חידת שחור ופתור

שחור ופתור (Nonogram או Griddler, ביפנית: エデル) הוא חידת היגיון גרפית שבה יש לגלות ציור חבוי בטבלת משבצות לבנה המורכב ממשבצות שצריכות להיצבע על רקע משבצות שצריכות להישאר לבנות.

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

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

שיטות פתרון[עריכת קוד מקור | עריכה]

חפיפה[עריכת קוד מקור | עריכה]

חפיפה-דוגמה 1
חפיפה-דוגמה 2

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

בדוגמה הראשונה ניתן לראות שבין אם "ניישר" את ה-8 עד הסוף שמאלה, ובין אם "ניישר" את ה-8 עד הסוף ימינה, שש המשבצות המרכזיות יהיו תמיד צבועות.

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

שחור ופתור במדעי המחשב[עריכת קוד מקור | עריכה]

בעיית שחור ופתור היא בעיה NP-שלמה[1]. לפיכך אין אלגוריתם פולינומי שפותר את כל בעיות שחור ופתור, אלא אם P = NP. עם זאת, עבור מחלקות מסוימות של חידות, כמו אלו עבורן בכל שורה ועמודה יש רצף יחיד של משבצות שחורות, וכל המשבצות השחורות מקושרות, ניתן למצוא פתרון בזמן פולינומי על ידי רדוקציה לבעית 2-ספיקות[2].

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, TR96-0008, Technical Report, Department of Computer Science, Tokyo Institute of Technology
  2. ^ Brunetti, Sara; Daurat, Alain (2003), "An algorithm reconstructing convex lattice sets", Theoretical computer science 304 (1–3): 35–57, doi:10.1016/S0304-3975(03)00050-1; Chrobak, Marek; Dürr, Christoph (1999), "Reconstructing hv-convex polyominoes from orthogonal projections", Information Processing Letters 69 (6): 283–289, doi:10.1016/S0020-0190(99)00025-3; Kuba, Attila; Balogh, Emese (2002), "Reconstruction of convex 2D discrete sets in polynomial time", Theoretical Computer Science 283 (1): 223–242, doi:10.1016/S0304-3975(01)00080-9.