Roomshade · خوراک اندیشه

چهار قاعده‌ای که در هم قفل می‌شوند

هر پازل Roomshade بر چهار قید استوار است که دست‌به‌دست هم می‌دهند تا یک راه‌حلِ یگانه و گریزناپذیر پدید آورند.

به انگلیسی نوشته و ویرایش شده است. این نسخهٔ فارسی با ترجمهٔ ماشینی تهیه شده است؛ هر جا دقت اهمیت دارد، متن اصلی انگلیسی معتبر است. خواندن متن اصلی به انگلیسی ←

معماریِ قید

هر پازل Roomshade با شبکه‌ای خالی آغاز می‌شود که خط‌های پررنگ آن را به اتاق‌های مستطیلی بخش کرده‌اند. برخی اتاق‌ها عددی دارند و برخی دیگر خالی می‌مانند. کار بازیکن این است که در هر اتاقِ عددنشان دقیقاً به همان شمار خانه را سایه بزند و هم‌زمان سه قید دیگر را که در سراسر تخته گسترده‌اند رعایت کند. این چهار قاعده — شمارِ هر اتاق، محدودیت مجاورت، الزام پیوستگی، و حدِ گسترهٔ خطی — جدا از هم کار نمی‌کنند. آن‌ها سامانه‌ای درهم‌قفل می‌سازند که در آن برآورده کردن یک قاعده اغلب شرایط لازم برای برآورده کردن قاعده‌ای دیگر را فراهم می‌کند، و نقض هر یک از آن‌ها پازل را باطل می‌سازد. ³ ¹

ظرافت این طراحی در آن است که هر قاعده چگونه بقیه را مقید می‌کند. قاعدهٔ شمارِ هر اتاق به‌صورت محلی عمل می‌کند و تنها بر خانه‌های درون مرزهای یک اتاق حکم می‌راند. قاعدهٔ مجاورت نیز محلی است اما میان اتاق‌های همسایه پیوند برقرار می‌کند. قاعدهٔ پیوستگی سراسری عمل می‌کند و می‌خواهد که تمام ناحیهٔ سفید یک مسیر پیوستهٔ واحد بسازد. قاعدهٔ گسترهٔ خطی در امتداد خط‌های راستی عمل می‌کند که ممکن است از چند اتاق بگذرند. این قیدها با هم پازلی می‌آفرینند که در آن استنتاج‌های محلی به نتیجه‌های سراسری سرریز می‌کنند، و راه‌حل نه از حدس زدن بلکه از دریافتنِ این نکته سر برمی‌آورد که قاعده‌ها چگونه در هم قفل می‌شوند تا هر احتمالی جز یکی را حذف کنند. ³

چهار قاعده، یک راه‌حل.

قاعدهٔ شمارِ هر اتاق

نخستین قاعده، که بی‌درنگ به چشم می‌آید، می‌گوید اتاقی که عددی دارد باید دقیقاً همان شمار خانهٔ سایه‌خورده در خود داشته باشد. این سازوکار اصلیِ سرنخ در پازل است؛ همان اطلاعاتی که بازیکن دربارهٔ درونِ هر اتاق دریافت می‌کند. اتاقی به اندازهٔ سه خانه با سرنخ دو، دقیقاً به دو خانهٔ سایه‌خورده و یک خانهٔ سفید نیاز دارد. اتاقی به اندازهٔ شش خانه با سرنخ سه، سه خانهٔ سایه‌خورده و سه خانهٔ سفید می‌خواهد. اتاقِ بی‌برچسب چنین قیدی را تحمیل نمی‌کند، هرچند قاعدهٔ مجاورت همچنان سقفی برایش می‌گذارد: می‌تواند از صفر خانهٔ سایه‌خورده تا بیشترین شماری که خانه‌هایش بدون تماس دو تای آن‌ها برمی‌دارند در خود جای دهد، که برای یک مستطیل نصف خانه‌هایش گرد شده به بالاست. ³

