Creation of matrix with specific attempts at the end

Question

What I want to do is build a Slay-the-Spire-like Map. As you can see in the following image, the map is splitted in ISteps and IRooms. Each IStep is connected to the next one by its IRooms. There is no dead-end, so each IRooms is connected with the previous and next ISteps.

Firstly, I have these two C# interfaces:

public interface IStep
{
    IRoom this[int index] { get; }
    int Size { get; }
    void Connect(IStep nextStep, int[,] matrix);
}

public interface IRoom
{
    IRoom[] NextRooms { get; }
    void Connect(IRoom nextRoom);
}

Here is what I want to achieve:

• A IStep has a set of 3-to-5 IRooms.
• I can connect two ISteps together, which connects the IRooms.
• Each IRoom has at least one connection to the other IStep ...
• ... and at most three
• Connections cannot cross, but can begin from / end to the same IRoom

Here is what is true:

• The minimum number of connections is equal to the larger IStep.Size
• The maximum number is equal to both IStep.Size minus 1
• Each row and each column has to contains at least one 1

I decided to represent these connections in a matrix-like display:
\begin{bmatrix} 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} This matrix says:

• IStep from is connected to IStep to
• from.Size = 3 and to.Size = 5
• There is a total of 6 connections
• from[0] is connected to to[0]
• from[0] is also connected to to[1]
• ...
• from[2] is connected to to[4]

---

To create this matrix, I use the following F# module:

type CellType =
| Uncertain
| Disconnected
| Connected

module Connector2D =

    let getAt array row col = Array2D.get array row col
    let setAt array row col value = Array2D.set array row col value

    let len1 array = Array2D.length1 array
    let len2 array = Array2D.length2 array

    let IsUncertain array row col = getAt array row col = Uncertain

    let IsDisconnected array row col = getAt array row col = Disconnected

    let IsConnected array row col = getAt array row col = Connected

    let filterBy predicate array =
        seq {   for i  in 0 .. len1 array - 1 do
                    for j in 0 .. len2 array - 1 do
                        if predicate array i j then
                            yield (i, j)
            }

    let ListUncertain array = array |> filterBy IsUncertain

    let ListDisconnected array = array |> filterBy IsDisconnected

    let ListConnected array = array |> filterBy IsConnected


    let CountUncertain array = ListUncertain array |> Seq.length

    let CountDisconnection array = ListDisconnected array |> Seq.length

    let CountConnection array = ListConnected array |> Seq.length

    let Disconnect array row col =
        match getAt array row col with
        | Uncertain -> 
            setAt array row col Disconnected
            true
        | Connected -> false
        | Disconnected -> true

    // Check no-cross rule
    let Connect array row col =
        if IsUncertain array row col then
            setAt array row col Connected
            // Disconnect all 'top-right' connections
            for i in 0 .. row - 1 do
                for j in col + 1 .. len2 array - 1 do
                    Disconnect array i j |> ignore
            // Disconnect all 'bottom-left' connections
            for i in row + 1 .. len1 array - 1 do
                for j in 0 .. col - 1 do
                    Disconnect array i j |> ignore
        IsConnected array row col

    // Check no-more-than-three rule
    let Create rows cols =
        let matrix = Array2D.create rows cols Uncertain
        Connect matrix 0 0 |> ignore
        Connect matrix (rows - 1) (cols - 1) |> ignore
        for i in 3 .. rows - 1 do
            Disconnect matrix i 0 |> ignore
        for i in 0 .. rows - 4 do
            Disconnect matrix i (cols - 1) |> ignore
        for j in 3 .. cols - 1 do
            Disconnect matrix 0 j |> ignore
        for j in 0 .. cols - 4 do
            Disconnect matrix (rows - 1) j |> ignore
        matrix

And my matrix creation method is this one:

public void Connect(IStep from, IStep to)
{
    Random rnd = new Random();
    int min = Math.Max(from.Size, to.Size);
    int max = from.Size + to.Size;
    int count = rnd.Next(min, max);

    int[,] matrix = MapConnections.Create(from.Size, to.Size);
    List<int> emptyRows = Enumerable.Range(1, from.Size - 2).ToList();
    List<int> emptyCols = Enumerable.Range(1, to.Size - 2).ToList();
    while (MapConnections.CountConnection(matrix) < count)
    {
        var possibleConnections = MapConnections.ListUncertain(matrix).ToList();

        var tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) && emptyCols.Contains(pc.Item2)).ToList();
        if (tmp.Count == 0)
            tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) || emptyCols.Contains(pc.Item2)).ToList();
        if (tmp.Count != 0)
            possibleConnections = tmp;

        var connection = possibleConnections[rnd.Next(possibleConnections.Count)];
        MapConnections.Connect(matrix, connection.Item1, connection.Item2);
        emptyRows.Remove(connection.Item1);
        emptyCols.Remove(connection.Item2);
    }

    from.Connect(to, matrix);
}

