یکی از مسائل جالب طراحی الگوریتم مساله کاشیکاری یا فرش کردن زمین با موزاییک است.

فرض کنید قطعه زمین مربعی شکل با ابعادی از توان دو داریم. مثلا با ابعاد 16 متر:

هدف فرش کردن این قطعه زمین با استفاده از موزاییکهایی با فرمهای زیر است:

به قسمی که یکی از خانه های زمین شطرنجی شده فوق پوشیده نشود. می توان فرض کرد از این خانه برای احداث باغچه یا حوضچه کوچکی استفاده خواهد شد. توجه داشته باشید که اندازه اضلاع مربعهای کوچک موزاییکها نیز همانند صفحه شطرنجی فوق یک متر است. در ضمن حق شکستن این موزاییکها به تکه های کوچکتر را نداریم.

به عنوان مثال فرض کنید زمینی با ابعاد چهار متر داریم، که می خواهیم خانه مشخص شده زیر پوشیده نشود:

می توان این زمین را به صورت زیر فرش کرد:

اما راه حل کلی مساله چیست؟

با توجه به اینکه ابعاد زمین توانی از عدد دو است، روش تقسیم و حل را برای پوشانیدن این قطعه زمین امتحان می کنیم.

بر اساس تعریف روش تقسیم و حل، باید بتوان مساله را به زیر مسائلی از نوع خود مساله تقسیم کرد، و با ادغام نتایج حاصل از آنها به نتیجه اصلی دست پیدا کرد. چون ابعاد این قطعه زمین توانی از عدد دو است، پس می توان آن را به دو قسمت تقسیم کرد. با تقسیم طول و عرض زمین به دو قسمت، چهار قطعه زمین کوچکتر به دست می آید:

اما همه این چهار قطعه زمین شرایط مساله اصلی را دارا نیستند. در صورت مساله عنوان شده است که باید از پوشانیدن یکی از خانه های قطعه زمین صرف نظر کرد. از چهار قطعه زمین کوچکتر تنها یکی از آنها این شرط را برآورده می کند و بقیه قطعه زمینها باید به طور کامل پوشانیده شوند.

این نقص را می توان با به کار بردن یک موزاییک حل کرد:

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

اگر قطعه زمینهای کوچکتر از ابعاد 2 باشند، به سادگی با قرار دادن یک موزاییک می توان آنرا پوشانید:

پس به طور خلاصه برای حل مساله باید به این صورت عمل کنیم:

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

تعداد موزاییکها:

یکی از سوالات مهم این است که برای پوشانیدن قطعه زمین با توجه به شرایط مساله چند موزاییک لازم است؟

فرض کنید ( T( n تعداد موزاییکهای لازم برای پوشانیدن زمینی با ابعاد n باشد. با توجه به استفاده از روش تقسیم و حل، هر قطعه زمین به چهار قطعه زمین با ابعاد نصف تبدیل می شود. اما برای این تبدیل از یک موزاییک استفاده می کنیم. پس می توان نوشت:

T( n ) = 4 × T( n / 2 ) + 1

اگر ابعاد قطعه زمین دو متر باشد، تنها یک موزاییک برای پوشانیدن آن کافی است:

T( 2 ) = 1

پس می توان گفت تعداد موزاییکهای لازم برای پوشش زمینی با ابعاد n از رابطه بازگشتی زیر به دست می آید:

T( n ) = 4 × T( n / 2 ) + 1          ,         T( 2 ) = 1

با حل این رابطه بازگشتی با استفاده از روشهای متعارف ریاضی نتیجه زیر حاصل می شود:

T( n ) = ( n² - 1 ) / 3

اما راه ساده تری هم برای به دست آوردن این رابطه وجود دارد:

در داخل قطعه زمینی با ابعاد n تعداد n² خانه مربعی شکل وجود دارد. یکی از این خانه ها نباید پوشانیده شود. پس n² - 1 خانه مربعی شکل کوچک داریم که باید توسط موزاییکها پوشانیده شوند. هر موزاییک نیز می تواند سه خانه مربعی شکل کوچک را پوشش دهد. پس در مجموع به n² - 1 ) / 3 ) موزاییک نیاز خواهیم داشت.