این قاعده به‌تنهایی برای حل بیشتر پازل‌ها کافی نیست. برای نمونه، اتاقی 3×2 با سرنخ دو می‌تواند دو خانهٔ سایه‌خورده‌اش را به پانزده شیوهٔ متفاوت بچیند. این قاعده اطلاعات محلی می‌دهد اما ابهامی چشمگیر بر جای می‌گذارد. با این همه، دقیقاً همین ابهام است که قاعده‌های دیگر آن را برطرف می‌کنند. قاعدهٔ مجاورت، قاعدهٔ پیوستگی و قاعدهٔ گسترهٔ خطی هر یک چیدمان‌هایی را حذف می‌کنند که زیر قاعدهٔ شمارش به‌تنهایی مجاز می‌بودند. قاعدهٔ شمارش صحنه را می‌چیند؛ قاعده‌های دیگر تعیین می‌کنند کدام بازیگران اجازهٔ ظاهر شدن دارند. ³

محدودیت مجاورت

قاعدهٔ دوم هرگونه مجاورتِ ضلعی میان دو خانهٔ سایه‌خورده را ممنوع می‌کند. دو خانهٔ سایه‌خورده هرگز نباید در یک ضلع مشترک باشند؛ تنها می‌توانند از گوشه با هم تماس داشته باشند. این قاعده الزامی برای فاصله‌گذاری می‌آفریند که از مرزهای اتاق‌ها هم عبور می‌کند. وقتی خانه‌ای سایه می‌خورد، بی‌درنگ سایه زدن به همسایه‌های هم‌ضلعش را ممنوع می‌کند، فارغ از اینکه آن همسایه‌ها به همان اتاق تعلق داشته باشند یا به اتاقی مجاور. این کار اثری موج‌گونه پدید می‌آورد: سایه زدن به یک خانه می‌تواند امکان‌ها را در اتاق‌های همسایه حذف کند، و این به نوبهٔ خود می‌تواند خانه‌های دیگری را ناگزیر سایه‌خورده یا سفید کند. ¹

قاعدهٔ مجاورت وقتی با قاعدهٔ شمارِ هر اتاق ترکیب شود به‌ویژه نیرومند است. اتاقی 1×3 با سرنخ دو را در نظر بگیرید. دو خانهٔ سایه‌خورده نمی‌توانند پهلوبه‌پهلو بنشینند، پس باید دو سرِ اتاق را بگیرند و خانهٔ میانی باید سفید بماند: قاعدهٔ شمارش تعیین می‌کند چند تا، و قاعدهٔ مجاورت تعیین می‌کند کدام‌ها. برعکس، اتاقی را در نظر بگیرید که تنها یک خانه‌اش می‌تواند سایه بخورد. قاعدهٔ مجاورت محدود می‌کند که کدام خانه‌ها در اتاق‌های همسایه می‌توانند سایه بخورند، چون سایه زدن به خانه‌ای مجاورِ آن تک‌خانهٔ سایه‌خورده قاعده را نقض می‌کند. همین هم‌کنشی میان قاعدهٔ شمارش و قاعدهٔ مجاورت است که بخش بزرگی از استنتاج پازل از آن آغاز می‌شود. ³

سایه زدن به یک خانه، همسایه‌های هم‌ضلعش را ممنوع می‌کند.

الزام پیوستگی

قاعدهٔ سوم می‌خواهد که همهٔ خانه‌های سفید یک ناحیهٔ واحدِ پیوسته از راه اضلاع بسازند. یعنی از هر خانهٔ سفید بتوان تنها با حرکت ضلع‌به‌ضلع از میان خانه‌های سفید به هر خانهٔ سفید دیگری رسید. این قاعده به‌صورت سراسری در سراسر تخته عمل می‌کند و همین آن را به یکی از نیرومندترین قیدهای بازی بدل می‌سازد. این قاعده جلوی تکه‌تکه شدن ناحیهٔ سفید به جیب‌های جداافتاده را می‌گیرد، اتفاقی که در غیر این صورت می‌تواند وقتی حلقه‌ای از خانه‌های سایه‌خورده جیبی از خانه‌های سفید را از بقیهٔ تخته حصار می‌کند رخ دهد. ³

قاعدهٔ پیوستگی به‌ویژه در مراحل پایانی حل پازل حیاتی می‌شود، آنجا که وضعیت بیشتر خانه‌ها روشن شده و پرسش باقی‌مانده این است که آیا خانه‌های سفید ناحیه‌ای پیوستهٔ واحد می‌سازند یا نه. این قاعده می‌تواند برخی خانه‌ها را ناگزیر سفید کند، حتی آنجا که قاعدهٔ مجاورت اجازهٔ سایه خوردنشان را می‌دهد. برای نمونه، اگر سایه زدن به خانه‌ای معیّن گروهی از خانه‌های سفید را از بقیهٔ تخته جدا بیندازد، آن خانه باید سفید باشد. این قاعده تصمیم‌های محلی را به پیامدهای سراسری بدل می‌کند و از بازیکن می‌خواهد در حالی که تک‌تک خانه‌ها را تعیین می‌کند، آگاهی خود را از ساختار سفیدِ کل تخته حفظ کند. ³

