لغز توزيع الأرقام

السلام عليكــم ورحمـة الله وبركاتــه ،،

اذا كان اللغز صعب لدرجة انه لا يحل ل 3 ايام فانا مستعد لوضع حلة

السلام عليكــم ورحمـة الله وبركاتــه ،،

هل الحل التالي يحقق الشرط؟.

لا , لاحظ 3و4 متتالين قطرين .

السلام عليكــم ورحمـة الله وبركاتــه ،،

لا حظ ايضا 7 و 8

لم انتبه لكلمه مائل.

سوف اضع محاوله اخرى ان شاء الله

السلام عليكــم ورحمـة الله وبركاتــه ،،

هذه اخرى

السلام عليكــم ورحمـة الله وبركاتــه ،،

مبارك للأخ amin_mu123 الحل صحيح 100%

والان سوف اضع البرنامج الذى عملته ليقوم بحل اللغز

البرنامج معمول على السي شارب يعني بدو دوت نت 2 لتشغيله

البرنامج مع الكود كامل في المرفقات

SolveSquares.rar

مشكور وان شاء الله مأجور اخي

لاحظت ان الكود بطيء وبما اننا في قسم خوارزميات

حبيت اضيف هذا السؤال :

هل من الممكن تحسين وقت الخوارزمية الموجودة في الكود ؟

B)

بالتوفيق .

ibr_exn كتب:

هل من الممكن تحسين وقت الخوارزمية الموجودة في الكود ؟

بدأت اقلق منك اخى ابراهيم :P. ياريت حضرتك او الاخ akramKamal يقوم بوضع الخوارزميه المشار اليها. فانا لا اتعامل مع السى شارب. وبعدها نرى ان كان يمكن تحسين اداء الخوارزميه او لا :)

اعتقد ده ممكن يكون تطبيق كويس لطرق الذكاء الاصطناعى :)

يا عم تقلق ايه.هو في حدا قدك . :lol:

انا كمان ماليش في السي شارب :blink:

اعتقد ان هذا هو الكود الرئيسي . -_-

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace SolveSquares
{
	public partial class Form1 : Form
	{
		public Form1()
		{
			InitializeComponent();


		}
		int[] Solve()
		{
			for (int i = 0; i < 16777216; i++)
			{
				long l = long.Parse(Convert.ToString(i, 8));
				char[] chars = l.ToString("00000000").ToCharArray();
				int[] value = new int[chars.Length];
				for (int k = 0; k < value.Length; k++)
					value[k] = chars[k] - 48;
				if (!IsDenial(value)) return value;
			}
			return null;
		}
		int[] Indexes(int index)
		{
			List<int> result = new List<int>();
			switch (index)
			{
				case 0: return new int[] {1,2,3 };
				case 1: return new int[] { 0,2,4,5 };
				case 2: return new int[] { 0,1,4,5,6,3 };
				case 3: return new int[] { 0,2,5,6 };
				case 4: return new int[] { 1,2,5,7 };
				case 5: return new int[] { 1,2,3,6,4,7 };
				case 6: return new int[] { 2,3,5,7 };
				case 7: return new int[] { 4,5,6 };
				default: return new int[0];
			}
		}
		bool IsDenial(int[] Value)
		{
			for (int i = 0; i < Value.Length; i++)
			{
				for (int j = 0; j < Value.Length; j++)
					if (i != j && Value == Value[j]) return true;
			}
			for (int i = 0; i < Value.Length; i++)
			{
				int[] indexes = Indexes(i);
				for (int j = 0; j < indexes.Length; j++)
					if (Math.Abs(Value - Value[indexes[j]]) == 1) return true;
			}


			return false;
		}

		private void button1_Click(object sender, EventArgs e)
		{
			int[] result = Solve();
			textBox1.Text = result[0] + 1 + "";
			textBox2.Text = result[1] + 1 + "";
			textBox3.Text = result[2] + 1 + "";
			textBox4.Text = result[3] + 1 + "";
			textBox5.Text = result[4] + 1 + "";
			textBox6.Text = result[5] + 1 + "";
			textBox7.Text = result[6] + 1 + "";
			textBox8.Text = result[7] + 1 + "";
		}
	}
}