---

An example of what my algorithm should do is (for 5 connections goal):

\begin{bmatrix} 1 & - & - & 0\\ - & - & - & -\\ - & - & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & -\\ 0 & 0 & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & - & 0 & 0\\ - & 1 & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}

---

My actual problem is that I can encounter this scenario (for 4 connections goal):

\begin{bmatrix} 1 & - & - & 0\\ - & - & - & -\\ - & - & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & -\\ 0 & 0 & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}

Finally, nothing is connected to my to[1]. For this very example, I could force the ones to be in the diagonal, but I want to achieve is a generic algorithm, not a case-by-case one.

---

If you wonder, there are all the bad selections for a first-connection, in every case (apply symmetry):

• For 4 connections: \begin{bmatrix} 1 & - & - & 0\\ - & - & * & -\\ - & * & - & -\\ 0 & - & - & 1 \end{bmatrix}

• For 5 connections: \begin{bmatrix} 1 & - & - & 0\\ - & - & * & 0\\ - & - & - & -\\ 0 & * & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0 & 0\\ - & - & * & * & 0\\ - & * & - & * & -\\ 0 & * & * & - & -\\ 0 & 0 & - & - & 1 \end{bmatrix}

• For 6 connections: \begin{bmatrix} 1 & - & - & 0 & 0\\ - & - & - & * & 0\\ - & - & - & - & -\\ 0 & * & - & - & -\\ 0 & 0 & - & - & 1 \end{bmatrix}

---

As asked, here are my classes and tests:

public class Step : IStep
{
    private IRoom[] Rooms { get; set; }
    public IRoom this[int index] { get { return Rooms[index]; } }
    public int Size { get { return Rooms.Length; } }

    public Step(IRoom first, IEnumerable<IRoom> rooms) : this(first, rooms.ToArray())
    { }
    public Step(IRoom first, params IRoom[] rooms)
    { Rooms = new IRoom[] { first }.Concat(rooms).ToArray(); }

    public void Connect(IStep nextStep, int[,] matrix)
    {
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < nextStep.Size; j++)
                if (MapConnections.IsConnected(matrix, i, j))
                    this[i].Connect(nextStep[j]);
    }
}

public /*abstract*/ class Room : IRoom
{
    public IRoom[] NextRooms { get; private set; }

    public void Connect(IRoom nextRoom)
    {
        if (NextRooms == null)
            NextRooms = new[] { nextRoom };
        else
            NextRooms = NextRooms.Concat(new[] { nextRoom }).ToArray();
    }
}

public interface IStepConnector
{
    void Connect(IStep from, IStep to);
}

public class StepConnector : IStepConnector
{
    public void Connect(IStep from, IStep to)
    {
        Random rnd = new Random();
        int min = Math.Max(from.Size, to.Size);
        int max = from.Size + to.Size;
        int count = rnd.Next(min, max);

        int[,] matrix = MapConnections.Create(from.Size, to.Size);
        List<int> emptyRows = Enumerable.Range(1, from.Size - 2).ToList();
        List<int> emptyCols = Enumerable.Range(1, to.Size - 2).ToList();
        while (MapConnections.CountConnection(matrix) < count)
        {
            var possibleConnections = MapConnections.ListUncertain(matrix).ToList();

            var tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) && emptyCols.Contains(pc.Item2)).ToList();
            if (tmp.Count == 0)
                tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) || emptyCols.Contains(pc.Item2)).ToList();
            if (tmp.Count != 0)
                possibleConnections = tmp;

            var connection = possibleConnections[rnd.Next(possibleConnections.Count)];
            MapConnections.Connect(matrix, connection.Item1, connection.Item2);
            emptyRows.Remove(connection.Item1);
            emptyCols.Remove(connection.Item2);
        }

        from.Connect(to, matrix);
    }
}

[TestMethod]
public void CodeReviewTest()
{
    IStep from = new Step(new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom());
    IStep to = new Step(new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom());

    IStepConnector connector = new StepConnector();
    connector.Connect(from, to);

    List<IRoom> toRooms = new List<IRoom>();
    for (int i = 0; i < 5; i++)
    {
        Assert.IsTrue(from[i].NextRooms.Length > 0);
        for (int j = 0; j < from[i].NextRooms.Length; j++)
        {
            if (!toRooms.Contains(from[i].NextRooms[j]))
                toRooms.Add(from[i].NextRooms[j]);
        }
    }

    for (int j = 0; j < 5; j++)
    {
        Assert.IsTrue(toRooms.Contains(to[j]));
    }
}