Skip to content

Commit 371088c

Browse files
JianNLJianNL
committed
sudoku solution
1 parent e4abafc commit 371088c

8 files changed

Lines changed: 314 additions & 3 deletions

File tree

‎studycpp/Function.h‎

Lines changed: 40 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,43 @@ void useOfinitializer_list(initializer_list<string> l)
1111
{
1212
cout << *beg << endl;
1313
}
14-
}
14+
}
15+
16+
17+
void useOfvectorPara(vector<int> vec)
18+
{
19+
cout << "useOfvectorPara" << endl;
20+
for (auto c : vec)
21+
{
22+
cout << c << endl;
23+
c = 1;
24+
}
25+
}
26+
27+
28+
void useOfcomplicatedVectorPara(vector<vector<int> > comVec)
29+
{
30+
cout << "useOfcomplicatedVectorPara" << endl;
31+
for (auto iter = comVec.begin(); iter != comVec.end();++iter)
32+
{
33+
for (auto iter_iner = (*iter).begin(); iter_iner != (*iter).end();++iter_iner)
34+
{
35+
*iter_iner = 1;
36+
}
37+
}
38+
}
39+
40+
41+
void printOfcomplicatedVectorPara(vector<vector<int> > comVec)
42+
{
43+
cout << "printOfcomplicatedVectorPara" << endl;
44+
for (auto iter = comVec.begin(); iter != comVec.end();++iter)
45+
{
46+
for (auto iter_iner = (*iter).begin(); iter_iner != (*iter).end();++iter_iner)
47+
{
48+
cout << *iter_iner ;
49+
}
50+
cout << endl;
51+
}
52+
53+
}

‎studycpp/arithmeticOperate.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,17 @@
44
using namespace std;
55

66

