|
1 / 0 / 0
Регистрация: 23.12.2008
Сообщений: 54
|
|
| 1 | |
Алгоритм генерации судоку - нужна помощь06.12.2008, 09:41. Показов 34780. Ответов 2
Метки нет (Все метки)
Необходима помощь в составлении алгоритма генерации массивов судоку. Короткая справка: Стандартный судоку представляет собой таблицу 9*9, заполненную цифрами от 1 до 9 по следующим правилам: 1)ни в одной строке не должно быть повторяющихся цифр 2)ни в одном столбце не должно быть повторяющихся цифр 3)двумерный массив разделен на сектора размерностью 3*3 клетки(таких секторов 9) и в этих секторах не должно быть повторяющихся цифр Повторяю, нужен именно алгоритм генерации исходной таблицы, а не алгоритм решения! я смог додуматься только до такого: 1)назначаю массивы кандидатов для строк, столбцов и секторов размерность каждого массива n*n,где n - размерность таблицы судоку то есть если таблица судоку 4*4, то массивы кандидатов выглядят так: с1: 1 2 3 4 //первая строка 1 2 3 4//вторая строка 1 2 3 4//третья строка 1 2 3 4//четвертая строка тоже самое и для столбцов, и для секторов. 2)далее в двойном цикле по строкам и столбцам сначала определяем номер сектора(здесь у меня вообще сделано по дилетантски, кто подскажет более оптимальный алгоритм, буду премного благодарен) затем случайно определяем число от 1 до n, затем смотрим присутствует ли оно в массиве кандидатов на эту строчку, столбец и сектор. Если присутствует, то элементу массива судоку присваеваем это число, а в массивах кандидатов его зануляем. Выглядит это примерно так: Генерируем к примеру 12 элемент(все описываю для массива судоку 4*4). Номер его строки 3, номер столбца 4, номер сектора 4. Выпало число 3 тогда массивы кандидатов будут выглядеть так: строки: 1 2 3 4 1 2 3 4 1 2 0 4 1 2 3 4 столбцы: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 0 сектора: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 0 Шаг 2 повторяем до тех пор, пока не будут сгенерированы верно все элементы. Алгоритм у меня кривой, не хватает одного или нескольких пунктов. Если кто то знает каких пунктов не хватает у меня, или может поделиться своим алгоритмом, то прошу помочь. в качестве реализации выбрал язык BС++: Код
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
const int n = 4 ;
void init_ar ( int ar[ n ][ n ] )
{
int i , j ;
for(i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
ar[ i ][ j ] = j ;
}
void init_cands( int c1[ n ][ n ] , int c2[ n ][ n ] , int c3[ n ][ n ] )
{
init_ar( c1 ) ;
init_ar( c2 ) ;
init_ar( c3 ) ;
}
void gen_sud( int c11[ n ][ n ],int c22[ n ][ n ],int c33[ n ][ n ],int a[ n ][ n ][ n ] )
{
int z , i , j , k ;
randomize() ;
init_cands( c11 , c22 , c33 ) ;
for( i = 1 ; i <= 4 ; i++ )
{
for( j = 1 ; j <=4 ; j++ )
{
if( i <= 2 && j <= 2 )
k = 1 ;
if( i <= 2 && j >= 3 )
k = 2 ;
if( i >= 3 && j <= 2 )
k = 3 ;
if( i >= 3 && j >= 3 )
k = 4 ;
z = random( 4 ) + 1 ;
while( 1 )
{
if( c11 [ i ][ z ] == 0 || c22[ j ][ z ] == 0 || c33[ k ][ z ] == 0 )
{
z = random( 4 ) + 1 ;
}
else
{
c11[ i ][ z ] = 0 ;
c22[ j ][ z ] = 0 ;
c33[ k ][ z ] = 0 ;
a[ i ][ j ][ k ] = z ;
cout << " " << a[ i ][ j ][ k ] ;
break ;
}
}
}
}
}
void main()
{
clrscr();
int s[n][n][n],str[n][n],stb[n][n],mgrid[n][n];
gen_sud(str,stb,mgrid,s);
getch();
}
Можно еще реализовать алгоритм рекурсивно(читал на сайтах), но я не понимаю что представляет из себя алгоритм перебора с возвратом и каким образом с помощью него можно реализовать данную задачу(читал еще про алгоритм раскраски графа) если кто то знает ссылку на сайт, где объясняется мой вопрос, прошу поделиться. З.Ы.: Прошу не кидать сслыки на сайты, где выкладывают просто исходники или алгоритм типа: "Смотрим строчки и столбцы с секторами и проверяем, уникально ли число в данной области " - это я и так знаю. ошибка в примере массивов кандидатов. Недосмотрел: строки: 1 2 3 4 1 2 3 4 1 2 0 4 1 2 3 4 столбцы: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 0 4 сектора: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 0 4 Прогоняя по шагам программу(для массива 9*9), я понял что она зацикливается примерно в таких случаях: 2 7 4 1 9 3 6 8 5 3 6 8 4 5 7 2 1 9 1 9 5 8 6 2 4 3 7 8 4 2 7 2 5 1 9 3 5 3 9 4 2 8 7 6 X Х - число на котором программа циклится То есть если в общей области строки и столбца (или сектора) попадается элемент который уже ставили, то программа зацикливается. Как сделать обработчик таких ситуаций? Тут вроде нужна рекурсия (алгоритм перебора с возвратом наверное), но я не понимаю как этот алгоритм можно применить к данной ситуации. Прочитал что представляет из себя рекурсия, ну и попытался сгенерировать массив диагональный массив судоку(там нет разделения на сектора, а есть только проверка в главной и побочной диагонали). Составил алгоритм, он описывается так: 1. первую ячейку таблицы назначаем произвольным образом 2. заполняем следующие ячейки: а. назнаем произвольное число б. если это число: не содержится в текущем столбце, текушей строке, или находится на какой либо диагонали и не содержится в ней, то текущей ячейке присваиваем это число в. если число не удовлетворяет описанным условиям, делаем откат на один шаг и назначаем другое число для предыдущей ячейки, удовлетворяющая описанным выше условиям г. если число заполненных ячеек = 81, заканчиваем работу вот код программы составленный вроде по алгоритму, но она почему то не работает(выдает бесконечный массив а потом вылетает). Попытался прогонять по шагам - почему то нормально ставятся только первые 6 ячеек, остальное идет с повторениями. Помогите разобраться чего не хватает в программе(может я неправильно понял принцип действия рекурсии). Помогите разобраться. Вод код: Код
#include <conio.h>
#include <stdlib.h>
#include <iostream.h>
int const n=9;
void init(int a[n][n])//inicializacia tablici(prisvaivaem 0)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
}
int unic(int a[n][n],int ci,int cj,int k)//unicalnost v stroke,stolbze i diagonali
{
int i,j,f=0;
for(i=1;i<=n;i++)
if(a[i][cj]==k) f++;
for(j=1;j<=n;j++)
if(a[ci][j]==k) f++;
if(ci==cj)
{
for(i=1;i<=n;i++)//glavnaia diagonal
if(a[i][i]==k) f++;
}
else
if(cj==n-ci+1)
{
for(i=1;i<=n;i++)//pobochnaia diagonal
if(a[i][n-i+1]==k) f++;
}
return f;
}
void rec(int a[n][n],int i,int j)//recursia dlia zapolnenia tablici
{
int it,jt,fl,num;
for(it=i;it<=n;it++)
{
for(jt=j;jt<=n;jt++)
{
num=random(9)+1;
fl=unic(a,it,jt,num);
if(fl==0)//esli sovpadenii net
{
a[it][jt]=num;
cout<<" "<<a[it][jt];
if(jt==9) cout<<"\n";
}
else//ecli est sovpadenia, to vozvrashemsia k
//predidushei iacheike
{
if(jt==1&&it>1)
rec(a,it-1,jt+8);
else
rec(a,it,jt-1);
}
}
}
}
void main()
{
clrscr();
randomize();
int s[n][n];
int i,j;
init(s);
s[1][1]=random(9)+1;
rec(s,1,2);
getch();
}
1. выбираем случайным образом координаты ячейки 2. если встретили ячейку с цифрой ноль(т.е. уже удаленную) то возвращаемся на шаг 1, иначе шаг 3 3. сохраняем значение ячеки в какой нибудь буфферной переменной и ставим цифру 0 в данную ячейку 4. восстанавливаем значение предыдущего удаленного элемента таблицы 5. если текущему (т. е. не предыдущему удаленному, а удаленному на данном шаге элементу) можно сопоставить более одного значения из набора 1 2 3 4 5 6 7 8 9 таким образом, чтобы они не противоречили правилам судоку,то возвращаемся на шаг 1, иначе данную ячейку оставляем с цифрой 0. Но программу составить почему то не получается, я не понимаю как реализовать пункт 4. Вот так бывает, составищь вроде алгоритм , а средств его реализации не знаешь  Помогите, чем сможете.
0
|
|
( Лучшие ответы (1)
| 06.12.2008, 09:41 | |
|
Ответы с готовыми решениями:
2
Алгоритм решения судоку Алгоритм решения Судоку Алгоритм генерации сетки Алгоритм генерации речи |
|
32 / 32 / 4
Регистрация: 29.12.2008
Сообщений: 75
|
|
| 29.12.2008, 20:59 | 2 |
 Сообщение было отмечено как решение
Решение
Предлагаю алгоритм генерации судоку, основанный на использовании уже ранее сгенерированных судоку.
Разберем на простом примере В качестве исходной можно взять следующую судоку: 1234 2341 3412 4123 (каждая новая строка получается из предыдущей сдвигом вправо по кольцу). Для генерации следующей судоку достаточно переставить местами две случайно выбранные строки (например, первую и третью). Получим новую судоку 3412 2341 1234 4123 Далее генерируем новую судоку путем перестановки в предыдущей любых двух случайно выбранных столбцов (например столбцов с номерами 3 и 4): 3421 2314 1243 4132 и т.д. Теоретически все это можно продолжать до бесконечности, однако, думаю, после 10 перестановок строк и столбцов новый вариант судоку будет значительно отличаться от исходного. Перейдем теперь к генерации реальной судоку. Вернемся теперь к судоку 9x9. Эти судоку, как известно, разделяются на 9 "больших" полей размера 3x3 (т.е. одно "большое" поле представляет собой квадрат из 9=3x3 "маленьких" полей). Для генерации таких судоку нужно сочетать перестановку строк и столбцов "больших" полей с перестановкой строк и столбцов "маленьких" полей внутри "большого". Например: 123 456 789 456 789 123 789 123 456 231 564 897 564 897 231 897 231 564 312 645 978 645 978 312 978 312 645 (в данной исходной судоку 9 "больших" полей отделены друг от друга пробелами и пустыми строками). Для генерации новой судоку достаточно переставить местами любые две "большие" строки (или два "больших" столбца - на выбор). Например, переставим первую и третью "большую" строку. 312 645 978 645 978 312 978 312 645 231 564 897 564 897 231 897 231 564 123 456 789 456 789 123 789 123 456 Это уже новое судоку. Теперь в последней сгенерированной судоку переставим первый и третий "большие" столбцы: 978 645 312 312 978 645 645 312 978 897 564 231 231 897 564 564 231 897 789 456 123 123 789 456 456 123 789 Следующую судоку сгенерим таким образом: возьмем случайно выбранную "большую строку". Например, вторую: 897 564 231 231 897 564 564 231 897 Переставим в ней две случайно-выбранные маленькие строки (например вторую и третью). Получим 897 564 231 564 231 897 231 897 564 Добавим получившуюся "большую" строку вместо второй "большой" строки последней сгенерированной судоку, получим 978 645 312 312 978 645 645 312 978 897 564 231 564 231 897 231 897 564 789 456 123 123 789 456 456 123 789 Это новое судоку. Почти аналогично поступаем со случаным образом выбранным "большим" столбцом в последней сгенерированной судоку. Пусть это будет первый столбец. 978 312 645 897 564 231 789 123 456 Переставим в нем два случайно выбранных "маленьких" столбца (например, первый и второй): 798 132 465 987 654 321 879 213 546 Добавим новый большой столбец в последнюю сгенерированную судоку: 798 645 312 132 978 645 465 312 978 987 564 231 654 231 897 321 897 564 879 456 123 213 789 456 546 123 789 Комбинируй все изложенные здесь отдельные приемы по несколько раз каждый, в произвольном сочетании друг с другом, чтобы получить судоку, значительно отличающуюся от исходной. Конечно, при желании могу все вышесказанное оформить в виде блок-схемы. Но, думаю, алгоритм и так ясен и любой (даже начинающий программист) способен написать под него программу.
5
|
|
|
ниначмуроФ
851 / 535 / 110
Регистрация: 12.10.2009
Сообщений: 1,913
|
|
| 14.10.2009, 20:44 | 3 |
|
посмотри тут http://www.deco.tu2.ru/arch/archive.html
0
|
|
| 14.10.2009, 20:44 | |
| 14.10.2009, 20:44 | |
|
Помогаю со студенческими работами здесь
3
Алгоритм генерации труб Алгоритм генерации улиц/города алгоритм генерации G-code по файлу STL Алгоритм генерации турнирной сетки типа Double Elimination Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Наверх