VPF::Алгоритм генерации судоку - Форум программистов

Алина

Дата 2.7.2006, 21:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 60
Регистрация: 14.5.2005

Репутация: нет
Всего: нет

Популярная нынче игра в циферки - судоку. На поле 9х9 вписать числа от 1 до 9 так, чтобы они не повторялись ни в строке, ни в столбике, ни в клетке 3х3 (таких клеток на игровом поле 9), если изначально в некоторых клетках задан некоторый набор чисел.

Написать решалку для нее мне удалось без проблем, а вот с алгоритмом для генерации головоломок почему-то сложнее. Может кто-то подскажет его?

Могу выложить свой, только вот он решать-решает, а генерировать не умеет...

Алина

Дата 3.7.2006, 07:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 60
Регистрация: 14.5.2005

Репутация: нет
Всего: нет

Вроде рабочий уже...

Код


#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


void Step1(void);
void Step2(void);


typedef int TCandidat[9];

TCandidat mesh[9][9];
int start[9][9], roll[9][9];
int board[9][9];
int tempi=0,tempj=0;
TCandidat temp_cand;
int Rall_number=0;
int cont=0;
int old_opened=-1;

//void Step1(void);
//void Step2(void);


void Cand_Init(TCandidat a)
{int i;
 for(i=0;i<9;i++)
  a[i]=1;
}

void Init_9_9( int a[9][9])
{int i,j;
 for(i=0;i<9;i++)
  for(j=0;j<9;j++)
   a[i][j]=0;
}

int Cand_Count(TCandidat a)
{int i, c=0;
 for(i=0;i<9;i++)
  if (a[i]==1) c++;
 return c;
}

int Unic_RCM(int a,int b, int val)
{int i,j,flag=0;
 // unic in a row
 for(j=0;j<9;j++)
   if(board[a][j]==val) flag++;
 if (flag==0) //unikalno v stroke, proverjaem stolbets
  {for(i=0;i<9;i++)
    if(board[i][b]==val) flag++;
  }
 if (flag==0) //unikalno i v stroke, i v stolbtse, proverim sector
 {for(i=(a/3)*3;i<(a/3)*3+3;i++)
   for(j=(b/3)*3;j<(b/3)*3+3;j++)
    if(board[i][j]==val) flag++;
 }
if( flag==0)
 return 1; // chislo unikalno
else
 return 0; // chislo ne unikalno
}

int Cand_to_Number(TCandidat a)
{int i,c=0;
 for(i=0;i<9;i++)
   if(a[i]==1)
    {c=i+1;
     break;
    }
 return c;
}

void Step1(void)
{for(int i=0;i<9;i++)
  for(int j=0;j<9;j++)
   board[i][j]=start[i][j];
 // find a place for a value
 do
 {
 tempi=random(9);
 tempj=random(9);
 }
 while(board[tempi][tempj]!=0);
// cout<<"\nposition:"<<tempi<<" "<<tempj;
 //find a value
 int val_count=0, temp_val;
 Cand_Init(temp_cand);
 while(val_count<9)
 {do
  {temp_val=random(9);
  }
  while(temp_cand[temp_val]==0);// eto znachenie ushe vibiralos
  val_count++;
  temp_cand[temp_val]=0;
  if(Unic_RCM(tempi,tempj, temp_val+1)==1)
   {board[tempi][tempj]=temp_val+1;
    start[tempi][tempj]=temp_val+1;
    break;
   }
 }

 if(Rall_number<=50)
 {cout<<endl<<"Rall_number="<<Rall_number;
  if(val_count==8)
   Step1(); //rekursija
  else
   Step2(); // popitka reshenija
 }
 else
  {if(cont<30)
   {Rall_number=0;
    cout<<endl<<"cont="<<cont;//getch();
   for(i=0;i<15;i++)
    {tempi=random(9);
     tempj=random(9);
     start[tempi][tempj]=0;
    }
    cont++;
    Step1();
   }
   cout<<endl<<"Rall_number="<<Rall_number<<"!!! Stop!!!";
  }

}

