Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
#1

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

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

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

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

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

Интересная задача
Добрый вечер! если не трудно можете мне помочь с решение задания Шарик...

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

Интересная задача на числа Фибоначчи
Требуется решить данную задачу: Караси и пираньи В озеро «Карасевое» ради...

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

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

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

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

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

Добавлено через 2 минуты
тут перебор для всех нулей проводится?)
0
Ternsip
663 / 191 / 29
Регистрация: 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, изначально в судоку могут отсутсвовать числа (пустые клетки) на этих местах в исходном массиве стоят нули, обратите внимание.
0
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:34  [ТС] #9
да это я понял=)) то есть там хоть сколько нулей может быть=)
0
Ternsip
663 / 191 / 29
Регистрация: 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 - должно быть квадратом натурального числа
1
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:59  [ТС] #11
Спасибо))) под рекурсию сам попробую) только вот я дуб в этом) ну пофиг)
0
Ternsip
663 / 191 / 29
Регистрация: 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;
}
0
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
03.05.2013, 20:51  [ТС] #13
она всегда NO выводит
0
Ternsip
663 / 191 / 29
Регистрация: 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
Она правильно работает.
0
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
04.05.2013, 14:54  [ТС] #15
да это я дурак......можно вопрос) можете пояснить все с <vector> и <algorithm>??

Добавлено через 17 часов 27 минут
для чего нам трехмерный массив?
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
05.05.2013, 20:02 #16
Lonter, двумерный массив блоков (квадратиков)
1
Lonter
1 / 1 / 2
Регистрация: 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))); и вот это не до конца догоняю)
0
Ternsip
663 / 191 / 29
Регистрация: 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) блоке
0
Lonter
1 / 1 / 2
Регистрация: 22.04.2013
Сообщений: 45
06.05.2013, 17:23  [ТС] #19
ну теперь я думаю справлюсь) спасибо)
0
06.05.2013, 17:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2013, 17:23
Привет! Вот еще темы с решениями:

Интересная задача на предельные значения переменных
Проинициализируйте переменнyю i таким образом, чтобы распечаталось слово. ...

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

Интересная задача с географическими координатами и идеальным поездом передвигающимся от силы гравитации
Всем доброго времени суток. С дублировал тему так как на форуме явы народа...

Довольно странно.
Приписать к числу 1022 слева и справа по одной цифре так, что-бы полученное...


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

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

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