Заполнить матрицу...SUDOCU

[vx]

Решите задачу пожалуйста.
Заполнить матрицу ( 9х9 ) случайными значениями, так чтобы числа не повторялись в строках и столбцах.

P.S. Если вы знаете что такое SUDOCU вы поймете суть задачи.

[Алексей++]

ну, скажем, суть задачи ясна, только требуется уточнение:
1) диапазон чисел - ?
2) числа - вещественные или целые ?

что есть SUDOCU не знаю )

[Sla]

попадался алгоритм генерации таблиц судоку
можно посмотреь здесь http://sudoku.org.ua/rus/ каккак парень заполняет (если не изменяет память) он ее заполняет из уже подготовленных таблиц)
Алексей1153++, цифры 1 -- 9

[rumpelstilzchen]

vx, напиши алгоритм (псевдокод), по алгоритму, поможем написать прогу в реальном коде.

[Sla]

rumpelstilschen, задача не написать прогу - а создать алгоритм, а он и не есть простым (это приблизительно как задача о 8 ферзях)
т.е. перебор с откатами

[Алексей++]

первая мысль приходит такая: окромя основной доски, заводим ещё 9 досок (матрицы,матрицы хы хы) M1[9][9], M2[9][9], ... M9[9][9] , которые являются индикаторами "минного поля" для цифр.

для удобства скучковать в трёхмерный массив

M1[N][x][y]
  N - индекс доски (0...8)
  x - 0...8
  y - 0...8

индикаторные доски изначально заполнены нулями - то есть ещё ничего не занято.
Когда на основную доску Mmain ставится цифра , то в соответствующей индикаторной доске крестиком расставляются единички - сюда такую цифру больше ставить нельзя. На всех остальных досках можно поставить одну единичку - там, где цифра была поставлена.

таким образом, всегда знаем, куда нельзя поставить очередную цифру Z.  Теперь, перебираем по порядку клетки и  ставим в них случайное число от 1 до 9.

   1) сгенерировать число, взять очередные координаты.
   2) Если число Z нельзя сюда поставить, то:
      3) инкреминировать, пока нельзя будет поставить.
   4) если пункт 3 не дал результатов, то где то ошибка в алгоритме.

и повторять 1-2-3-4 до посинения


а чтобы похожесть решений была меньше, то клетки перебирать не по очереди, а в случайном порядке, либо же начать со случайной клетки, а дальше по порядку

[Антон (LogRus)]

Я бы сделал, так посчитал бы все возможные варианты строк их всего-то 9!

а потом бы их комбинировал, делая валидацию столбцов
делов-то

[Алексей++]

разве 9 ?
123456789
132456789
213456789
231456789
312456789
321456789
412356789
413256789
421356789
423156789
431256789
432156789
...
...

[Вад]

Алексей1153++, "9!" - это "9 факториал" =)

[Алексей++]

нее, меньше. Не помню комбинаторику - все сочетания из N предметов надо посчитать. Или чё - серьёзно так много ? ))

[Aveic]

Серьезно, их ровно 362880, что и есть 9!. Я написал 9 вложенных циклов, перебирающих все 9 значений каждого элемента, и проверяя каждый набор на валидность, в итоге получилось 362880.

[Finch]

В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.

(это приблизительно как задача о 8 ферзях)

Скорее всего, задача о 8 ладьях

[Aveic]

В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.

Это одна из разновидностей, есть еще разновидность, где не должны повторятся цифры на главной и побочной диагонали.

[Sands]

Aveic, Еще с основной задачей не разобрались, а уже пошли разновидности )))

[Алексей++]

В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.

тогда мой вариант всё равно катит - в минных полях рисовать нужные квадраты - и всё станет как требуется

[Aveic]

Aveic, Еще с основной задачей не разобрались, а уже пошли разновидности )))

Да вообще задача была просто:

Решите задачу пожалуйста.
Заполнить матрицу ( 9х9 ) случайными значениями, так чтобы числа не повторялись в строках и столбцах.

[PooH]

а тупой перебор с рекурсией тут разве не прокатит?
я думаю он вернет что-то типа:
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

я так понимаю это удовлетворяет условиям

[Sla]

PooH, это одно из решения

[PooH]

