# Graph puzzle resolver

The image below shows the puzzle in the solved state. The puzzle consists of 10 cells. Among the cells one is empty, the rest are numbered from 1 to 9. An empty cell is used for permutations of numbers along the allowed paths shown as lines connecting the cells. Puzzle is considered solved if all cells are ordered as shown in the image. Create console program in C# that partially or completely resolves puzzle on the specified figure. The program interface of implementation should be written in the form of:

public interface IResolver
{
int[] Solve(int[] input);
}


where the input cell array int[] input are written left-to-right and top-to-bottom, blank cell indicates number 0. (the initial state can be written as [1,2,3,0,4,5,6,7,8,9].) The output array must contain a sequence of moves – the numbers from 1 to 9, which must be moved at the next step in free cell.

## Example

Let the input value of the method Solve (int[] input) be input [1,2,3,4,6,5,0,7,8,9], then the optimal solution of the problem will consist of two steps, in the figure below: At the first step 6 ↔ 0 are exchanged, 6 is written to the output array. In the second step, 4 ↔ 0 are exchanged, while in the output the array 4 is written. The result of the program will be [6,4].

## Solution

Resolver.cs

public class Resolver
{
// Available indexes for move
(
new Dictionary<int, int[]>
{
 = new[] { 1, 2 },
 = new[] { 0, 4 },
 = new[] { 0, 3, 5 },
 = new[] { 2, 4 },
 = new[] { 1, 3, 6 },
 = new[] { 2, 7 },
 = new[] { 4, 8 },
 = new[] { 5, 8, 9 },
 = new[] { 6, 7, 9 },
 = new[] { 7, 8 }
}
);

private static bool IsSolved(IList<int> input) => input.SequenceEqual(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9 });

private static void ValidateInput(IList<int> input)
{
if (input == null)
throw new ArgumentNullException(nameof(input));

// Input must consist only from numbers from 0 to 9
if (!input.OrderBy(x => x).SequenceEqual(Enumerable.Range(0, 10)))
throw new ArgumentException("Invalid input.", nameof(input));
}

private IEnumerable<int[]> _indexMovesCollection;

public Resolver(IList<int> input)
{
ValidateInput(input);

}

private int GetZeroIndex() => _input.IndexOf(0);

public int[] Solve()
{
// Minimum number of moves based on distance from empty cell to target cell
Dictionary<int, int> minimumNumberOfMovesDictionary = new Dictionary<int, int>
{
 = 2,
 = 2,
 = 1,
 = 0,
 = 1,
 = 2,
 = 2,
 = 3,
 = 3,
 = 4
};

int minimumNumberOfMoves = minimumNumberOfMovesDictionary[GetZeroIndex()];

if (minimumNumberOfMoves == 0 && IsSolved(_input)) return new int;

const int maximumNumberOfMoves = 100;

int zeroIndex = GetZeroIndex();

// Get all move combinations
_indexMovesCollection = AvailableMoveIndexes[zeroIndex].Select(index => new[] { index });

for (int moveCount = 1; moveCount < maximumNumberOfMoves; moveCount++)
{
if (moveCount >= minimumNumberOfMoves)
{
foreach (int[] indexMoves in _indexMovesCollection)
{
if (TrySolution(indexMoves, out int[] moveHistory))
return moveHistory;
}
}

_indexMovesCollection = _indexMovesCollection
.SelectMany(indexMoves =>
AvailableMoveIndexes[indexMoves.Last()]
// Remove combinations where subsequent move can undo previous move
.Except(new[] { indexMoves.Length < 2 ? zeroIndex : indexMoves[indexMoves.Length - 2] })
.Select(indexMove => indexMoves.Append(indexMove).ToArray()))
.ToArray();
}

// Too many moves
throw new Exception("Unsolvable puzzle.");
}

private bool TrySolution(int[] indexMoves, out int[] moveHistory)
{
int[] transformedPuzzle = _input.ToArray();
List<int> moveHistoryList = new List<int>(indexMoves.Length);

foreach (int indexMove in indexMoves)
{
int move = transformedPuzzle[indexMove];

// swap cell values to simulate move
transformedPuzzle[Array.IndexOf(transformedPuzzle, 0)] = move;
transformedPuzzle[indexMove] = 0;

}

moveHistory = moveHistoryList.ToArray();

return IsSolved(transformedPuzzle);
}
}


