Solves a Flow Free puzzle!

Free Flow Solver.cpp

#include <iostream>
#include <sstream>

#include <forward_list>
#include <list>
#include <vector>
#include <map>
#include <stack>
#include <queue>

#include <exception>
#include <future>

struct Coordinate {
	Coordinate() {};

	Coordinate(int x, int y) : x(x), y(y) {};

	bool IsNeighbour(const Coordinate &other) const {
		return abs(x - other.x) + abs(y - other.y) == 1;
	}

	bool operator==(const Coordinate &other) const {
		return x == other.x && y == other.y;
	}

	bool operator<(const Coordinate &other) const {
		return  ((x << 8) + y) < ((other.x << 8) + other.y);
	}

	bool operator!=(const Coordinate &other) const {
		return !(*this == other);
	}

	int x = 0, y = 0;
};

std::ostream& operator<<(std::ostream& os, const Coordinate& coordinate) {
	os << "(" << coordinate.x << ", " << coordinate.y << ")";
	return os;
}

std::istream& operator >> (std::istream &stream, Coordinate &coordinate) {
	stream.ignore(1); // Drop '('
	stream >> coordinate.x;
	stream.ignore(1); // Drop ','
	stream >> coordinate.y;
	stream.ignore(1); // Drop ')'
	return stream;
}

typedef std::pair<Coordinate, Coordinate> CoordinatePair;

struct Tile {
	const static int EMPTY = 0;

	// 0 for empty tiles, any other color for another tile.
	int color = 0;
};

class GameBoard {
public:
	GameBoard() {
		tiles_ = new Tile[0];
		emptyTileCount_ = 0;
	}

	GameBoard(const GameBoard &other) :
		width_(other.width_), height_(other.height_), tails_(other.tails_),
		emptyTileCount_(other.emptyTileCount_), expandHistory_(other.expandHistory_) {
		tiles_ = new Tile[width_ * height_];
		for (int i = 0; i < width_ * height_; i++) {
			tiles_[i] = other.tiles_[i];
		}
	}

	GameBoard(GameBoard &&other) :
		width_(other.width_), height_(other.height_), tails_(other.tails_),
		emptyTileCount_(other.emptyTileCount_), expandHistory_(other.expandHistory_) {
		tiles_ = other.tiles_;
		other.tiles_ = nullptr;
	}

	GameBoard(int width, int height) :
		width_(width), height_(height) {
		tiles_ = new Tile[width * height];
		emptyTileCount_ = width * height;
	}

	GameBoard& operator=(const GameBoard &other) {
		width_ = other.width_;
		height_ = other.height_;
		emptyTileCount_ = other.emptyTileCount_;
		tails_ = other.tails_;
		expandHistory_ = other.expandHistory_;

		delete[] tiles_;
		tiles_ = new Tile[width_ * height_];
		for (int i = 0; i < width_ * height_; i++) {
			tiles_[i] = other.tiles_[i];
		}

		return *this;
	}

	int GetWidth() const {
		return width_;
	}

	int GetHeight() const {
		return height_;
	}

	bool IsSolved() const {
		if (emptyTileCount_ != 0) return false;
		for (const CoordinatePair& tailPair : tails_) {
			if (!tailPair.first.IsNeighbour(tailPair.second)) {
				return false;
			}
		}
		return true;
	}

	bool IsSolved(int color) const {
		for (const CoordinatePair& tailPair : tails_) {
			if (GetTile(tailPair.first).color != color) continue;
			return tailPair.first.IsNeighbour(tailPair.second);
		}
		throw std::logic_error("Asking for status of non-existant color");
	}

	Tile GetTile(Coordinate position) const {
		return *GetTile_(position);
	}

	std::forward_list<Coordinate> GetNeighbours(Coordinate position) const {
		std::forward_list<Coordinate> toReturn;
		int x = position.x;
		int y = position.y;
		if (x > 0) toReturn.push_front(Coordinate(x - 1, y));
		if (x < width_ - 1) toReturn.push_front(Coordinate(x + 1, y));
		if (y > 0) toReturn.push_front(Coordinate(x, y - 1));
		if (y < height_ - 1) toReturn.push_front(Coordinate(x, y + 1));
		return toReturn;
	}