لاحظ التكرار الاول يستمر الى 16777216 ( 8 اس 8)

اعتقد اذا حنجرب كل الاحتمالات ( وهي طريقة سيئه ) يكفي ان نعمل تباديل لل8 ( مضروب ال8 )

يعني المربع الاول سنضع فيه احد ال8 ارقام والثاني احد ال 7 ارقام الباقيه وهكذا .

ساحاول التفكير في طريقة افضل بعد الاختبارات.

السلام عليكــم ورحمـة الله وبركاتــه ،،

شكرا لك أخي ibr_exn على تشجيعك لعمل خوارزمية اسرع فبالفعل قمت بعمل هذه الخوارزمية واصبحت الان تحل اللغز لحظيا وبدون وقت ضائع

وذلك لاني استخدمت طريقة توليد التباديل لمتسلسلة معينة والتي قد أفدتني بها

البرنامج مع الكود في المرفقات

والسلام عليكم

SolveSquares.rar

اعتقد انه ايضا يمكن التحسين على الخوارزميه الاخيره. (متأكد انك شاطر وبتجيبها )

لاحظ انه في نظرية الخوارزميات ان الخوارزميات من الصنف هذا ( الاس والمضروب ) تعتبر سيئه .

اتمنى الاخ الفاضل akramKamal يتفضل بشرح الخوارزميه بدلا من وضع برامج.

الاخ اكرم :

انا مع د. عماد .

حتى يستفيد بقية الاعضاء ، قم بشرح مبسط وعام لفكرة الخوارزمية وبعدها قم بوضع الكود مع التعليقات التوضيحيه.

بالتوفيق .

السلام عليكــم ورحمـة الله وبركاتــه ،،

في البداية أشكركم على الاهتمام

شرح الخوارزمية بسيط جدا وهو كالتالي

نوجد جميع التبديلات للمتسلسلة 1 2 3 4 5 6 7 8

ثم نقوم بفحص كل تبديلة على حدة حتى نحصل على تبديلة تؤدي الشروط

شرح الكود

أولا : الميثود التي تقوم بايجاد جميع التبديلات

تقوم هذه الميثود بتوليد جميع التبديلات وارجاعها في array of array integer

Procedure GetPermutations
Input: numbers= array of integers
	   m= Count of numbers will be Permutations 
			  result = handle to the result  Permutations
Output: AllPermutations of this integer array
If m == 0 then
	  Add to   result  numbers
	  Return
Else 
	   For i  = 0 to numbers.length  do
			 If numbers==0  then
		   numbers=1
					  GetPermutations(numbers,m, result)
	   		numbers=0
 		End if
		End for
End If
End  Procedure

ثانيا : الميثود التي تقوم بارجاع مصفوفة من indexes المرتبطة ب index معين

مثلا ال index 0 سيكون النتيجة 1 2 3

لاحظ الصورة التالية

Procedure Indexes
Input: index as integer
Output: the Indexes connected with this index
switch (index)
	  case 0: return new int[] { 1, 2, 3 };
	  case 1: return new int[] { 0,2,4,5 };
	  case 2: return new int[] { 0, 1, 4, 5, 6, 3 };
	  case 3: return new int[] { 0,2,5,6 };
	  case 4: return new int[] { 1, 2, 5, 7 };
	  case 5: return new int[] { 1, 2, 3, 6, 4, 7 };
	  case 6: return new int[] { 2, 3, 5, 7 };
	  case 7: return new int[] { 4, 5, 6 };
	  default: return null;
  end switch
  End  Procedure

ثالثا : الميثود التي تقوم بفحص كون التبديلة تؤدي الشروط أو لا

Procedure isVaildSolution
Input: inputArray
OutPut: true if vaild, false if not vaild