ResolverImplementation.cs

public class ResolverImplementation : IResolver
{
public int[] Solve(int[] input) => new Resolver(input).Solve();
}


## Unit tests

I've added NUnit tests to ensure my solution works.

public class ResolverTests
{
[Test]
public void ShouldThrowArgumentNullException_WhenNullPassed()
{
// Arrange

// Act

// Assert
Assert.Throws<ArgumentNullException>(() => new Resolver(null));
}

[Test]
public void ShouldThrowArgumentException_WhenWrongInputPassed()
{
// Arrange

// Act

// Assert
Assert.Throws<ArgumentException>(() => new Resolver(new[] { -1, 2, 3, 0, 4, 5, 6, 7, 8, 9 }), "Invalid input.");
}

[Test]
public void ShouldThrowArgumentException_WhenDuplicateElementsPassed()
{
// Arrange

// Act

// Assert
Assert.Throws<ArgumentException>(() => new Resolver(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 1 }), "Invalid input.");
}

[Test]
public void ShouldReturnEmptyArray_WhenSolvedPuzzlePassed()
{
// Arrange
Resolver resolver = new Resolver(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9 });

// Act
int[] solution = resolver.Solve();

// Assert
Assert.AreEqual(solution, new int);
}

[Test]
public void ShouldReturnSolution_WhenSimplestSolutionPassed()
{
// Arrange
Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 });

// Act
int[] solution = resolver.Solve();

// Assert
Assert.AreEqual(solution, new[] { 4 });
}

[Test]
public void ShouldReturnSolution_WhenSimpleSolutionPassed()
{
// Arrange
Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 6, 5, 0, 7, 8, 9 });

// Act
int[] solution = resolver.Solve();

// Assert
Assert.AreEqual(solution, new[] { 6, 4 });
}

[Test]
public void ShouldReturnSolution_WhenAverageSolutionPassed()
{
// Arrange
Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 6, 5, 8, 9, 7, 0 });

// Act
int[] solution = resolver.Solve();

// Assert
Assert.AreEqual(solution, new[] { 9, 7, 8, 6, 4 });
}

[Test]
public void ShouldReturnSolution_WhenHardSolutionPassed()
{
// Arrange
Resolver resolver = new Resolver(new[] { 8, 7, 9, 6, 5, 4, 1, 2, 0, 3 });

// Act
int[] solution = resolver.Solve();

// Assert
Assert.AreEqual(solution, new[] { 2, 4, 9, 6, 5, 1, 2, 3, 4, 9, 6, 8, 7, 1, 2, 3, 4, 9, 6, 8, 7, 1, 2, 3, 4, 6, 8, 7, 5, 3, 4, 6, 8, 7, 5, 3 });
}
}


## Notes

I'm using Append and Prepend LINQ methods in solution which are available in .NET Core, .NET Standard 1.6+, .NET Framework 4.7.1+. If you don't have specified versions of .NET you can add them manually like own extenstion methods like this.

public static class EnumerableExtensions
{
public static IEnumerable<TSource> Append<TSource>(this IEnumerable<TSource> source, TSource element) => source.Concat(new[] { element });

public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource element) => new[] { element }.Concat(source);
}


## Testing

For generating puzzle sequences and testing solutions I've added separate WPF application with single window where click on allowed cells near empty one swaps them.

MainWindow.xaml

<Window x:Class="Puzzle9.Game.MainWindow"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
mc:Ignorable="d"
Title="MainWindow" Height="450" Width="800">
<Viewbox>
<Canvas Width="150" Height="160">
<Canvas.Resources>
<Style TargetType="Button">
<Setter Property="Foreground" Value="#5680a7" />
<Setter Property="HorizontalContentAlignment" Value="Center" />
<Setter Property="VerticalContentAlignment" Value="Center" />
<Setter Property="Template">
<Setter.Value>
<ControlTemplate TargetType="{x:Type Button}">
<Border x:Name="border" Width="20" Height="20" BorderThickness="1" BorderBrush="#5680a7" Background="{TemplateBinding Background}" SnapsToDevicePixels="true" CornerRadius="10">
<ContentPresenter x:Name="contentPresenter" Focusable="False" HorizontalAlignment="{TemplateBinding HorizontalContentAlignment}" Margin="{TemplateBinding Padding}" RecognizesAccessKey="True" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" VerticalAlignment="{TemplateBinding VerticalContentAlignment}"/>
</Border>
</ControlTemplate>
</Setter.Value>
</Setter>
</Style>

