পাইথনে স্কয়ার নম্বর গেমে জয় সম্ভব কিনা চেক করা

দুই খেলাড়ির গেমে nটি মার্বেল থাকে। প্রতিটি টার্নে একটি পজিটিভ পারফেক্ট স্কয়ার সংখ্যক মার্বেল নিতে হয়। না পারলে হেরে যাওয়া পড়ে। প্রথম চান্স আপনার। অপ্টিমাল খেললে জয় সম্ভব কিনা বের করুন।

ইনপুট উদাহরণ

n = 14

আউটপুট: True

লজিক

• প্রথমে ৯টি মার্বেল নিন (বাকি ৫)।
• বিপক্ষিত ৪ নিলে (বাকি ১)।
• আপনি ১টি নিয়ে ০ করে দিন → বিপক্ষ নিতে পারে না → আপনি জিতলেন।

পাইথন কোড

from math import sqrt

def solve(n):
    if n <= 0:
        return False
    ans = False
    for i in range(int(sqrt(n)), 0, -1):
        if i * i > n:
            break
        ans = ans or (not solve(n - i * i))
        if ans:
            return ans
    return ans

# টেস্ট
print(solve(14))  # True

ব্যাখ্যা

এটি একটি ক্লাসিক Game Theory সমস্যা (Win/Lose State)। রিকার্সিভলি সব সম্ভাব্য মুভ চেক করা হয়। বড় n-এর জন্য DP মেমোইজেশন বা বটম-আপ অ্যাপ্রোচ ভালো।