For i  = 0 to inputArray.length  do
	 Int[] indexes= Indexes(i)
	 For j  = 0 to indexes.length  do
   	  If  inputArray- inputArray[indexes[j]]==1 or -1 then
			  Return false;
		End if
		   End for
End for
Return true // this mean that this input array is valid
End  Procedure

رابعا : الميثود التي تقوم بايجاد التبديلة الصحيحة

Procedure Solve
Input: perms= AllPermutations that result from Procedure  
			  GetPermutations
OutPut: inger aray of the solution

For i  = 0 to perms.length  do
	 If isVaildSolution(perms) then
		  Return perms  //We found the solution
	  End if
End for
Return null // this mean that no solution
End  Procedure

واخيرا ارجو ان يكون الأمر مفهوم

ولا تنسونا من الدعاء

السلام عليكــم ورحمـة الله وبركاتــه ،،

بداية يجب الاتفاق على مجموعه من البنود التى يجب ان تلتزم بها اى خوارزميه , والا فسيكون الحل خاطئ. وهى

1) المطلوب فى الخوارزميه , توزيع الاعداد الطبيعية من 1 الى 8 فى شكل مصفوفه تحقق مجموعه من الشروط وهى
أ- المصفوفه بها اربعة صفوف وثلاثة اعمده , اى تحتوى على 12 عنصر.
ب- الــ 12 عنصر هم الاعداد الثمانية السابقه , وكذلك الاربعة اركان للمصفوفه تكون فارغه (مثلا اصفار).
ج- لاى عنصر غير صفرى من عناصر المصفوفه , يجب ان يكون الفرق بينه وبين اى جار من جيرانه (فى اى صف او اى عمود او اى قطر) لا يقل عن 2.

2) لكل توزيع محتمل , يجب اختباره للوقوف على تحقيقه للشرط فى البند 1 ج.
3) لعمل الاختبار فى الخطوة 2 , فانه يجب مقارنة كل عنصر من عناصر المصفوفه مع جيرانه (عدد الجيران يكون بين 3 جيران او 8 جيران حسب موقع العنصر محل الاختبار).

الالتزام بالبنود السابقه , يعطى خوارزميه وحلول صحيحه ان شاء الله , ولكنها لا تضمن درجة جوده وكفاءة هذه الخوارزميه

ولتوفير الوقت والحسابات , فاعتقد ان الخوارزميه المميزة يجب ان تراعى البنود التاليه:

4) حيث ان التكرار فى عناصر المصفوفه غير وارد , وكذلك الاركان ثابته لا تتغير (اصفار). فيكون لدينا عدد احتمالات للتوزيع قدره مضروب العدد 8.
5) لتوفير الوقت فى الاختبار فى البند 3 , يمكننا مقارنة كل عنصر مع جيرانه الذين يسبقونه فقط (او الذين يلونه فقط). على اعتبار اننا نتحرك من اليسار لليمين ومن فوق الى تحت. وهذا يوفر نصف وقت الاختبار.
6) عند اول عنصر يفشل عنده الشرط 1 ج , يجب التوقف والانتقال الى التوزيع التالى للارقام.
7) حيث اننا سنتوقف حسب البند 6, عند او عنصر لا يحقق الشرط 1 ج , فليس له داعى توليد كل التوزيعات المحتمله قبل مرحلة الاختبار. بمعنى انه يمكننا توليد عناصر كل توزيع محتمل (لدينا مضروب 8 توزيعا) عنصر بعنصر , فاذا ما وجدنا ان العنصر الحالى لا يحقق الشرط 1 ج , فيمكننا التوقف عن توليد باقى عناصر هذا التوزيع والانتقال الى التوزيع التالى.

حل على السريع باستخدام الماتلاب :)

 
function r=numbers2()
 