<Style TargetType="Line">
<Setter Property="Stroke" Value="#5680a7" />
<Setter Property="StrokeThickness" Value="1" />
<Setter Property="Panel.ZIndex" Value="-1" />
</Style>
</Canvas.Resources>
<Button Name="Button0" Canvas.Left="45" Canvas.Top="10" Click="Button_Click">1</Button>
<Button Name="Button1" Canvas.Left="95" Canvas.Top="10" Click="Button_Click">2</Button>
<Button Name="Button2" Canvas.Left="20" Canvas.Top="40" Click="Button_Click">3</Button>
<Button Name="Button3" Canvas.Left="70" Canvas.Top="40" Click="Button_Click"></Button>
<Button Name="Button4" Canvas.Left="120" Canvas.Top="40" Click="Button_Click">4</Button>
<Button Name="Button5" Canvas.Left="20" Canvas.Top="70" Click="Button_Click">5</Button>
<Button Name="Button6" Canvas.Left="120" Canvas.Top="70" Click="Button_Click">6</Button>
<Button Name="Button7" Canvas.Left="45" Canvas.Top="100" Click="Button_Click">7</Button>
<Button Name="Button8" Canvas.Left="95" Canvas.Top="100" Click="Button_Click">8</Button>
<Button Name="Button9" Canvas.Left="70" Canvas.Top="130" Click="Button_Click">9</Button>
<Line X1="55" Y1="20" X2="105" Y2="20" />
<Line X1="55" Y1="20" X2="30" Y2="50" />
<Line X1="105" Y1="20" X2="130" Y2="50"/>
<Line X1="30" Y1="50" X2="130" Y2="50" />
<Line X1="30" Y1="50" X2="30" Y2="80" />
<Line X1="130" Y1="50" X2="130" Y2="80" />
<Line X1="30" Y1="80" X2="55" Y2="110" />
<Line X1="130" Y1="80" X2="105" Y2="110" />
<Line X1="55" Y1="110" X2="80" Y2="140" />
<Line X1="55" Y1="110" X2="105" Y2="110" />
<Line X1="105" Y1="110" X2="80" Y2="140" />
</Canvas>
</Viewbox>
</Window>


MainWindow.xaml.cs

using System.Linq;
using System.Windows;
using System.Windows.Controls;
using Puzzle9.Core;

namespace Puzzle9.Game
{
public partial class MainWindow : Window
{
public MainWindow() => InitializeComponent();

private void Button_Click(object sender, RoutedEventArgs e)
{
Button button = sender as Button;
Canvas parent = button.Parent as Canvas;

int currentIndex = parent.Children.IndexOf(button);

Button zeroButton = parent.Children.OfType<Button>().First(b => b.Content == null);
int zeroIndex = parent.Children.IndexOf(zeroButton);

if (Resolver.AvailableMoveIndexes[zeroIndex].Contains(currentIndex))
{
zeroButton.Content = button.Content;
button.Content = null;
}
}
}
}

• For the output array to record what happened, don't you need to add two numbers to the output array at each step? – George Barwood Feb 17 '19 at 7:46
• @GeorgeBarwood No, swapping cells will always be with empty cell (shown with zero), so only one number per step will be enough. – Vadim Ovchinnikov Feb 17 '19 at 8:10
• I get it. One thing I would question is the use of "Collection" in names, e.g. GetIndexMovesCollection. IMO that is an awkward name. – George Barwood Feb 17 '19 at 11:33
• This is a silly job-interview question. I would refuse solvig it for being pointless. – t3chb0t Feb 17 '19 at 17:49
• @t3chb0t Maybe it can show how I can practically create algorithms, how maintainable and readable my code is and so on. – Vadim Ovchinnikov Feb 17 '19 at 17:58

    public static ReadOnlyDictionary<int, int[]> AvailableMoveIndexes => new ReadOnlyDictionary<int, int[]>