حدِ گسترهٔ خطی

قاعدهٔ چهارم، که ظریف‌ترین آن‌هاست، می‌گوید هیچ خطِ راستِ افقی یا عمودی از خانه‌های سفیدِ به‌هم‌پیوسته نباید بر سه اتاق یا بیشتر گسترده شود. یک رشتهٔ راست از خانه‌های سفید می‌تواند دست‌بالا از یک مرز اتاق بگذرد، یعنی می‌تواند خانه‌هایی از حداکثر دو اتاق داشته باشد. این قاعده در امتداد خط‌های راستی عمل می‌کند که مرزهای اتاق‌ها را قطع می‌کنند، و قیدی می‌آفریند که تا خط‌های افقی و عمودی تخته را وارسی نکنید نامرئی می‌ماند. ¹

این قاعده به‌ویژه در حذف چیدمان‌هایی کارآمد است که در غیر این صورت سه قاعدهٔ نخست را برآورده می‌کردند. برای نمونه، رشته‌ای بلند و افقی از خانه‌های سفید که از دو مرز اتاق بگذرد این قاعده را نقض می‌کند، حتی اگر خانه‌ها بر پایهٔ قاعدهٔ مجاورت به‌درستی فاصله‌گذاری شده باشند و به اتاق‌هایی با شمارِ درست تعلق داشته باشند. این قاعده خانه‌های سفید را وامی‌دارد در نقاطی راهبردی از خط‌هایشان با خانه‌های سایه‌خورده بریده شوند، و همان الگوی بصری‌ای را می‌سازد که در آن خانه‌های سفید گویی با خانه‌های سایه‌خوردهٔ جداکننده قطعه‌قطعه شده‌اند. ³

قاعده‌ها چگونه در هم قفل می‌شوند

نیروی راستین Roomshade از شیوهٔ همکاری این چهار قاعده سر برمی‌آورد. قاعدهٔ شمارِ هر اتاق اطلاعات آغازین را می‌دهد اما چیدمان‌های بسیاری را ممکن باقی می‌گذارد. قاعدهٔ مجاورت با ممنوع کردن خانه‌های سایه‌خوردهٔ هم‌ضلع، برخی چیدمان‌ها را حذف می‌کند. قاعدهٔ پیوستگی چیدمان‌هایی را حذف می‌کند که ناحیهٔ سفید را تکه‌تکه می‌کنند. قاعدهٔ گسترهٔ خطی چیدمان‌هایی را حذف می‌کند که خط‌های سفیدِ گذرنده از اتاق‌های بیش از حد می‌سازند. هر قاعده زیرمجموعهٔ متفاوتی از احتمال‌ها را حذف می‌کند، و با هم همه را جز یک چیدمان — همان راه‌حل یگانه — از میان برمی‌دارند. ³

این درهم‌قفل شدن پازلی می‌آفریند که راه‌حلش را نمی‌توان با برآورده کردن جداگانهٔ قاعده‌ها یافت. خانه‌ای ممکن است زیر قاعدهٔ شمارش و قاعدهٔ مجاورت مجاز باشد اما قاعدهٔ پیوستگی آن را ممنوع کند. خانه‌ای دیگر ممکن است قاعدهٔ مجاورت را برآورده کند اما خط سفیدی بسازد که حدِ گسترهٔ خطی را نقض می‌کند. بازیکن باید پیوسته هر چهار قاعده را هم‌زمان وارسی کند و بداند که استنتاجی بر پایهٔ یک قاعده ممکن است زیر قاعده‌ای دیگر امکان‌ها یا قیدهای تازه‌ای بیافریند. جوهرهٔ استنتاج در این پازل همین است: دنبال کردن پیامدهای هر قاعده در حالی که در سراسر تخته پخش می‌شوند. ³

هر قاعده هر قاعدهٔ دیگر را مقید می‌کند.