7+
8+
9+
void normalArithmetic()
10+
{
11+
cout << "normalArithmetic" << endl;
12+
int i = 4;
13+
cout << ((i / 3.0) * 3) << endl;
14+
cout << i / 3 * 3 << endl;
15+
}
16+
17+
718
void wrappedaround()
819
{
920
cout << "wrappedaround" << endl;

‎studycpp/main.cpp‎

Lines changed: 48 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
#include "arithmeticOperate.h"
88
#include "TypeConversion.h"
99
#include "Function.h"
10+
#include "sudoku.h"
1011

1112

1213

@@ -91,6 +92,7 @@ int main()
9192
vector test!
9293
*/
9394
//normaluseOfVector();
95+
//useOfremove_if();
9496

9597
/*
9698
vector test!
@@ -121,7 +123,7 @@ int main()
121123
/*
122124
arithmeticOperate
123125
*/
124-
126+
//normalArithmetic();
125127
//wrappedaround();
126128
//useOfRelationalOperator();
127129
/*
@@ -144,8 +146,52 @@ int main()
144146
/*
145147
function
146148
*/
147-
useOfinitializer_list({ "fsdfsfsdf", "sdfsdfsfddsf", "helloworld" });
149+
//useOfinitializer_list({ "fsdfsfsdf", "sdfsdfsfddsf", "helloworld" });
150+
//vector<int> vec1 = { 1, 2, 3, 4, 5 };
151+
//useOfvectorPara(vec1);
152+
//for (auto e:vec1)
153+
//{
154+
//cout << e << endl;
155+
//}
156+
/*
157+
function
158+
*/
159+
160+
/*
161+
sudoku
162+
*/
163+
/*
164+
vector<vector<int> > s = {
165+
{ 2, 7, 6, 0, 0, 0, 0, 8, 0 },
166+
{ 3, 0, 0, 8, 0, 0, 0, 1, 5 },
167+
{ 5, 0, 0, 2, 0, 9, 7, 0, 0 },
168+
{ 0, 8, 2, 3, 0, 0, 4, 0, 0 },
169+
{ 0, 0, 0, 0, 5, 0, 0, 0, 0 },
170+
{ 0, 0, 1, 0, 0, 4, 3, 6, 0 },
171+
{ 0, 0, 4, 5, 0, 8, 0, 0, 7 },
172+
{ 1, 6, 0, 0, 0, 3, 0, 0, 4 },
173+
{ 0, 3, 0, 0, 0, 0, 5, 2, 1 }
174+
};
175+
vector<vector<int> > s1 = {
176+
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
177+
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
178+
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
179+
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
180+
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
181+
{ 0, 0, 0, 1, 0, 0, 0, 3, 0 },
182+
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
183+
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
184+
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 }
185+
};
186+
*/
148187

188+
//useOfcomplicatedVectorPara(s);
189+
//printOfcomplicatedVectorPara(s);
190+
//sudoku solution;
191+
//solution.printSolution(s);
192+
//solution.getSolution(s1);
193+
//cout << "the solution is" << endl;
194+
//solution.printSolution();
149195

150196

151197

‎studycpp/studycpp.vcxproj‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,7 @@
7373
<ItemGroup>
7474
<ClCompile Include="main.cpp" />
7575
<ClCompile Include="referenceTest.h" />
76+
<ClCompile Include="sudoku.cpp" />
7677
</ItemGroup>
7778
<ItemGroup>
7879
<ClInclude Include="arithmeticOperate.h" />
@@ -82,6 +83,7 @@
8283
<ClInclude Include="lvalueAndrvalue.h" />
8384
<ClInclude Include="securityFun.h" />
8485
<ClInclude Include="stringStudy.h" />
86+
<ClInclude Include="sudoku.h" />
8587
<ClInclude Include="TypeConversion.h" />
8688
<ClInclude Include="useOfArray.h" />
8789
<ClInclude Include="vectorStudy.h" />

‎studycpp/studycpp.vcxproj.filters‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,9 @@
4545
<ClInclude Include="Function.h">
4646
<Filter>Header Files</Filter>
4747
</ClInclude>
48+
<ClInclude Include="sudoku.h">
49+
<Filter>Header Files</Filter>
50+
</ClInclude>
4851
</ItemGroup>
4952
<ItemGroup>
5053
<ClCompile Include="main.cpp">
@@ -53,5 +56,8 @@
5356
<ClCompile Include="referenceTest.h">
5457
<Filter>Header Files</Filter>
5558
</ClCompile>
59+
<ClCompile Include="sudoku.cpp">
60+
<Filter>Source Files</Filter>
61+
</ClCompile>
5662
</ItemGroup>
5763
</Project>

‎studycpp/sudoku.cpp‎

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
#include "sudoku.h"
2+
3+
4+
5+
6+
7+
8+
vector<int> sudoku::getRow(vector<vector<int> > matrix,int rowNum)
9+
{
10+
vector<int> rowData;
11+
for (auto e:matrix[rowNum])
12+
{
13+
if (e>0)
14+
{
15+
rowData.push_back(e);
16+
}
17+
}
18+
return rowData;
19+
}
20+
21+
22+
vector<int> sudoku::getCol(vector<vector<int> > matrix,int colNum)
23+
{
24+
vector<int> colData;
25+
int temp=0;
26+
for (int i = 0; i != 9; ++i)
27+
{
28+
if ((temp=matrix[i][colNum])>0)
29+
{
30+
colData.push_back(temp);
31+
}
32+
}
33+
return colData;
34+
}
35+
36+
37+
vector<int> sudoku::getGrid(vector<vector<int> > matrix,int rowNum, int colNum)
38+
{
39+
int startRow = (rowNum / 3) * 3;
40+
int startCol = (colNum / 3) * 3;
41+
vector<int> gridData;
42+
int temp=0;
43+
for (int i = startRow; i != startRow + 3;++i)
44+
{
45+
for (int j = startCol; j != startCol + 3;++j)
46+
{
47+
if ((temp=matrix[i][j])>0)
48+
{
49+
gridData.push_back(temp);
50+
}
51+
}
52+
}
53+
return gridData;
54+
}
55+
56+
57+
vector<int> sudoku::getPossibleVaule(vector<vector<int> > matrix,int rowNum, int colNum)
58+
{
59+
vector<int> nineNumbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
60+
vector<int> rowData = getRow(matrix,rowNum);
61+
vector<int> colData = getCol(matrix,colNum);
62+
vector<int> gridData = getGrid(matrix,rowNum, colNum);
63+
auto p = remove_if(nineNumbers.begin(), nineNumbers.end(), [rowData, colData, gridData](int n){
64+
if (find(rowData.begin(),rowData.end(),n)!=rowData.end())
65+
{
66+
return true;
67+
}
68+
if (find(colData.begin(),colData.end(),n)!=colData.end())
69+
{
70+
return true;
71+
}
72+
if (find(gridData.begin(),gridData.end(),n)!=gridData.end())
73+
{
74+
return true;
75+
}
76+
return false;
77+
});
78+
nineNumbers.erase(p, nineNumbers.end());
79+
return nineNumbers;
80+
}
81+
82+
83+
84+
bool sudoku::getEmptyPos(vector<vector<int> > matrix,int &rowNum, int &colNum)
85+
{
86+
for (int i = 0; i != 9; ++i)
87+
{
88+
for (int j = 0; j != 9;++j)
89+
{
90+
if (matrix[i][j]==0)
91+
{
92+
rowNum = i;
93+
colNum = j;
94+
return true;
95+
}
96+
}
97+
}
98+
return false;
99+
}
100+
101+
102+
bool sudoku::getSolution(vector<vector<int> > matrix)
103+
{
104+
int rowNum = -1;
105+
int colNum = -1;
106+
if (getEmptyPos(matrix, rowNum, colNum))
107+
{
108+
auto possibleValues = getPossibleVaule(matrix, rowNum, colNum);
109+
if (possibleValues.empty())
110+
{
111+
return false;
112+
}
113+
for (auto e : possibleValues)
114+
{
115+
matrix[rowNum][colNum] = e;
116+
if (!getSolution(matrix))
117+
{
118+
continue;
119+
}
120+
else
121+
return true;
122+
}
123+
return false;
124+
125+
126+
}
127+
else
128+
{
129+
printSolution(matrix);
130+
cout << "________________________" << endl;
131+
return true;
132+
}
133+
}
134+
135+
136+
void sudoku::printSolution(vector<vector<int> > matrix)
137+
{
138+
for (int i = 0; i != 9;++i)
139+
{
140+
for (int j = 0; j != 9;++j)
141+
{
142+
cout << matrix[i][j] << " ";
143+
}
144+
cout << endl;
145+
}
146+
}

‎studycpp/sudoku.h‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#include <iostream>
2+
#include <vector>
3+
#include <algorithm>
4+
5+
6+
using namespace std;
7+
8+
class sudoku
9+
{
10+
public:
11+
sudoku()
12+
{
13+
14+
}
15+
bool getSolution(vector<vector<int> > matrix);
16+
void printSolution(vector<vector<int> > matrix);
17+
18+
private:
19+
vector<int> getRow(vector<vector<int> > matrix,int rowNum);
20+
vector<int> getCol(vector<vector<int> > matrix,int colNum);
21+
vector<int> getGrid(vector<vector<int> > matrix,int rowNum, int colNum);
22+
vector<int> getPossibleVaule(vector<vector<int> > matrix,int rowNum, int colNum);
23+
bool getEmptyPos(vector<vector<int> > matrix,int &rowNum, int &colNum);
24+
25+
};

0 commit comments

Comments
 (0)