Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Boriss
Статус: Академик
Рейтинг: 1682
∙ повысить рейтинг »
Micren
Статус: Профессионал
Рейтинг: 1437
∙ повысить рейтинг »
_Ayl_
Статус: Студент
Рейтинг: 1406
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И ПО / Программирование / C/C++

Номер выпуска:1469
Дата выхода:11.01.2010, 02:00
Администратор рассылки:Dr_Andrew, Старший модератор
Подписчиков / экспертов:679 / 187
Вопросов / ответов:2 / 2
IRC-канал по теме:#C

Вопрос № 175838: Здравствуйте, эксперты. Подскажите, как написать генератор номеров для судоку? Я сам пытаюсь сделать, но на данной части застрял - программа генерирует номера, чтобы они не повторялись ни в строках, ни в столбцах. Номера-то генерируются...


Вопрос № 175854: Здравствуйте, эксперты. Имеется код программы, рабочей, которая генерирует судоку 9*9. Только один недочет - программа не проверяет столбцы 3*3 на повторяющие элементы. В общем, надо к коду приграммы как-то присоденить вот этот код:

Вопрос № 175838:

Здравствуйте, эксперты.

Подскажите, как написать генератор номеров для судоку?

Я сам пытаюсь сделать, но на данной части застрял - программа генерирует номера, чтобы они не повторялись ни в строках, ни в столбцах. Номера-то генерируются, однако, программа зависает, и ни одного номера не выводит...

Как это можно исправить?

Вот код программы:

Код:

time_t kl;
srand(kl);
const int size=6;
int number;
int sudoku[size][size];
int i, j;
int k, l;
int chance;

bool repeated;

for(i=0; i<size; i++)
{
for(j=0; j<size; j++)
{

chance=rand()%5;
if(chance==0)
{
cout << 0 << " ";
continue;
}

for(;;)
{
repeated=false;
number=rand()%6+1;

for(l=0; l<i; l++)
if(sudoku[l][j]==number)
{
repeated=true;
break;
}
for(k=0; k<j; k++)
if(sudoku[i][k]==number)
{
repeated=true;
break;
}

if(repeated==true)
continue;

sudoku[i][j]=number;
break;
}
cout << sudoku[i][j] << " ";
}
cout << endl;
}

Отправлен: 05.01.2010, 02:31
Вопрос задал: Иванов Андрей Владимирович, 5-й класс
Всего ответов: 1
Страница вопроса »


Отвечает amnick, 8-й класс :
Здравствуйте, Иванов Андрей Владимирович.

Мой вариант программы приведен в приложении.
Здесь надо использовать алгоритм с возвратом — если не получается сгенерировать число для очередной ячейки, то вернуться к предыдущей и т.д. Если не получается сгенерировать очередную строку, то вернуться к предыдущей. Правда, ситуация возврата к предыдущей строке не возникла ни разу за более, чем 150 прогонов моей программы (разумеется, для проверки я организовал дополнительный цикл, которого нет в приведенном коде, а не запускал программу вручную 150 раз). Вероятно, что такая ситуация и не может возникнуть, но на всякий случай я вставил соответствующие проверки.

Если что-то непонятно, то спрашивайте в мини-форуме.

Пример вывода программы:
Код:
0: 4 3 6 2 5 1
1: 3 1 4 6 2 5
2: 6 5 2 3 4
2: 6 5 2 3 1 4
3: 5 4 1
3: 5 4 3 1 6 2
4: 1 6 5 4 3
4: 1 6 5 4
4: 1 6 5
4: 1 6
4: 1 2 5 4 3 6
5: 2 6 1 5 4 3


0: 1 5 3 6 4 2
1: 6 3 5 1 2 4
2: 5 2 4 3 1 6
3: 2 4 6 5 3 1
4: 3 6 2 4 5
4: 3 6 2 4
4: 3 6 2
4: 3 6 1 4 5
4: 3 6 1 4
4: 3 6 1 2 5
4: 3 6 1 2
4: 3 6 1
4: 3 6
4: 3 1 2 4 5
4: 3 1 2 4 6 5
5: 4 6 1 2 5 3