(
new Dictionary<int, int[]>
{
 = new[] { 1, 2 },
...


Nice clean representation, but why public? I would expect private or (perhaps better) internal with an InternalsVisibleTo attribute to allow a unit test to validate that the possible moves are bidirectional (i.e. AvailableMoveIndexes[i].Contains(j) if and only if AvailableMoveIndexes[j].Contains(i)).

    private readonly ReadOnlyCollection<int> _input;


Why the name? I don't tend to think of objects as having input: programs and processes have input.

Also, would IReadOnlyList<int> be a better type to use? It makes it explicit that the order is relevant.

        Dictionary<int, int> minimumNumberOfMovesDictionary = new Dictionary<int, int>
{
 = 2,
...


For a dense lookup like this, IMO an int[] makes more sense.

        if (minimumNumberOfMoves == 0 && IsSolved(_input)) return new int;


Is minimumNumberOfMoves != 0 && IsSolved(_input) possible?

Answer: no, so this could be simplified to if (IsSolved(_input)) return new int;

        const int maximumNumberOfMoves = 100;


Where does this number come from? Do you have a mathematical proof that it's exactly the maximum number required? Do you have a mathematical proof that the it's a valid upper bound? Or is it just a conservative guess?

The answer to that question should be in a comment in the code.

Here follow rhetorical questions, and to distinguish my answers / comments from the questions themselves I'm using spoiler blocks. These are the questions I would ask in an interview. I'd probably ask similar questions in a non-interview code review as well, if the person who wrote the code was a junior programmer, but I might give more hints up front in that case.

        for (int moveCount = 1; moveCount < maximumNumberOfMoves; moveCount++)
{
...
}


Since this is an interview question, you can expect to be asked what type of search you're doing. I would put a comment above the loop to answer that question.

If I asked you why you chose that type of search, do you have an answer? If it was because you didn't have time to implement a better one, what would you have liked to implement?

Your response in comments was "Loop is used for solving puzzle from minimum to maximum moves." The response I was hoping for was "Breadth-first search". I personally would have chosen to implement Dijkstra's algorithm or A*. It seems likely that one of the main reasons for setting this particular task is to see (a) whether you know standard algorithms; (b) whether you recognise when they're applicable.

                        // Remove combinations where subsequent move can undo previous move
.Except(new[] { indexMoves.Length < 2 ? zeroIndex : indexMoves[indexMoves.Length - 2] })


That gives a bit of optimisation by detecting and skipping loops of length 2, but loops of length 3 around positions 7,8,9 are still possible. How would you detect and skip loops of any length?

The straightforward way of doing that is to use a representation which supports hashcode and equality testing, and then to use a HashMap<> to track the positions which you've already seen.

The memory usage is quite high. How could you change your data structure to minimise memory usage?

The reason that the memory usage is quite high is the copying of arrays to add an element to the end. You could instead use a linked list where each node points backwards instead of forwards; it would be necessary to reverse the list for output, but each element of _indexMovesCollection would require just one int (or even byte) for the last element and one reference to the previous element.

• 1) AvailableMoveIndexes is public because it is used in WPF application for manual puzzle generation and manual solving. 2) I don't understand why IReadOnlyList<int> would be better for private field _input. 3) minimumNumberOfMoves != 0 && IsSolved(_input) is not possible because 0 should reside only in index #3. 4) 100 is my guess, I don't have a clue how to calculate maximum number of moves or understand that puzzle is unsolvable. 5) Loop is used for solving puzzle from minimum to maximum moves. I don't have better idea to implement. 6) No idea about reducing memory usage. – Vadim Ovchinnikov Feb 18 '19 at 10:38
• 1) Good answer. 2) Because it makes it clear that the order matters. ReadOnlyCollection is not inherently ordered. – Peter Taylor Feb 18 '19 at 11:15