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

کد back track

کد بهینه شده

چند تا راه: 1-راه خودت که زمانش حدودا 95000 دقیقه 2-باید سه تا از هر سطر رو پر کنیم بعد چک کنیم جواب در سته یا نه که میشه : $ \binom{7}{3} ^7 $ که حدودا میشه $64*10^9$ که میشه حدودا ده دقیقه 3-بازگشتی با الگوریتم ژنتیکی: این که یه تا بع بازگشتی بنویسی که بار اول سه تا چیز بزاره تو 7 جا سطر بعد هر جا که میتونه بذاره هر وقت هم ستون پر بود نذاره که اگه هر وقت درست شد یه جواب درست داریم که میتونیم حسابش کنیم این میشه حدودا 1.5 دقیقه

من پسگرد را با حذف حالتهایی که به جواب نمی‌رسند نوشتم سریعتر بود. (اگر درست انجامش داده باشم.) جمع تعداد ۱هایی که تا حالا گذاشتم را نگه داشتم و بعد گفتم اگر بقیه‌ی خانه‌هایی که چک نکردم همه ۱ باشند هیچ وقت مجموعش ۲۱ می‌شود یا نه. که البته این شرط خیلی زمانش را کم نکرد در نتیجه یک شرط دیگه گذاشتم که اگر همه‌ی ستون‌های باقی‌مانده هر کدام ۳ تا یک داشته باشند آیا جمع فعلی می‌تواند به ۲۱ برسد یا نه. با این شرط دومی زمانش کم شد. برنامه

منم دیپی زدم دیپی ۱۲ بعدی !!! فقط اولش سطر اول و سطر دوم رو دستی پر کردم . آخرش حالت ها رو ضرب کردم

simple code

این راه حل هم جواب میده که ستون به ستون همه حالات مختلف ردیف ها رو توی ست ذخیره کنی. کد: http://paste.ubuntu.com/18882972/

Runtime: 0.035s