Sliding Puzzle: a hard LeetCode problem

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

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

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;
}
}