شطرنج خدایان

تمام وضعیت‌های ممکن صفحه‌ی شطرنج را در نظر می‌گیریم (تعداد وضعیت‌های صفحه‌ی شطرنج از تعداد اتم‌های عالم بیشتر است. با این حال تعداد وضعیت‌های صفحه‌ی شطرنج بی‌نهایت نیست.

هر وضعیت را معادل یک رأس در یک گراف در نظر می‌گیریم و از هر وضعیت (رأس) $A$ یالی جهت‌دار به سوی هر وضعیت (رأس) $B$ رسم می‌کنیم هرگاه از $A$ بتوان با یک حرکت به $B$ رفت.

یک گراف خیلی بزرگ ساخته می‌شود. یک سری ار وضعیت‌ها حالت‌های باخت نهایی (کیش و مات) و یک سری وضعیت‌های تساوی هستند.

در ابتدا $L$ را برابر مجموعه‌ی تمام حالت‌های باخت نهایی (کیش و مات) و $T$ را برابر تمام حالت‌های تساوی نهایی و $W$ را برابر با مجموعه‌ی تهی می‌گیریم و الگوریتم زیر را اجرا می‌کنیم.

مادامی که رأسی خارج از $L$ و $W$ و $T$ باقی‌مانده، برای هر رأس $u$ خارج از هر سه مجموعه‌ی $L$ و $T$ و $W$

• چنانچه $u$ دارای یال $u\stackrel{}{\to }v$ باشد به طوری که $v\in L$، آنگاه $u$ را در $W$ قرار دهید.
• در غیر اینصورت چنانچه یال $u\stackrel{}{\to }v$ موجود باشد که $v\in T$، $u$ را در $T$ قرار دهید.
• در صورتی که برای هر یال $u\stackrel{}{\to }v$ رأس $v$ در $W$ باشد، آنگاه $u$  در $L$ قرار دهید.

ثابت می‌شود که الگوریتم فوق تمام رأس‌های گراف را به 3 مجموعه‌ی $L$ و $T$ و $W$ افراز می‌کند. بنابراین حالت ابتدایی که معادل یکی از رأس‌های این گراف است، در یکی از این 3 دسته قرار خواهد گرفت.