KnightMoves/Knight.cpp at master · tarassel/KnightMoves · 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
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
/*
// Deep drilling, wrong, should go wide not down
#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

struct Pos
{
	Pos():x(0),y(0){}
	Pos(int _x, int _y):x(_x),y(_y){}
	int x, y;
	Pos* move(int _x, int _y){x += _x; y += _y; return this;}
	bool operator==(const Pos& rval) const { if (x == rval.x && y == rval.y) return true; return false;}
	bool operator!=(const Pos& rval) const { return !(*this==rval);}
	string str(){
 		ostringstream oss;
		oss << "[" << x << ":" << y << "]";
		return oss.str();
	}
};

vector<Pos> moves;
vector<Pos> visitedCells;
unsigned size = 4;

bool IsOnBoard(Pos& pos)
{
	if (pos.x >= 0 && pos.x < size && pos.y >= 0 && pos.y < size)
		return true;
	return false;
}

vector<Pos> FindMoves(Pos& from)
{
	vector<Pos> possibleMoves;

	if (IsOnBoard(*from.move(-1,2)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(-1,-1)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(0,-2)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(1,-1)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(2,0)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(1,1)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(0,2)))
		possibleMoves.push_back(from);
	if (IsOnBoard(*from.move(-1,1)))
		possibleMoves.push_back(from);

	return possibleMoves;
}

struct MovesNode
{
	MovesNode(){}
	MovesNode(Pos p): pos(p){}

	Pos pos;
	vector<MovesNode> moves;
};

void AddLayersUpTo(Pos& from, MovesNode& node, Pos& to)
{
	cout << "Adding layer for " << from.str() << endl;
	node.pos = from;
	vector<Pos> moves = FindMoves(from);
	for (unsigned i=0; i<moves.size() && find(visitedCells.begin(), visitedCells.end(), moves[i]) == visitedCells.end(); i++)
	{
		cout << "> New node " << moves[i].str() << endl;
		MovesNode newNode(moves[i]);
		// Continue only if not found
		if (moves[i] != to)
		{
			visitedCells.push_back(moves[i]);
			AddLayersUpTo(moves[i], newNode, to);
		}
		else
			cout << "FOUND IT!" << endl;
		node.moves.push_back(newNode);
	}
	cout << "Exit from layer" << endl;
}

vector<Pos> GetKnightPath(Pos from, Pos to)
{
	MovesNode root;
	visitedCells.push_back(from);

	AddLayersUpTo(from, root, to);

	return vector<Pos>();
}


int _tmain(int argc, _TCHAR* argv[])
{
	size = 4;
	Pos from(0,0), to(3,3);
	cout << "Start for board " << size << "x" << size << " from " << from.str() << " to " << to.str() << endl;
	GetKnightPath(from, to);

	return 0;
}*/