0: 3 4 6 5 1 2
1: 1 6 5 4 2 3
2: 2 1 3 6 5 4
3: 4 5 1 3 6
3: 4 5 1 3
3: 4 5 1 2 6
3: 4 5 1 2 3 6
4: 5 3 2 1 4
4: 5 3 2 1 6
4: 5 3 2 1
4: 5 3 2
4: 5 3 4 1 6
4: 5 3 4 1
4: 5 3 4
4: 5 3
4: 5 2 4 1 6
4: 5 2 4 1
4: 5 2 4 3 6 1
5: 6 3 2 1 4 5


Успехов!

Приложение:

Ответ отправил: amnick, 8-й класс
Ответ отправлен: 05.01.2010, 16:02

Оценка ответа: 5

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258377 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 175854:

    Здравствуйте, эксперты.
    Имеется код программы, рабочей, которая генерирует судоку 9*9. Только один недочет - программа не проверяет столбцы 3*3 на повторяющие элементы. В общем, надо к коду приграммы как-то присоденить вот этот код:

    Код:

    int i_from, j_from;

    for(i=0; i<size; i++)
    {
    for(j=0; j<size; j++)
    {

    if(i<3) i_from=0;
    else if(i<6) i_from=3;
    else i_from=6;

    if(j<3) j_from=0;
    else if(j<6) j_from=3;
    else j_from=6;

    for(;;)
    {
    repeated=false;
    number=rand()%9+1;

    for(l=i_from; l<i; l++)
    for(k=j_from; k<j; k++)
    if(sudoku[l][k]==number)
    {
    repeated=true;
    break;
    }
    ...
    }


    Подскажите, как это сделать?

    Далее код самой программы: (спасибо эксперту amnick)
    Код:

    #include <time.h>
    #include <iostream>
    #include <stdlib.h>
    using namespace std;

    const int size = 9;
    const int initial_mask = ~((-1) << size);

    int sudoku[size][size]; // это матрица судоку
    // этот массив будет использоваться для пометки проверенных чисел
    // лишняя колонка позволяет избежать дополнительной проверки индекса
    int check[size][size+1];


    // генерируем ячейку
    bool cell( int i, int j )
    {
    int chk = check[i][j]; // маска чисел, уже проверенных в этой ячейке
    if( !chk )
    return false; // на предыдущих проходах уже были проверены все числа

    for(;;)
    {
    // генерируем число, новое для этой ячейки
    int number, bit;
    do {
    number = rand() % size;
    bit = 1 << number;
    } while( !(chk & bit) );
    chk &= ~bit;
    ++number;

    // проверяем, было ли это число ран ее ...
    bool repeated = false;
    // ... в столбце
    for(int l=0; l<i; l++)
    if(sudoku[l][j]==number)
    {
    repeated = true;
    break;
    }
    if( repeated ) {
    // number уже есть в этом стобце
    if( chk == 0 ) return false; // проверены все числа
    continue; // пытаемся снова
    }

    // ... в строке
    for(int k=0; k<j; k++)
    if(sudoku[i][k]==number)
    {
    repeated = true;
    break;
    }

    if( repeated ) {
    // number уже есть в этой строке
    if( chk == 0 ) return false; // проверены все числа
    continue; // пытаемся снова
    }

    sudoku[i][j] = number; // нашли подходящее (пока) число
    check[i][j] = chk; // сохраняем маску проверенных чисел

    cout << number << " ";
    return true;
    }

    }

    // генерируем строку
    bool row( int i )
    {
    check[i][0] = initial_mask; // сброс маски для первой ячейки
    int j = 0;
    while( j < size ) {
    if( cell( i, j )) {
    // ячейка заполнена, переходим к следующей
    ++j;
    check[i][j] = initial_m ask; // сброс маски для очередной ячейки
    // индекс j здесь не проверяли - помните объявление int check[size][size+1] ?
    }
    else {
    // увы, не получилось
    // возвращаемся к предыдущей ячейке и ищем для нее какое-то другое число
    // будет использована ранее сохраненная маска check[][]
    if( --j < 0 )
    return false; // придется вернуться к предыдущей строке

    // вывод отладочной информации - отслеживание возвратов
    cout << endl << i << ": ";
    for( int k = 0; k < j; ++k )
    cout << sudoku[i][k] << " ";
    }
    }
    cout << endl;
    return true;
    }

    int main()
    {
    time_t kl;
    time( &kl );
    srand(kl);

    int i = 0;
    while( i < size ) {
    cout << i << ": ";
    if( row( i ))
    ++i;
    else
    if( --i < 0 ) { cout << endl << "error! << endl"; break; }
    }

    int j;
    cout << endl;
    for(i=0; i<size; i++)
    {
    for(j=0; j<9; j++)
    cout << sudoku[i][j] << " ";
    cout << endl;
    }
    }

    Отправлен: 06.01.2010, 01:01
    Вопрос задал: Иванов Андрей Владимирович, 5-й класс
    Всего ответов: 1
    Страница вопроса »


    Отвечает amnick, 8-й класс :
    Здравствуйте, Иванов Андрей Владимирович.

    Изменения в программе нужны совсем небольшие. Проверка добавляется в функцию cell(). Размеры под-области задаются константами (в начале программы). При отладке я проверил, например, матрицу 6x6 с прямоугольными под-областями 3x2. Дополнительно, в конце функции main() добавлен вывод матрицы с разделителями. Для простоты, в приложении приведен код программы целиком.

    Результат пары прогонов программы:
    Код:
    0: 9 5 7 2 1 4 6 8 3
    1: 1 2 4 7 5 8 9
    1: 1 2 4 7 5 8
    1: 1 2 4 7 5 3 9
    1: 1 2 4 7 5 3
    1: 1 2 4 7 5 6 9
    1: 1 2 4 7 5 6
    1: 1 2 4 7 5 9
    1: 1 2 4 7 5
    1: 1 2 4 7 9 3 5
    1: 1 2 4 7 9 3
    1: 1 2 4 7 9 6 5
    1: 1 2 4 7 9 6
    1: 1 2 4 7 9 8 5
    1: 1 2 4 7 9 8
    1: 1 2 4 7 9 5
    1: 1 2 4 7 9
    1: 1 2 4 7 3 6 9 5
    1: 1 2 4 7 3 6 9
    1: 1 2 4 7 3 6 5 9
    1: 1 2 4 7 3 6 5
    1: 1 2 4 7 3 6
    1: 1 2 4 7 3 8 9 5
    1: 1 2 4 7 3 8 9
    1: 1 2 4 7 3 8 5 9
    1: 1 2 4 7 3 8 5
    1: 1 2 4 7 3 8
    1: 1 2 4 7 3 5 9
    1: 1 2 4 7 3 5
    1: 1 2 4 7 3 9 5
    1: 1 2 4 7 3 9
    1: 1 2 4 7 3
    1: 1 2 4 7 8 3 9 5
    1: 1 2 4 7 8 3 9
    1: 1 2 4 7 8 3 5 9
    1: 1 2 4 7 8 3 5
    1: 1 2 4 7 8 3
    1: 1 2 4 7 8 9 5
    1: 1 2 4 7 8 9
    1: 1 2 4 7 8 6 5 9
    1: 1 2 4 7 8 6 5
    1: 1 2 4 7 8 6 9 5
    1: 1 2 4 7 8 6 9
    1: 1 2 4 7 8 6
    1: 1 2 4 7 8 5 9
    1: 1 2 4 7 8 5
    1: 1 2 4 7 8
    1: 1 2 4 7 6 8 9 5
    1: 1 2 4 7 6 8 9
    1: 1 2 4 7 6 8 5 9
    1: 1 2 4 7 6 8 5
    1: 1 2 4 7 6 8
    1: 1 2 4 7 6 3 9 5
    1: 1 2 4 7 6 3 9
    1: 1 2 4 7 6 3 5 9
    1: 1 2 4 7 6 3 5
    1: 1 2 4 7 6 3
    1: 1 2 4 7 6 9 5
    1: 1 2 4 7 6 9
    1: 1 2 4 7 6 5 9
    1: 1 2 4 7 6 5
    1: 1 2 4 7 6
    1: 1 2 4 7
    1: 1 2 4 3 5 6 7 9
    1: 1 2 4 3 5 6 7
    1: 1 2 4 3 5 6 9 7
    1: 1 2 4 3 5 6 9
    1: 1 2 4 3 5 6
    1: 1 2 4 3 5 7 9
    1: 1 2 4 3 5 7
    1: 1 2 4 3 5 9 7
    1: 1 2 4 3 5 9
    1: 1 2 4 3 5 8 9 7
    1: 1 2 4 3 5 8 9
    1: 1 2 4 3 5 8 7 9
    1: 1 2 4 3 5 8 7
    1: 1 2 4 3 5 8
    1: 1 2 4 3 5
    1: 1 2 4 3 9 7 5
    1: 1 2 4 3 9 7
    1: 1 2 4 3 9 5 7
    1: 1 2 4 3 9 5
    1: 1 2 4 3 9 8 5 7
    1: 1 2 4 3 9 8 5
    1: 1 2 4 3 9 8 7 5
    1: 1 2 4 3 9 8 7
    1: 1 2 4 3 9 8
    1: 1 2 4 3 9 6 7 5
    1: 1 2 4 3 9 6 7
    1: 1 2 4 3 9 6 5 7
    1: 1 2 4 3 9 6 5
    1: 1 2 4 3 9 6
    1: 1 2 4 3 9
    1: 1 2 4 3 7 8 9 5
    1: 1 2 4 3 7 8 9
    1: 1 2 4 3 7 8 5 9
    1: 1 2 4 3 7 8 5
    1: 1 2 4 3 7 8
    1: 1 2 4 3 7 5 9
    1: 1 2 4 3 7 5
    1: 1 2 4 3 7 9 5
    1: 1 2 4 3 7 9
    1: 1 2 4 3 7 6 5 9
    1: 1 2 4 3 7 6 5
    1: 1 2 4 3 7 6 9 5
    1: 1 2 4 3 7 6 9
    1: 1 2 4 3 7 6
    1: 1 2 4 3 7
    1: 1 2 4 3 8 7 9 5
    1: 1 2 4 3 8 7 9
    1: 1 2 4 3 8 7 5 9
    1: 1 2 4 3 8 7 5
    1: 1 2 4 3 8 7
    1: 1 2 4 3 8 5 9 7
    1: 1 2 4 3 8 5 9
    1: 1 2 4 3 8 5 7 9
    1 : 1 2 4 3 8 5 7
    1: 1 2 4 3 8 5
    1: 1 2 4 3 8 9 5 7
    1: 1 2 4 3 8 9 5
    1: 1 2 4 3 8 9 7 5
    1: 1 2 4 3 8 9 7
    1: 1 2 4 3 8 9
    1: 1 2 4 3 8 6 5 7 9
    2: 3 6 8 9 7 5 4 1 2
    3: 4 8 9 5 6 2 3
    3: 4 8 9 5 6 2 1 3 7
    4: 6 1 3 4 9 8 2 5
    4: 6 1 3 4 9 8 2
    4: 6 1 3 4 9 8
    4: 6 1 3 4 9 7 8 5
    4: 6 1 3 4 9 7 8 2 5
    5: 2 7 5 1 3 8 9 4 6
    6: 7 3 2 8 5 1
    6: 7 3 2 8 5 9
    6: 7 3 2 8 5
    6: 7 3 2 8 4 1
    6: 7 3 2 8 4 9
    6: 7 3 2 8 4
    6: 7 3 2 8
    6: 7 3 2 6 4 1
    6: 7 3 2 6 4 9
    6: 7 3 2 6 4
    6: 7 3 2 6 5 9
    6: 7 3 2 6 5 1
    6: 7 3 2 6 5
    6: 7 3 2 6
    6: 7 3 2
    6: 7 3 6 8 4 9 2 5 1
    7: 8 4 1 7 2 3
    7: 8 4 1 7 2
    7: 8 4 1 7 5 3
    7: 8 4 1 7 5
    7: 8 4 1 7
    7: 8 4 1 6 2 3 7 9
    7: 8 4 1 6 2 3 7
    7: 8 4 1 6 2 3
    7: 8 4 1 6 2
    7: 8 4 1 6 5 3 7 9
    7: 8 4 1 6 5 3 7
    7: 8 4 1 6 5 3
    7: 8 4 1 6 5
    7: 8 4 1 6
    7: 8 4 1
    7: 8 4 2 6 5 1 7 9
    7: 8 4 2 6 5 1 7
    7: 8 4 2 6 5 1 3 9
    7: 8 4 2 6 5 1 3
    7: 8 4 2 6 5 1
    7: 8 4 2 6 5 3 7 9
    7: 8 4 2 6 5 3 7
    7: 8 4 2 6 5 3
    7: 8 4 2 6 5
    7: 8 4 2 6
    7: 8 4 2 7 5 3
    7: 8 4 2 7 5 1 3 6
    7: 8 4 2 7 5 1 3 9
    7: 8 4 2 7 5 1 3
    7: 8 4 2 7 5 1
    7: 8 4 2 7 5
    7: 8 4 2 7
    7: 8 4 2
    7: 8 4
    7: 8 9 2 7 5 1 3 6 4
    8: 5 4 1 6 2 3 7 9 8

    Matrix:
    9 5 7 | 2 1 4 | 6 8 3
    1 2 4 | 3 8 6 | 5 7 9
    3 6 8 | 9 7 5 | 4 1 2
    ------+-------+-------
    4 8 9 | 5 6 2 | 1 3 7
    6 1 3 | 4 9 7 | 8 2 5
    2 7 5 | 1 3 8 | 9 4 6
    ------+-------+-------
    7 3 6 | 8 4 9 | 2 5 1
    8 9 2 | 7 5 1 | 3 6 4
    5 4 1 | 6 2 3 | 7 9 8

    **********************

    0: 4 1 5 9 6 7 8 3 2
    1: 6 3 8 2 5 4 9 1 7
    2: 9 7 2 3 1 8 5 4 6
    3: 2 4 7 1 9 6 3 5 8
    4: 3 9 6 5 7 2 1
    4: 3 9 6 5 7 2 4
    4: 3 9 6 5 7 2
    4: 3 9 6 5 7
    4: 3 9 6 5 8 2 7
    4: 3 9 6 5 8 2 1 7 4
    5: 1 8
    5: 1 5
    5: 1
    5: 5 8 1 4 7 3 2 9
    5: 5 8 1 4 7 3 2 6 9
    6: 1 2 9 6 4 5 7 8 3
    7: 8 6 3 7 2 9 4
    7: 8 6 3 7 2 9
    7: 8 6 3 7 2 1 4 9 5
    8: 7 5 4 8 3 9 6 2 1

    Matrix:
    4 1 5 | 9 6 7 | 8 3 2
    6 3 8 | 2 5 4 | 9 1 7
    9 7 2 | 3 1 8 | 5 4 6
    ------+-------+--- ----
    2 4 7 | 1 9 6 | 3 5 8
    3 9 6 | 5 8 2 | 1 7 4
    5 8 1 | 4 7 3 | 2 6 9
    ------+-------+-------
    1 2 9 | 6 4 5 | 7 8 3
    8 6 3 | 7 2 1 | 4 9 5
    7 5 4 | 8 3 9 | 6 2 1


    Если есть вопросы, то спрашивайте в мини-форуме. Могу ответить сегодня до 23МСК или в понедельник.

    Успехов!

    Приложение:

    Ответ отправил: amnick, 8-й класс
    Ответ отправлен: 06.01.2010, 19:48

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258409 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)

    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.


    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.13 от 28.12.2009

    В избранное