а кто просил два ? задача решена !!!
а если серьезно, то такой результат будет после рекурсии, если делать последовательный перебор, а если делать не последовательный перебор, то будут разные результаты...

[Aveic]

в общем, решил задачу в лоб (совпадает с решением от LogRus): сгенерировал сначала возможные строки, (их всего 9!=362880), потом выставлял строки с проверкой столбцов. Вот код на С++:

Код: (C++)

#include <iostream>
#include <time.h>

typedef int row_t[9];

const unsigned int N=362880;
row_t rows[N];
int theK=0;



void assign_row(int k,int* row)
{
        for(int i=0;i<9;i++)
                rows[k][i]=row[i];
}

bool is_valid_row(int* row)
{
    for(int i=0;i<9;i++)
                for(int j=0;j<9;j++)
                {
                        if(i==j)
                                continue;
                        if(row[i]==row[j])
                                return false;
                }
        return true;
}

void fill_rows()
{
        row_t row;
        for(int i0=1;i0<=9;i0++)
        {
                row[0]=i0;
                for(int i1=1;i1<=9;i1++)
                {
                        row[1]=i1;
                        for(int i2=1;i2<=9;i2++)
                        {
                                row[2]=i2;
                                for(int i3=1;i3<=9;i3++)
                                {
                                        row[3]=i3;
                                        for(int i4=1;i4<=9;i4++)
                                        {
                                                row[4]=i4;
                                                for(int i5=1;i5<=9;i5++)
                                                {
                                                        row[5]=i5;
                                                        for(int i6=1;i6<=9;i6++)
                                                        {
                                                                row[6]=i6;
                                                                for(int i7=1;i7<=9;i7++)
                                                                {
                                                                        row[7]=i7;
                                                                        for(int i8=1;i8<=9;i8++)
                                                                        {
                                                                                row[8]=i8;
                                                                                if(is_valid_row(row))
                                                                                {
                                                                                        assign_row(theK,row);
                                                                                        theK++;
                                                                               
                                                                                }
                                                                        }
                                                                }
                                                        }
                                                }                                              
                                        }
                                }
                        }
                }
        }
}

int used[N];    //flags of used arrays 0 -not used, 1- used
row_t matrix[9];

int cur_row=0;


void assign_matrix_row(int n,int r)
{
        for(int i=0;i<9;i++)
                matrix[n][i]=rows[r][i];
}

bool is_valid_matrix(int n_row)
{
        for(int i=0;i<n_row;i++)
        {
                for(int j=0;j<9;j++)
                        if(matrix[i][j]==matrix[n_row][j])
                                return false;
        }
        return true;
}

unsigned int get_next_r()
{
        static unsigned int was=98440;
        if(was>=N)
                was=0;
        return was++;
}

void print_matrix();

void put_next_row()
{
        if(cur_row>=9)
                return; //end of calculating
        for(;;)
        {
                unsigned int r=get_next_r();
                if(used[r]==1)
                        continue;
                else
                {
                        used[r]=1;
                        assign_matrix_row(cur_row,r);
                        if(is_valid_matrix(cur_row))
                        {
                                cur_row++;
                                break;
                        }                      
                }
        }//for(;;) :)
        put_next_row();
}



void print_matrix()
{
        std::cout<<"M=\n";
        for(int i=0;i<9;i++)
        {
                for(int j=0;j<9;j++)
                        std::cout<<matrix[i][j]<<" ";
                std::cout<<"\n";
        }

}

int main()
{
        srand(time_t(0));
        fill_rows();
        std::cout<<"Done generating rows (N="<<theK<<")\n";
        put_next_row();
        print_matrix();
       
        return 0;
}

По идеи, функцию fill_rows() можно вызвать один раз - для вывода в файл, а потом парсить оттуда матрицу rows. Далее для рандомности создания матриц, нужно поработать с функцией get_next_r(). Именно она выбирает строки для вставки.
И напоследок один из примеров работы программы:

Код:

Done generating rows (N=362880)
M=
3 5 6 8 2 7 9 1 4
4 1 2 3 5 6 7 8 9
5 2 1 4 3 8 6 9 7
6 3 4 1 7 9 2 5 8
7 4 3 2 9 1 8 6 5
8 6 5 9 1 2 4 7 3
9 7 8 5 4 3 1 2 6
1 8 9 7 6 4 5 3 2
2 9 7 6 8 5 3 4 1
Press any key to continue

