VPF::Алгоритм решениыа судуку!! - Форум программистов

Lampa24

Дата 22.3.2008, 12:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 12
Регистрация: 22.3.2008

Репутация: нет
Всего: нет

Даите сылку на алгоритм.

nerezus

Дата 22.3.2008, 13:59 (ссылка)

(нет голосов)

Загрузка ...

Вселенский отказник

Профиль
Группа: Участник
Сообщений: 3330
Регистрация: 15.6.2005

Репутация: нет
Всего: 43

А почему бы и не перебором?

--------------------

Сообщество художников Artsociety.ru

Optimus

Дата 22.3.2008, 14:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 186
Регистрация: 1.9.2007

Репутация: нет
Всего: 14

Цитата(Lampa24 @ 22.3.2008, 12:15

)

Даите сылку на алгоритм.

Вбейте в гугле: Алгоритм решения судоку
и получите ссылки

--------------------

"постановка задачи наполовину решает саму задачу"

maxdiver

Дата 22.3.2008, 14:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Насколько мне известно, судоку 9x9 решается слегка улучшенным перебором (фактически самый простой перебор, просто реализован не самым тупым образом) за время O(9!), т.е. очень быстро.

Akina

Дата 22.3.2008, 21:27 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(maxdiver @ 22.3.2008, 15:06

)

за время O(9!)

O(9!) = O(1)
Это так, между нами...

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

maxdiver

Дата 22.3.2008, 23:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Akina
Вот так и знал, придерутся smile

Я имел в виду, что выполняет k*9! операций, где k - достаточно маленькое число, видимо, порядка единиц-десятков.

added:
По-русски говоря, порядка 9! операций smile

Это сообщение отредактировал(а) maxdiver - 22.3.2008, 23:38

SoWa

Дата 24.3.2008, 07:23 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

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

--------------------

Всем добра smile

maxdiver

Дата 16.4.2008, 15:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Сегодня на контесте писал как раз эту задачу. Работает мгновенно (меньше 10 мс), но при условии, что решение есть. Если решения нет, то может работать порядка полусекунды. Вот код:

Код

int a[9][9]; // входные данные; a[i][j] = 0 если клетка пустая; на выходе здесь будет ответ

int freex[9], freey[9], freeb[9];
int sumx[9], sumy[9], sumb[9];
bool usedx[9][10], usedy[9][10], usedb[9][10];

int bl (int x, int y) {
    return x / 3 * 3 + y / 3;
}

bool brute (int x = 0) {
    while (x<9 && freex[x]==0)  ++x;
    if (x==9)
        return true;
    for (int y=0; y<9; ++y)
        if (a[x][y] == 0) {
            int b = bl(x,y);
            if (freex[x] == 1)
                a[x][y] = 45 - sumx[x];
            else if (freey[y] == 1)
                a[x][y] = 45 - sumy[y];
            else if (freeb[b] == 1)
                a[x][y] = 45 - sumb[b];
            else {
                --freex[x],  --freey[y],  --freeb[b];
                for (a[x][y]=1; a[x][y]<=9; ++a[x][y])
                    if (!usedx[x][a[x][y]] && !usedy[y][a[x][y]] && !usedb[b][a[x][y]]) {
                        usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = true;
                        sumx[x]+=a[x][y],  sumy[y]+=a[x][y],  sumb[b]+=a[x][y];
                        if (brute (x))
                            return true;
                        usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = false;
                        sumx[x]-=a[x][y],  sumy[y]-=a[x][y],  sumb[b]-=a[x][y];
                    }
                a[x][y] = 0;
                ++freex[x],  ++freey[y],  ++freeb[b];
                return false;
            }
            if (usedx[x][a[x][y]] || usedy[y][a[x][y]] || usedb[b][a[x][y]]) {
                a[x][y] = 0;
                return false;
            }
            --freex[x],  --freey[y],  --freeb[b];
            usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = true;
            sumx[x]+=a[x][y],  sumy[y]+=a[x][y],  sumb[b]+=a[x][y];
            if (brute (x))
                return true;
            usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = false;
            sumx[x]-=a[x][y],  sumy[y]-=a[x][y],  sumb[b]-=a[x][y];
            a[x][y] = 0;
            ++freex[x],  ++freey[y],  ++freeb[b];
            return false;
        }
    return (bool) 314159265; // never get there :)
}

int main() {

    freopen ("input.txt", "rt", stdin);
    freopen ("output.txt", "wt", stdout);

    char s[11];
    for (int i=0; i<9; ++i) {
        gets (s);
        for (int j=0; j<9; ++j)
            a[i][j] = s[j]-'0';
    }

    for (int i=0; i<9; ++i)
        for (int j=0; j<9; ++j)
            if (a[i][j] == 0)
                ++freex[i],  ++freey[j],  ++freeb[bl(i,j)];
            else {
                sumx[i]+=a[i][j],  sumy[j]+=a[i][j],  sumb[bl(i,j)]+=a[i][j];
                usedx[i][a[i][j]] = usedy[j][a[i][j]] = usedb[bl(i,j)][a[i][j]] = true;
            }

    if (!brute())
        puts ("NO SOLUTION");
    else
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j)
                cout << a[i][j];
            cout << endl;
        }

}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »