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

Cудоку перебор - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
ShmidT333
0 / 0 / 0
Регистрация: 16.02.2012
Сообщений: 3
16.02.2012, 23:55     Cудоку перебор #1
Здравствуйте,мы с товарищем решили написать решалку для судоку,но появилась проблемма,которая как оказалось поставила нас в тупик.

Введение:
Сам судоку у нас хранится в структуре sudoky,где "x" само значение судоку(равен 0 если точка неизвесна), "y" количество вариантов для точки(равен 0 если точка проставлена), дальше массив "c[10]" в массиве хранятся варианты которые подходят для этой точки), и массив "ind[10]" вспомогательный массив для функций.Принимаем мы из файла,точки пришутся через пробел и неопределённые точки пишутся 0.
C++
1
2
3
4
5
6
7
8
9
struct sudoky{
    int x,y;
    int c[10];
    int ind[10];
    sudoky()
    {x=y=0;for(int i=0;i<10;i++){
        c[i]=i;ind[i]=0;}
    }
};
Я думаю, что все из вас знают, как решается эта головоломка(судоку).
Как правило сложные судоку решаются различными методами, но самая простая часть(расстановка вариантов для точек, запись однозначный вариантов) приводит судоку к неопределённости, в том смысле, что нет однозначных вариантов расположения точек. Мы написали 4 разных метода, которые
позволяют раскрывать эту неопределённость.Я думаю эти 4 метода вовсе не нужны вам,если понадобятся кину. вот код той функции,как я сказал простой части.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
void doneopr(void){
    
 
for(i=0;i<9;i++){
    
        for(j=0;j<9;j++)
        if(a[i][j].x==0)
            {for(k=1;k<10;k++){
                for(q=0;q<9;q++)
                    if(a[i][q].x==k){
                        a[i][j].c[k]=0;
                    }
            
                for(q=0;q<9;q++)
                    if(a[q][j].x==k){
                        a[i][j].c[k]=0;
                    }
 
            }
 
        }
    }
 
//end proverka!!!
 
 
//proverka 2
 
for(i=0;i<9;i++)
        for(j=0;j<9;j++)
        if(a[i][j].x==0)
            {for(k=1;k<10;k++){
                if(i%3==2){
                    if(j%3==2){for(q=i-2;q<=i;q++)
                    for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                else { if(j%3==1){for(q=i-2;q<=i;q++)
                            for(t=j-1;t<=j+1;t++)
                            if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i-2;q<=i;q++)
                                for(t=j;t<=j+2;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                                            }
                                    }
                }
                else { if(i%3==1){if(j%3==2){for(q=i-1;q<=i+1;q++)
                    for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                    else { if(j%3==1){for(q=i-1;q<=i+1;q++)
                            for(t=j-1;t<=j+1;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i-1;q<=i+1;q++)
                                    for(t=j;t<=j+2;t++)
                                    if(a[q][t].x==k){
                                a[i][j].c[k]=0;}}
                                            }
                                    }}
                else {if(i%3==0){if(j%3==2){for(q=i;q<i+3;q++)
                        for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                        else { if(j%3==1){for(q=i;q<=i+2;q++)
                                for(t=j-1;t<=j+1;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i;q<=i+2;q++)
                                    for(t=j;t<=j+2;t++)
                                    if(a[q][t].x==k){
                                        a[i][j].c[k]=0;}}
                                            }
                                    }
                }
                }
                }
        }
        }
//search!
for(i=0;i<9;i++){
        for(j=0;j<9;j++)
        if(!a[i][j].x){p=0;
            for(k=1;k<10;k++)
                if(a[i][j].c[k])p++;
            a[i][j].y=p;
        }
}
//zamena
r=r1=0;
for(i=0;i<9;i++)
 
 for(j=0;j<9;j++){
 if(a[i][j].y==1){r++;
  for(k=1;k<10;k++)
   if(a[i][j].c[k]!=0){
    a[i][j].x=a[i][j].c[k];
    a[i][j].y=0;
//  for(q=0;q<10;q++)
    //  a[i][j].c[q]=0;
   
   }
 
 
 
} if(a[i][j].y==0)r1++;
}
if(r!=0&&r1!=0)doneopr();  // r - это количество 1 в судоку, r1 количество 0
}
Проблемма:
Наши 4 метода о которых я говорил выше, упрощают судоку, а бывает и решают её=), но на самых сложных они тоже становятся бесполезными. И тут мы думаем сделать перебор, но как его реализовать мы не знаем=( Перебор должен перебирать значения из точек у которых нет однозначного значения из массива с.

вот пример такого судоку:
C++
1
2
3
4
5
6
7
8
9
2 0 0 8 6 0 0 9 7
0 5 4 0 0 2 0 0 3
0 0 0 0 0 0 0 5 2
0 0 0 3 8 0 0 0 9
0 0 0 0 0 0 0 0 0
6 4 1 0 0 0 0 0 5
5 9 0 0 0 0 0 0 0
0 0 2 9 3 0 0 0 0
0 0 0 1 0 0 0 0 0
вот что выводит программа:
C++
1
2
3
4
5
6
7
8
9
2 1 3 8 6 5 4 9 7 
0 5 4 7 0 2 0 0 3 
0 0 0 4 0 3 0 5 2 
7 2 5 3 8 0 0 0 9 
0 0 0 5 0 0 0 0 0 
6 4 1 2 0 0 0 0 5 
5 9 0 6 0 0 0 0 0 
1 0 2 9 3 0 5 0 0 
4 0 0 1 5 0 9 2 0
и вот на этих точках надо сделать перебор.
Жду советов и предложений.
Заранее спасибо.
Вроде всё=)

Добавлено через 4 минуты
Формально, перебрать весь массив с, и после каждого перебора делать проверку на решенность судоку.Проверка написана.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.02.2012, 23:55     Cудоку перебор
Посмотрите здесь:

Перебор списка C++
C++ Перебор комбинаций
C++ Перебор чисел
Перебор C++
Перебор текста C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
17.02.2012, 00:04     Cудоку перебор #2
Делаем копию данных, выставляем первое возможное значение для одной из ячеек(желательно той, для которой минимум вариантов), решаем дальше аналитически. Если уперлись в ошибку, возвращаемся до сохраненного варианта и ставим следующие возможное значение.
Kirrosh
0 / 0 / 0
Регистрация: 15.02.2012
Сообщений: 5
17.02.2012, 00:08     Cудоку перебор #3
Проблема в том что ошибка может быть в любой из непоставленных клеток. В общем случае определить где именно нельзя.
ShmidT333
0 / 0 / 0
Регистрация: 16.02.2012
Сообщений: 3
17.02.2012, 00:15  [ТС]     Cудоку перебор #4
Эм.. мы думали над этим, но когда подставив так как Вы сказали,потом решая аналитически, можно уперется ещё в одну неопределённость,а потом ещё в одну,их может быть очень много, а может и совсем одна=)

Добавлено через 2 минуты
думаю,этот способ, может иметь место, но опять таки создаются проблемы, причём не малые.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
17.02.2012, 00:21     Cудоку перебор #5
Цитата Сообщение от ShmidT333 Посмотреть сообщение
"c[10]" в массиве хранятся варианты которые подходят для этой точки), и массив "ind[10]" вспомогательный массив для
почто десять то ????
могу предложить простейшиа алгоритм
берем открытую ячейку и по вертикали горизонтали от нее выбрасываем в ячейках это число


я бы по другому сделал
C++
1
int d[9];
и все
номер элемента массива это число а значение есть это число (1) в ячейке или нет(0)
например сначала все числа могут быть все элементы 1
потом пятерка не может быть
C++
1
d[4]=0;
соответственно массив выглядит 111101111
для проверки в цикле делаешь сумму элементов
больше 1 не понятно какое число
1 число равно номеру элемента+1
0 неправильное решение
ShmidT333
0 / 0 / 0
Регистрация: 16.02.2012
Сообщений: 3
17.02.2012, 00:31  [ТС]     Cудоку перебор #6
10 для небольшого удобства в методах,удобно расположение именно c[i]=i;(смотри конструктор по умолчанию в структуре),это впринципе не важно.

