আমরা পাইথনে এন কুইন্স সলিউশন পেতে পারি কি না তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে যেখানে 0 খালি ঘরের প্রতিনিধিত্ব করছে এবং 1 সেই ঘরে দাবার রানীকে প্রতিনিধিত্ব করছে। আমরা এই বোর্ডটি পূরণ করতে পারি কিনা এবং একটি বৈধ এনকুইন সমাধান পেতে পারি কিনা তা আমাদের পরীক্ষা করতে হবে। যেমনটি আমরা জানি n কুইন্স ধাঁধা একটি n × n চেসবোর্ডে n রানী রাখতে বলে যাতে কোন দুই দাবা রাণী একে অপরকে আক্রমণ করতে না পারে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট True হবে, কারণ একটি সমাধান −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন isSafe() সংজ্ঞায়িত করুন। এটি বোর্ড, i, j

  লাগবে

• রেঞ্জ 0 থেকে বোর্ডের আকারের জন্য, করুন

  • যদি r i এর মত না হয় এবং বোর্ড[r, j] 1 এর মত হয়, তাহলে

    • রিটার্ন ফলস

• r :=i + 1, c :=j + 1

• যখন r <বোর্ডের সারি আকার এবং c <বোর্ডের কলামের আকার, করুন

  • যদি বোর্ড[r, c] 1 এর মত হয়, তাহলে

    • রিটার্ন ফলস

  • r :=r + 1, c :=c + 1

• r:=i + 1, c :=j - 1

• যখন r <বোর্ডের সারির আকার এবং c>=0, করুন

  • যদি বোর্ড[r, c] 1 এর মত হয়, তাহলে

    • রিটার্ন ফলস

  • r :=r + 1, c :=c - 1

• r :=i - 1, c :=j + 1

• যখন r>=0 এবং c <বোর্ডের কলামের আকার, করুন

  • যদি বোর্ড[r, c] 1 এর মত হয়, তাহলে

    • রিটার্ন ফলস

  • r :=r - 1, c :=c + 1

• r :=i - 1, c :=j - 1

• যখন r>=0 এবং c>=0, করবেন

  • যদি বোর্ড[r, c] 1 এর মত হয়, তাহলে

    • রিটার্ন ফলস

  • r :=r - 1, c :=c - 1

• রিটার্ন ট্রু

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• r :=0, c :=0

• স্ট্যাক :=একটি নতুন স্ট্যাক

• যখন r <বোর্ডের সারির আকার, করুন

  • যদি 1 বোর্ডে থাকে [r], তাহলে

    • r :=r + 1

    • পরবর্তী পুনরাবৃত্তির জন্য যান

  • অন্যথায়,

    • পাওয়া গেছে :=মিথ্যা

    • যখন c <বোর্ডের কলামের আকার, করুন

      • যদি isSafe(board, r, c) সত্য হয়, তাহলে

        • বোর্ড[r, c] :=1

        • স্ট্যাকের মধ্যে [r, c] ঢোকান

        • পাওয়া গেছে :=সত্য

        • লুপ থেকে বেরিয়ে আসুন

      • c :=c + 1

    • যদি সত্য পাওয়া যায়, তাহলে

      • c :=0, r :=r + 1

    • অন্যথায়,

      • যদি স্ট্যাক খালি হয়, তাহলে

        • রিটার্ন ফলস

      • m :=স্ট্যাক থেকে শীর্ষ উপাদান মুছুন

      • r :=m[0], c :=m[1] + 1

      • বোর্ড[r, c - 1] :=0

• রিটার্ন ট্রু

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

শ্রেণির সমাধান:def solve(self, board):def isSafe(board, i, j):r এর জন্য রেঞ্জে(len(board)):যদি r !=i এবং বোর্ড[r][j] ==1:False r, c =i + 1, j + 1 যখন r =0:if board[r][c] ==1:রিটার্ন False r +=1 c -=1 r, c =i - 1, j + 1 যখন r>=0 এবং c =0 এবং c>=0:যদি বোর্ড[r][c] ==1:রিটার্ন False r -=1 c -=1 রিটার্ন True r =c =0 স্ট্যাক =[] যখন r  
ইনপুট
 <প্রে>[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0 ], [0, 0, 0, 1, 0] ]

আউটপুট

সত্য