CS211Projects/CS211eightNumbersInACross.cpp at main · kairadiant/CS211Projects · GitHub

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
/*
Kayla Washington-Tapia
Assignment 7: 8 Numbers in a Cross
10.22.2021
CSCI 211 21D
*/

#include<iostream>
using namespace std;

void print(int q[]){ //outputs solution in cross format
	static int s=0;
	cout<<"Solution "<<++s<<endl;
	cout<<" "<<q[1]<<q[6]<<endl;
	cout<<q[0]<<q[2]<<q[5]<<q[7]<<endl;
	cout<<" "<<q[3]<<q[4]<<endl;
}

bool okay(int q[],int c){ //checks to make sure numbers in row are okay
	static int helper[8][5]={
	{-1},
	{-1},
	{0, 1, -1},
	{0, -1},
 	{0, 2, 3, -1},
 	{0, 2, 3, -1},
 	{0, 1, 2, 4, -1},
	{0, 1, 2, 5, -1},
	};

	for(int i=0;i<c;i++){
		if(q[i]==q[c]){
			return false;
		}
	}
	for(int i=0;helper[c][i]!=-1;i++){
		if(abs(q[c]-q[helper[c][i]])==1){
			return false;
		}
	}
	return true;
}

int main(){
	int q[8],place=0;
	q[place]=1;

	while(place>=0){
		++place;
		if(place==8){ //if all solutions were found
			print(q);
			place--; //backtrack

		}
		else{
			q[place]=0;
		}
		while(place>=0){
			++q[place];
			if(q[place]>8){ //if no solutions in row
				place--;
			}
			else{
				if(okay(q,place)){ //if number placement is okay
					break;
				}
			}
		}
	}
}