A Yashi game scenario is defined on a n by n grid, where n is an integer greater than or equal to 2. The grid must have a minimum of two nodes on it. The goal consists of connecting all the nodes, and ending up with a planar spanning tree where each line cannot be a diagonal one.
More specifically, the game is defined with these constraints:
(1) Diagonals lines not permitted (no overlap);
(2) All points must be connected;
(3) Lines should not cross each other;
(4) The total number of lines used must be exactly n-1, where n represent the total number of points;
(5) The structure must not form any cycles.
There is three versions of the game:
Version 1: Determine whether there is a valid solution.
Version 2: If a solution is possible, calculate the total number of solutions.
Version 3: If a solution exists, identify the one with the least cost.
The notebook provided contains the complete implementation of the game to solve the three versions.