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