numbers1=[1 2 3 4 5 6 7 8];
res=zeros(4,3);
for a1=1:8
res(1,2)=numbers1(a1);
numbers2=getnum(numbers1,res(1,2));
for a2=1:7
res(2,1)=numbers2(a2);
if accept(res,2,1)==1
numbers3=getnum(numbers2,res(2,1));
for a3=1:6
res(2,2)=numbers3(a3);
if accept(res,2,2)==1
numbers4=getnum(numbers3,res(2,2));
for a4=1:5
res(2,3)=numbers4(a4);
if accept(res,2,3)==1
numbers5=getnum(numbers4,res(2,3));
for a5=1:4
res(3,1)=numbers5(a5);
if accept(res,3,1)==1
numbers6=getnum(numbers5,res(3,1));
for a6=1:3
res(3,2)=numbers6(a6);
if accept(res,3,2)==1
numbers7=getnum(numbers6,res(3,2));
for a7=1:2
res(3,3)=numbers7(a7);
if accept(res,3,3)==1
numbers8=getnum(numbers7,res(3,3));
res(4,2)=numbers8(1);
if accept(res,4,2)==1
r=res;
return
end
end
end
end
end
end
end
end
end
end
end
end
end
end
 
 
 
function r=accept(matr,i0,j0)
r=1;
for i=max(1,i0-1):i0
for j=max(1,j0-1):min(3,j0+1)
if (matr(i,j)~=0) && (abs(matr(i,j)-matr(i0,j0))==1)
r=0;
return
end
end
end
 
 
function r=getnum(vec,elem)
for i=1:length(vec)
if vec(i)==elem
vec(i:end-1)=vec(i+1:end);
r=vec(1:end-1);
return
end
end

(2)

(6)(8)(5)

(4)(1)(3)

(7)

(7)

(4)(1)(3)

(6)(8)(5)

(2)

ما شاء الله د. عماد واسف للرد المتأخر ،

نظرا لاني مبتديء بالماتلاب وادرس عليه حاليا ،احاول افهم الكود الذ كتبته . :wacko:

هل الدالة numbers2 تستدعي نفسها كل مره ؟

لاحظت ايضا ان ناتج عدد عبارات التكرار for تعطي مضروب 8

عارف حتقول على مقفل <_< هل بالامكان وضع تعليقات على الكود لتوضيح عمل كل عباره .

ibr_exn كتب:

نظرا لاني مبتديء بالماتلاب وادرس عليه حاليا ،احاول افهم الكود الذ كتبته . :wacko:

هل الدالة numbers2 تستدعي نفسها كل مره ؟

لاحظت ايضا ان ناتج عدد عبارات التكرار for تعطي مضروب 8

عارف حتقول على مقفل <_< هل بالامكان وضع تعليقات على الكود لتوضيح عمل كل عباره .

ياباشا احنا مش قد التواضع ده :).

كما اوضحت سابقا , فان عدد التوزيع التى يمكن الحصول عليها هى يساوى مضروب العدد 8 اى 40320 توزيعا. وطبعا كل توزيع سيتم اختبار عناصره (عنصر بعنصر) للوقوف على تحقيق التوزيع للشرط 1 ج فى المشاركة السابقة. فلو قلنا ان هناك دالة ما ACCEPT لعمل هذا الاختبار على كل عنصر (مقارنته مع جيرانه). فان الحد الاقصى الذى سيتم استدعاءه لهذه الداله هو عدد الاحتمالات للتوزيعات (40320) مضروبا فى عناصر كل توزيع (8) اى 322560 استدعاءا.

اذا لدينا الطرق التاليه للوصول للحل:

1) توليد كل التوزيعات دفعه واحده ثم اختبار عناصر كل توزيعه بالدالة ACCEPT.

2) توليد التوزيعات توزيعا تلو الاخر بحيث يتم توليد التوزيع الحالى ثم اختباره بالدالة ACCEPT وفى حالة الفشل ننتقل للتوزيع الجديد.

3) توليد التوزيعات توزيعا تلو الاخر , وتوليد عناصر كل توزيع عنصر تلو الاخر. بحيث يتم توليد العنصر الحالى ثم اختباره بالدالة ACCEPT وفى حالة النجاح ننتقل للعنصر التالى اما فى حالة الفشل ننتقل للتوزيع الجديد.