	std::forward_list<Coordinate> GetNeighbours(Coordinate position, bool preferX) const {
		std::forward_list<Coordinate> toReturn;
		if (preferX) {
			toReturn = GetNeighbours(position);
		} else {
			int x = position.x;
			int y = position.y;
			if (y > 0) toReturn.push_front(Coordinate(x, y - 1));
			if (y < height_ - 1) toReturn.push_front(Coordinate(x, y + 1));
			if (x > 0) toReturn.push_front(Coordinate(x - 1, y));
			if (x < width_ - 1) toReturn.push_front(Coordinate(x + 1, y));
		}
		return toReturn;
	}

	std::forward_list<Coordinate> GetTails() const {
		std::forward_list<Coordinate> tails;
		for (CoordinatePair tailPair : tails_) {
			tails.push_front(tailPair.first);
			tails.push_front(tailPair.second);
		}
		return tails;
	}

	// Moves a tail tile to a neighbour cell.
	// newTail must be a neighbour of tail.
	void ExpandTail(Coordinate tail, Coordinate newTail) {
		int tileColor = GetTile(tail).color;

		if (!tail.IsNeighbour(newTail)) {
			std::stringstream errorStream;
			errorStream << "Asked to expand " << tail << " to " << newTail << " but they aren't neighbours.";
			throw std::logic_error(errorStream.str());
		} else if (GetTile(newTail).color != Tile::EMPTY) {
			std::stringstream errorStream;
			errorStream << "Asked to expand " << tail << " to " << newTail << " but target cell is not empty.";
			throw std::logic_error(errorStream.str());
		} else {
			CoordinatePair& tailPair = tails_[tileColor - 1];
			if (tail != tailPair.first) {
				// Swap tails in tailpair
				Coordinate temp = tailPair.first;
				tailPair.first = tailPair.second;
				tailPair.second = temp;
				if (tail != tailPair.first) {
					std::stringstream errorStream;
					errorStream << "Asked to expand tail " << tail << " but that's not a tail.";
					throw std::logic_error(errorStream.str());
				}
			}
			tailPair.first = newTail;
			GetTile_(newTail)->color = tileColor;
			emptyTileCount_ -= 1;
			expandHistory_.push(CoordinatePair(tail, newTail));
		}
	}

	// Undoes the last ExpandTail call.
	void UndoLastExpandTail() {
		CoordinatePair lastMove = expandHistory_.top();
		Coordinate oldTail = lastMove.first;
		Coordinate newTail = lastMove.second;
		int tileColor = GetTile(newTail).color;

		CoordinatePair& tailPair = tails_[tileColor - 1];
		if (newTail != tailPair.first) {
			// Swap tails in tailpair, we know that tailPair.second == lastMove.second
			Coordinate temp = tailPair.first;
			tailPair.first = tailPair.second;
			tailPair.second = temp;
		}
		emptyTileCount_ += 1;
		tailPair.first = oldTail;  // Write oldTail back in the tailpair
		GetTile_(newTail)->color = Tile::EMPTY;  // Clear newTails grid cell.
		expandHistory_.pop();
	}

	std::string GetSolution() const {
		std::stringstream ss;
		std::vector<std::list<Coordinate>> routes(tails_.size());
		
		for (CoordinatePair tail : tails_) {
			int color = GetTile(tail.first).color;
			routes[color - 1].push_front(tail.second);
			routes[color - 1].push_back(tail.first);
		}

		std::stack<CoordinatePair> expandHistory = expandHistory_;  // Copy so we can pop() without screwing up our history.
		while (!expandHistory.empty()) {
			CoordinatePair move = expandHistory.top();
			Coordinate oldSpot = move.first;
			Coordinate newSpot = move.second;
			int color = GetTile(oldSpot).color;
			if (newSpot == routes[color - 1].front()) routes[color - 1].push_front(oldSpot);
			else routes[color - 1].push_back(oldSpot);
			expandHistory.pop();
		}
		for (const std::list<Coordinate> &route : routes) {
			for (const Coordinate &spot : route) {
				ss << spot << " ";
			}
			ss << "\n";
		}
		return ss.str();
	}

