vx
Гость
|
|
« : 27-02-2008 06:45 » |
|
Решите задачу пожалуйста. Заполнить матрицу ( 9х9 ) случайными значениями, так чтобы числа не повторялись в строках и столбцах.
P.S. Если вы знаете что такое SUDOCU вы поймете суть задачи.
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #1 : 27-02-2008 07:09 » |
|
ну, скажем, суть задачи ясна, только требуется уточнение: 1) диапазон чисел - ? 2) числа - вещественные или целые ?
что есть SUDOCU не знаю )
|
|
|
Записан
|
|
|
|
Sla
|
|
« Ответ #2 : 27-02-2008 07:20 » |
|
попадался алгоритм генерации таблиц судоку можно посмотреь здесь http://sudoku.org.ua/rus/ каккак парень заполняет (если не изменяет память) он ее заполняет из уже подготовленных таблиц) Алексей1153++, цифры 1 -- 9
|
|
« Последнее редактирование: 27-02-2008 08:06 от Sla »
|
Записан
|
Мы все учились понемногу... Чему-нибудь и как-нибудь.
|
|
|
rumpelstilzchen
|
|
« Ответ #3 : 27-02-2008 09:11 » |
|
vx, напиши алгоритм (псевдокод), по алгоритму, поможем написать прогу в реальном коде.
|
|
|
Записан
|
|
|
|
Sla
|
|
« Ответ #4 : 27-02-2008 09:26 » |
|
rumpelstilschen, задача не написать прогу - а создать алгоритм, а он и не есть простым (это приблизительно как задача о 8 ферзях) т.е. перебор с откатами
|
|
|
Записан
|
Мы все учились понемногу... Чему-нибудь и как-нибудь.
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #5 : 27-02-2008 09:50 » |
|
первая мысль приходит такая: окромя основной доски, заводим ещё 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 до посинения
а чтобы похожесть решений была меньше, то клетки перебирать не по очереди, а в случайном порядке, либо же начать со случайной клетки, а дальше по порядку
|
|
« Последнее редактирование: 27-02-2008 09:53 от Алексей1153++ »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #6 : 27-02-2008 10:05 » |
|
Я бы сделал, так посчитал бы все возможные варианты строк их всего-то 9! а потом бы их комбинировал, делая валидацию столбцов делов-то
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #7 : 27-02-2008 10:20 » |
|
разве 9 ? 123456789 132456789 213456789 231456789 312456789 321456789 412356789 413256789 421356789 423156789 431256789 432156789 ... ...
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #8 : 27-02-2008 11:07 » |
|
Алексей1153++, "9!" - это "9 факториал" =)
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #9 : 27-02-2008 11:30 » |
|
нее, меньше. Не помню комбинаторику - все сочетания из N предметов надо посчитать. Или чё - серьёзно так много ? ))
|
|
« Последнее редактирование: 27-02-2008 11:32 от Алексей1153++ »
|
Записан
|
|
|
|
Aveic
Постоялец
Offline
Пол:
Yellow
|
|
« Ответ #10 : 27-02-2008 12:06 » |
|
Серьезно, их ровно 362880, что и есть 9!. Я написал 9 вложенных циклов, перебирающих все 9 значений каждого элемента, и проверяя каждый набор на валидность, в итоге получилось 362880.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #11 : 27-02-2008 12:10 » |
|
В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры. (это приблизительно как задача о 8 ферзях)
Скорее всего, задача о 8 ладьях
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
Aveic
Постоялец
Offline
Пол:
Yellow
|
|
« Ответ #12 : 27-02-2008 12:20 » |
|
В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.
Это одна из разновидностей, есть еще разновидность, где не должны повторятся цифры на главной и побочной диагонали.
|
|
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #13 : 27-02-2008 12:27 » |
|
Aveic, Еще с основной задачей не разобрались, а уже пошли разновидности )))
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #14 : 27-02-2008 12:29 » |
|
В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.
тогда мой вариант всё равно катит - в минных полях рисовать нужные квадраты - и всё станет как требуется
|
|
|
Записан
|
|
|
|
Aveic
Постоялец
Offline
Пол:
Yellow
|
|
« Ответ #15 : 27-02-2008 12:36 » |
|
Aveic, Еще с основной задачей не разобрались, а уже пошли разновидности )))
Да вообще задача была просто: Решите задачу пожалуйста. Заполнить матрицу ( 9х9 ) случайными значениями, так чтобы числа не повторялись в строках и столбцах.
|
|
|
Записан
|
|
|
|
PooH
Глобальный модератор
Offline
Пол:
... и можно без хлеба!
|
|
« Ответ #16 : 27-02-2008 12:44 » |
|
а тупой перебор с рекурсией тут разве не прокатит? я думаю он вернет что-то типа: 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 я так понимаю это удовлетворяет условиям
|
|
« Последнее редактирование: 27-02-2008 12:48 от PooH »
|
Записан
|
Удачного всем кодинга! -=x[PooH]x=-
|
|
|
Sla
|
|
« Ответ #17 : 27-02-2008 12:57 » |
|
PooH, это одно из решения
|
|
|
Записан
|
Мы все учились понемногу... Чему-нибудь и как-нибудь.
|
|
|
PooH
Глобальный модератор
Offline
Пол:
... и можно без хлеба!
|
|
« Ответ #18 : 27-02-2008 13:00 » |
|
а кто просил два ? задача решена !!! а если серьезно, то такой результат будет после рекурсии, если делать последовательный перебор, а если делать не последовательный перебор, то будут разные результаты...
|
|
|
Записан
|
Удачного всем кодинга! -=x[PooH]x=-
|
|
|
Aveic
Постоялец
Offline
Пол:
Yellow
|
|
« Ответ #19 : 27-02-2008 13:04 » |
|
в общем, решил задачу в лоб (совпадает с решением от LogRus): сгенерировал сначала возможные строки, (их всего 9!=362880), потом выставлял строки с проверкой столбцов. Вот код на С++: #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
Глобальный модератор
Offline
Пол:
... и можно без хлеба!
|
|
« Ответ #20 : 27-02-2008 13:09 » |
|
у я предлагал примерно так: 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 выводить матрицу, то получатся все возможные варианты... только я даже боюсь представить сколько это времени займет =)
|
|
« Последнее редактирование: 27-02-2008 13:15 от PooH »
|
Записан
|
Удачного всем кодинга! -=x[PooH]x=-
|
|
|
vx
Гость
|
|
« Ответ #21 : 27-02-2008 13:16 » |
|
Aveic, твой алгоритм хорош но вот на моем компе он выполняеться минуты 2.=(
|
|
|
Записан
|
|
|
|
vx
Гость
|
|
« Ответ #22 : 27-02-2008 13:20 » |
|
И еще, матрицу надо заполнить СЛУЧАЙНЫМИ значениями.
|
|
|
Записан
|
|
|
|
vx
Гость
|
|
« Ответ #23 : 27-02-2008 13:38 » |
|
Вот написал код. Только надо написать функцию '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; }
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #24 : 27-02-2008 13:40 » |
|
В принципе, можно найти все (или сколько время позволяет) варианты допустимых комбинаций 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, и т.д.).
|
|
« Последнее редактирование: 27-02-2008 13:48 от Вад »
|
Записан
|
|
|
|
vx
Гость
|
|
« Ответ #25 : 27-02-2008 13:48 » |
|
Вад: Извините, но чёта я не понял, можно по проще.
|
|
|
Записан
|
|
|
|
Aveic
Постоялец
Offline
Пол:
Yellow
|
|
« Ответ #26 : 27-02-2008 13:50 » |
|
Aveic, твой алгоритм хорош но вот на моем компе он выполняеться минуты 2.=(
основное время отнимает функция fill_rows(). По идеи ее нужно вызвать только 1 раз (чтобы вывести в файл, и остальные разы, оттуда считывать). Можешь сам реализовать... И еще, матрицу надо заполнить СЛУЧАЙНЫМИ значениями.
еще раз говорю, все дело в функции get_next_r() поставить там код static unsigned int was=rand()%N;
и получишь каждый раз разные значения, если rand() будет действительно выдавать разные значения...
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #27 : 27-02-2008 13:55 » |
|
В общем, использование только "1 2 3 4 5 6 7 8 9" в качестве первой строки резко уменьшает число вариантов перебора. А потом все остальные варианты получаются перестановкой 1 -> x1, 2 -> x2 и т.д.
|
|
|
Записан
|
|
|
|
vx
Гость
|
|
« Ответ #28 : 27-02-2008 14:02 » |
|
Люди а как насчет моего кода(приведен выше)
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #29 : 27-02-2008 14:08 » |
|
vx, 1. Не делай рандом внутри цикла. Это только замедляет. Делай просто цикл 1..9 с проверкой, нет ли этого значения в текущих строке и столбце, перебирая все значения. 2. Делай первую строку 1 2 3 4 5 6 7 8 9 и заполняй все остальные примерно так, как у тебя сделано, + мой пункт 1. 3. Генерируй перестановку X (9 чисел) так же, как генерируешь строку в приведённой тобой реализации (с проверкой повторения только в строке). 4. Заменяй в таблице символ i на значение из вектора перестановки x[ i ].
|
|
« Последнее редактирование: 27-02-2008 14:10 от Вад »
|
Записан
|
|
|
|
|