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

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

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

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

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

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

Добавлено через 2 часа 50 минут
а вроде задание так звучит: дан текстовый файл, в нем размерность массива и сам массив....проверить, является ли массив решением судоку. Проверку оформить через рекурсию.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.04.2013, 13:48     Судоку. Задача довольно-таки интересная
Посмотрите здесь:

Довольно Трудная задача(Двумерные массивы) - C++
Вот попалась такая задача: Найти седловую точку целочисленной матрицы с числом строк не более 12, числом столбцов не более 20....

Интересная задача на графы - C++
Помогите решить. Никак не могу придумать способ. Мне говорят, что на графы, а связать это с графами не могу. Может хоть способ решения и...

Интересная задача на вывод процентов - C++
Задан текст, слова которого разделены %. Выяснить и вывести на экран, какой процент слов в тексте начинается на заданную букву (буква...

Очень интересная задача, не все смогут - C++
Напишите программу, использующую рекурсию, определяющую положение восьми ферзей на шахматной доске, при котором ни один ферзь не угрожает...

Интересная задача. (вывод своего кода на экран) - C++
Вот, сидели с другом на паре и возник вопрос: Можно ли в с\с++ написать программу , которая выведет сама свой код на экран? В голову...

Довольно странно. - C++
Приписать к числу 1022 слева и справа по одной цифре так, что-бы полученное шестизначное число делилось на 7,8,9. Весь моск сломал. ...

Подскажите по C++ довольно простую литературу - C++
Проблема заключается в том, что мне бы хотелось изучить язык программирования C++. Вся сложность в моем непонимании многих нюансов данного...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
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
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
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
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
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
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
Она правильно работает.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2013, 14:54     Судоку. Задача довольно-таки интересная
Еще ссылки по теме:

Довольно большое время работы с std::min() - C++
Здравствуйте! Имеется 2 исходника. 1: #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;stack&gt; #include...

Довольно странный и смешной глюк. (и очень непонятный.) - C++
Появился странный глюк. В точке 1 ввожу текст в структуру при помощи обычного cin. В точке 2 видно, что значение принято. В точке 3,...

Довольно сложная задачка (как можно добыть функцию?) - C++
Вопрос заключается в следующем: как можно добыть функцию? Допустим есть он-лайн игра (многим известная, Point Blank), мне надо порыскать в...

Почему результат компиляции маленькой программы на с++ имеет довольно большой размер? - C++
Почему 20 строчек программа после компиляции exe файл занимает пол метра 512 кб?) так много

Таки почему? - C++
Здрасте,это опять я со своими тупыми вопросами. Собсно: first *b=new second; first-базовый класс,second-производный. Собсно,в...


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

Или воспользуйтесь поиском по форуму:
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
04.05.2013, 14:54  [ТС]     Судоку. Задача довольно-таки интересная #15
да это я дурак......можно вопрос) можете пояснить все с <vector> и <algorithm>??

Добавлено через 17 часов 27 минут
для чего нам трехмерный массив?
Yandex
Объявления
04.05.2013, 14:54     Судоку. Задача довольно-таки интересная
Ответ Создать тему
Опции темы

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