	friend std::ostream& operator<<(std::ostream& os, const GameBoard& board);
	friend std::istream& operator >> (std::istream& instream, GameBoard& board);

	~GameBoard() {
		delete[] tiles_;
	}
private:
	Tile* GetTile_(Coordinate position) const {
		return &tiles_[position.x + position.y * width_];
	}

	Tile* tiles_ = nullptr;
	int width_ = 0, height_ = 0;
	int emptyTileCount_ = 0;

	// A "tail" is the position of a colored square that can still be expanded from.
	// There should be exactly 2 tails per color, unless the color is filled,
	// in which case there should be 0.
	std::vector<CoordinatePair> tails_;

	// Stack of coordinate pairs.
	// Each represent a call of ExpandTail. 
	std::stack<CoordinatePair> expandHistory_;
};

std::ostream& operator<<(std::ostream& os, const GameBoard& board) {
	Coordinate point;
	os << "\n";
	for (point.y = 0; point.y < board.GetHeight(); ++point.y) {
		for (point.x = 0; point.x < board.GetWidth(); ++point.x) {
			char* lastChar = (point.x != board.width_ - 1) ? " " : "\n";
			int color = board.GetTile(point).color;
			os << color << lastChar;
		}
	}
	return os;
}

std::istream& operator >> (std::istream& instream, GameBoard& board) {
	int colors;
	instream >> colors >> board.width_ >> board.height_;
	delete[] board.tiles_;
	board.tiles_ = new Tile[board.width_ * board.height_];
	instream.ignore(1); // Skip '\n'

	Tile tile;
	board.tails_ = std::vector<CoordinatePair>(colors);
	for (int i = 0; i < colors; i++) {
		tile.color = i + 1;
		Coordinate first, second;
		instream >> first;
		instream.ignore(1); // Drop ' '
		instream >> second;
		instream.ignore(1); // Drop '\n'
		*board.GetTile_(first) = tile;
		*board.GetTile_(second) = tile;
		board.tails_[i] = CoordinatePair(first, second);
	}
	board.emptyTileCount_ = board.width_ * board.height_ - 2 * colors;
	return instream;
}

enum Status {
	NOTHING_DONE, BOARD_CHANGED, UNSOLVEABLE_BOARD
};

Status ForcedMovesPass(GameBoard& board) {
	Coordinate position;
	for (Coordinate position : board.GetTails()) {
		int emptyNeighbourCount = 0;
		Tile positionTile = board.GetTile(position);
		if (board.IsSolved(positionTile.color)) continue;

		Coordinate lastEmptyNeighbour;
		for (Coordinate neighbour : board.GetNeighbours(position)) {
			if (board.GetTile(neighbour).color == Tile::EMPTY) {
				emptyNeighbourCount += 1;
				lastEmptyNeighbour = neighbour;
			}
		}
		// If we have exactly enough space we know what to fill in.
		if (emptyNeighbourCount == 1) {
			board.ExpandTail(position, lastEmptyNeighbour);
			return BOARD_CHANGED;
		} else if (emptyNeighbourCount == 0) {
			return UNSOLVEABLE_BOARD;
		}
	}
	return NOTHING_DONE;
}

Status EmptySpotsPass(GameBoard& board) {
	Coordinate emptyPosition;
	for (emptyPosition.y = 0; emptyPosition.y < board.GetHeight(); ++emptyPosition.y) {
		for (emptyPosition.x = 0; emptyPosition.x < board.GetWidth(); ++emptyPosition.x) {
			if (board.GetTile(emptyPosition).color != Tile::EMPTY) continue;
			int emptyNeighbourCount = 0;
			Coordinate lastEmptyNeighbour;
			for (Coordinate neighbour : board.GetNeighbours(emptyPosition)) {
				if (board.GetTile(neighbour).color == Tile::EMPTY) {
					emptyNeighbourCount += 1;
					lastEmptyNeighbour = neighbour;
				}
			}
			if (emptyNeighbourCount >= 2) {
				continue;
			} else if (emptyNeighbourCount == 1) {
				int tailsFound = 0;
				Coordinate lastTail;
				for (Coordinate tail : board.GetTails()) {
					if (emptyPosition.IsNeighbour(tail)) {
						tailsFound += 1;
						lastTail = tail;
					}
				}
				if (tailsFound > 2) continue;
				else if (tailsFound == 1) {
					board.ExpandTail(lastTail, emptyPosition);
					board.ExpandTail(emptyPosition, lastEmptyNeighbour);
					return BOARD_CHANGED;
				} else if (tailsFound == 0) {
					return UNSOLVEABLE_BOARD;
				}
			} else if (emptyNeighbourCount == 0) {
				std::vector<Coordinate> tailNeighbours;
				for (Coordinate tail : board.GetTails()) {
					if (emptyPosition.IsNeighbour(tail)) {
						tailNeighbours.push_back(tail);
					}
				}
				if (tailNeighbours.size() < 2) {
					return UNSOLVEABLE_BOARD;
				}
				Coordinate toExpandIfOnlyPair;
				int pairsFound = 0;
				for (Coordinate first : tailNeighbours) {
					for (Coordinate second : tailNeighbours) {
						if (first != second && board.GetTile(first).color == board.GetTile(second).color) {
							toExpandIfOnlyPair = first;
							pairsFound += 1;
						}
					}
				}
				pairsFound /= 2; // We find all pairs twice.
				if (pairsFound == 0) {
					return UNSOLVEABLE_BOARD;
				} else if (pairsFound == 1) {
					board.ExpandTail(toExpandIfOnlyPair, emptyPosition);
					return BOARD_CHANGED;
				}
			}
		}
	}
	return NOTHING_DONE;
}

// Iterator object used for listing all possible boards where
// tail is connect to it's same-colored tail.
class PossibleRoutesIterator {
public:
	struct SearchState {
		Coordinate tail;
		std::forward_list<Coordinate> neighbours;
		std::forward_list<Coordinate>::iterator neighbourIterator;
		bool checkedCurrent;
	};

	PossibleRoutesIterator(GameBoard board, const Coordinate& tail) : board_(board) {
		states_.push(SearchState());
		SearchState& initial = states_.top();
		initial.tail = tail;
		initial.neighbours = board_.GetNeighbours(tail);
		initial.neighbourIterator = initial.neighbours.begin();
		initial.checkedCurrent = false;
	}

	bool Next() {
		while (!states_.empty()) {
			SearchState& state = states_.top();
			if (!state.checkedCurrent) {
				state.checkedCurrent = true;
				int color = board_.GetTile(state.tail).color;
				if (board_.IsSolved(color)) {
					return true;
				}
			} else if (state.neighbourIterator != state.neighbours.end()) {
				Coordinate neighbour = *state.neighbourIterator;
				if (board_.GetTile(neighbour).color == Tile::EMPTY) {
					board_.ExpandTail(state.tail, neighbour);
					states_.push(SearchState());
					SearchState& nextState = states_.top();
					nextState.tail = neighbour;
					nextState.neighbours = board_.GetNeighbours(nextState.tail, state.tail.x == neighbour.x);
					nextState.neighbourIterator = nextState.neighbours.begin();
					nextState.checkedCurrent = false;
				}
				++state.neighbourIterator;
			} else {
				board_.UndoLastExpandTail();
				states_.pop();
			}
		}
		return false;
	}

	GameBoard& Current() {
		return board_;
	}
private:
	GameBoard board_;
	std::stack<SearchState> states_;
};

