שחור ופתור

שחור ופתור (Nonogram או Griddler, ביפנית: 絵かきロジック היגוי: ekaki-rojiku כלומר "ציור הגיון") היא חידת היגיון גרפית שבה יש לגלות ציור חבוי בטבלת משבצות לבנה על ידי השחרה של חלק מהן.
בראש כל טור ושורה של הטבלה, רשומות סדרות של מספרים המייצגים רצפים של משבצות צבועות באותו הטור או באותה השורה, בסדר הנתון. לדוגמה- "1 3 6" בראש שורה (ראו שורה שמינית מלמטה בדוגמה משמאל) משמעו שיש בטור שלושה רצפים נפרדים של משבצות שצריכות להיצבע, רצף אחד של שש משבצות, אחריו אך במרחק לא ידוע ממנו, רצף נוסף של שלוש משבצות ולאחריו משבצת צבועה אחת ואחרונה לשורה זו. הפתירה נעשית על ידי הצלבה של הטורים והשורות.
ישנם מספר סוגים לחידה זו, למשל תשבץ שחור לבן לעומת תשבץ צבעוני. בתשבץ שחור לבן חייב להיות רווח של לפחות משבצת אחת בין כל קבוצה מושחרת, ובתשבץ הצבעוני שתי קבוצות בצבעים שונים יכולות להיות סמוכות זו לזו. משבצותיהם של חלק מהתשבצים עשויות ממשולשים, כך שכל משבצת צריכה לענות על התנאים שקובעות שלוש סדרות של מספרים, לעומת שתי סדרות של מספרים המשפיעות על משבצות ריבועיות. חידה דומה ומעט מורכבת יותר, היא הטרידלר, המורכבת ממשולשים. חידה זו פותרים תוך הצלבה של 3 צדדים, לעומת ההצלבה בין 2 כיוונים בשחור ופתור הרגיל.

שיטות פתרון

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

חפיפה

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

פיסוק

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

כספית

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

רקורסיה עמוקה יותר

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

מספר רב של שורות

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

פתרונות מרובים

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

שחור ופתור במדעי המחשב

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