могу предложить простейшиа алгоритм
берем открытую ячейку и по вертикали горизонтали от нее выбрасываем в ячейках это число

номер элемента массива это число а значение есть это число (1) в ячейке или нет(0)
например сначала все числа могут быть все элементы 1
потом пятерка не может быть
Код C++1 d[4]=0;

соответственно массив выглядит 111101111
для проверки в цикле делаешь сумму элементов
больше 1 не понятно какое число
1 число равно номеру элемента+1
0 неправильное решение
это и делает функия doneopr().
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
17.02.2012, 01:02     Cудоку перебор #7
Цитата Сообщение от ShmidT333 Посмотреть сообщение
это и делает функия doneopr().
ты бы хоть коментарии поставил что делаешь и в чем ошибка
а то два листа непонятного текста читать
Цитата Сообщение от ShmidT333 Посмотреть сообщение
x=y=0;for(int i=0;i<10;i++){
c[i]=i;
вот это вообще классно
0123456789
дублирование информации
хоть бы что нибудь про алгоритмы прочитал
сравни мою реализацию(причем я её сейчас придумал) и свою
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
class elem //класс ячейки
 
{
publik:
int value;
elem(){for(int i=0;i<9;i++) arr[i]=1;// конструктор по умолчанию
           value=0;}
elem(int val){set(val)};               // конструктор если задано значение
void set(int val){for(int i=0;i<9;i++) arr[i]=0;  // функция установки значения
                   arr[val-1]=1;
                    value=val;}
int verify{ int tmp=0                     // проверка и может быть установка значения
              for(int i=0;i<9;i++) tmp+=arr[i];
              if(tmp==0) return -1;       // нет решений
              if(tmp>1)   return 0;         // не установлено значение
              for(int i=0;i<9;i++)           // установка значения
                  if(arr[i]) 
                   {
                    value=i+1;
                    return value;
                    }
 void erase(int val){arr[val-1]=0;}   // стираем число которое не может быть
 
                       
privat:
  int arr[9];       
 }
class bloc            // блок 3х3 ячейки
{
public:
 elem elems[3][3];
}
class sudoku       // класс судоку
{
public:
bloc sud[3][3];
}
методы для блока и судоку расписывать не стал
wolf19996
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 5
25.02.2012, 21:31     Cудоку перебор #8
На этот форум пришёл решая эту задачу, так вот зделал код работающий по алгоритму
1 анализ судоку с поиском количества пропущеных ячеек (n)
2 создание двумерного массива размером n строк и 9 столбцов
3 заполнения этого массива возможными значениями, остальное заполняем 0
4 поочерёдная подстановка значений в соответствующие ячейки

проблема: выдаёт перегрузку стэка на 6334 операции подстановки, помогите пожалуйста, как последний алгоритм переписать или в чём ошибка может быть? (пишу на с++)
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
25.02.2012, 21:38     Cудоку перебор #9
В переполнении стека же. Выделяй память под большие объекты из кучи, избавься от лишних рекурсивных вызовов...
wolf19996
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 5
25.02.2012, 21:45     Cудоку перебор #10
Лишняя рекурсия вычищена пропуском шага в цикле если подставляемый элемент-0. И фильтром по массиву решений.
Единственный не динамический массив это сам судоку, всё остальное представлено динамическими или я чего-то не понимаю.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
25.02.2012, 22:04     Cудоку перебор #11
Похоже, что рекурсии всё же слишком много.
Цитата Сообщение от wolf19996 Посмотреть сообщение
Единственный не динамический массив это сам судоку
Ничего, что это самый большой объект из объектов, с которым ты работаешь?

Добавлено через 1 минуту
Где код-то? libastral к концу недели нестабильно работает.
wolf19996
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 5
25.02.2012, 22:04     Cудоку перебор #12
это не самый большой самый большой это n на 9 он (т.е. массив решений под каждый элемент) он размером около 450 символов, а то и больше, а во-вторых этот массив вроде не на столько и большой, но сейчас переделаю.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
// sudoku решалка для судоку
 
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
 
 
void fud(int **res,int a)
    {
for (int i = 0; i<a; i++)
        delete [] res[i];
delete [] res;
res=NULL;
        }
void fvost(int et[9]) // функция восстановления эталонной строки
{for (int i=0; i<9; i++)
{et[i]=i+1;}
}
 
int fprovs(int ar[9][9])//половина алгоритма проверки (строчная)
    {int et[9];
    int a;
    a=0;
    fvost(et);  
    for (int i=0; i<9; i++)
    {for(int j=0; j<9; j++)
        { for (int t=0; t<9; t++)
            {if (ar[i][j]==et[t]) et[t]=0; a++; 
            }
        }
    fvost(et);
    }
    return a;
    }
 
int fprov(int ar[9][9])// вторая половина (столбичная) о_О
    {int et[9];
    int a;
    a=0;
    fvost(et);  
    for (int i=0; i<9; i++)
    {for(int j=0; j<9; j++)
        { for (int t=0; t<9; t++)
            {if (ar[j][i]==et[t])et[t]=0;a++;
            }
        }
     fvost(et);
    }
    return a;
    }
 
void fans(int ar[9][9], int r[9][9]) //функция анализа строк  для поиска массива решений
{for(int j=0; j<9; j++)
{for(int o=0; o<9; o++)
    {for(int l=0; l<9; l++)
    {if (ar[j][o]==r[j][l]){r[j][l]=0;}}
}
}
for(int i=0; i<9; i++)
{for(int j=0; j<9; j++)
    {cout<<r[i][j];}
cout<<endl;}
cout<<endl<<endl;
}
 
void fanst(int ar[9][9], int r[9][9])//функция анализа столбцов  для поиска массива решений
{for(int j=0; j<9; j++)
{for(int o=0; o<9; o++)
    {for(int l=0; l<9; l++)
    {if (ar[o][j]==r[j][l]){r[j][l]=0;}}
}
}
for(int i=0; i<9; i++)
{for(int j=0; j<9; j++)
    {cout<<r[i][j];}
cout<<endl;}
}
 
int fk(int ar[9][9])//функция анализа таблиы с целью поиска параметров для двумерного массива с решениями для строк
{int a=0;
 
for(int i=0; i<9; i++)
    {for(int j=0; j<9; j++)
        {if (ar[i][j]==0) a++;}
}
return a;
}
 
void fresh ( int ar[9][9], int **res, int **uk,int a,int r[9][9], int rstr [9][9])//функция сопаставления решений строк с целью поиска решений
{int b;
b=0;
int *st=new int[a];
int *sb=new int[a];
for (int i=0; i<9; i++)
    {for(int j=0; j<9; j++)
        {if (ar[i][j]==0)
            {uk[b]=&ar[i][j];st[b]=i; sb[b]=j; b++;}
        }
        }
for(int i=0; i<a; i++)
    {cout<<st[i];
    cout<<sb[i]<<endl;
    }
 
int o;
o=0;
for (int i=0; i<a; i++)
    {for(int j=0; j<9; j++)
        {for(int l=0; l<9; l++)
        {
            if (r[st[i]][j]==rstr[sb[i]][l]) {res[i][j]=r[st[i]][j]; break;}
            else res[i][j]=0;
            
        }
        }
 
    }
delete []st;
st=NULL;
delete []sb;
sb=NULL;
 
}
 
 
void fbfs(int a,int **res ,int **uk, int ar[9][9],int o, int stop,int m)//самая "страшная" функция, которая ищет подходящую комбинацию
    {
    for(int i=0; i<9; i++)
    {if (stop=1) exit;
    m++;
    cout<<endl<<m<<endl;
        cout<<a<<"\t"<<i<<endl;
    
        if (res[a][i]==0){continue;}//обращение за пределы массива 
*uk[a]=res[a][i];
if (a-1>0) {fbfs(a-1, res, uk, ar,o,stop,m);}
if ((fprov(ar)+fprovs(ar))==162)
{for (int i=0; i<9; i++)
    {for (int o=0; o<9; o++)
{cout<<ar[i][o];}
cout<<endl;}
exit;stop=1;}
 
}
fbfs(o, res, uk, ar,o,stop,m);
}
 
 
 
int main()
{int ar[9][9];
 
ar[0][0]=2;ar[0][1]=0;ar[0][2]=0;ar[0][3]=0;ar[0][4]=0;ar[0][5]=5;ar[0][6]=8;ar[0][7]=9;ar[0][8]=0;
ar[1][0]=0;ar[1][1]=6;ar[1][2]=0;ar[1][3]=0;ar[1][4]=9;ar[1][5]=0;ar[1][6]=7;ar[1][7]=1;ar[1][8]=0;
ar[2][0]=9;ar[2][1]=0;ar[2][2]=0;ar[2][3]=7;ar[2][4]=0;ar[2][5]=0;ar[2][6]=0;ar[2][7]=0;ar[2][8]=4;
ar[3][0]=0;ar[3][1]=0;ar[3][2]=0;ar[3][3]=0;ar[3][4]=6;ar[3][5]=0;ar[3][6]=0;ar[3][7]=5;ar[3][8]=8;
ar[4][0]=0;ar[4][1]=0;ar[4][2]=6;ar[4][3]=0;ar[4][4]=0;ar[4][5]=0;ar[4][6]=4;ar[4][7]=0;ar[4][8]=0;
ar[5][0]=5;ar[5][1]=9;ar[5][2]=0;ar[5][3]=0;ar[5][4]=3;ar[5][5]=0;ar[5][6]=0;ar[5][7]=0;ar[5][8]=0;
ar[6][0]=3;ar[6][1]=0;ar[6][2]=0;ar[6][3]=0;ar[6][4]=0;ar[6][5]=8;ar[6][6]=0;ar[6][7]=0;ar[6][8]=7;
ar[7][0]=0;ar[7][1]=4;ar[7][2]=9;ar[7][3]=0;ar[7][4]=2;ar[7][5]=0;ar[7][6]=0;ar[7][7]=8;ar[7][8]=0;
ar[8][0]=0;ar[8][1]=8;ar[8][2]=5;ar[8][3]=1;ar[8][4]=0;ar[8][5]=0;ar[8][6]=0;ar[8][7]=0;ar[8][8]=9;
 
for (int i=0; i<9; i++)
    {for (int j=0; j<9; j++)
{cout<<ar[i][j];}
cout<<endl;}
 
cout<<endl<<endl;
 
int r[9][9];
for (int i=0; i<9; i++)
{for(int j=0; j<9; j++)
    {r[i][j]=j+1;}
}
 
fans(ar, r);
int rst[9][9];
for (int i=0; i<9; i++)
{for(int j=0; j<9; j++)
{rst[i][j]=j+1;}}
fanst (ar, rst);
int a;
a=fk(ar);
cout<<endl;
 
int **uk= new int*[a];
 
int **res = new int*[a];
for (int i = 0; i < a; i++) res[i] = new int[9];
 
 
fresh( ar, res,  uk, a, r,  rst);
 
for (int i=0; i<a; i++)
    {for (int j=0; j< 9; j++)
        {
        cout<<res[i][j];
        }
    cout<<endl;
    }
int o, stop, m;
o=a-1;
stop=0;
m=0;
cout<<endl<<endl;
fbfs(a-1, res, uk,ar, o,stop,m);
fud(res,a);
fud(uk,a);
_getch();
    return 0;
}
P.S.
код исправлен судоку был переделан под динамический всё тот же стоп на 6333 элементе
wolf19996
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 5
06.03.2012, 22:42     Cудоку перебор #13
Тадам... код написан и работает если будет интерес выложу)
Devochka
 Аватар для Devochka
31 / 19 / 1
Регистрация: 07.10.2011
Сообщений: 98
16.07.2012, 13:01     Cудоку перебор #14
Интересно! Хотелось бы рабочий код. (если он решает и сложные уровни) Иногда не могу решить в журнале, так может хоть с помощью программки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2012, 13:02     Cудоку перебор
Еще ссылки по теме:

C++ Перебор символов
C++ Cделать перебор id-ов
Перебор C++

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

Или воспользуйтесь поиском по форуму:
wolf19996
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 5
16.07.2012, 13:02     Cудоку перебор #15
код сделан ещё зимой)
Yandex
Объявления
16.07.2012, 13:02     Cудоку перебор
Ответ Создать тему
Опции темы

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