[PooH]

у я предлагал примерно так:

Код: (Text) pseudo code

function check(x,y) return boolean
{
  int i=1;
  bool f=false;
  loop
    matrix[x,y]:=i;
    if check_rules(x,y) /* проверка условий */ and check(next_x, next_y) /* рекурсия */ then f:=true;
    i+=1;
  while i<10 and not f;
  return f;
}

причем, кажется, если никогда не возвращать true при проверке последней клетки, а всесто true выводить матрицу, то получатся все возможные варианты... только я даже боюсь представить сколько это времени займет =)

[vx]

Aveic, твой алгоритм хорош но вот на моем компе он выполняеться минуты 2.=(

[vx]

И еще, матрицу надо заполнить СЛУЧАЙНЫМИ значениями.

[vx]

Вот написал код. Только надо написать функцию 'bool search_in_matrix(int buf, int y, int x)'

Код:

#include <iostream>
#include <cstdlib>
#include <time>
using namespace std;
int maitrix[9][9] = {};
bool search_in_matrix(int buf, int y, int x)
{
	// Поиск значения buf c координатами x и y в matrix[9][9];
}
int main()
{
	srand(time(0));
	for(int y=0; y<9; y++)
	{
		for(int x=0; x<9; x++)
		{
			do
			{
				buf=rand() % 10;
					if(buf==0) buf=1;
			}while(search_in_matrix(buf, y, x));
			matrix[y][x] = buf;
			cout << matrix[y][x] << " ";
		}
		cout << endl;
	}
	return 0;
}

[Вад]

В принципе, можно найти все (или сколько время позволяет) варианты допустимых комбинаций 9 чисел на доске 9х9 (без учёта значения каждого числа), а произвольность обеспечить генерацией произвольного отображения n -> Xn (сгенерить случайную последовательность чисел 1..9, например, [7 3 4 1 9 6 2 8 5], и заменить соответственно 1 на 7, 2 на 3, 3 на 4 и т.д.), применив отображение ко всей доске.

P.S. Подумал, что немного непонятно. Предлагаю искать не все перестановки, а все возможные перестановки x1, x2, ...x9. Потому что если взять первую строку
"x1, ... x9" и строку "x2...x9, x1" - то они инвариантны, легко переводятся друг в друга с помощью перестановки циклическим сдвигом.
Соответственно, реальную перестановку получаем генерацией произвольного соотвествия (пусть x1 = случайному числу, x2- случайному, неравному x1, и т.д.).

[vx]

Вад: Извините, но чёта я не понял, можно по проще.

[Aveic]

Aveic, твой алгоритм хорош но вот на моем компе он выполняеться минуты 2.=(

основное время отнимает функция fill_rows(). По идеи ее нужно вызвать только 1 раз (чтобы вывести в файл, и остальные разы, оттуда считывать). Можешь сам реализовать...

И еще, матрицу надо заполнить СЛУЧАЙНЫМИ значениями.

еще раз говорю, все дело в функции get_next_r() поставить там код

Код:

static unsigned int was=rand()%N;

и получишь каждый раз разные значения, если rand() будет действительно выдавать разные значения...

[Вад]

В общем, использование только "1 2 3 4 5 6 7 8 9" в качестве первой строки резко уменьшает число вариантов перебора. А потом все остальные варианты получаются перестановкой 1 -> x1, 2 -> x2 и т.д.

[vx]

Люди а как насчет моего кода(приведен выше)

[Вад]

vx,
1. Не делай рандом внутри цикла. Это только замедляет. Делай просто цикл 1..9 с проверкой, нет ли этого значения в текущих строке и столбце, перебирая все значения.
2. Делай первую строку 1 2 3 4 5 6 7 8 9 и заполняй все остальные примерно так, как у тебя сделано, + мой пункт 1.
3. Генерируй перестановку X (9 чисел) так же, как генерируешь строку в приведённой тобой реализации (с проверкой повторения только в строке).
4. Заменяй в таблице символ i на значение из вектора перестановки x[ i ].