Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
#1

Судоку. Задача довольно-таки интересная - C++

30.04.2013, 13:48. Просмотров 1088. Ответов 18
Метки нет (Все метки)

Написать программу через рекурсию, делающую судоку....

Добавлено через 2 часа 50 минут
а вроде задание так звучит: дан текстовый файл, в нем размерность массива и сам массив....проверить, является ли массив решением судоку. Проверку оформить через рекурсию.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 14:29     Судоку. Задача довольно-таки интересная #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Автор решения : Матов Дмитрий.
// 6 ms на худшем тесте
#include <cstdio>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define for1(i, n) for(int i = 1; i <= (int)(n); i++)
 
int a[9][9];
bool u_r[9][9], u_c[9][9], u_s[9][9];
 
void rec(char x, char y)
{
    if (y == 9)
    {
        y = 0;
        ++x;
    }
    if (x == 9)
    {
        forn(i, 9)
        {
            forn(j, 9) printf("%d", a[i][j] + 1);
            printf("\n");
        }
        exit(0);
    }
    if (a[x][y] >= 0)
    {
        rec(x, y + 1);
        return;
    }
    char s = (x / 3) * 3 + (y / 3);
    forn(i, 9)
    {
        if (u_r[x][i] || u_c[y][i] || u_s[s][i]) continue;
        u_r[x][i] = u_c[y][i] = u_s[s][i] = true;
        a[x][y] = i;
        rec(x, y + 1);
        u_r[x][i] = u_c[y][i] = u_s[s][i] = false;
        a[x][y] = -1;
    }
}
 
int main()
{
    char c;
    forn(i, 9)
    {
        forn(j, 9)
        {
            scanf("%c", &c);
            a[i][j] = c - '1';
            if (a[i][j] >= 0)
            {
                u_r[i][a[i][j]] = true;
                u_c[j][a[i][j]] = true;
                u_s[(i / 3) * 3 + (j / 3)][a[i][j]] = true;
            }
        }
        scanf("\n");
    }
    rec(0, 0);
    return 0;
}
Ввод
567823941
931764582
824951360
048315796
679248135
153607824
782136450
395472618
406589273

Вывод
567823941
931764582
824951367
248315796
679248135
153697824
782136459
395472618
416589273

Добавлено через 2 минуты
Lonter, А проверка вообще халява, проверьте условие судоку
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
30.04.2013, 14:30  [ТС]     Судоку. Задача довольно-таки интересная #3
а что значит forn?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 14:31     Судоку. Задача довольно-таки интересная #4
Lonter, макрос #define forn(i, n) for(int i = 0; i < (int)(n); i++)
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 09:37  [ТС]     Судоку. Задача довольно-таки интересная #5
Вы уверены что а[9][9]? а не [8][8]

Добавлено через 11 минут
И вроде как в рекурсии не стоит циклы делать
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 11:20     Судоку. Задача довольно-таки интересная #6
Lonter, Конечно уверен, вы наверное новичёк и с Passcal только что перешли В С++ массивы нумеруются от [0..n-1] => тут в массиве 9 элементов от 0 до 8 включительно, в судоку тоже 9 элементов. В рекурсии стоит делать циклы, так как мы подбираем ответ к судоку. На позиции всех нулей во внутреннем цикле рекурсии подбирается цифра [от 1 до 9]

Добавлено через 1 час 28 минут
Lonter, Я надеюсь, что вы понимаете, что я вам дал пример решения судоку перебором, а не то что вы хотели, т.к. это сложнее, полезнее и интересней, а в своём задании вы и сами разберётесь, оно очень простое
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:30  [ТС]     Судоку. Задача довольно-таки интересная #7
я новичок это да) но я перешел даже не с паскаля а с VBA)

Добавлено через 2 минуты
тут перебор для всех нулей проводится?)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 11:33     Судоку. Задача довольно-таки интересная #8
Lonter, ну, смотрите, вам нужно считать cin >> n размерность квадратной матрицы, затем считываете 2d массив
C++
1
2
3
for (int i = 0; i < n; i++)
 for (int j = 0; j < n; j++)
  cin >> a[i][j];
потом проверяете чтобы в каждом столбце и строке были все числа от 1 до n, затем разделяете его на равные квадраты стороной = sqrt(n) и в них аналогично проверяете. Такие операции можно проделать сразу при считывании.

Добавлено через 1 минуту
Lonter, повторяю, я вам привёл пример задачи, которая решает судоку 9x9, изначально в судоку могут отсутсвовать числа (пустые клетки) на этих местах в исходном массиве стоят нули, обратите внимание.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:34  [ТС]     Судоку. Задача довольно-таки интересная #9
да это я понял=)) то есть там хоть сколько нулей может быть=)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 11:55     Судоку. Задача довольно-таки интересная #10
Lonter,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
#include "Windows.h"
#include <conio.h>
 
using namespace std;
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    cin >> n;
    vector <set<int>> col(n), row(n);
    int m = sqrt((double)n);
    vector < vector <set <int> > > block(m, vector <set <int> > (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            row[i].insert(temp);
            col[j].insert(temp);
            block[i/m][j/m].insert(temp);
        }
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (block[i][j].size() != n) {
            cout << "NO";
            return 0;
        }
    for (int i = 0; i < n; i++)
        if (col[i].size() != n || row[i].size() != n) {
            cout << "NO";
            return 0;
        }
    cout << "YES";
    return 0;
}
Добавлено через 17 секунд
Lonter, пример ввода :
9
5 6 7 8 2 3 9 4 1
9 3 1 7 6 4 5 8 2
8 2 4 9 5 1 3 6 7
2 4 8 3 1 5 7 9 6
6 7 9 2 4 8 1 3 5
1 5 3 6 9 7 8 2 4
7 8 2 1 3 6 4 5 9
3 9 5 4 7 2 6 1 8
4 1 6 5 8 9 2 7 3