اندازهٔ شبکه و ابعاد اتاق

پازل‌های Roomshade در سه اندازهٔ استاندارد می‌آیند: کوچک (5×5)، متوسط (6×6) و بزرگ (7×7). این ابعاد بر پیچیدگی پازل اثر می‌گذارند اما بر خودِ قاعده‌ها نه. شبکهٔ 5×5 خانه‌ها و اتاق‌های کمتری از شبکهٔ 7×7 دارد، پس راه‌حل معمولاً به گام‌های استنتاجی کمتری نیاز دارد. با این همه، ساختار بنیادی پازل صرف‌نظر از اندازه همان می‌ماند. ³

هر اتاق مستطیلی است که ابعادش در هر راستا میان یک تا سه خانه است. این یعنی اتاق‌ها از تک‌خانه‌های 1×1 تا اتاق‌های نُه‌خانه‌ای 3×3 را در بر می‌گیرند. ابعاد اتاق به شیوه‌هایی جالب بر کاربست قاعده‌ها اثر می‌گذارند. اتاقی 1×1 با سرنخ یک باید سایه بخورد؛ اتاقی 1×1 با سرنخ صفر باید سفید بماند. اتاقی 3×3 با سرنخ پنج به پنج خانهٔ سایه‌خورده و چهار خانهٔ سفید نیاز دارد، و قاعدهٔ مجاورت دقیقاً یک راه برای جای دادنشان باقی می‌گذارد: چهار گوشه و مرکز. ابعاد اتاق، در کنار مقادیر سرنخ‌ها، شرایط آغازینی را می‌سازند که قاعده‌ها باید از دلشان راه‌حل یگانه را بیرون بکشند. ³

سرنخ‌های نمایان و سرنخ‌های خالی

برخی اتاق‌ها عدد سرنخشان را نشان می‌دهند و برخی دیگر خالی‌اند. سرنخِ خالی نشان می‌دهد که آن اتاق قیدِ شمارش ندارد؛ اتاق می‌تواند هر شماری خانهٔ سایه‌خورده داشته باشد، از صفر تا بیشترین شماری که خانه‌هایش بدون تماس دو تای آن‌ها برمی‌دارند. اتاق‌های خالی همچنان از قاعدهٔ مجاورت، قاعدهٔ پیوستگی و قاعدهٔ گسترهٔ خطی پیروی می‌کنند، اما قیدی عددی به پازل نمی‌افزایند. ³

وجود اتاق‌های خالی لایه‌ای از پیچیدگی به پازل می‌افزاید. بدون قید عددی، بازیکن باید یکسره بر پایهٔ سه قاعدهٔ دیگر تعیین کند که در اتاق‌های خالی کدام خانه‌ها را سایه بزند. این کار تحلیلی دقیق می‌طلبد از اینکه سایه زدن به خانه‌ها در اتاق‌های خالی چه اثری بر اتاق‌های همسایه و بر ساختار سفیدِ سراسری می‌گذارد. اتاق‌های خالی می‌توانند نقش رابط میان اتاق‌های عددنشان را بازی کنند و بگذارند مسیرهای سفید میانشان جاری شود، یا می‌توانند از خانه‌های سایه‌خورده پر شوند تا خط‌های سفید ناخواسته را سد کنند. هم‌کنشی میان اتاق‌های خالی و اتاق‌های عددنشان عنصری کلیدی در طراحی Roomshade است. ³

از استنتاج محلی تا استنتاج سراسری

زیبایی Roomshade در آن است که استنتاج‌های محلی چگونه به نتیجه‌های سراسری سرریز می‌کنند. یک خانهٔ سایه‌خورده در گوشه‌ای از تخته می‌تواند، از رهگذر اثرهای درهم‌قفلِ قاعده‌ها، وضعیت خانه‌هایی را که چندین اتاق آن‌طرف‌ترند تعیین کند. قاعدهٔ مجاورت به‌صورت محلی پخش می‌شود و همسایه‌های خانه‌های سایه‌خورده را ممنوع می‌کند. قاعدهٔ پیوستگی به‌صورت سراسری پخش می‌شود و می‌خواهد تمام ناحیهٔ سفید پیوسته بماند. قاعدهٔ گسترهٔ خطی در امتداد خط‌های راست پخش می‌شود و رشته‌های سفیدی را که از اتاق‌های بیش از حد می‌گذرند ممنوع می‌کند. ¹

