Sudoku generator program :)

تم وضع جدول للتنظيم 

بعد الامتحانات سيتم وضع امكانية اللعب ان شاء الله :)

بسم الله الرحمن الرحيم

سودوكو: هي لعبة منطقية مبنية على وضع الأرقام في المكان المناسب. الهدف هو ملء ال 9*9 مربعات بأرقام بحيث أن كل عمود وصف ومربع من المربعات التسعة (والتي تدعى مناطق) تحتوي على الأرقام من واحد إلى التسعة دون تكرار.

أما كلمة سودوكو فهي يابانية وتعني الرقم الوحيد.  وذلك كما عرفتها ويكيبيديا  http://ar.wikipedia.org/wiki/%D8%B3%D9%88%D8%AF%D9%88%D9%83%D9%88

ومن التعريف نستنتج وجود 4 قيود :

1- ان يكون الجدول مربعا وان تنحصر الأرقام بين ال 1 و طول المربع 

2- عدم امكانية تكرار رقم اكثر من مرة في صف

3 - عدم امكانية تكرار رقم اكثر من مرة في عمود

4- عدم امكانية تكرار رقم اكثر من مرة في مربع ابعاده 3*3 بحيث يوجد 9 مربعات الجدول وذلك تبعا للسودوكو التقليدية

لعمل جدول سودوكو به فراغات نحتاج أولا ان نقوم بعمل ذلك الجدول كاملا , فمن غير المنطقي ان نقوم بوضع الأرقام في بعض الأماكن بطريقة عشوائية حتي نولد جدول لا يوجد به اخطاء .... فالجدول في ذلك الوضع نعم لا يوجد به اخطاء ولكن عند الحل سيوجد أكثر من حل أو من الممكن أن لا يوجد حل اساسا

لذلك خطوات العمل هي :

1 - عمل دالة تتأكد من أن الجدول صحيح

2 - نقوم بتوليد جدول كامل

3 -   نقوم بحذف عناص بحيث لا يجعل للعبة بعد ذلك أكثر من حل

بالنسبة لعمل دالة تتأكد من أن الجدول صحيح .. سأتركها لكم .

أما الخطوة الثانية فهي ما تحتاج للتوضيح

خوارزمية ال backtracking :

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

مثال

نفترض ان تلك لعبة سودوكو مبسطة 4 * 4 بقيد العمود والصف فقط

نفترض تطبيق الخوارزمية عليها : فسنلاحظ وجود لعبتين مرشحتين للمربع الأول في الصف الأول هما 2 و 1

نفترض اننا بدأنا بالرقم 2 فسنصل لحائط سد لان المربع الثاني لن تكون له ولا لعبة مرشحة

ولذلك سترجع الخوارزمية خطوة للوراء بعد استبعاد المرشح 2 ... فلن يبقي الا المرشح 1 

وبذلك سينتقل للمربع التالي فسنجد انه لا يوجد الا المرشح 2 له

وسنجد ايضا انه لن يوجد الا مرشح واحد ايضا في المربع الثاني في الصف الثالث وهو 4 

 وهكذا نقوم بتجربة المرشحين واذا وصلنا ل Dead end نرجع خطوة ونسبتعد ذلك المرشح .. واذا وجد مرشح بديل نستعمله والا نرجع خطوة مرة اخري للخلف ونستبعد المرشح وهكذا حتي نصل لحل و ننتهي تماما 

طريقة التطبيق لعمل جدول كامل :

نبدأ بالترتيب من أول مربع في أول صف ... نقوم بحساب عدد اللعبات المرشحة ( وذلك عن طريق الدالة التي تتأكد من أن ذلك العنصر مناسب في مكانه بحيث لا يتكرر في عمود أو صف أو في مربع )  ونضعهم في array  ونقوم بعمل shuffle لها ثم نقوم بعمل حلقة تكرارية ونبدأ  بالمرشح الأول في ال array  ونقوم بعمل استدعاء ذاتي للدالة recursion ونقوم بحساب اللعبات المرشحة ونضعها في array ونقوم بعمل shuffle لها ثم نبدأ بالمرشح الأول في ال array ونقوم بعمل استدعاء ذاتي فاذا وصلنا لطريق سد (ومعني طريق سد هو عدم وجود اي لعبات مرشحة لذلك المكان او انتهاء اللعبات المرشحة بعد ان وصلو كلهم لطريق سد ) نقوم بعمل  return false وقبلها نقوم بافراغ ما قامت به تلك الدالة ... واذا انتهينا من كل الاماكن نقوم بعمل return true اي بعد عمق 80