Добавлено через 56 секунд
Lonter, считывается из файла input.txt выводится в файл output.txt

Добавлено через 3 минуты
Lonter,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    cin >> n;
    vector <set<int>> col(n), row(n);
    int m = sqrt((double)n);
    vector < vector <set <int> > > block(m, vector <set <int> > (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            if (row[i].count(temp) || col[j].count(temp) || block[i/m][j/m].count(temp)) {
                cout << "NO";
                return 0;
            }
            row[i].insert(temp);
            col[j].insert(temp);
            block[i/m][j/m].insert(temp);
        }
    }
    cout << "YES";
    return 0;
}
Добавлено через 3 минуты
Lonter,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    cin >> n;
    vector <vector <bool>> col(n, vector <bool>(n)), row(n, vector <bool>(n, false));
    int m = sqrt((double)n);
    vector < vector < vector <bool> > > block(m, vector < vector <bool> > (m, vector <bool>(n, false)));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp; temp--;
            if (row[i][temp] || col[j][temp] || block[i/m][j/m][temp]) {
                cout << "NO";
                return 0;
            }
            row[i][temp] = col[j][temp] = block[i/m][j/m][temp] = true;
        }
    }
    cout << "YES";
    return 0;
}
Добавлено через 17 секунд
Lonter, вот вам 3 варианта решения.

Добавлено через 5 минут
Lonter,
Пример ввода :
4
1 2 3 4
4 3 2 1
3 4 1 2
2 1 4 3

Добавлено через 45 секунд
Lonter, помните, n - должно быть квадратом натурального числа
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:59  [ТС]     Судоку. Задача довольно-таки интересная #11
Спасибо))) под рекурсию сам попробую) только вот я дуб в этом) ну пофиг)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 12:04     Судоку. Задача довольно-таки интересная #12
Lonter, цикл можно в рекурсию переделать очень легко

Добавлено через 3 минуты
Lonter,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector <vector <bool>> col, row;
vector < vector < vector <bool> > > block;
 
void scan(int i, int j){
    if (j >= n) {
        j = 0;
        i++;
    }
    if (i >= n)
        return;
    int temp;
    cin >> temp; temp--;
    if (row[i][temp] || col[j][temp] || block[i/m][j/m][temp]) {
        cout << "NO";
        exit(0);
    }
    row[i][temp] = col[j][temp] = block[i/m][j/m][temp] = true;
    scan(i, j+1);
}
 
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    cin >> n;
    col = row = vector <vector <bool>> (n, vector <bool>(n, false));
    m = sqrt((double)n);
    block = vector < vector < vector <bool> > > (m, vector < vector <bool> > (m, vector <bool>(n, false)));
    scan(0, 0);
    cout << "YES";
    return 0;
}
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
03.05.2013, 20:51  [ТС]     Судоку. Задача довольно-таки интересная #13
она всегда NO выводит
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 21:24     Судоку. Задача довольно-таки интересная #14
Lonter, введите тест
4
1 2 3 4
4 3 2 1
3 4 1 2
2 1 4 3
Выведет YES
Она правильно работает.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
04.05.2013, 14:54  [ТС]     Судоку. Задача довольно-таки интересная #15
да это я дурак......можно вопрос) можете пояснить все с <vector> и <algorithm>??

Добавлено через 17 часов 27 минут
для чего нам трехмерный массив?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.05.2013, 20:02     Судоку. Задача довольно-таки интересная #16
Lonter, двумерный массив блоков (квадратиков)
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
05.05.2013, 20:19  [ТС]     Судоку. Задача довольно-таки интересная #17
if (row[i][temp] || col[j][temp] || block[i/m][j/m][temp]) это совпадение ищет??

block = vector < vector < vector <bool> > > (m, vector < vector <bool> > (m, vector <bool>(n, false))); и вот это не до конца догоняю)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
06.05.2013, 17:16     Судоку. Задача довольно-таки интересная #18
Цитата Сообщение от Lonter Посмотреть сообщение
block = vector < vector < vector <bool> > > (m, vector < vector <bool> > (m, vector <bool>(n, false))); и вот это не до конца догоняю)
это конструктор, означает массив m * m * n (m * m блоков в которых может лежать число от 0 до n-1)

Цитата Сообщение от Lonter Посмотреть сообщение
if (row[i][temp] || col[j][temp] || block[i/m][j/m][temp]) это совпадение ищет??
это проверка на наличие такой цифры в соответствующих : 1) строке 2) столбце 3) блоке
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2013, 17:23     Судоку. Задача довольно-таки интересная
Еще ссылки по теме:

Почему результат компиляции маленькой программы на с++ имеет довольно большой размер? C++
C++ Интересная задача на вывод процентов
Довольно большое время работы с std::min() C++
Интересная задача на графы C++
Подскажите по C++ довольно простую литературу C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
06.05.2013, 17:23  [ТС]     Судоку. Задача довольно-таки интересная #19
ну теперь я думаю справлюсь) спасибо)
Yandex
Объявления
06.05.2013, 17:23     Судоку. Задача довольно-таки интересная
Ответ Создать тему
Опции темы

Текущее время: 00:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru