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

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

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

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

Добавлено через 2 часа 50 минут
а вроде задание так звучит: дан текстовый файл, в нем размерность массива и сам массив....проверить, является ли массив решением судоку. Проверку оформить через рекурсию.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.04.2013, 13:48
Ответы с готовыми решениями:

Тормозит новый, довольно-таки мощный компьютер
Всем привет. Недавно решил сделать апгрейд компьютера, купил материнскую плату и процессор....

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

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

Довольно короткая, но замысловатая задача с вероятностями
Не уверен, к какому разделу это можно отнести, посему, напишу в общий. Существует некоторый...

18
667 / 195 / 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
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
30.04.2013, 14:30  [ТС] 3
а что значит forn?
0
667 / 195 / 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
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 09:37  [ТС] 5
Вы уверены что а[9][9]? а не [8][8]

Добавлено через 11 минут
И вроде как в рекурсии не стоит циклы делать
0
667 / 195 / 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
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
01.05.2013, 11:30  [ТС] 7
я новичок это да) но я перешел даже не с паскаля а с VBA)

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

Добавлено через 17 часов 27 минут
для чего нам трехмерный массив?
0
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
05.05.2013, 20:02 16
Lonter, двумерный массив блоков (квадратиков)
1
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))); и вот это не до конца догоняю)
0
667 / 195 / 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
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
06.05.2013, 17:23  [ТС] 19
ну теперь я думаю справлюсь) спасибо)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.05.2013, 17:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Задача по типу судоку
Здравствуйте. Вообщем задача звучит так: создать массив 4х4, так чтобы сумма цифр каждой строки,...

Интересная задача
Здравствуйте! Никак не пойму, каким методом решается следующая задача. Если кто сталкивался с...

Интересная Задача
Всем привет. Есть интересная задача (сразу скажу что есть и 2 вариант, но хотелось бы понять почему...

Интересная задача
A = 9; B = -17; C = 13; D = -39; ЕСЛИ (B &gt; D) ТОГДА C=(D+B)*5; ЕСЛИ (D &gt; C) ТОГДА A=(A mod B)...


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

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

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