لو كودك منظم ومعمول بطريقة كويسة ال execution time عشان يعمل جدول كامل هيكن في حدود 0.1 - 0.01 

طريقة حذف العناصر تعتمد علي نفس الفكرة ولكن للأسف لا استطيع شرحها الان لضيق الوقت

ملحوظة : انا لم اقم بتطبيقها بهذا الشكل لكن اعتقد ان هذا الشكل افضل وسهل الفهم

الشكل العام :

bool BackTracking(int index){    int candidate[9]= {0,0,0,0,0,0,0,0,0}; // لتمثيل اللعبات المرشحة وعددهم في احسن الحالات 9    int length = 0;    for ( int i = 0 ; i <= 8 ; i++ )     //  حلقة تكرارية لملئ المتغير المخصص للعبات المرشحة    {        Board[index] = i + 1 ;     // لأن الاعداد تتراوح بين 1 - 9 وليس 0 - 8        if ( IsItValid() == true ) // لو وجد عدم تعارض فتكون تلك لعبة مرشحة        {            candidate[length]= i + 1 ;            length++;         }        Board[index] = 0 ;   // حيث القيمة صفر تعني انها فارغة    }    if( length == 0 )   // لو لم يوجد ولا لعبة مرشحة        return false ;    random_shuffle(&candidate[0],&candidate[length]); // لاحظ لولا وجود هذا السطر لكانت النتيجة متماثلة دائما     for ( int i = 0 ; i < length ; i++ )     {        Board[index] = candidate ;        if(index == MAX  ) // ماكس هو المتغير الذي يعني اخر مربع وهو في حالة السودوكو 80 لان هناك 81 مربع ونحن نبدأ من الصفر            return true;        if ( BackTracking(index+1) == false ) // وهذا يعني ان تلك العبة تصل لطريق مسدود            Board[index] = 0 ;        else            return true ; // وهذا يعني اننا انتهينا ولله الحمد :D     }    return false; // قمنا بعمل ذلك لان الدالة لن تصل الي هنا الا بعد تجربة كل الالعاب المرشحة وبعد استبيان ان كلهم يصلو لطريق مسدود}

توجد طريقة اخري لعمل لوحة سودوكو سريعة جدا ولكنها نوعا ما تعتبر غش

تتمثل في :

1 - ملئ array يمثل اللوحة بقيم لوحة معمولة مسبقا ( من اي جريدة او موقع او حتي من المولد الذي قمت - انت - بعمله بخوارزمية backtracking :D )

2- ملئ array اخر بقيم اللوحة وهي محذوف منها المطلوب حله

3- قم بقلب ال arrays مرات كثييرة بطرق عديدة معروفة لا تخل بصحة اللعبة

4 - تظهر لك array الأولي بشكل جديد تماما تمثل الحل الصحيح وتظهر لك array الثانية بشكل جديد تماما ايضا

ومبروك قمت بعمل لعبة :D

تمت اضافة امكانية اللعب والتحكم بأسهم اللوحة

للأسف لم أجد طريقة غير getch() في conio.h

منتظر رأيكم

// ايه الفشل ده .. عليا امتحانين يوم الأحد وانا بلعب :D

#include <iostream>#include <ctime>#include <cstdlib>#include <algorithm>#include <conio.h>#include <windows.h>using namespace std;void Board(int number[],int MoveMent);void clean();void Organize();int number[81];int number_solution[81];class check{private:    void information(int index , int *row , int *column , int *block ) // first 2 are rows .. last 2 are columns    {        int temp = index;        *block=0;        while(temp > 8)            temp = temp - 9 ;        *column = temp;        *row = int(index/9);        if( *row <= 2 )        {            if(*column <=2)            {                *block = 0;                return;            }            else if(*column > 2 && *column <= 5)            {                *block = 1;                return;            }            else            {                *block = 2;                return;            }        }        if(*row > 2)        {            if(*row <= 5 )            {                if(*column <=2)                {                    *block = 3;                    return;                }                else if(*column > 2 && *column <= 5)                {                    *block = 4;                    return;                }                else                {                    *block = 5;                    return;                }            }            if(*row > 5)            {                if(*column <=2)                {                    *block = 6;                    return;                }                else if(*column > 2 && *column <= 5)                {                    *block = 7;                    return;                }                else                {                    *block = 8;                    return;                }            }        }    }public :    bool ValidOrNot(int numbera[] , int index)    {        int row,column,block,limits[4],temp;        information( index,&row,&column,&block );        //check rows        int check_rows[10]= {0,0,0,0,0,0,0,0,0,0};        for(int i = 0 ; i <= 8 ; i++)        {            check_rows[numbera[row*9+i]]++;        }        for(int T = 1 ; T<=9 ; T++)            if(check_rows[T]>1)                return false;        //check column        int check_column[10]= {0,0,0,0,0,0,0,0,0,0};        for(int i = 0 ; i <= 8 ; i++)        {            check_column[numbera[column+i*9]]++;        }        for(int T = 1 ; T<=9 ; T++)            if(check_column[T]>1)                return false;        //check blocks        int Check_Block[10]= {0,0,0,0,0,0,0,0,0,0};        // 0 - 1 rows  2 - 3 columns        temp=block;        while( temp > 2 )            temp = temp - 3;        limits[2]=temp*3;        limits[3]=temp*3 + 2;        if(block <= 2)        {            limits[0] = 0;            limits[1] = 2;        }        if (block >=3 && block <= 5 )        {            limits[0] = 3;            limits[1] = 5;        }        else if (block >= 6 && block <= 8)        {            limits[0] = 6 ;            limits[1] = 8 ;        }        for(int R = limits[0] ; R <= limits[1] ; R++)        {            for(int C = limits[2] ; C <= limits[3] ; C ++ )            {                Check_Block[numbera[9*R + C]]++;            }        }        for(int T = 1 ; T<=9 ; T++)            if(Check_Block[T]>1)                return false;        return true;    }};class generator{private:    int solution = 0 ;    void BTSolver(int index , check helper)    {        if(solution > 1 )            return ;        if(number[index] != 0 )        {            if( index == 80 )            {                solution++;                return;            }            else                BTSolver(index+1 , helper);        }        else            for(int i = 0 ; i <= 8 ; i++)            {                if(solution > 1 )                    return ;                number[index]=i+1;                if(helper.ValidOrNot(number,index) == true )                {                    if(index == 80)                        solution++;                    else                        BTSolver(index+1 , helper );                }                number[index]=0;            }        return ;    }    int RandomRemover(check helper)    {        int Remover[81];        for(int i = 0 ; i<= 80 ; i++)        {            Remover=i;        }        random_shuffle(&Remover[0],&Remover[81]);        for(int i = 0 ; i <= 80 ; i++)        {            solution = 0;            int temp = number[Remover];            number[Remover]=0;            BTSolver(0,helper);            if(solution > 1)                number[Remover]=temp;            system("cls");            cout<<(i*100)/(80)<<" %" ;        }        return true;    }    bool BTCreator(int index , check helper ,int *Board ){    int candidate[9]= {0,0,0,0,0,0,0,0,0}; // لتمثيل اللعبات المرشحة وعددهم في احسن الحالات 9    int length = 0;    for ( int i = 0 ; i <= 8 ; i++ )     //  حلقة تكرارية لملئ المتغير المخصص للعبات المرشحة    {        Board[index] = i + 1 ;     // لأن الاعداد تتراوح بين 1 - 9 وليس 0 - 8        if ( helper.ValidOrNot( *&Board , index ) == true ) // لو وجد عدم تعارض فتكون تلك لعبة مرشحة        {            candidate[length]= i + 1 ;            length++;        }        Board[index] = 0 ;   // حيث القيمة صفر تعني انها فارغة    }    if( length == 0 )   // لو لم يوجد ولا لعبة مرشحة        return false ;    random_shuffle(&candidate[0],&candidate[length]); // لاحظ لولا وجود هذا السطر لكانت النتيجة متماثلة دائما    for ( int i = 0 ; i < length ; i++ )    {        Board[index] = candidate ;        if(index == 80  ) // ماكس هو المتغير الذي يعني اخر مربع وهو في حالة السودوكو 80 لان هناك 81 مربع ونحن نبدأ من الصفر            return true;        if ( BTCreator(index+1,helper,&*Board) == false ) // وهذا يعني ان تلك العبة تصل لطريق مسدود            number[index] = 0 ;        else            return true ; // وهذا يعني اننا انتهينا ولله الحمد :D    }    return false; // قمنا بعمل ذلك لان الدالة لن تصل الي هنا الا بعد تجربة كل الالعاب المرشحة وبعد استبيان ان كلهم يصلو لطريق مسدود}public:    bool BTManager ()   // Back tracking algorithm Manager    {        check helper;        BTCreator( 0 , helper , number );        for(int i = 0 ; i<=80 ; i++)        {            number_solution=number;        }        RandomRemover(helper);    }};int main(){    srand(time(NULL));    clean();    generator generates;    generates.BTManager();    Organize();}void Organize(){    int MoveMent = 1;    check Ahmed;    int number_temp[81];    int F_I[81];    for(int i = 0 ; i <= 80 ; i++)    {        F_I=0;        number_temp=number;        if(number != 0)        {            F_I=1;        }    }    Board( number_temp,MoveMent);    while(true)    {        for(int i = 0 ; i <= 80 ; i++)        {            if(number_temp==0)                break;            if(i == 80)            {                cout<<endl<<endl<<"CONGRATULATIONS ! YOU ARE THE BEST :D";                return ;            }        }        bool AX = false;        bool ANY = true;        if( F_I[MoveMent-1] == 1 )            ANY = false;        char getc = getch();        switch (getc)        {             case 27 :            {                system("cls");                Board(number_solution,MoveMent);                return ;            }        case 75  :        {            if(MoveMent > 1)            {                AX=true;                MoveMent --;                break;            }        }        case 77 :        {            if(MoveMent < 81)            {                AX=true;                MoveMent ++ ;                break;            }        }        case 72:        {            if(MoveMent > 9)            {                AX = true;                MoveMent -= 9 ;                break;            }        }        case 80 :        {            if(MoveMent <= 72)            {                AX=true;                MoveMent += 9 ;                break;            }        }        }        if(( getc == 8 || getc=='1' || getc == '0' || getc == '2' || getc == '3' || getc == '4' || getc == '5' || getc == '6' || getc == '7' || getc == '8' || getc == '9') && ANY == true   )        {            if(getc == 8)                getc=='0';            int temxp = number_temp[MoveMent-1];            number_temp[MoveMent-1] = atoi(&getc);            if( Ahmed.ValidOrNot(number_temp,MoveMent-1) == true)                AX = true;            else            {                number_temp[MoveMent-1]=temxp;                Beep(1000,500);            }        }        if(AX == true)        {            system("cls");            Board(number_temp,MoveMent);        }    }}void Board(int numbers[], int MoveMent) // Draw board{    char S = 221;    cout<<endl;    int j = 0;    int temp[2]= {0,0};    for(int row = 0 ; row<= 35 ; row++)    {        if(row % 4 == 0)        {            temp[0]++;            if( (temp[0]-1) % 3 == 0 )                cout<<string(73 , 220);            else            {                for(int i = 0 ; i<= 2 ; i++)                {                    cout<<S;                    cout<<string(23,'-');                }                cout<<S;            }        }        else        {            if( (row - 2) % 4 == 0)            {                for(int i = 0 ; i<=8 ; i++)                {                    temp[1]++;                    if( (temp[1]-1) % 3 == 0 )                        cout<<S;                    else                        cout<<"|";                    temp[1]==0;                    cout<<"   ";                    if( number[j] != number_solution[j] && numbers[j] != 0 || numbers[j] != number[j] )                        SetConsoleTextAttribute( GetStdHandle( STD_OUTPUT_HANDLE ), 0x02 );                    if ( MoveMent == j + 1 )                        SetConsoleTextAttribute( GetStdHandle( STD_OUTPUT_HANDLE ), 0x20 );                    if(  numbers[j] != 0 )                        cout<< numbers[j];                    else                        cout<<" ";                    SetConsoleTextAttribute( GetStdHandle( STD_OUTPUT_HANDLE ), 0x07 );                    cout<<"   ";                    j++;                }                cout<<S;            }            else            {                for(int i = 0 ; i<=8 ; i++)                {                    temp[1]++;                    if( (temp[1]-1) % 3 == 0 )                        cout<<S;                    else                        cout<<"|";                    temp[1]==0;                    cout<<string(7,' ');                }                cout<<S;            }        }        cout<<endl;    }    cout<<string(73 , 220);    cout<<endl<<"To see solution please press ESC " ;}void clean(){    for(int i = 0 ; i<= 80 ; i++)    {        number=0;    }}