void Step2(void)
{int i,j,k1,k2;
// cout<<endl<<"position:"<<tempi<<" "<<tempj;
//cout<<endl<<"val -= "<<board[tempi][tempj]<<endl;

for(i=0;i<9;i++)
 for(j=0;j<9;j++)
  Cand_Init(mesh[i][j]);

 for(i=0;i<9;i++)
  for(j=0;j<9;j++)
   if (board[i][j]!=0)// v jachejku vpisano chislo
    {//zapreschaem v stolbtse
     for(k1=0;k1<9;k1++)
      mesh[k1][j][board[i][j]-1]=0;

     //zapreschaem v stroke
     for(k2=0;k2<9;k2++)
      mesh[i][k2][board[i][j]-1]=0;
     // sektor
     for(k1=(i/3)*3;k1<(i/3)*3+3;k1++)
      for(k2=(j/3)*3;k2<(j/3)*3+3;k2++)
       mesh[k1][k2][board[i][j]-1]=0;
     //sozdaem masku jachejki (i,j)
     for(k1=0;k1<9;k1++)
      mesh[i][j][k1]=0;
     mesh[i][j][board[i][j]-1]=1;

    }
 //jachejki, gde vse chisla zaprescheni
 int flag=0, t=0;
 for(i=0;i<9;i++)
  for(j=0;j<9;j++)
   if (Cand_Count(mesh[i][j])==0) flag++;
 if (flag!=0) //net reshenija
  {cout<<endl<<"Net reshenija! Otkat poslednego izmenenija!"<<endl;
   start[tempi][tempj]=0;
   Rall_number++;
   Step1();
  }
 else
  {for(i=0;i<9;i++)
    for(j=0;j<9;j++)
     if (Cand_Count(mesh[i][j])==1)
      {//podstavliajem tsifru na dosku
       board[i][j]=Cand_to_Number(mesh[i][j]);
       t++;
      }
   int number;
   //prosmatrivaem stroki
   for(i=0;i<9;i++)
    for(number=0;number<9;number++)
     {flag=0;
      for(j=0;j<9;j++)
       if(mesh[i][j][number]==1) flag++;
      if(flag==1)//nashli tolko odno vozmozhnoje mesto
       for(j=0;j<9;j++)
     if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
     }
    //prosmatrivaem stolbtsi
    for(j=0;j<9;j++)
     for(number=0;number<9;number++)
      {flag=0;
       for(i=0;i<9;i++)
    if(mesh[i][j][number]==1) flag++;
       if(flag==1)
    for(i=0;i<9;i++)
      if (mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
      }
    // prosmatrivaem sectora
    for(int a=0;a<9;a=a+3)
     for(int b=0;b<9;b=b+3) //eto perebiraem vse sectora
      { for(number=0;number<9;number++)
     {flag=0;
      for(i=(a/3)*3;i<(a/3)*3+3;i++)
       for(j=(b/3)*3;j<(b/3)*3+3;j++)
        if(mesh[i][j][number]==1) flag++;
      if(flag==1)
       for(i=(a/3)*3;i<(a/3)*3+3;i++)
        for(j=(b/3)*3;j<(b/3)*3+3;j++)
         if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
     }
      }
    //schitaem skolko mest zapolneno v matritse
    flag=0;
    for(i=0;i<9;i++)
     for(j=0;j<9;j++)
      if (board[i][j]==0)
       flag++;
    cout<<endl<<"Not opened cells:"<<flag;
    cout<<"\nt="<<t<<endl;
    if((flag>0)&&(flag<81)&&(old_opened!=flag))
     {
      old_opened=flag;
       cout<<"\nGOTO Step2";
      Step2();
     }
    else
     if((flag>0)&&(flag<81)&&(old_opened==flag))
      {old_opened=flag;
       cout<<"\nGOTO Step1";
       Step1();
      }
  }
}


void main(void)
{
randomize();
Init_9_9(start); Init_9_9(roll); Init_9_9(board);
cout<<endl;
int t,i,j;

for(i=0;i<9;i++)
 for(j=0;j<9;j++)
  Cand_Init(mesh[i][j]);
//Step1();
cout<<endl<<"Maski"<<endl;
for(i=0;i<9;i++)
 {for(j=0;j<9;j++)
   {if(board[i][j]!=0)
    t=Unic_RCM(i,j,board[i][j]);
    else
      t=8;
    cout<<t<<" ";
    }
  cout<<endl;
 }
getch();
cout<<endl<<"Setka"<<endl;
for(i=0;i<9;i++)
 {for(j=0;j<9;j++)
   {//t=Unic_RCM(i,j,2);
    for(int k1=0;k1<9;k1++)
     cout<<mesh[i][j][k1];
    cout<<" ";
    }
  cout<<endl;
 }
getch();

Step1();

    //schitaem skolko mest zapolneno v matritse
    int flag=0;
    for(i=0;i<9;i++)
     for(j=0;j<9;j++)
      if (board[i][j]==0)
       flag++;
    cout<<endl<<"Opened cells:"<<flag;
    //schitaem skolko mest zapolneno v matritse
    flag=0;
    for(i=0;i<9;i++)
     for(j=0;j<9;j++)
      if (board[i][j]!=0)
       flag++;
    cout<<endl<<"Passed cells:"<<flag;

cout<<"Task:"<<endl;
for(i=0;i<9;i++)
 {for(j=0;j<9;j++)
   cout<<start[i][j]<<" ";
  cout<<endl;
 }

cout<<"Solve:"<<endl;
for(i=0;i<9;i++)
 {for(j=0;j<9;j++)
   cout<<board[i][j]<<" ";
  cout<<endl;
 }
getch();

// Step1();
getch();
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »