SQL Server 2022

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

21 rows affected

DECLARE @Delim1 CHAR = '|' -- Choses character must not be present in the Data
DECLARE @Delim2 CHAR = '='

;WITH CTE_Key1List AS (
    -- Get a distinct list of keys. Order the keys by number of options descending,
    -- so that those keys with the fewest options will be processed first. (Later
    -- processing starts with the highest RowNum and words its way down.) This
    -- will hopefully reduce backtracking in a tight scenario.
    SELECT Key1, ROW_NUMBER() OVER(ORDER BY COUNT(*) DESC) AS RowNum
    FROM Data
    GROUP BY Key1
),
CTE_Solver AS (
    -- CTE Bootstrap:
    -- Working from MAX(RowNum) backwards, select the first set of
    -- candidate mappings for the selected Key1 value
	-- Build a map list of the form "|Key1=Key2|Key1=Key2|...|".
    SELECT
        K.RowNum,
        CAST(CONCAT(@Delim1, D.Key1, @Delim2, D.Key2, @Delim1) AS VARCHAR(MAX)) AS Mapping
    FROM CTE_Key1List K
    JOIN Data D ON D.Key1 = K.Key1
    WHERE K.RowNum = (SELECT MAX(RowNum) FROM CTE_Key1List)
    -- CTE recursion:
	-- For each lower RowNum value down to 1, include candidate mappings for
	-- the next Key1 value. Exclude any cases that attempt to reuse an
	-- already-assigned Key2 value.
    UNION ALL
    SELECT
        K.RowNum,
        CONCAT(S.Mapping, D.Key1, @Delim2, D.Key2, @Delim1) AS Mapping
    FROM CTE_Solver S
    JOIN CTE_Key1List K
        ON K.RowNum = S.RowNum - 1 
    JOIN Data D
        ON D.Key1 = K.Key1
        AND CHARINDEX(CONCAT(@Delim2, D.Key2, @Delim1), S.Mapping) = 0 -- Unused
    WHERE S.RowNum > 1
),
CTE_Result AS (
    SELECT R.Key1, R.Key2
    FROM (
	    -- Get just one sucessful mapping out of possibly many
        SELECT TOP 1 TRIM(@Delim1 FROM S.Mapping) AS TrimmedMapping
        FROM CTE_Solver S
        WHERE S.RowNum = 1
    ) S
	-- Split the mapping list into individual Key1=Key2 pairs
    CROSS APPLY STRING_SPLIT(S.TrimmedMapping, @Delim1) M
	-- Locate the = delimiter and separate the two values.
    CROSS APPLY (SELECT CHARINDEX(@Delim2, M.value) SplitPos) P
	CROSS APPLY (
	    SELECT
            Key1 = CAST(LEFT(M.value, P.SplitPos - 1) AS INT),
            Key2 = STUFF(M.value, 1, P.SplitPos, '')
	) R
)
--SELECT * FROM CTE_Solver S                          -- All working steps (unordered)
--SELECT * FROM CTE_Solver S ORDER BY MapList         -- All working steps
--SELECT * FROM CTE_Solver S WHERE S.RowNum = 1       -- All solutions
--SELECT TOP 1 * FROM CTE_Solver S WHERE S.RowNum = 1 -- One solution
SELECT * FROM CTE_Result ORDER BY Key1                -- Solution details

Key1	Key2
1	A
2	B
3	C
4	J
5	L
6	K
7	M
8	I
9	Z