Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Заполнить матрицу...SUDOCU  (Прочитано 34559 раз)
0 Пользователей и 1 Гость смотрят эту тему.
vx
Гость
« : 27-02-2008 06:45 » 

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

P.S. Если вы знаете что такое SUDOCU вы поймете суть задачи.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 27-02-2008 07:09 » 

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

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

Sla
Модератор

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 27-02-2008 07:20 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
rumpelstilzchen
Тролль
*
ru
Offline Offline

« Ответ #3 : 27-02-2008 09:11 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 27-02-2008 09:26 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline 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)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #6 : 27-02-2008 10:05 » 

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

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

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 27-02-2008 10:20 » 

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

Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 27-02-2008 11:07 » 

Алексей1153++, "9!" - это "9 факториал" =)
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 27-02-2008 11:30 » 

нее, меньше. Не помню комбинаторику - все сочетания из N предметов надо посчитать. Или чё - серьёзно так много ? ))
« Последнее редактирование: 27-02-2008 11:32 от Алексей1153++ » Записан

Aveic
Постоялец

ru
Offline Offline
Пол: Мужской
Yellow


« Ответ #10 : 27-02-2008 12:06 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #11 : 27-02-2008 12:10 » 

В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.
(это приблизительно как задача о 8 ферзях)
Скорее всего, задача о 8 ладьях Улыбаюсь
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Aveic
Постоялец

ru
Offline Offline
Пол: Мужской
Yellow


« Ответ #12 : 27-02-2008 12:20 » 

В Судоку есть еше одно правило, в малых квадратах тоже должны быть не повторяюшиеся цифры.
Это одна из разновидностей, есть еще разновидность, где не должны повторятся цифры на главной и побочной диагонали.
Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #13 : 27-02-2008 12:27 » 

Aveic, Еще с основной задачей не разобрались, а уже пошли разновидности )))
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #14 : 27-02-2008 12:29 » 

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

Aveic
Постоялец

ru
Offline Offline
Пол: Мужской
Yellow


« Ответ #15 : 27-02-2008 12:36 » 

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

ru
Offline 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
Модератор

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 27-02-2008 12:57 » 

PooH, это одно из решения
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #18 : 27-02-2008 13:00 » 

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

Удачного всем кодинга! -=x[PooH]x=-
Aveic
Постоялец

ru
Offline Offline
Пол: Мужской
Yellow


« Ответ #19 : 27-02-2008 13:04 » 

в общем, решил задачу в лоб (совпадает с решением от 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
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #20 : 27-02-2008 13:09 » 

у я предлагал примерно так:
Код: (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 выводить матрицу, то получатся все возможные варианты... только я даже боюсь представить сколько это времени займет =)
« Последнее редактирование: 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;
}
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #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
Постоялец

ru
Offline Offline
Пол: Мужской
Yellow


« Ответ #26 : 27-02-2008 13:50 » 

Aveic, твой алгоритм хорош но вот на моем компе он выполняеться минуты 2.=(
основное время отнимает функция fill_rows(). По идеи ее нужно вызвать только 1 раз (чтобы вывести в файл, и остальные разы, оттуда считывать). Можешь сам реализовать...
И еще, матрицу надо заполнить СЛУЧАЙНЫМИ значениями.
еще раз говорю, все дело в функции get_next_r() поставить там код
Код:
static unsigned int was=rand()%N;
и получишь каждый раз разные значения, если rand() будет действительно выдавать разные значения...
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #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 » 

Люди а как насчет моего кода(приведен выше)Не понял
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #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 от Вад » Записан
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines