Write a java program to solve the Hex Nut puzzle via backtracking.

The Hex Nut puzzle is a group of seven hexagonal pieces having their edges numbered with various combinations of the numbers 1 through 6. The goal of the puzzle is to arrange six of nuts around the seventh nut in such an arrangement that the numbers printed on the touching sides of adjacent nuts are the same.

You will read puzzle data from standard input. The first line of input will tell how many puzzles will be given. There will then be that number of sets of nuts listed one nut per line. Each nuts edge labels are listed in a clockwise order. A blank line will separate each set of seven nuts.

Examine each set of nuts and determine if there can be any valid arrangement of those nuts so that their labels compose a valid solution to the puzzle. If there is, then print Solution Found. otherwise print No Solution. instead. Print the output of one set of nuts per line.

Sample Input:

2 1 6 4 5 2 3 6 2 4 5 3 1 4 1 2 3 6 5 5 1 2 4 6 3 6 3 2 5 1 4 6 4 3 2 5 1 3 6 5 4 1 2 1 2 3 4 5 6 1 4 3 6 5 2 1 4 6 2 3 5 1 6 2 4 5 3 1 6 4 2 5 3 1 6 5 3 2 4 1 6 5 4 3 2 

Sample Output:

No Solution. Solution Found.

java programming language hex nut puzzle . backtracking

Please, could you provide the full java code for this problem. Thank you!!