Another Casual Coder

Problem is here: https://leetcode.com/problems/sliding-puzzle/description/

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.

Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

Input: board = [[3,2,4],[1,5,0]]
Output: 14

The good thing about this problem is the small input: we're dealing with a matrix with 6 cells only. Since we're looking for the least number of moves to go from one state (beginning state) to another state (the end state), one approach should be coming to mind: breadth-first-search, or BFS.
To implement a BFS here we'll need few tools:

A) A class that will encapsulate the elements to be enqueued. This class will have the config, position of the empty cell, and number of steps to get to this state
B) A Hashtable to keep track of the visited states
C) A key to be used in the Hashtable. In this case we'll flatten the 3x2 board into one dimension
D) A function to check whether we've arrived at the end state
E) A function to attempt to move from one state to another

All that together, and you have yourself a solution. Cheers, Marcelo.

public class Solution
{
public int SlidingPuzzle(int[,] board)
{
int[] config = new int[6];
int zeroIndex = 0;

int index = 0;
for (int c = 0; c < board.GetLength(0); c++)
{
for (int r = 0; r < board.GetLength(1); r++)
{
config[index] = board[c, r];
if (board[c, r] == 0) zeroIndex = index;
index++;
}
}

int retVal = 0;

Puzzle puzzle = new Puzzle(config, zeroIndex, 0);
string key = Key(puzzle);

Hashtable configSeen = new Hashtable();
configSeen.Add(key, true);
Queue queue = new Queue();
queue.Enqueue(puzzle);
bool found = false;

while (queue.Count > 0)
{
Puzzle p = (Puzzle)queue.Dequeue();

if (IsFinalConfig(p))
{
found = true;
retVal = p.steps;
break;
}

switch (p.zeroPosition)
{
case 0:
AttemptEnqueue(p, 0, 1, configSeen, queue);
AttemptEnqueue(p, 0, 3, configSeen, queue);
break;
case 1:
AttemptEnqueue(p, 1, 0, configSeen, queue);
AttemptEnqueue(p, 1, 2, configSeen, queue);
AttemptEnqueue(p, 1, 4, configSeen, queue);
break;
case 2:
AttemptEnqueue(p, 2, 1, configSeen, queue);
AttemptEnqueue(p, 2, 5, configSeen, queue);
break;
case 3:
AttemptEnqueue(p, 3, 0, configSeen, queue);
AttemptEnqueue(p, 3, 4, configSeen, queue);
break;
case 4:
AttemptEnqueue(p, 4, 3, configSeen, queue);
AttemptEnqueue(p, 4, 5, configSeen, queue);
AttemptEnqueue(p, 4, 1, configSeen, queue);
break;
case 5:
AttemptEnqueue(p, 5, 4, configSeen, queue);
AttemptEnqueue(p, 5, 2, configSeen, queue);
break;
}
}

return found ? retVal : -1;
}

private void AttemptEnqueue(Puzzle p, int i, int j, Hashtable configSeen, Queue queue)
{
Swap(p, i, j);
string key = Key(p);
if (!configSeen.ContainsKey(key))
{
configSeen.Add(key, true);
Puzzle np = new Puzzle(p.config, j, p.steps + 1);
queue.Enqueue(np);
}
Swap(p, j, i);
}

private void Swap(Puzzle p, int i, int j)
{
int temp = p.config[i];
p.config[i] = p.config[j];
p.config[j] = temp;
}

private string Key(Puzzle p)
{
string key = "";
for (int i = 0; i < p.config.Length; i++)
{
key += p.config[i].ToString();
}
return key;
}

private bool IsFinalConfig(Puzzle puzzle)
{
for (int i = 0; i < puzzle.config.Length - 1; i++)
{
if (puzzle.config[i] != i + 1) return false;
}
return puzzle.config[puzzle.config.Length - 1] == 0;
}
}

public class Puzzle
{
public int[] config = null;
public int zeroPosition = 0;
public int steps = 0;

public Puzzle(int[] config, int zeroPosition, int steps)
{
this.config = (int[])config.Clone();
this.zeroPosition = zeroPosition;
this.steps = steps;
}
}