class BoardSolver {
public:
	int Solve(GameBoard &board, int threadCount) {
		if (ExpandByDeduction(board) == UNSOLVEABLE_BOARD) return UNSOLVEABLE_BOARD;
		if (board.IsSolved()) return BOARD_CHANGED;


		// Get first unsolved tail
		Coordinate tail = board.GetTails().front();
		for (Coordinate tail : board.GetTails()) {
			if (board.IsSolved(board.GetTile(tail).color)) continue;
		}

		PossibleRoutesIterator routit(board, tail);
		for (int i = 0; i < threadCount; i++) {
			if (!routit.Next()) {
				threadCount = i;
				threads.resize(threadCount);
				break;
			}
			threads.push_back(std::thread(SolveBranchingInThread, this, routit.Current(), i));
		}

		bool foundSolution = false;

		// Keep starting new threads until we don't have any more paths or found a solution.
		while (routit.Next() && !foundSolution) {
			std::unique_lock<std::mutex> lock(finishedThreadsResultsmtx);

			if (finishedThreadsResults.empty()) {
				finishedThreadsCV.wait(lock, [&] {return !finishedThreadsResults.empty(); });
			}

			ThreadResult result = finishedThreadsResults.front();
			finishedThreadsResults.pop();
			foundSolution = result.status != UNSOLVEABLE_BOARD;
			if (!foundSolution) {
				threads[result.threadId].join();
				threads[result.threadId] = std::thread(SolveBranchingInThread, this, routit.Current(), result.threadId);
			} else {
				board = result.board;
			}
		}

		// Wait for all running thread to finish and check if they found a solution if we don't have one yet.
		for (std::thread &t : threads) t.join();
		std::unique_lock<std::mutex> lock(finishedThreadsResultsmtx);
		while (!finishedThreadsResults.empty() && !foundSolution) {
			ThreadResult result = finishedThreadsResults.front();
			foundSolution = result.status != UNSOLVEABLE_BOARD;
			if (foundSolution) {
				board = result.board;
			}
		}
	};

private:
	struct ThreadResult {
		int threadId;
		Status status;
		GameBoard board;
		clock_t duration;
	};

	std::vector<std::thread> threads;
	std::mutex finishedThreadsResultsmtx;
	std::condition_variable finishedThreadsCV;
	std::queue<ThreadResult> finishedThreadsResults;

	Status SolveBranching(GameBoard &board) {
		if (ExpandByDeduction(board) == UNSOLVEABLE_BOARD) return UNSOLVEABLE_BOARD;
		if (board.IsSolved()) return BOARD_CHANGED;

		// Get first unsolved tail
		Coordinate tail = board.GetTails().front();
		for (Coordinate t : board.GetTails()) {
			if (board.IsSolved(board.GetTile(t).color)) continue;
			tail = t;
		}

		PossibleRoutesIterator routit(board, tail);
		while (routit.Next()) {
			GameBoard newBoard(routit.Current());
			Status result = SolveBranching(newBoard);
			if (result == UNSOLVEABLE_BOARD) continue;
			board = newBoard;
			return result;
		};
		return UNSOLVEABLE_BOARD;
	};

	static void SolveBranchingInThread(BoardSolver* solver, GameBoard board, int id) {
		ThreadResult result;
		result.threadId = id;
		result.status = solver->SolveBranching(board);
		if (result.status != UNSOLVEABLE_BOARD) result.board = board;
		std::lock_guard<std::mutex> lock(solver->finishedThreadsResultsmtx);
		solver->finishedThreadsResults.push(result);
		solver->finishedThreadsCV.notify_one();
	}

	Status ExpandByDeduction(GameBoard &board) {
		bool boardChanged = false;
		while (true) {
			int result = ForcedMovesPass(board);
			if (result == UNSOLVEABLE_BOARD) return UNSOLVEABLE_BOARD;
			else if (result == BOARD_CHANGED) {
				boardChanged = true;
				continue;
			}
			result = EmptySpotsPass(board);
			if (result == UNSOLVEABLE_BOARD) return UNSOLVEABLE_BOARD;
			else if (result == BOARD_CHANGED) {
				boardChanged = true;
				continue;
			}
			else break;
		}
		return boardChanged ? BOARD_CHANGED : NOTHING_DONE;
	}
};

int main() {
	GameBoard board;
	std::cin >> board;
	BoardSolver solver;
	solver.Solve(board, 8);
	std::cout << board.GetSolution();
	return 0;
}