Doubt in creating a Sierpinski carpet using TSQL (

Question

TSql Challenge 56 is over .... So I can safetly ask doubt on that

I have tried to solve the problem as under

WITH CTE AS 
( 
    SELECT   
            id ,
                        level ,
                        1 AS row ,
                        REPLICATE('X', POWER(3, level)) AS carpet
               FROM     TC56
               UNION ALL
               SELECT   id ,
                        level ,
                        row + 1 ,
                        carpet
               FROM     CTE
               WHERE    Row < POWER(3, level)
             )
    SELECT  
        id
        ,row
        ,carpet
    FROM    CTE
    ORDER BY id,row

But the output is not at par with the one specified.. My output is as under

id row carpet
1 1 X
2 1 XXX
2 2 XXX
2 3 XXX
3 1 XXXXXXXXX
3 2 XXXXXXXXX
3 3 XXXXXXXXX
3 4 XXXXXXXXX
3 5 XXXXXXXXX
3 6 XXXXXXXXX
3 7 XXXXXXXXX
3 8 XXXXXXXXX
3 9 XXXXXXXXX

The problem is that I am not able to fill positions that needs to be filled with empty spaces

Help needed

Answer 1

Here's a solution that can be extended to be able to generate Sierpinski carpets of greater orders. Currently it can correctly generate Sierpinski carpets up to the 3^rd order.

By 'correctly' I mean, it can produce all the necessary rows for greater order patterns, but presently additional columns need to be added (those sortN ones) to provide the correct arrangement of the rows. I've added comments where modifications are required.

WITH TC56 (id, level) AS (
  SELECT 1, 0 UNION ALL
  SELECT 2, 1 UNION ALL
  SELECT 3, 2
),
x AS (
  SELECT CAST('X' AS varchar(max)) AS x
),
rec_cte AS (
  SELECT
    x,
    level = 0,
    sort1 = 0,
    sort2 = 0,
    sort3 = 0
    /* add new columns here */
  FROM x
  UNION ALL
  SELECT
    x = CAST(x.x + CASE TC56.level WHEN 1 THEN SPACE(LEN(x.x)) ELSE x.x END + x.x
             AS varchar(max)),
    level = x.level + 1,
    sort1 = TC56.level,
    sort2 = (TC56.level * 3 + x.sort1) % 3,
    sort3 = ((TC56.level * 3 + x.sort1) * 3 + x.sort2) % 3
    /* computations of the new columns' values follow the above pattern; e.g.
    sort4 = (((TC56.level * 3 + x.sort1) * 3 + x.sort2) * 3 + x.sort3) % 3 */
  FROM rec_cte x
    CROSS JOIN TC56
  WHERE x.level < 3  /* the necessary level to generate;
                   the last sortN's N number defines the maximum value
                   for which the pattern produced is guaranteed to be correct;
                   in this script the last sort column is sort3, so
                   the maximum 'supported' order is 3 */
)
SELECT * FROM rec_cte
ORDER BY level, sort1, sort2, sort3 /* add the new columns here */

Here's the result:

x                              level       sort1       sort2       sort3
------------------------------ ----------- ----------- ----------- -----------
X                              0           0           0           0
XXX                            1           0           0           0
X X                            1           1           0           0
XXX                            1           2           0           0
XXXXXXXXX                      2           0           0           0
X XX XX X                      2           0           1           0
XXXXXXXXX                      2           0           2           0
XXX   XXX                      2           1           0           0
X X   X X                      2           1           1           0
XXX   XXX                      2           1           2           0
XXXXXXXXX                      2           2           0           0
X XX XX X                      2           2           1           0
XXXXXXXXX                      2           2           2           0
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           0           0           0
X XX XX XX XX XX XX XX XX X    3           0           0           1
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           0           0           2
XXX   XXXXXX   XXXXXX   XXX    3           0           1           0
X X   X XX X   X XX X   X X    3           0           1           1
XXX   XXXXXX   XXXXXX   XXX    3           0           1           2
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           0           2           0
X XX XX XX XX XX XX XX XX X    3           0           2           1
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           0           2           2
XXXXXXXXX         XXXXXXXXX    3           1           0           0
X XX XX X         X XX XX X    3           1           0           1
XXXXXXXXX         XXXXXXXXX    3           1           0           2
XXX   XXX         XXX   XXX    3           1           1           0
X X   X X         X X   X X    3           1           1           1
XXX   XXX         XXX   XXX    3           1           1           2
XXXXXXXXX         XXXXXXXXX    3           1           2           0
X XX XX X         X XX XX X    3           1           2           1
XXXXXXXXX         XXXXXXXXX    3           1           2           2
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           2           0           0
X XX XX XX XX XX XX XX XX X    3           2           0           1
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           2           0           2
XXX   XXXXXX   XXXXXX   XXX    3           2           1           0
X X   X XX X   X XX X   X X    3           2           1           1
XXX   XXXXXX   XXXXXX   XXX    3           2           1           2
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           2           2           0
X XX XX XX XX XX XX XX XX X    3           2           2           1
XXXXXXXXXXXXXXXXXXXXXXXXXXX    3           2           2           2