-
Notifications
You must be signed in to change notification settings - Fork 0
/
8 Cell Cross.cpp
116 lines (101 loc) · 2.84 KB
/
8 Cell Cross.cpp
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
/*
1) All numbers should be unique in the cross array
2) Number n in cross[i] cannot be concecative numbers to any cell above it, below it, diagnel to it from upward and downward
3) When on the cell to check, you always start at 1
4) If we fail to find a number in that cross[i] cell then we increment the number inside to check the next number
3 5
7 1 8 2
4 6
*/
#include <iostream>
#include <math.h>
#include <array>
using namespace std;
struct Cross
{
int cross[8] = {1};
int checkArray[8][5] = {{-1}, {0,-1}, {0,-1}, {0,1,2,-1}, {0,1,3,-1}, {1,4,-1}, {2,3,4,-1}, {3,4,5,6,-1}};
int solutions = 0;
// Prints the array after its done.
void PrintCrossAreay()
{
solutions++;
cout << "Solution #: " << solutions << endl;
cout << " " << cross[0] << " " << cross[1] << endl;
for(int i = 2; i < 6; i++)
{
cout << cross[i] << " ";
}
cout << endl;
cout << " " << cross[6] << " " << cross[7] << endl << endl;;
}
// Makes sure the numbers in each cell is unique and not consecutive diagonally
bool OK(int c)
{
// Loops through the indexs before c to make sure there are no numbers that are the same
for(int i = 0; i < c; i++)
{
// Checks if the cells are equals
if(cross[i] == cross[c])
return false;
}
int i = 0;
// Checks the index of cross to the indexs of the array checkArray
while(checkArray[c][i] != -1)
{
// If they are 1 less or more to the current number in c
if(abs(cross[c] - cross[checkArray[c][i]]) == 1)
return false;
i++;
}
return true;
}
// Uses other methods to solve the puzzle.
void Solve()
{
int c = 0;
cross[c] = 1;
while(c > -1)
{
if(OK(c))
{
c += 1;
if(c > 7)
{
// Prints the array
PrintCrossAreay();
// Backtrack since we reached the maximum array size
c -= 1;
cross[c] += 1;
}
}
else
{
cross[c] += 1;
if(cross[c] > 8)
{
// Resets the cell
cross[c] = 1;
// Backtrack since we reached the maximum number can exist in a cell
c -= 1;
cross[c] += 1;
}
}
// Makes sure the number on the index c doesnt pass 8
if(cross[c] > 8)
{
// Resets the cell
cross[c] = 1;
// Backtrack since we reached the maximum number can exist in a cell
c -= 1;
cross[c] += 1;
}
}
}
};
int main()
{
Cross s;
s.Solve();
return 0;
}