این پخش‌شدن پازلی می‌آفریند که در آن بازیکن باید با در دسترس قرار گرفتن اطلاعات تازه، پیوسته درک خود را از تخته به‌روز کند. خانه‌ای که زمانی مبهم بود، با تعیین شدن خانه‌ای همسایه ممکن است ناگزیر شود. اتاقی که به نظر می‌رسید چند چیدمان معتبر دارد، با اِعمال قاعدهٔ پیوستگی ممکن است به یک چیدمان فرو کاسته شود. راه‌حل نه از یک جرقهٔ واحد بلکه از اثر انباشتهٔ کاربستِ مکرر این چهار قاعده سر برمی‌آورد، تا آنجا که وضعیت هر خانه تعیین شود. ³

قاعده‌ها موتور منطقیِ پازل‌اند.

سرشتِ قطعیِ راه‌حل

هر پازل Roomshade دقیقاً یک راه‌حل دارد. این یگانگی تصادفی نیست، بلکه ساختِ پازل آن را تضمین می‌کند. حل‌گرِ پس‌گردی که برای تولید پازل‌ها به کار می‌رود وارسی می‌کند که تنها یک سایه‌گذاری هر چهار قاعده را برآورده کند. این سرشت قطعی برای طراحی پازل بنیادی است: اگر چند راه‌حل ممکن بود، پازل باطل شمرده می‌شد. کار بازیکن آن است که راه‌حل یگانه را با استنتاج کشف کند، نه با حدس زدن. ³

قطعی بودن پازل یعنی هر استنتاج معتبر باید یقینی باشد. اگر بتوان از راه قاعده‌ها تعیین کرد که خانه‌ای سایه‌خورده است یا سفید، پس در راه‌حل یگانه هم همان است. اگر وضعیت خانه‌ای را نتوان بدون حدس زدن تعیین کرد، یا پازل هنوز حل نشده یا بازیکن هنوز استنتاج درست را نیافته است. همین ویژگی است که Roomshade را از پازل‌هایی که بر آزمون و خطا تکیه دارند جدا می‌کند؛ تعیین وضعیت هر خانه باید به‌طور منطقی از قاعده‌ها و از اطلاعاتی که پیش‌تر برقرار شده‌اند نتیجه شود. ³

Sources & notes

"Heyawake," Wikipedia, a binary-determination logic puzzle published by Nikoli, first appearing in Puzzle Communication Nikoli #39 in September 1992; the Japanese name means "divided rooms," the grid being divided into variously sized rectangular rooms by bold lines; a number in a room indicates exactly how many painted (shaded) cells it must hold; painted cells may never be orthogonally connected and all the white cells must be interconnected; and a straight line of connected white cells may not contain cells from more than two rooms. en.wikipedia.org/wiki/Heyawake.
"Nikoli (publisher)," Wikipedia, a Japanese publisher specializing in games and, especially, logic puzzles, established in 1980 by Maki Kaji; its Sudoku, the most popular logic problem in Japan, was popularized in the English-speaking world in 2005; it is notable for a vast library of "culture-independent" puzzles focused on logic rather than language; and it has invented or introduced many puzzle genres, including Slitherlink, Nurikabe, Heyawake, and Masyu. en.wikipedia.org/wiki/Nikoli_(publisher).
Roomshade game engine: a Heyawake realization on a rows×cols grid partitioned into axis-aligned rectangular ROOMS, enforcing four rules: (1) a room with a number holds EXACTLY that many shaded cells (unlabeled rooms are free); (2) no two shaded cells are orthogonally adjacent; (3) all unshaded (white) cells form one orthogonally-connected region; and (4) no horizontal or vertical straight run of white cells may span three or more rooms; sizes are small (5×5), medium (6×6), and large (7×7) with rooms of dimension 1–3 and a clue that is either the shaded count or blank; the grid is partitioned by a greedy randomized fill, and a backtracking solver both fills a valid solution and verifies the puzzle's uniqueness, all pure and seeded-deterministic. Read from the game's own source.
Further reading on Heyawake: Markus Holzer and Oliver Ruepp, “The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake,” in Fun with Algorithms (FUN 2007), Lecture Notes in Computer Science; the analysis behind the result that deciding whether a Heyawake instance has a solution is NP-complete. doi.org.