بفرض جدلا اننا سنجد الحل عند التوزيع الـ 2000 مثلا. فان اقصى عدد للعناصر التى يتم توليدها هى 2000 فى 8 يساوى 16000 عنصر. وبفرض انه يتم الانتقال للتوزيع الجديد عند اول فشل لعناصر التوزيع الحالى.

1) الطريقه الاولى:

سنكون قمنا بتوليد عدد توزيعات قدره 40320 توزيعا باجمالى عدد عناصر قدره 322560 عنصرا. وتم استدعاء الدالة ACCEPT عدد Y (اقل من 16000, وهو يعتمد على عدد العناصر التى تم اختبارها لكل توزيع حتى فشل الاختبار)

2) الطريقه الثانية:

سنكون قمنا بتوليد عدد توزيعات قدره 2000 توزيعا باجمالى عدد عناصر قدره 16000 عنصرا. وتم استدعاء الدالة ACCEPT عدد Y (اقل من 16000, وهو يعتمد على عدد العناصر التى تم اختبارها لكل توزيع حتى فشل الاختبار)

3) الطريقة الثالثة

سنكون قمنا بتوليد عدد توزيعات قدره 2000 توزيعا باجمالى عدد عناصر قدره Z عنصرا (اقل بكثيييييير جدا من 16000). وتم استدعاء الدالة ACCEPT عدد Z ايضا.

وطبعا هنا Z اقل بكثير جدا جدا من 16000 لاننا ببساطه لم نولد كل عناصر كل توزيع ممرنا عليه , وكذلك فاننا ايضا اختصرنا عدد كبير جدا من التوزيعات لم نمر عليه اصلا. كيف ذلك؟ تخيل ان هناك 5 توزيعا متشابهين تماما حتى العنصر الرابع (مثلا) ومختلفين بعد ذلك. وتخيل ان الاختبار لهم سيفشل عند العنصر الرابع. بالطريقة الاولى والثانيه فاننا سنقوم بتوليد الـ 5 توزيعات. ونختبرهم كتوزيعات مستقله. اما بالطريقه الثالثة فلن نولد الا توزيعا واحد منهم , وفى حالة فشله سيتم تجاهل كل التوزيعات التى تتشابه مع التوزيع الحالى حتى العنصر الرابع لان اصلا العنصر الرابع فشل فى تحقيق الاختبار , فسيفشل للـ 5 توزيعات , ولا داعى للتكرار.

طبعا واضح ان الطريقه الثانيه قامت بتحسين النتائج فى تقليل عدد العناصر المولده الى 16000 عنصرا ولم تحسن عدد مرات استدعاء الدالة ACCEPT. بينما الطريقه الثالثة قامت بتحسين عدد العناصر المولده الى Z وهو رقم اقل بكثير جدا من 16000 وكذلك قامت بتقليل عدد مرات استدعاء الدالة ACCEPT. وذلك لانه فى الطريقه الثالثة يتم توليد العنصر الجديد واختباره , وفى حالة الفشل فلا نقوم بتوليد باقى عناصر هذه التوزيع ولا جميع التوزيعات المتشابهه معه حتى هذه العنصر. وهذا تسريع كبير جدا للحسابات فى هذا المثال. وهى الطريقه التى اعتمدتها هنا.

واليكم الكود مرة ثانيه بعد اضافة بعض التعليقات كما طلب الاخ ابراهيم. ولاحظ ان السطر الذى يبدأ بـ % يعنى انه سطر ملاحظات غير فعال ولا مؤثر فى الكود.

والله اعلى واعلم ,,,

ماشاء الله ، كفيت و وفيت.شرح رائع د. عماد .

احسد طلابك عليك :cry:

ibr_exn كتب:

ماشاء الله ، كفيت و وفيت.شرح رائع د. عماد .

احسد طلابك عليك :cry:

بارك الله فيك اخى ابراهيم. وبلاش تحسدهم احسن :):):)

جميل