using System;
using System.IO;

namespace BoxAndSquare {

	class Program {

		enum RestrictedState {
			Top = 1, Bottom, Left, Right, Head
		}

		enum Direction {
			Top = 1, Bottom, Left, Right
		}

		struct BoxPosition {
			public int x;
			public int y;
		}

		const int SquareMaxIndex = 9;
		const int MaxStepCount = (SquareMaxIndex + 1) * (SquareMaxIndex + 1);

		static RestrictedState boxState;
		static BoxPosition boxPosition;
		static bool[,] square;
		static BoxPosition targetPosition;
		static int stepCount;

		static TextWriter writer;

		static void Solve() {
			boxState = RestrictedState.Head;
			boxPosition.x = 0;
			boxPosition.y = 0;
			square = new bool[SquareMaxIndex + 1, SquareMaxIndex + 1];
			square[boxPosition.x, boxPosition.y] = true;
			stepCount = 1;
			targetPosition.x = 0;
			targetPosition.y = SquareMaxIndex;
			if (NextMove()) {
				writer.WriteLine("Solution found");
			} else {
				writer.WriteLine("No solution");
			}
		}


		static bool NextMove() {
			for (int i = 1; i < 5; ++i) {
				if (Move((Direction)i))
					return true;
			}
			return false;
		}

		static bool Move(Direction moveDirection) {
			if ((int)moveDirection != (int)boxState) {
				bool doRecursion = false;
				RestrictedState oldState = boxState;
				BoxPosition oldPosition = boxPosition;
				int oldStepCount = stepCount;
				switch (moveDirection) {
					case Direction.Top:
						if (boxPosition.y > 0 && !square[boxPosition.x, boxPosition.y - 1]) {
							// перемещаем кубик

							// 1) приращиваем координату
							boxPosition.y -= 1;
							// 2) меняем состояние
							switch (boxState) {
								case RestrictedState.Bottom:
									boxState = RestrictedState.Head;
									break;
								case RestrictedState.Head:
									boxState = RestrictedState.Top;
									break;
							}
							// 3) метим клетку
							square[boxPosition.x, boxPosition.y] = true;

							// 4) увеличиваем число шагов
							++stepCount;
						

							doRecursion = true;
						}
						break;
					case Direction.Bottom:
						if (boxPosition.y < SquareMaxIndex && !square[boxPosition.x, boxPosition.y + 1]) {
							// перемещаем кубик

							// 1) приращиваем координату
							boxPosition.y += 1;
							// 2) меняем состояние
							switch (boxState) {
								case RestrictedState.Top:
									boxState = RestrictedState.Head;
									break;
								case RestrictedState.Head:
									boxState = RestrictedState.Bottom;
									break;
							}
							// 3) метим клетку
							square[boxPosition.x, boxPosition.y] = true;

							// 4) увеличиваем число шагов
							++stepCount;


							doRecursion = true;
						}
						break;
					case Direction.Left:
						if (boxPosition.x > 0 && !square[boxPosition.x - 1, boxPosition.y]) {
							// перемещаем кубик

							// 1) приращиваем координату
							boxPosition.x -= 1;
							// 2) меняем состояние
							switch (boxState) {
								case RestrictedState.Right:
									boxState = RestrictedState.Head;
									break;
								case RestrictedState.Head:
									boxState = RestrictedState.Left;
									break;
							}
							// 3) метим клетку
							square[boxPosition.x, boxPosition.y] = true;

							// 4) увеличиваем число шагов
							++stepCount;


							doRecursion = true;
						}
						break;
					case Direction.Right:
						if (boxPosition.x < SquareMaxIndex && !square[boxPosition.x + 1, boxPosition.y]) {
							// перемещаем кубик

							// 1) приращиваем координату
							boxPosition.x += 1;
							// 2) меняем состояние
							switch (boxState) {
								case RestrictedState.Left:
									boxState = RestrictedState.Head;
									break;
								case RestrictedState.Head:
									boxState = RestrictedState.Right;
									break;
							}
							// 3) метим клетку
							square[boxPosition.x, boxPosition.y] = true;

							// 4) увеличиваем число шагов
							++stepCount;


							doRecursion = true;							
						}
						break;
				}
				if (doRecursion) {
					// проверяем завершение задачи или
					// делаем следующий ход

					bool taskCompleted = (boxPosition.x == targetPosition.x
						&& boxPosition.y == targetPosition.y);
					
					if ( (taskCompleted && stepCount == MaxStepCount)
						 || (!taskCompleted && NextMove()) ) {
						writer.WriteLine(moveDirection.ToString());  
						return true;
					}
					/*	этот критерий позволяет гонять кубик до заданной клетки
					if (taskCompleted || NextMove()) {
						Console.WriteLine(moveDirection.ToString());
						return true;
					}
					 */

					// выполняем откат
					square[boxPosition.x, boxPosition.y] = false;
					boxPosition = oldPosition;
					boxState = oldState;
					stepCount = oldStepCount;
				}
			}
			return false;
		}

		static void Main(string[] args) {
			using (FileStream stream = new FileStream("sol.txt", FileMode.OpenOrCreate)) 
			using(writer = new StreamWriter(stream)){				
				DateTime startTime = DateTime.Now;
				writer.WriteLine("operation started at " + startTime.ToString());				
				Solve();
				DateTime endTime = DateTime.Now;
				writer.WriteLine("operation completed at " + endTime.ToString());				
				TimeSpan timeUsed = endTime - startTime;
				writer.WriteLine("time taken " + timeUsed.ToString());
				writer.Flush();
			}
		}
	}
}