A service from Red Gate
Home SQL .NET SysAdmin Opinion Blogs Forums Books
Sign in  | Join  | Help
SQL Home  >  T-SQL Programming  >  The Bejeweled Puzzle in SQL
Av rating:
Total votes: 11
Total comments: 42
 send to a friend
 printer friendly version


Alex Kozak
The Bejeweled Puzzle in SQL
09 October 2008
by Alex Kozak

Alex Kozak provided another SQL puzzle to hone your SQL Skills with.  Entries are now closed and the winner is announced at the end of the article

Many DBAs and developers, at least those that have their servers and applications well under control, may be familiar with the popular, and rather addictive, PC and Xbox games such as Bejeweled and Jewel Quest. They belong to the group of 'match 3' puzzles that are played on grids of different sizes, though typically 8x8. The grid cells are filled with tokens, such as gems or coins, of various shapes and colours and the basic idea is to create horizontal or vertical rows containing a minimum of three matching tokens, by swapping adjacent tokens in the grid. For example, in the 'bejewelled' puzzle shown in Figure 1, we can create a sequence of three blue stones in the second row of the grid by swapping the highlighted red stone with the blue one directly below it:


Figure 1. Bejeweled puzzle

All swaps must be done vertically or horizontally and only swaps that create a sequence of at least three tokens of the same kind, in a column or row, are permitted. When a successful swap is made, the sequence of collected tokens disappears, creating holes (gaps) in the grid. The tokens above these holes immediately cascade down to fill these holes, in turn creating holes in the  top cells in the corresponding columns, which are filled by randomly-generated new tokens. The more tokens a player can make disappear in a single swap, the more points the player gets and the faster he can advance to the next level.

After each swap, the game engine assesses the situation on the game board and if no further valid moves can be made, the game is over. In timed variants, the game can be also terminated if time expires. If valid moves exist, but a player does not make it during a certain time, or if a player presses the "Hint" button, the game engine shows the move that can be made.

The SQL Puzzle

It occurred to me that it would be a very interesting challenge to recreate a bejewled-style puzzle and solve it using SQL!

Figure 2 shows a table, called bejewelled, which represents 9x9 Bejeweled grid:

#

1

2

3

4

5

6

7

8

9

1

8

5

2

8

6

8

9

9

1

2

3

8

6

4

9

3

6

9

6

3

2

8

9

3

4

3

7

4

9

4

1

9

4

5

7

9

9

5

6

5

7

6

2

9

7

9

9

6

8

6

5

2

9

6

5

8

6

8

9

7

4

4

2

5

9

5

8

6

9

8

5

9

9

3

7

7

6

2

6

9

2

3

2

7

9

6

6

2

9

Figure 2. Table bejeweled

The blue numbers from 1 to 9 symbolize nine different types of tokens. In this case, we are dealing only with a fixed grid, rather than one that continually adds randomly-generated tokens, but the goal is similar: you must swap adjacent tokens to create an island of three or more identical numbers in a row or column. For example, if you swap the values of columns 1 and 2 in row 1, you will create a sequence of three 8's in column 2 (rows 1, 2 and 3).

The Challenge!

So, here was the challenge! Using SQL or Transact-SQL, you needed to find all of the possible moves (horizontal and vertical) for the snapshot of Bejeweled table shown in Figure 2.

You had to  present your solution in the following format:

Row number

Column number

Value

1

1

8

5

4

9

Etc…

…

…

You did not need to show where to move the value of the specific cell. Just show what value to move, and from what cell it should be moved.

There were no constraints on how you coded the solution: you could use any SQL and Transact-SQL statements, commands and build-in functions. SQL Server version–specific solutions (for instance, for SQL Server 2008 only) were also allowed. However you did it, you had to present your SQL code, along with a brief explanation of algorithm / implementation you used.

The script in Listing 1  allowed you to create and load table bejeweled:

Listing1. Create and load table bejewelled

IF EXISTS(SELECT * FROM sysobjects 
   WHERE ID = (OBJECT_ID('bejeweled')) AND xtype = 'U')
DROP TABLE bejeweled
GO

CREATE TABLE bejeweled(
 [#] [tinyint] NULL,
 [1] [tinyint] NULL,
 [2] [tinyint] NULL,
 [3] [tinyint] NULL,
 [4] [tinyint] NULL,
 [5] [tinyint] NULL,
 [6] [tinyint] NULL,
 [7] [tinyint] NULL,
 [8] [tinyint] NULL,
 [9] [tinyint] NULL
)

INSERT INTO bejeweled VALUES(1, 8, 5, 2, 8, 6, 8, 9, 9, 1);
INSERT INTO bejeweled VALUES(2, 3, 8, 6, 4, 9, 3, 6, 9, 6);
INSERT INTO bejeweled VALUES(3, 2 , 8, 9, 3, 4, 3, 7, 4, 9);
INSERT INTO bejeweled VALUES(4, 1, 9, 4, 5, 7, 9, 9, 5, 6);
INSERT INTO bejeweled VALUES(5, 7, 6, 2, 9, 7, 9, 9, 6, 8);
INSERT INTO bejeweled VALUES(6, 5, 2, 9, 6, 5, 8, 6, 8, 9);
INSERT INTO bejeweled VALUES(7, 4, 4, 2, 5, 9, 5, 8, 6, 9);
INSERT INTO bejeweled VALUES(8, 5, 9, 9, 3, 7, 7, 6, 2, 6);
INSERT INTO bejeweled VALUES(9, 2, 3, 2, 7, 9, 6, 6, 2, 9);

There were three winners:

  • Timothy Walters - for his second solution with the offset table; He gets a $50 Amazon Voucher.
  • Ryan Randall – for his first and second solutions; He gets a choice between a license for SQL Prompt and SQL Data Generator
  • DrLechter – for his first and second solutions; He gets a choice between a license for SQL Prompt and SQL Data Generator

Timothy Walters's solution is very simple and elegant. Almost all of the logic has been implemented in the lookup table and that makes the solution portable and flexible.

In addition, his solution can be easiely modified in order to show the directions of the moves by adding one more column to the offset table.

Here is how it can be done:


--====== Table matches needs to be loaded only once
CREATE TABLE matches(offsetRow1 INT, offsetCol1 INT, offsetRow2 INT, ofsetCol2 INT, directions VARCHAR(20))
-- for horizontal
INSERT INTO matches VALUES(-1, -1, -1, -2, 'up')
INSERT INTO matches VALUES(-1, -1, -1, 1, 'up')
INSERT INTO matches VALUES(-1, 1, -1, 2, 'up')        
INSERT INTO matches VALUES( 1, -1, 1, -2, 'down')          
INSERT INTO matches VALUES( 1, -1, 1, 1, 'down')
INSERT INTO matches VALUES( 1, 1, 1, 2, 'down')      
INSERT INTO matches VALUES( 0, -2, 0, -3, 'left')    
INSERT INTO matches VALUES( 0, 2, 0, 3, 'right')            
-- for verical
INSERT INTO matches VALUES(-2, -1, -1, -1, 'left')
INSERT INTO matches VALUES(-1, -1, 1, -1, 'left')
INSERT INTO matches VALUES( 1, -1, 2, -1, 'left')
INSERT INTO matches VALUES(-2, 1, -1, 1, 'right')
INSERT INTO matches VALUES(-1, 1, 1, 1, 'right')
INSERT INTO matches VALUES( 1, 1, 2, 1, 'right')
INSERT INTO matches VALUES(-2, 0, -3, 0, 'up')
INSERT INTO matches VALUES( 2, 0, 3, 0, 'down')

--==================================================
;WITH CTE
      AS
  (
  SELECT
        [Row] = CAST( [#] AS INT ),
        [Col] = CAST( [Col] AS INT ),
        [Value]
    FROM bejeweled
        UNPIVOT ([Value] FOR [Col] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) unpvt
  )
SELECT DISTINCT T.Row, T.Col, T.Value, directions
  FROM CTE T
      JOIN CTE T1
      ON T.Value = T1.Value
      JOIN CTE T2
      ON T.Value = T2.Value
      JOIN matches
      ON (T1.Row - T.Row) = offsetRow1
    AND (T1.Col - T.Col) = offsetCol1
    AND (T2.Row - T.Row) = offsetRow2
    AND (T2.Col - T.Col) = ofsetCol2
  ORDER BY T.Row, T.Col

There is one more person – AmandaS that should be specially mentioned. Her second solution was very similar to Timothy Walters' and Ryan Randall's solutions, but was submitted five days later.

A few more people should be mentioned as well:

  • Saharafrog – interesting solution
  • Doug Stewart
  • Steve Munson - his solution shows the coordinates of the cells that should be moved and the coordinates of destination cells
  • RBarry Young
  • Dennis A
  • SkyBeaver


This article has been viewed 9989 times.
Alex Kozak

Author profile: Alex Kozak

Alex Kozak is a Senior DBA/Analyst working for SAP Canada. He has more than 15 years of database and programming experience. Microsoft has included some of his articles in the MSDN Library.

Search for other articles by Alex Kozak

Rate this article:   Avg rating: from a total of 11 votes.


Poor
OK
Good
Great
Must read
 
Have Your Say
Do you have an opinion on this article? Then add your comment below:
You must be logged in to post to this forum

Click here to log in.

Subject: Possible Solution
Posted by: Chris Howarth (view profile)
Posted on: Thursday, October 09, 2008 at 3:54 PM
Message: Here's my attempt at a solution whereby every possible scenario is tested after unpivoting the source data to allow simple calculations to be performed.

I'm sure that there must be more elegant solutions though
;
            /*
Row Col Val
-------------------
1   1   8
3   9   9
5   4   9
6   5   5
6   7   6
7   7   8
7   8   6
9   4   7
9   9   9
*/
;WITH CTE
AS
    (
    SELECT ([#] * 10) + [xpos] AS [Coord],
                [#] AS [ypos],
                [xpos],
                [Value]
        FROM bejeweled
                UNPIVOT ([Value] FOR [xpos] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) unpvt
    )
SELECT [ypos] AS [Row Number],
            [xpos] AS [Column Number],
            [Value] AS [Value]
    FROM CTE main
    WHERE (EXISTS (
        SELECT 1
            FROM CTE [u2l]
            WHERE [u2l].[Value] = main.[Value]
                AND [u2l].[Coord] = main.[Coord] - 12)
            AND EXISTS (
        SELECT 1
            FROM CTE [u1l]
            WHERE [u1l].[Value] = main.[Value]
                AND [u1l].[Coord] = main.[Coord] - 11))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [u1l]
            WHERE [u1l].[Value] = main.[Value]
                AND [u1l].[Coord] = main.[Coord] - 11)
            AND EXISTS (
        SELECT 1
            FROM CTE [u1r]
            WHERE [u1r].[Value] = main.[Value]
                AND [u1r].[Coord] = main.[Coord] - 9))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [u1r]
            WHERE [u1r].[Value] = main.[Value]
                AND [u1r].[Coord] = main.[Coord] - 9)
            AND EXISTS (
        SELECT 1
            FROM CTE [u2r]
            WHERE [u2r].[Value] = main.[Value]
                AND [u2r].[Coord] = main.[Coord] - 8))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [3l]
            WHERE [3l].[Value] = main.[Value]
                AND [3l].[Coord] = main.[Coord] - 3)
            AND EXISTS (
        SELECT 1
            FROM CTE [2l]
            WHERE [2l].[Value] = main.[Value]
                AND [2l].[Coord] = main.[Coord] - 2))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [3r]
            WHERE [3r].[Value] = main.[Value]
                AND [3r].[Coord] = main.[Coord] + 3)
            AND EXISTS (
        SELECT 1
            FROM CTE [2r]
            WHERE [2r].[Value] = main.[Value]
                AND [2r].[Coord] = main.[Coord] + 2))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE d2l
            WHERE d2l.[Value] = main.[Value]
                AND d2l.[Coord] = main.[Coord] + 8)
            AND EXISTS (
        SELECT 1
            FROM CTE d1l
            WHERE d1l.[Value] = main.[Value]
                AND d1l.[Coord] = main.[Coord] + 9))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE d1l
            WHERE d1l.[Value] = main.[Value]
                AND d1l.[Coord] = main.[Coord] + 9)
            AND EXISTS (
        SELECT 1
            FROM CTE d1r
            WHERE d1r.[Value] = main.[Value]
                AND d1r.[Coord] = main.[Coord] + 11))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE d1r
            WHERE d1r.[Value] = main.[Value]
                AND d1r.[Coord] = main.[Coord] + 11)
            AND EXISTS (
        SELECT 1
            FROM CTE d2r
            WHERE d2r.[Value] = main.[Value]
                AND d2r.[Coord] = main.[Coord] + 12))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [3u]
            WHERE [3u].[Value] = main.[Value]
                AND [3u].[Coord] = main.[Coord] - 30)
            AND EXISTS (
        SELECT 1
            FROM CTE [2u]
            WHERE [2u].[Value] = main.[Value]
                AND [2u].[Coord] = main.[Coord] - 20))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [3d]
            WHERE [3d].[Value] = main.[Value]
                AND [3d].[Coord] = main.[Coord] + 30)
            AND EXISTS (
        SELECT 1
            FROM CTE [2d]
            WHERE [2d].[Value] = main.[Value]
                AND [2d].[Coord] = main.[Coord] + 20))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [r2d]
            WHERE [r2d].[Value] = main.[Value]
                AND [r2d].[Coord] = main.[Coord] + 11)
            AND EXISTS (
        SELECT 1
            FROM CTE [r1d]
            WHERE [r1d].[Value] = main.[Value]
                AND [r1d].[Coord] = main.[Coord] + 21))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [l2d]
            WHERE [l2d].[Value] = main.[Value]
                AND [l2d].[Coord] = main.[Coord] + 9)
            AND EXISTS (
        SELECT 1
            FROM CTE [l1d]
            WHERE [l1d].[Value] = main.[Value]
                AND [l1d].[Coord] = main.[Coord] + 19))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [r2u]
            WHERE [r2u].[Value] = main.[Value]
                AND [r2u].[Coord] = main.[Coord] - 19)
            AND EXISTS (
        SELECT 1
            FROM CTE [r1u]
            WHERE [r1u].[Value] = main.[Value]
                AND [r1u].[Coord] = main.[Coord] - 9))
        OR
    (EXISTS (
        SELECT 1
            FROM CTE [l2u]
            WHERE [l2u].[Value] = main.[Value]
                AND [l2u].[Coord] = main.[Coord] - 21)
            AND EXISTS (
        SELECT 1
            FROM CTE [l1u]
            WHERE [l1u].[Value] = main.[Value]
                AND [l1u].[Coord] = main.[Coord] - 11))
Subject: Entirely set-based solution
Posted by: kaboing (view profile)
Posted on: Friday, October 10, 2008 at 9:40 AM
Message: Set-based, using a #temp-table for the unpivoted data.
SELECT [#] AS row, col, val INTO #temp
    FROM
            bejeweled
            unpivot
    (val FOR col IN ([1], [2], [3], [4], [5], [6], [7], [8], [9]))
            AS unpvt
SELECT t.* -- Cols with two connected, missing one on either end
    FROM
    (
    SELECT t1.row, t1.col AS col1, t2.col AS col2, t1.val
        FROM #temp t1
                INNER JOIN #temp t2 ON t1.row=t2.row
            AND t1.col=t2.col+1
            AND t1.val=t2.val )
            AS rc
            INNER JOIN #temp t ON ((t.row=rc.row+1
                OR t.row=rc.row-1)
            AND ((t.col=rc.col1+1)
                OR (t.col=rc.col2-1))
            AND t.val=rc.val)
        OR ((t.row=rc.row)
            AND ((t.col=rc.col1+2)
                OR (t.col=rc.col2-2))
            AND t.val=rc.val)
    UNION
SELECT t3.* -- Interleaving cols
    FROM #temp t1
            INNER JOIN #temp t2 ON t1.row=t2.row
        AND t1.col=t2.col+2
        AND t1.val=t2.val
            LEFT OUTER JOIN #temp t3 ON (t3.row=t1.row+1
            OR t3.row=t1.row-1)
        AND (t3.col=t1.col-1
            AND t3.col=t2.col+1)
        AND t3.val=t1.val
    WHERE t3.val IS NOT NULL
    UNION
SELECT t.* -- Rows with two connected, missing one on either end
    FROM
    (
    SELECT t1.col, t1.row AS row1, t2.row AS row2, t1.val
        FROM #temp t1
                INNER JOIN #temp t2 ON t1.col=t2.col
            AND t1.row=t2.row+1
            AND t1.val=t2.val
    ) AS cc
            INNER JOIN #temp t ON ((t.col=cc.col+1
                OR t.col=cc.col-1)
            AND ((t.row=cc.row1+1)
                OR (t.row=cc.row2-1))
            AND t.val=cc.val)
        OR
    ((t.col=cc.col)
            AND ((t.row=cc.row1+2)
                OR (t.row=cc.row2-2))
            AND t.val=cc.val)
    UNION
SELECT t3.* -- Interleaving rows
    FROM #temp t1
            INNER JOIN #temp t2 ON t1.col=t2.col
        AND t1.row=t2.row+2
        AND t1.val=t2.val
            LEFT OUTER JOIN #temp t3 ON (t3.col=t1.col+1
            OR t3.col=t1.col-1)
        AND (t3.row=t1.row-1
            AND t3.row=t2.row+1)
        AND t3.val=t1.val
    WHERE t3.val IS NOT NULL
DROP TABLE #temp
Subject: The results
Posted by: kaboing (view profile)
Posted on: Friday, October 10, 2008 at 9:41 AM
Message: Forgot to post my results as well...

1, 1, 8
3, 9, 9
5, 4, 9
6, 2, 2
6, 5, 5
6, 7, 6
7, 7, 8
7, 8, 6
9, 4, 7
9, 9, 9
Subject: My mad solution
Posted by: Phil Factor (view profile)
Posted on: Sunday, October 12, 2008 at 5:08 PM
Message:

I drank two cups of coffee. There was a buzzing in my ears, a snapping sound, and this came out. it would work in SQL Server 2000/7.5 if you changed the table variable into a temporary table

SELECT
  [jewel]=[1], [column]=1, [row]=[#], [sequence]=(([#]-1) *9)+1, [othersequence]=[#]+((1-1)*9)
                   INTO #bejewelled
FROM bejeweled UNION ALL
SELECT [2], 2, [#], (([#]-1) *9)+2, [othersequence]=[#]+((2-1)*9)  FROM bejeweled UNION ALL
SELECT [3], 3, [#], (([#]-1) *9)+3, [othersequence]=[#]+((3-1)*9)  FROM bejeweled UNION ALL
SELECT [4], 4, [#], (([#]-1) *9)+4, [othersequence]=[#]+((4-1)*9)  FROM bejeweled UNION ALL
SELECT [5], 5, [#], (([#]-1) *9)+5, [othersequence]=[#]+((5-1)*9)  FROM bejeweled UNION ALL
SELECT [6], 6, [#], (([#]-1) *9)+6, [othersequence]=[#]+((6-1)*9)  FROM bejeweled UNION ALL
SELECT [7], 7, [#], (([#]-1) *9)+7, [othersequence]=[#]+((7-1)*9)  FROM bejeweled UNION ALL
SELECT [8], 8, [#], (([#]-1) *9)+8, [othersequence]=[#]+((8-1)*9)  FROM bejeweled UNION ALL
SELECT [9], 9, [#], (([#]-1) *9)+9, [othersequence]=[#]+((9-1)*9)  FROM bejeweled
ORDER BY sequence


DECLARE @JewelSequence VARCHAR(255)
DECLARE @rowoffset INT, @ii INT,@coloffset INT,@row INT,@col INT
SELECT @JewelSequence='', @ii=1
SELECT @JewelSequence=@JewelSequence+CAST(jewel AS VARCHAR(1)) FROM #bejewelled ORDER BY sequence
SELECT @jewelsequence=@JewelSequence+CAST(jewel AS VARCHAR(1)) FROM #bejewelled ORDER BY othersequence
DECLARE @combinations TABLE (row INT, Col INT, Jewel INT, dir VARCHAR(5), Sequence VARCHAR(40))
WHILE @ii < 72
   BEGIN
   IF @ii %9 <>0
       BEGIN
       SELECT @rowoffset=((@ii/9)*9)+1,
               @coloffset= 82+(((@ii%9)-1)*9),@Row=(@ii/9)+1,@col=@ii%9
       INSERT INTO @combinations(row,col,Jewel,dir,sequence)
       SELECT @row,@col,SUBSTRING(@JewelSequence,@ii,1),'right',
              COALESCE(STUFF(SUBSTRING(@JewelSequence,@rowoffset,9),@ii % 9,2,REVERSE(SUBSTRING(@JewelSequence,@ii,2))),'-')+' '+
              COALESCE(STUFF(SUBSTRING(@JewelSequence,@coloffset,9),@row,1,SUBSTRING(@JewelSequence,@ii+1,1)),'-')+' '+
              COALESCE(STUFF(SUBSTRING(@JewelSequence,@coloffset+9,9),@row,1,SUBSTRING(@JewelSequence,@ii,1)),'-')
       END
       --do a vertical swap
   INSERT INTO @combinations(row,col,Jewel,dir,sequence)
       SELECT @row,@col,SUBSTRING(@JewelSequence,@ii,1),'down',
              STUFF(SUBSTRING(@JewelSequence,@coloffset,9),@row,2,REVERSE(SUBSTRING(@JewelSequence,@coloffset+@row-1,2)))+' '+
              STUFF(SUBSTRING(@JewelSequence,@rowoffset,9),@col,1,SUBSTRING(@JewelSequence,@ii+9,1))+' '+
              STUFF(SUBSTRING(@JewelSequence,@rowoffset+9,9),@col,1,SUBSTRING(@JewelSequence,@ii,1))
     
   SELECT @ii=@ii+1
   END
SELECT row, Col, Jewel,Dir,Seq FROM @combinations
INNER JOIN
(SELECT [seq]=REPLICATE(CAST(number AS CHAR(1)),3) FROM numbers WHERE number BETWEEN 1 AND 9)hits
ON [sequence] LIKE '%'+hits.seq+'%'




/*
row         Col         Jewel       Dir   Seq
----------- ----------- ----------- ----- ----
1           1           8           right 888
3           8           4           right 999
5           4           9           right 999
6           2           2           right 222
6           5           5           down  555
6           7           6           right 666
6           7           6           down  666
6           7           6           down  888
7           7           8           right 666
7           8           6           down  666
8           4           3           down  777
*/


Subject: YAS (Yet another solution)
Posted by: Sherif (not signed in)
Posted on: Monday, October 13, 2008 at 4:41 AM
Message: --Hello,
--Here's my attempt, bit similar to Phil's solution


-- create numbers table transposed (pivot)
create table #numbers_t( [col] [tinyint] , [1] [tinyint] , [2] [tinyint] , [3] [tinyint] , [4] [tinyint] , [5] [tinyint] , [6] [tinyint] , [7] [tinyint] , [8] [tinyint] , [9] [tinyint] )
declare @sql varchar(8000), @counter tinyint,@crlf char(2)
select @counter=1, @crlf=char(10)+char(13),@sql='insert into #numbers_t'
while @counter<10
begin

select @sql =@sql+@crlf+'select '+convert(varchar,@counter)+' as [col],'+@crlf
+'sum(case [row] when 1 then ['+convert(varchar,@counter)+']else 0 end) as [1],'+@crlf
+'sum(case [row] when 2 then ['+convert(varchar,@counter)+']else 0 end) as [2],'+@crlf
+'sum(case [row] when 3 then ['+convert(varchar,@counter)+']else 0 end) as [3],'+@crlf
+'sum(case [row] when 4 then ['+convert(varchar,@counter)+']else 0 end) as [4],'+@crlf
+'sum(case [row] when 5 then ['+convert(varchar,@counter)+']else 0 end) as [5],'+@crlf
+'sum(case [row] when 6 then ['+convert(varchar,@counter)+']else 0 end) as [6],'+@crlf
+'sum(case [row] when 7 then ['+convert(varchar,@counter)+']else 0 end) as [7],'+@crlf
+'sum(case [row] when 8 then ['+convert(varchar,@counter)+']else 0 end) as [8],'+@crlf
+'sum(case [row] when 9 then ['+convert(varchar,@counter)+']else 0 end) as [9]'+@crlf
+'from numbers'+@crlf
+'union all',@counter=@counter+1
end
set @sql= substring(@sql,1,len(@sql)-len('union all'))
exec (@sql)

-- create possible adjacent locations
create table #adj(cell1 [tinyint], cell2 [tinyint], possible [tinyint])
insert into #adj values(1,2,3)
insert into #adj values(1,3,2)
insert into #adj values(2,3,1)
insert into #adj values(2,3,4)
insert into #adj values(2,4,3)
insert into #adj values(3,4,2)
insert into #adj values(3,4,5)
insert into #adj values(3,5,4)
insert into #adj values(4,5,3)
insert into #adj values(4,5,6)
insert into #adj values(4,6,5)
insert into #adj values(5,6,4)
insert into #adj values(5,6,7)
insert into #adj values(5,7,6)
insert into #adj values(6,7,5)
insert into #adj values(6,7,8)
insert into #adj values(6,8,7)
insert into #adj values(7,8,6)
insert into #adj values(7,8,9)
insert into #adj values(7,9,8)
insert into #adj values(8,9,7)

create table #moves ( [row] [tinyint] , [col] [tinyint] , [from_row] [tinyint],[from_col] [tinyint])
--insert into #moves (row,col,from_row,from_col)values (0,0,0,0)
-- 1. columns
select @counter=2,@sql='select c.possible as row, a.[1] as value, 1 as col , 2 as from_col from numbers as a,numbers as b,#adj c, numbers as d where a.[1]=b.[1] and a.[row]=c.cell1 and b.[row]=c.cell2 and a.[1]= d.[2] and d.[row]=c.possible '+@crlf+'union all'
while @counter<9
begin
select @sql=@sql+@crlf+ 'select c.possible as row, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as col , '+convert(varchar,@counter-1)+' as from_col'+@crlf
+'from numbers as a,numbers as b,#adj c, numbers as d'+@crlf
+'where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[row]=c.cell1 and b.[row]=c.cell2 and a.['+convert(varchar,@counter)+']= d.['+convert(varchar,@counter-1)+'] and d.[row]=c.possible'+@crlf
+'union'+@crlf
+'select c.possible as row, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as col ,'+convert(varchar,@counter+1)+' as from_col'+@crlf
+'from numbers as a,numbers as b,#adj c, numbers as d'+@crlf
+'where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[row]=c.cell1 and b.[row]=c.cell2 and a.['+convert(varchar,@counter)+']= d.['+convert(varchar,@counter+1)+'] and d.[row]=c.possible'+@crlf+'union all',
@counter=@counter+1
end
set @sql= @sql+@crlf+'select c.possible as row, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as col , '+convert(varchar,@counter-1)+' as from_col from numbers as a,numbers as b,#adj c, numbers as d where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[row]=c.cell1 and b.[row]=c.cell2 and a.['+convert(varchar,@counteer)+']= d.['+convert(varchar,@counter-1)+'] and d.[row]=c.possible'
exec (@sql)
set @sql = 'insert into #moves '+@crlf+'select x.row,x.col,x.row,x.from_col from ('+@sql+') as x'
exec (@sql)

-- 2. rows
select @counter=2,@sql='select c.possible as col, a.[1] as value, 1 as row , 2 as from_row from #numbers_t as a,#numbers_t as b,#adj c, #numbers_t as d where a.[1]=b.[1] and a.[col]=c.cell1 and b.[col]=c.cell2 and a.[1]= d.[2] and d.[col]=c.possible '+@crlf+'union all'
while @counter<9
begin
select @sql=@sql+@crlf+ 'select c.possible as col, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as row , '+convert(varchar,@counter-1)+' as from_row'+@crlf
+'from #numbers_t as a,#numbers_t as b,#adj c, #numbers_t as d'+@crlf
+'where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[col]=c.cell1 and b.[col]=c.cell2 and a.['+convert(varchar,@counter)+']= d.['+convert(varchar,@counter-1)+'] and d.[col]=c.possible'+@crlf
+'union'+@crlf
+'select c.possible as col, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as row ,'+convert(varchar,@counter+1)+' as from_row'+@crlf
+'from #numbers_t as a,#numbers_t as b,#adj c, #numbers_t as d'+@crlf
+'where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[col]=c.cell1 and b.[col]=c.cell2 and a.['+convert(varchar,@counter)+']= d.['+convert(varchar,@counter+1)+'] and d.[col]=c.possible'+@crlf+'union all',
@counter=@counter+1
end
set @sql= @sql+@crlf+'select c.possible as col, a.['+convert(varchar,@counter)+'] as value, '+convert(varchar,@counter)+' as row , '+convert(varchar,@counter-1)+' as from_row from #numbers_t as a,#numbers_t as b,#adj c, #numbers_t as d where a.['+convert(varchar,@counter)+']=b.['+convert(varchar,@counter)+'] and a.[col]=c.cell1 and b.[col]=c.cell2 and a.['+convert(varchar,@counter)+']= d.['+convert(varchar,@counter-1)+'] and d.[col]=c.possible'
exec (@sql)

set @sql = 'insert into #moves'+@crlf+'select x.row,x.col,x.from_row,x.col from ('+@sql+') as x'
exec (@sql)

select row as [row/col],[1],[2],[3],[4],[5],[6],[7],[8],[9] from numbers
delete #moves where row=0
select 'move ('+convert(varchar,from_row)+','+convert(varchar,from_col)+') ' +
case
when row=from_row and col = from_col then 'none'
when row=from_row and col = from_col-1 then 'left'
when row=from_row and col = from_col+1 then 'right'
when row=from_row-1 and col = from_col then 'up'
when row=from_row+1 and col = from_col then 'down'
else '??'
end +
' to ('+convert(varchar,row)+','+convert(varchar,col)+')' as Moves
from #moves
order by from_row,from_col
drop table #adj
drop table #numbers_t
drop table #moves
go


	

    
        

    
	

          
Subject: very easy.

          
Posted by: lee jae hak (not signed in)

          
Posted on: Wednesday, October 15, 2008 at 2:07 AM

          
Message: WITH TEMP(no)
AS
(
SELECT 1 no
UNION ALL
SELECT no + 1 FROM TEMP
WHERE no + 1 <= 9
)
SELECT 
[#] [Row number]
, b.no [Column number]
, CASE
WHEN b.no=1 THEN [1]
WHEN b.no=2 THEN [2]
WHEN b.no=3 THEN [3]
WHEN b.no=4 THEN [4]
WHEN b.no=5 THEN [5]
WHEN b.no=6 THEN [6]
WHEN b.no=7 THEN [7]
WHEN b.no=8 THEN [8]
WHEN b.no=9 THEN [9]
END [Value]
FROM bejeweled a
CROSS JOIN TEMP b


	

    
        

    
	

          
Subject: Quite Simple I Think

          
Posted by: Phyre (not signed in)

          
Posted on: Wednesday, October 15, 2008 at 4:59 AM

          
Message: 
This is a simple solution - not tested, but seems to me it should work (or a derivative of it should, anyway)


Again, this works after switching the data into a new table with structure row,col,val
SELECT row, col, val FROM bejewelled b1 WHERE 
(col < 7 AND --Switch right
val = (SELECT val FROM bejewelled b2 WHERE
b2.row = b1.row AND b2.col = b1.col + 2)
AND val = (SELECT val FROM bejewelled b2 WHERE 
b2.row = b1.row AND b2.col = b1.col + 3)
) OR (col > 3 AND --switch left
val = (SELECT val FROM bejewelled b2 WHERE 
b2.row = b1.row AND b2.col = b1.col - 2)
AND val = (SELECT val FROM bejewelled b2 WHERE
b2.row = b1.row AND b2.col = b1.col - 3)
) OR (row < 7 AND --switch up
val = (SELECT val FROM bejewelled b2 WHERE 
b2.col = b1.col AND b2.row = b1.row - 2)
AND val = (SELECT val FROM bejewelled b2 WHERE 
b2.col = b1.col AND b2.row = b1.row - 3)
) OR (row > 3 AND --switch down
val = (SELECT val FROM bejewelled b2 WHERE 
b2.col = b1.col AND b2.row = b1.row + 2)
AND val = (SELECT val FROM bejewelled b2 WHERE 
b2.col = b1.col AND b2.row = b1.row + 3)
)


	

    
        

    
	

          
Subject: Limiting by types of movement

          
Posted by: Timothy Walters (view profile)

          
Posted on: Wednesday, October 15, 2008 at 5:10 AM

          
Message: [SQL]
;WITH CTE
AS
(
    SELECT 
        [Coord] = CAST( ([Col] * 10) + [#] AS INT ),
        [Row] = CAST( [#] AS INT ),
        [Col] = CAST( [Col] AS INT ),
        [Value]
    FROM bejeweled
        UNPIVOT ([Value] FOR [Col] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) unpvt
)
-- check for matches by moving up or down to make a horizontal line
SELECT T.Row, T.Col, T.Value
FROM CTE T
JOIN CTE T1
  ON T.Value = T1.Value
 AND ABS(T.Col - T1.Col) = 1 
 AND ABS(T.Row - T1.Row) = 1
JOIN CTE T2
  ON T.Value = T2.Value
 AND T2.Col = T1.Col
 AND ABS(T.Col - T2.Col) = 1 
 AND (
         -- one either side
         ( ABS(T.Row - T2.Row) = 1 AND T2.Row > T1.Row )
         OR 
         -- both one side
         ( ABS(T.Row - T2.Row) = 2 AND ABS(T2.Row - T1.Row) = 1 )
     )
UNION
-- check for matches by moving left or right to make a vertical line
SELECT T.Row, T.Col, T.Value
FROM CTE T
JOIN CTE T1
  ON T.Value = T1.Value
 AND ABS(T.Col - T1.Col) = 1 
 AND ABS(T.Row - T1.Row) = 1
JOIN CTE T2
  ON T.Value = T2.Value
 AND T2.Row = T1.Row
 AND ABS(T.Row - T2.Row) = 1 
 AND (
         -- one either side
         ( ABS(T.Col - T2.Col) = 1 AND T2.Col > T1.Col )
         OR 
         -- both one side
         ( ABS(T.Col - T2.Col) = 2 AND ABS(T2.Col - T1.Col) = 1 )
     )
UNION
-- check for matches by moving up or down to make a vertical line
SELECT T.Row, T.Col, T.Value
FROM CTE T
JOIN CTE T1
  ON T.Value = T1.Value
 AND T.Col = T1.Col
 AND ABS(T.Row - T1.Row) = 2
JOIN CTE T2
  ON T.Value = T2.Value
 AND T2.Col = T1.Col
 AND ABS(T.Row - T2.Row) = 3
 AND ABS(T2.Row - T1.Row) = 1
UNION
-- check for matches by moving left or right to make a horizontal line
SELECT T.Row, T.Col, T.Value
FROM CTE T
JOIN CTE T1
  ON T.Value = T1.Value
 AND T.Row = T1.Row
 AND ABS(T.Col - T1.Col) = 2 
JOIN CTE T2
  ON T.Value = T2.Value
 AND T2.Row = T1.Row
 AND ABS(T.Col - T2.Col) = 3
 AND ABS(T2.Col - T1.Col) = 1

ORDER BY T.Row, T.Col, T.Value
[/SQL]
Produces the results:
Row	Col	Value
1	1	8
3	9	9
5	4	9
6	2	2
6	5	5
6	7	6
7	7	8
7	8	6
9	4	7
9	9	9

This logic is based on the delta positions around a jewel to be moved, using ABS() it's possible to check left/right or up/down at the same time, while using the position of the second match (T2) relative to the first (T1) to make sure they're next to each other.

	

    
        

    
	

          
Subject: Oops...

          
Posted by: Phyre (not signed in)

          
Posted on: Wednesday, October 15, 2008 at 5:38 AM

          
Message: Yeah, I made the same mistake I make when actually playing these games... I never spot:

0x0
x0x as a potential move... :P

adding:
 or (val = (Select val from bejewelled b2 where b2.row = b1.row - 1 and b2.col = b1.col - 1) and val= (Select val from bejewelled b2 where b2.row = b1.row - 1 and b2.col = b1.col + 1)
) or (val = (Select val from bejewelled b2 where b2.row = b1.row + 1 and b2.col = b1.col - 1) and val= (Select val from bejewelled b2 where b2.row = b1.row + 1 and b2.col = b1.col + 1)
) or (val = (Select val from bejewelled b2 where b2.col = b1.col + 1 and b2.row = b1.row - 1) and val= (Select val from bejewelled b2 where b2.col = b1.col + 1 and b2.row = b1.row + 1)
) or (val = (Select val from bejewelled b2 where b2.col = b1.col - 1 and b2.row = b1.row - 1) and val= (Select val from bejewelled b2 where b2.col = b1.col - 1 and b2.row = b1.row + 1)
)

that should do it.  That's quite a long query now! :P

	

    
        

    
	

          
Subject: Deltas using a values table

          
Posted by: Timothy Walters (view profile)

          
Posted on: Wednesday, October 15, 2008 at 5:40 AM

          
Message: Here's another way to do it using a lookup table of possible position deltas:

;WITH CTE
      AS
  (
  SELECT
        [Row] = CAST( [#] AS INT ),
        [Col] = CAST( [Col] AS INT ),
        [Value]
    FROM bejeweled
        UNPIVOT ([Value] FOR [Col] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) unpvt
  )
SELECT DISTINCT T.Row, T.Col, T.Value
  FROM CTE T
      JOIN CTE T1
      ON T.Value = T1.Value
      JOIN CTE T2
      ON T.Value = T2.Value
      JOIN ( 
    VALUES
    -- horizontal matches (delta positions)
    (-1, -1, -1, -2),
    (-1, -1, -1, 1),
    (-1, 1, -1, 2),
    ( 1, -1, 1, -2),
    ( 1, -1, 1, 1),
    ( 1, 1, 1, 2),
    ( 0, -2, 0, -3),
    ( 0, 2, 0, 3),
    -- vertical matches (delta positions)
    (-2, -1, -1, -1),
    (-1, -1, 1, -1),
    ( 1, -1, 2, -1),
    (-2, 1, -1, 1),
    (-1, 1, 1, 1),
    ( 1, 1, 2, 1),
    (-2, 0, -3, 0),
    ( 2, 0, 3, 0)
  ) AS Matches( Match1Row, Match1Col, Match2Row, Match2Col )
      ON (T1.Row - T.Row) = Match1Row
    AND (T1.Col - T.Col) = Match1Col
    AND (T2.Row - T.Row) = Match2Row
    AND (T2.Col - T.Col) = Match2Col
  ORDER BY T.Row, T.Col
      



Outputs as per my last query. This one requires a DISTINCT clause since 6,7 has 2 moves and 7,8 has 3 moves (2 of which produce the same 4 in a row).

	

    
        

    
	

          
Subject: Here's mine...

          
Posted by: Ryan Randall (view profile)

          
Posted on: Wednesday, October 15, 2008 at 6:29 AM

          
Message: ; with a as (
              select 1 as x, # as y, [1] as v from bejeweled
    union all select 2, #, [2] from bejeweled
    union all select 3, #, [3] from bejeweled
    union all select 4, #, [4] from bejeweled
    union all select 5, #, [5] from bejeweled
    union all select 6, #, [6] from bejeweled
    union all select 7, #, [7] from bejeweled
    union all select 8, #, [8] from bejeweled
    union all select 9, #, [9] from bejeweled)
select distinct c.y as row, c.x as col, c.v as val
from a inner join a b on a.v = b.v inner join a c on a.v = c.v
where (a.x+1=b.x and a.y=b.y and (((c.x in (a.x-1, b.x+1)) and c.y in (a.y-1, a.y+1)) or (c.x in (a.x-2, b.x+2) and c.y=a.y)))
   or (a.x+2=b.x and a.y=b.y and c.x=a.x+1 and c.y in (a.y-1, a.y+1))
   or (a.y+1=b.y and a.x=b.x and (((c.y in (a.y-1, b.y+1)) and c.x in (a.x-1, a.x+1)) or (c.y in (a.y-2, b.y+2) and c.x=a.x)))
   or (a.y+2=b.y and a.x=b.x and c.y=a.y+1 and c.x in (a.x-1, a.x+1))
order by c.y, c.x

/*
row  col         val
---- ----------- ----
1    1           8
3    9           9
5    4           9
6    2           2
6    5           5
6    7           6
7    7           8
7    8           6
9    4           7
9    9           9
*/

	

    
        

    
	

          
Subject: Slightly shorter...

          
Posted by: Ryan Randall (view profile)

          
Posted on: Wednesday, October 15, 2008 at 6:35 AM

          
Message: 
; with a as (select x, # as y, v from bejeweled unpivot (v for x in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) a)
select distinct c.y as row, c.x as col, c.v as val
from a inner join a b on a.v = b.v inner join a c on a.v = c.v
where (a.x+1=b.x and a.y=b.y and (((c.x in (a.x-1, b.x+1)) and c.y in (a.y-1, a.y+1)) or (c.x in (a.x-2, b.x+2) and c.y=a.y)))
   or (a.x+2=b.x and a.y=b.y and c.x=a.x+1 and c.y in (a.y-1, a.y+1))
   or (a.y+1=b.y and a.x=b.x and (((c.y in (a.y-1, b.y+1)) and c.x in (a.x-1, a.x+1)) or (c.y in (a.y-2, b.y+2) and c.x=a.x)))
   or (a.y+2=b.y and a.x=b.x and c.y=a.y+1 and c.x in (a.x-1, a.x+1))
order by c.y, c.x

	

    
        

    
	

          
Subject: With direction...

          
Posted by: Ryan Randall (view profile)

          
Posted on: Wednesday, October 15, 2008 at 7:28 AM

          
Message: ; WITH
      a AS (
  SELECT CAST(x AS tinyint) x, # AS y, v 
    FROM bejeweled unpivot (v FOR x IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) a)
      , d AS (
  SELECT 1 AS i, 0 AS j, -1 AS k, -1 AS l, 'down' AS m, 'right' AS n
    UNION ALL 
  SELECT 1, 0, -1, 1, 'up', 'left' AS n
    UNION ALL 
  SELECT 1, 0, -2, 0, 'right', 'down' AS n
    UNION ALL 
  SELECT 1, 0, 2, -1, 'down', 'right' AS n
    UNION ALL 
  SELECT 1, 0, 2, 1, 'up', 'left' AS n
    UNION ALL 
  SELECT 1, 0, 3, 0, 'left', 'up' AS n
    UNION ALL 
  SELECT 2, 0, 1, -1, 'down', 'right' AS n
    UNION ALL 
  SELECT 2, 0, 1, 1, 'up', 'left' AS n)
      , e AS (
  SELECT c.y AS row, c.x AS col, c.v AS val,
    CASE WHEN (b.x=a.x+d.i 
          AND b.y=a.y+d.j 
          AND c.x=a.x+d.k 
          AND c.y=a.y+d.l) THEN m
          WHEN (b.x=a.x+d.j 
          AND b.y=a.y+d.i 
          AND c.x=a.x+d.l 
          AND c.y=a.y+d.k) THEN n
    END AS direction
    FROM a INNER JOIN a b ON a.v = b.v INNER JOIN a c ON a.v = c.v CROSS JOIN d)
SELECT DISTINCT * 
  FROM e 
  WHERE direction IS NOT NULL 
  ORDER BY row, col
      /*
row col val direction
---- ---- ---- ---------
1    1    8    right
3    9    9    left
5    4    9    right
6    2    2    right
6    5    5    down
6    7    6    down
6    7    6    right
7    7    8    up
7    8    6    down
7    8    6    left
9    4    7    up
9    9    9    up
*/ 

	

    
        

    
	

          
Subject: Could be shorter, if I wasn't busy

          
Posted by: Bill (view profile)

          
Posted on: Wednesday, October 15, 2008 at 4:55 PM

          
Message: WITH cteLeft AS (
  SELECT [#], Col, Val
    FROM bejeweled
        unpivot(Val FOR Col IN (
            [1],[2],[3],[4],[5],[6],[7],[8],[9])
    ) u
  ),
  cteHorizEligEnd AS (
  SELECT l.[#], l.Col, l.Val
    FROM cteLeft l
        JOIN cteLeft r ON l.[#] = r.[#]
      AND l.Val = r.Val
      AND l.Col = r.Col - 1
  ),
  cteHorizMovesEnd AS (
  SELECT r.[#], r.Col, r.Val
    FROM cteHorizEligEnd l
        JOIN cteLeft r ON l.Val = r.Val
      AND (
      (l.[#] = r.[#] 
          AND (l.Col = r.Col + 2 
            OR l.Col = r.Col - 3))
        OR ((l.[#] = r.[#] - 1 
            OR l.[#] = r.[#] + 1)
          AND (l.Col = r.Col + 1 
            OR l.Col = r.Col - 2))
    )
  ),
  cteHorizEligMid AS (
  SELECT l.[#], l.Col, l.Val
    FROM cteLeft l
        JOIN cteLeft r ON l.[#] = r.[#]
      AND l.Val = r.Val
      AND l.Col = r.Col - 2
  ),
  cteHorizMovesMid AS (
  SELECT r.[#], r.Col, r.Val
    FROM cteHorizEligMid l
        JOIN cteLeft r ON l.Val = r.Val
      AND l.Col = r.Col - 1
      AND (l.[#] = r.[#] - 1 
        OR l.[#] = r.[#] + 1)
  ),
  cteVertEligEnd AS (
  SELECT l.[#], l.Col, l.Val
    FROM cteLeft l
        JOIN cteLeft r ON l.[#] = r.[#] - 1
      AND l.Col = r.Col
      AND l.Val = r.Val
  ),
  cteVertMovesEnd AS (
  SELECT r.[#], r.Col, r.Val
    FROM cteVertEligEnd l
        JOIN cteLeft r ON l.Val = r.Val
      AND (
      (l.Col = r.Col 
          AND (l.[#] = r.[#] + 2 
            OR l.[#] = r.[#] - 3))
        OR ((l.Col = r.Col - 1 
            OR l.Col = r.Col + 1)
          AND (l.[#] = r.[#] + 1 
            OR l.[#] = r.[#] - 2))
    )
  ),
  cteVertEligMid AS (
  SELECT l.[#], l.Col, l.Val
    FROM cteLeft l
        JOIN cteLeft r ON l.[#] = r.[#] - 2
      AND l.Col = r.Col
      AND l.Val = r.Val
  ),
  cteVertMovesMid AS (
  SELECT r.[#], r.Col, r.Val
    FROM cteVertEligMid l
        JOIN cteLeft r ON l.Val = r.Val
      AND l.[#] = r.[#] - 1
      AND (l.Col = r.Col - 1 
        OR l.Col = r.Col + 1)
  )
SELECT *  FROM cteHorizMovesEnd
  UNION
SELECT *  FROM cteHorizMovesMid
  UNION
SELECT *  FROM cteVertMovesEnd
  UNION
SELECT *  FROM cteVertMovesMid
  ORDER BY [#], Col
       

	

    
        

    
	

          
Subject: I'm sure that a mathematician could do better

          
Posted by: saharafrog (view profile)

          
Posted on: Wednesday, October 15, 2008 at 5:42 PM

          
Message: This is functionally the exact same solution I posted before, I've now removed all the commented out junk I had left in during my "QA" process:

;WITH cteUnpivot AS--== get me a stack to work with (I can only think in one dimension)
  (
  SELECT RowNo, ColNo, X, CAST(RowNo AS INT)*CAST(X AS INT) RX, CAST(ColNo AS INT)*CAST(X AS INT) CX
    FROM
    (
    SELECT [#] RowNo, [1], [2], [3], [4], [5], [6], [7], [8], [9]
      FROM bejeweled) p
        UNPIVOT
    (X FOR ColNo IN ([1], [2], [3], [4], [5], [6], [7], [8], [9])
    ) AS unpvt)
      , cteMiddle AS
      /*filling the middle of an island*/
  (
  SELECT a.X, a.RowNo, a.ColNo
    FROM cteUnpivot a
        JOIN cteUnpivot b ON a.X=b.X
        JOIN cteUnpivot c ON a.X=c.X
    WHERE (ABS(ABS(b.RX-c.RX)-ABS(b.CX-c.CX))=2*a.X)
      AND ABS(b.RX-a.RX)=a.X 
      AND ABS(b.CX-a.CX)=a.X
      AND ABS(a.RX-c.RX)=a.X 
      AND ABS(a.CX-c.CX)=a.X)
      , cteEndInLine AS
      /*filling the beginning or end of an island, and in same row or column*/
  (
  SELECT a.X, a.RowNo, a.ColNo
    FROM cteUnpivot a
        JOIN cteUnpivot b ON a.X=b.X
        JOIN cteUnpivot c ON a.X=c.X
    WHERE ABS(b.RX-c.RX)+ABS(b.CX-c.CX) = a.X
      AND ABS(ABS(b.RX-a.RX)-ABS(b.CX-a.CX)) = 3*a.X
      AND ABS(b.RX-a.RX)*ABS(b.CX-a.CX) = 0
      AND ABS(ABS(a.RX-c.RX)-ABS(a.CX-c.CX)) = 2*a.X
      AND ABS(a.RX-c.RX)*ABS(a.CX-c.CX) = 0)
      , cteEndOffLine AS
      /*filling the beginning or end of an island, and in a different row and column*/
  (
  SELECT a.X, a.RowNo, a.ColNo
    FROM cteUnpivot a
        JOIN cteUnpivot b ON a.X=b.X
        JOIN cteUnpivot c ON a.X=c.X
    WHERE ABS(b.RX-c.RX)+ABS(b.CX-c.CX) = a.X
      AND ABS(ABS(b.RX-a.RX)-ABS(b.CX-a.CX)) = 0
      AND ABS(b.RX-a.RX)+ABS(b.CX-a.CX) = 2*a.X
      AND ABS(ABS(a.RX-c.RX)+ABS(a.CX-c.CX)) = 3*a.X
      AND ABS(ABS(a.RX-c.RX)-ABS(a.CX-c.CX)) = a.X)
SELECT RowNo, ColNo, X 
  FROM cteMiddle
  UNION 
SELECT RowNo, ColNo, X 
  FROM cteEndInLine
  UNION 
SELECT RowNo, ColNo, X 
  FROM cteEndOffLine
  ORDER BY RowNo, ColNo
      

	

    
        

    
	

          
Subject: My Solution

          
Posted by: DrLechter (view profile)

          
Posted on: Thursday, October 16, 2008 at 6:01 PM

          
Message: /*
This solution joins an unpivoted version of the main table to itself 3 times on token value and then restricts results to records with valid row/column deltas between tokens.*/

WITH cte
AS
(
SELECT
    CONVERT (INT, bjrc.[#]) AS row,
    CONVERT (INT, bjrc.[col]) AS col,
    [value]
FROM bejeweled
unpivot ([Value] FOR [col] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) bjrc
) 

SELECT DISTINCT t0.row, t0.col, t0.value
FROM cte AS t0
INNER JOIN cte AS t1 ON t1.value = t0.value -- match values first
INNER JOIN cte AS t2 ON t2.value = t0.value
WHERE
(
    -- horiz match from horiz move
    -- t0-dd-t1-t2 or t1-t2-dd-t0
    (t2.row = t1.row AND t1.row = t0.row)       -- everything in same row 
    AND ((ABS(t2.col - t1.col) = 1) AND (ABS(t2.col - t0.col) + ABS(t1.col - t0.col) = 5))
)
OR 
(
    -- horiz match from vert move
    -- dd-t1-t2 or t1-dd-t2 or t1-t2-dd
    -- t0-xx-xx or xx-t0-xx or xx-xx-t0
    (t2.row = t1.row) AND ABS (t1.row - t0.row) = 1
    AND 
    (
        ((ABS(t2.col - t1.col) = 1) AND (ABS(t2.col - t0.col) + ABS(t1.col - t0.col) = 3))
        OR
        ((ABS(t2.col - t1.col) = 2) AND (ABS(t2.col - t0.col) = 1 AND ABS(t1.col - t0.col) = 1))
    )
)
OR
(
    -- vert match from vert move
    --  t0  or  t1   
    --  dd      t2  
    --  t1      dd
    --  t2      t0
    --
    t2.col = t1.col AND t1.col = t0.col     -- everything in same col 
    AND ((ABS(t2.row - t1.row) = 1) AND (ABS(t2.row - t0.row) + ABS(t1.row - t0.row) = 5))
)
OR
(
    -- vert match from horiz move
    -- t0 dd  or  xx t1 
    -- xx t1      t0 dd
    -- xx t2      xx t2
    (t2.col = t1.col) AND ABS (t1.col - t0.col) = 1
    AND 
    (
        ((ABS(t2.row - t1.row) = 1) AND (ABS(t2.row - t0.row) + ABS(t1.row - t0.row) = 3))
        OR
        ((ABS(t2.row - t1.row) = 2) AND (ABS(t2.row - t0.row) = 1 AND ABS(t1.row - t0.row) = 1))
    )
)
ORDER BY t0.Row, t0.col 

Results:

row col value
--- --- -----
1 1 8
3 9 9
5 4 9
6 2 2
6 5 5
6 7 6
7 7 8
7 8 6
9 4 7
9 9 9

	

    
        

    
	

          
Subject: Another Solution

          
Posted by: Mark Lopez (not signed in)

          
Posted on: Friday, October 17, 2008 at 1:58 AM

          
Message: create function [dbo].[bejeweled_get_value](@x tinyint,@y tinyint) returns char(1)
as
begin
  /**
    this will get the value from the table 
  **/
  return (
   select ltrim(rtrim(str(case
        when @x=1 then [1]
        when @x=2 then [2]
        when @x=3 then [3]
        when @x=4 then [4]
        when @x=5 then [5]
        when @x=6 then [6]
        when @x=7 then [7]
        when @x=8 then [8]
        when @x=9 then [9]
        else 0
      end,1)))
   from bejeweled
   where [#]=@y
      )
end
------------------------------------------------------------------------------------------------------------


-- this is the actual code
declare @cx tinyint,
   @cy tinyint,
   @accu varchar(9),
   @accuz char(1),
   @cz tinyint

set @cx=0
while @cx < 9
begin
  set @cx=@cx+1
  set @cy=0
  set @accu=''

  while @cy < 9 -- get hozizontal string
  begin
    set @cy=@cy+1
    set @accu=@accu + dbo.bejeweled_get_value(@cx,@cy)
  end
  
  --print @accu

  set @accuz=substring(@accu,@cz,1)
  set @cz=1
  while @cz<9
  begin
    set @cz=@cz + 1
   
    if @accuz=substring(@accu,@cz,1)
    begin
   if @cz < 8 -- forward search is possible
   begin
     if substring(@accu,@cz+2,1)=@accuz       
      print ltrim(str(@cz+2)) + ',' + ltrim(str(@cx)) + ',' + substring(@accu,@cz+2,1)
        
    if @cx > 1 and @accuz=dbo.bejeweled_get_value(@cx-1,@cz+1)
      print ltrim(str(@cx-1)) + ',' + ltrim(str(@cx-1)) + ',' + dbo.bejeweled_get_value(@cx-1,@cz+1) 

    if @cx < 9 and @accuz=dbo.bejeweled_get_value(@cx+1,@cz+1)
      print ltrim(str(@cx-1)) + ',' + ltrim(str(@cx+1)) + ',' + dbo.bejeweled_get_value(@cx+1,@cz+1) 
      end

   if @cz > 2 -- backward search is posibble
      begin
     if substring(@accu,@cz-3,1)=@accuz
      print ltrim(str(@cz-3)) + ',' + ltrim(str(@cx)) + ',' + substring(@accu,@cz-3,1)

    if @cx > 1 and @accuz=dbo.bejeweled_get_value(@cx-1,@cz-2)
      print ltrim(str(@cz-2)) + ',' + ltrim(str(@cx-1)) + ',' + dbo.bejeweled_get_value(@cx-1,@cz-2)

    if @cx < 9 and @accuz=dbo.bejeweled_get_value(@cx+1,@cz-2)
      print ltrim(str(@cz-2)) + ',' + ltrim(str(@cx+1)) + ',' + dbo.bejeweled_get_value(@cx+1,@cz-2)

      end

    end
    else
    begin
      set @accuz=substring(@accu,@cz,1)
    end
  end
end

--print 'hehe'

set @cy=0
while @cy < 9
begin
  set @cy=@cy+1
  set @cx=0
  set @accu=''

  while @cx < 9 -- get hozizontal string
  begin
    set @cx=@cx+1
    set @accu=@accu + dbo.bejeweled_get_value(@cx,@cy)
  end
  
  --print @accu

  set @accuz=substring(@accu,@cz,1)
  set @cz=1
  while @cz<9
  begin
    set @cz=@cz + 1
   
    if @accuz=substring(@accu,@cz,1)
    begin
   --print 'possible: ' + ltrim(str(@accuz))

   if @cz < 8 -- forward search is possible
   begin   
      if substring(@accu,@cz+2,1)=@accuz       
      print ltrim(str(@cz+2)) + ',' + ltrim(str(@cy)) + ',' + substring(@accu,@cz+2,1)
     
    if @cy > 1 and @accuz=dbo.bejeweled_get_value(@cz+1,@cy-1)
      print ltrim(str(@cz+1)) + ',' + ltrim(str(@cy-1)) + ',' + dbo.bejeweled_get_value(@cz+1,@cy-1)
   
    if @cy < 9 and @accuz=dbo.bejeweled_get_value(@cz+1,@cy+1)
      print ltrim(str(@cz+1)) + ',' + ltrim(str(@cy+1)) + ',' + dbo.bejeweled_get_value(@cz+1,@cy+1)
      end

   if @cz > 2 -- backward search is posibble
      begin
     if substring(@accu,@cz-3,1)=@accuz
      print ltrim(str(@cz-3)) + ',' + ltrim(str(@cy)) + ',' + substring(@accu,@cz-3,1)

    if @cy > 1 and @accuz=dbo.bejeweled_get_value(@cz-2,@cy-1)
      print ltrim(str(@cz-2)) + ',' + ltrim(str(@cy-1)) + ',' + dbo.bejeweled_get_value(@cz-2,@cy-1)

    if @cy < 9 and @accuz=dbo.bejeweled_get_value(@cz-2,@cy+1)
      print ltrim(str(@cz-2)) + ',' + ltrim(str(@cy+1)) + ',' + dbo.bejeweled_get_value(@cz-2,@cy+1)
      end
    end
    else
    begin
      set @accuz=substring(@accu,@cz,1)
    end
  end
end

	

    
        

    
	

          
Subject: Might as well...

          
Posted by: Tao (not signed in)

          
Posted on: Friday, October 17, 2008 at 7:18 AM

          
Message: Not an elegant or extensible solution, but it is very straight forward, in a simple SQL way :). And it works:



--Assumptions:
-- - moving two of the same (presumably because there was already a winning position on the board) is not allowed
-- - only output one "cell" once, even if it can be moved in multiple directions (change to UNION ALL otherwise)
-- - do not consider the other part of the "swap" to be a move - only count the part that contributes a winning position.

CREATE TABLE #testemp (Row Int, Col Int, Value Int)
INSERT INTO #testemp SElECT [#], 1, [1] FROM bejeweled
INSERT INTO #testemp SElECT [#], 2, [2] FROM bejeweled
INSERT INTO #testemp SElECT [#], 3, [3] FROM bejeweled
INSERT INTO #testemp SElECT [#], 4, [4] FROM bejeweled
INSERT INTO #testemp SElECT [#], 5, [5] FROM bejeweled
INSERT INTO #testemp SElECT [#], 6, [6] FROM bejeweled
INSERT INTO #testemp SElECT [#], 7, [7] FROM bejeweled
INSERT INTO #testemp SElECT [#], 8, [8] FROM bejeweled
INSERT INTO #testemp SElECT [#], 9, [9] FROM bejeweled

--First consider one side of the vertical moves
SELECT t1.row, t1.col, t1.value
FROM #testemp t1
INNER JOIN #testemp t2 ON t1.row = t2.row - 1 AND t1.col = t2.col
LEFT JOIN #testemp lld ON t1.row = lld.row - 1 AND t1.col = lld.col - 2
LEFT JOIN #testemp ld ON t1.row = ld.row - 1 AND t1.col = ld.col - 1
LEFT JOIN #testemp rd ON t1.row = rd.row - 1 AND t1.col = rd.col + 1
LEFT JOIN #testemp rrd ON t1.row = rrd.row - 1 AND t1.col = rrd.col + 2
LEFT JOIN #testemp d ON t1.row = d.row - 2 AND t1.col = d.col
LEFT JOIN #testemp dd ON t1.row = dd.row - 3 AND t1.col = dd.col
WHERE t1.value <> t2.value 
	AND --solution conditions
		(dd.Value = d.Value and d.Value = t1.Value) OR
		(lld.Value = ld.Value and ld.Value = t1.Value) OR
		(ld.Value = t1.Value and t1.Value = rd.Value) OR
		(t1.Value = rd.Value and rd.Value = rrd.Value)


UNION 

--Then consider the other side of the vertical moves
SELECT  t2.row, t2.col, t2.value
FROM #testemp t1
INNER JOIN #testemp t2 ON t1.row = t2.row - 1 AND t1.col = t2.col
LEFT JOIN #testemp uu ON t1.row = uu.row + 2 AND t1.col = uu.col
LEFT JOIN #testemp u ON t1.row = u.row + 1 AND t1.col = u.col
LEFT JOIN #testemp llu ON t1.row = llu.row AND t1.col = llu.col - 2
LEFT JOIN #testemp lu ON t1.row = lu.row AND t1.col = lu.col - 1
LEFT JOIN #testemp ru ON t1.row = ru.row AND t1.col = ru.col + 1
LEFT JOIN #testemp rru ON t1.row = rru.row AND t1.col = rru.col + 2
WHERE t1.value <> t2.value 
	AND --solution conditions
		(t2.Value = u.Value and u.Value = uu.Value) OR
		(llu.Value = lu.Value and lu.Value = t2.Value) OR
		(lu.Value = t2.Value and t2.Value = ru.Value) OR
		(t2.Value = ru.Value and ru.Value = rru.Value) 


UNION 

--Then consider the first side of the horizontal moves 
SELECT  t1.row, t1.col, t1.value
FROM #testemp t1
INNER JOIN #testemp t2 ON t1.row = t2.row AND t1.col = t2.col - 1
LEFT JOIN #testemp uur ON t1.row = uur.row + 2 AND t1.col = uur.col - 1
LEFT JOIN #testemp ur ON t1.row = ur.row + 1 AND t1.col = ur.col - 1
LEFT JOIN #testemp dr ON t1.row = dr.row - 1 AND t1.col = dr.col - 1
LEFT JOIN #testemp ddr ON t1.row = ddr.row - 2 AND t1.col = ddr.col - 1
LEFT JOIN #testemp r ON t1.row = r.row AND t1.col = r.col - 2
LEFT JOIN #testemp rr ON t1.row = rr.row AND t1.col = rr.col - 3
WHERE t1.value <> t2.value 
	AND --solution conditions
		(t1.Value = r.Value and r.Value = rr.Value) OR
		(uur.Value = ur.Value and ur.Value = t1.Value) OR
		(ur.Value = t1.Value and t1.Value = dr.Value) OR
		(t1.Value = dr.Value and dr.Value = ddr.Value) 



UNION 

--Then consider the other side of the horizontal moves 
SELECT  t2.row, t2.col, t2.value
FROM #testemp t1
INNER JOIN #testemp t2 ON t1.row = t2.row AND t1.col = t2.col - 1
LEFT JOIN #testemp uul ON t1.row = uul.row + 2 AND t1.col = uul.col
LEFT JOIN #testemp ul ON t1.row = ul.row + 1 AND t1.col = ul.col
LEFT JOIN #testemp dl ON t1.row = dl.row - 1 AND t1.col = dl.col
LEFT JOIN #testemp ddl ON t1.row = ddl.row - 2 AND t1.col = ddl.col
LEFT JOIN #testemp ll ON t1.row = ll.row AND t1.col = ll.col + 2
LEFT JOIN #testemp l ON t1.row = l.row AND t1.col = l.col + 1
WHERE t1.value <> t2.value 
	AND --solution conditions
		(ll.Value = l.Value and l.Value = t2.Value) OR
		(uul.Value = ul.Value and ul.Value = t2.Value) OR
		(ul.Value = t2.Value and t2.Value = dl.Value) OR
		(t2.Value = dl.Value and dl.Value = ddl.Value) 


DROP TABLE #testemp

	

    
        

    
	

          
Subject: A simpler solution

          
Posted by: DrLechter (view profile)

          
Posted on: Friday, October 17, 2008 at 11:21 AM

          
Message: /*
This simplified solution relies on the fact that the good move detection algorithms for vertical and horizontal moves
are identical except for the fact the one refers to rows & cols while the other refers to cols & rows.  The unpivoted rows 
are returned twice - once for horizontal mode and once for vertical mode.  The results are then restricted to records 
with valid row/column deltas between tokens.
*/
;with ctei as
(
    select [#] as row,  convert (int, bjrc.col) as col, [value] from bejeweled
    unpivot ([value] for col IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as bjrc
),
cte as
(
    select 'H' as mode, ctei.*, ctei.row as rc, ctei.col as cr from ctei
    union all
    select 'V' as mode, ctei.*, ctei.col as rc, ctei.row as cr from ctei -- reverse rc and cr meaning for vertical
)

select distinct t0.row, t0.col, t0.value
from cte as t0
inner join cte as t1 on t1.value = t0.value and t1.mode = t0.mode -- match values and modes first 
inner join cte as t2 on t2.value = t0.value and t2.mode = t0.mode
where
(
    -- horiz match from horiz move - mode H    or    vert match from vert move - mode V
    -- t0-dd-t1-t2  or  t1-t2-dd-t0                  t0  or  t1   
    --                                               dd      t2  
    --                                               t1      dd
    --                                               t2      t0
    (t2.rc = t1.rc and t1.rc = t0.rc)       
    and ((abs(t2.cr - t1.cr) = 1) and (abs(t2.cr - t0.cr) + abs(t1.cr - t0.cr) = 5))
)
or 
(
    -- horiz match from vert move - mode H    or    vert match from horiz move - mode V
    -- dd-t1-t2  or  t1-dd-t2  or  t1-t2-dd         t0 dd  or  xx t1 
    -- t0-xx-xx  or  xx-t0-xx  or  xx-xx-t0         xx t1      t0 dd
    --                                              xx t2       xx t2
    (t2.rc = t1.rc) and abs (t1.rc - t0.rc) = 1
    and 
    (
        ((abs(t2.cr - t1.cr) = 1) and (abs(t2.cr - t0.cr) + abs(t1.cr - t0.cr) = 3))
        or
        ((abs(t2.cr - t1.cr) = 2) and (abs(t2.cr - t0.cr) = 1 and abs(t1.cr - t0.cr) = 1))
    )
)
order by t0.Row, t0.col 

	

    
        

    
	

          
Subject: proposed solution

          
Posted by: DOUG (view profile)

          
Posted on: Friday, October 17, 2008 at 12:59 PM

          
Message: --Submitted by Doug Stewart ----doug.stewart@msagroup.com

--CONVERT bejeweled table to alternate table format 
--(similar to UNPIVOT, but slightly modified)
declare @T table (seqno int IDENTITY, R int, C int, V int)
declare @R [tinyint], @C [tinyint], @Seq [tinyint]
SET @Seq=1 
WHILE @seq < 100
BEGIN
	INSERT  @T (R,C)  
	SELECT  (@Seq-1)/11+1,  --Rows 1 thru 9
			ISNULL(NULLIF((@Seq%11)-1,-1),10) --sequence 0 thr 10 (11 columns)
	SET @Seq=@Seq+1
END
UPDATE @T SET V = CASE C 
WHEN 1 THEN [1] WHEN 2 THEN [2] WHEN 3 THEN [3] 
WHEN 4 THEN [4] WHEN 5 THEN [5] WHEN 6 THEN [6] 
WHEN 7 THEN [7] WHEN 8 THEN [8] WHEN 9 THEN [9] 
ELSE 0 END
FROM bejeweled WHERE R = [#] 

--NOTE THAT VERTICAL TILES IN THE PUZZLE TABLES ARE 11 apart by seqno
-- AND Horizontal tiles are 1 apart. (obviously)

--This table desctibes the possible neighbors of the Targeted solution tiles
DECLARE @NEIGHBORS TABLE (targetSolutionTile VARCHAR(4), Offset [INT])
INSERT @NEIGHBORS SELECT 'A+2', 1 UNION SELECT 'A+2', 11 UNION SELECT  'A+2', -11 
INSERT @NEIGHBORS SELECT 'B-1', -1 UNION SELECT 'B-1', 11 UNION SELECT  'B-1', -11 
INSERT @NEIGHBORS SELECT 'C+22', -1 UNION SELECT 'C+22', 11 UNION SELECT  'C+22', 1 
INSERT @NEIGHBORS SELECT 'D-11', -1 UNION SELECT 'D-11', -11 UNION SELECT  'D-11', 1 
INSERT @NEIGHBORS SELECT 'E+1', 11 UNION SELECT 'E+1', -11 
INSERT @NEIGHBORS SELECT 'F+11', 1 UNION SELECT 'F+11', -1; 

WITH TARGETS (ValNeeded, seqno, targetSolutionTile)
AS (
	Select 
	--TWO TOGETHER HORIZONTALLY
	T1.V,T1.seqno+2 as target_seqno, 'A+2' as targetSolutionTile from @T as T1 Join @T as T2 
	ON T1.seqno+1 = T2.seqno And T1.V=T2.V --match to right 1--target right 2
	Where T1.V<>0
	union
	Select T1.V,T1.seqno-1, 'B-1'  from @T as T1 Join @T as T2 
	ON T1.seqno+1 = T2.seqno And T1.V=T2.V --match to right 1--target left 1
	Where T1.V<>0
	union
	--TWO TOGETHER VERICALLY
	Select T1.V,T1.seqno+22, 'C+22' from @T as T1 Join @T as T2 
	ON T1.seqno+11 = T2.seqno And T1.V=T2.V --match to below 1--target below 2
	Where T1.V<>0
	union
	Select T1.V,T1.seqno-11, 'D-11' from @T as T1 Join @T as T2 
	ON T1.seqno+11 = T2.seqno And T1.V=T2.V --match to below 1--target above 1
	Where T1.V<>0
	union
	--TWO TWO-SPACES APART HORIZONTALLY
	Select T1.V,T1.seqno+1, 'E+1' from @T as T1 Join @T as T2 
	ON T1.seqno+2 = T2.seqno And T1.V=T2.V --match to right 2--target right 1
	Where T1.V<>0
	union

	--TWO TWO-SPACES APART VERICALLY
	Select T1.V,T1.seqno+11, 'F+11' from @T as T1 Join @T as T2 
	ON T1.seqno+22 = T2.seqno And T1.V=T2.V --match to below 2--target below 1
	Where T1.V<>0
)

--USING TARGETED SOLUTION TILES AS STARTING POINT
--EXAMINE THE VALUES OF ADJACENT TILES THAT COULD BE MOVED (to make a solution)
Select DISTINCT T.R as [Row number], T.C as [Column Number], TG1.ValNeeded as [Value]
   FROM TARGETS TG1 
   JOIN @NEIGHBORS N ON TG1.targetSolutionTile = N.targetSolutionTile
   JOIN @T T  
     ON TG1.seqno+N.Offset = T.seqno
    AND T.V = TG1.ValNeeded
Order by [Row number], [Column Number]

	

    
        

    
	

          
Subject: My solution

          
Posted by: EdH (view profile)

          
Posted on: Friday, October 17, 2008 at 2:14 PM

          
Message: -- I found it easier to define the bejewelled 
-- table as follows,
-- rather than how it was coded in the example

create table bejewelled (
row int, col int, val int)

insert bejewelled 
select 1,1,8
union all
select 1,2,5
union all
select 1,3,2
union all
select 1,4,8
union all
select 1,5,6
union all
select 1,6,8
union all
select 1,7,9
union all
select 1,8,9
union all
select 1,9,1
union all
select 2,1,3
union all
select 2,2,8
union all
select 2,3,6
union all
select 2,4,4
union all
select 2,5,9
union all
select 2,6,3
union all
select 2,7,6
union all
select 2,8,9
union all
select 2,9,6
union all
select 3,1,2
union all
select 3,2,8
union all
select 3,3,9
union all
select 3,4,3
union all
select 3,5,4
union all
select 3,6,3
union all
select 3,7,7
union all
select 3,8,4
union all
select 3,9,9
union all
select 4,1,1
union all
select 4,2,9
union all
select 4,3,4
union all
select 4,4,5
union all
select 4,5,7
union all
select 4,6,9
union all
select 4,7,9
union all
select 4,8,5
union all
select 4,9,6
union all
select 5,1,7
union all
select 5,2,6
union all
select 5,3,2
union all
select 5,4,9
union all
select 5,5,7
union all
select 5,6,9
union all
select 5,7,9
union all
select 5,8,6
union all
select 5,9,8
union all
select 6,1,5
union all
select 6,2,2
union all
select 6,3,9
union all
select 6,4,6
union all
select 6,5,5
union all
select 6,6,8
union all
select 6,7,6
union all
select 6,8,8
union all
select 6,9,9
union all
select 7,1,4
union all
select 7,2,4
union all
select 7,3,2
union all
select 7,4,5
union all
select 7,5,9
union all
select 7,6,5
union all
select 7,7,8
union all
select 7,8,6
union all
select 7,9,9
union all
select 8,1,5
union all
select 8,2,9
union all
select 8,3,9
union all
select 8,4,3
union all
select 8,5,7
union all
select 8,6,7
union all
select 8,7,6
union all
select 8,8,2
union all
select 8,9,6
union all
select 9,1,2
union all
select 9,2,3
union all
select 9,3,2
union all
select 9,4,7
union all
select 9,5,9
union all
select 9,6,6
union all
select 9,7,6
union all
select 9,8,2
union all
select 9,9,9

-- for moves in each direction, there are four 
-- cases where the move makes a three-in-a-row
-- match.
-- two matching values to the left of the 
-- direction moved,
-- two matching values to the right of the 
-- direction moved,
-- filling in the center of two matching values, -- or aproaching a pair lined up in the
-- direction moved

-- because I used he direction moved as a base
-- of the solution it was very easy to include
-- the direction to be moved as part of the
-- solution as well

-- find cells where downward moves produce a match
select distinct a.*, 'd' as dir
from bejewelled a, bejewelled b, bejewelled c
where a.val = b.val
	and a.val = c.val
	and (
		(a.row = b.row - 1 and
			a.col = b.col-1 and
			a.row = c.row - 1 and
			a.col = c.col - 2) or
		(a.row = b.row - 1 and 
			a.col = b.col - 1 and
			a.row = c.row - 1 and 
			a.col = c.col + 1) or
		(a.row = b.row - 1 and 
			a.col = b.col + 1 and
			a.row = c.row - 1 and 
			a.col = c.col + 2) or
		(a.row = b.row - 2 and 
			a.col = b.col and
			a.row = c.row - 3 and 
			a.col = c.col))
union all
-- find cells where upward moves produce a match
select distinct a.*, 'u' as dir
from bejewelled a, bejewelled b, bejewelled c
where a.val = b.val
	and a.val = c.val
	and (
		(a.row = b.row + 1 and 
			a.col = b.col - 1 and
			a.row = c.row + 1 and 
			a.col = c.col - 2) or
		(a.row = b.row + 1 and 
			a.col = b.col - 1 and
			a.row = c.row + 1 and
			a.col = c.col + 1) or
		(a.row = b.row + 1 and 
			a.col = b.col + 1 and
			a.row = c.row + 1 and 
			a.col = c.col + 2) or
		(a.row = b.row + 2 and
			a.col = b.col and
			a.row = c.row + 3 and
			a.col = c.col))
union all
-- find cells where right moves produce a match
select distinct a.*, 'r' as dir
from bejewelled a, bejewelled b, bejewelled c
where a.val = b.val
	and a.val = c.val
	and (
		(a.col = b.col + 1 and 
			a.row = b.row - 1 and
			a.col = c.col + 1 and
			a.row = c.row - 2) or
		(a.col = b.col + 1 and
			a.row = b.row - 1 and
			and a.col = c.col + 1 
			and a.row = c.row + 1) or
		(a.col = b.col + 1 and
			a.row = b.row - 1 and
			a.col = c.col + 1 and
		 	a.row = c.row + 2) or
		(a.col = b.col + 2 and
			a.row = b.row and
			a.col = c.col + 3 and 
			a.row = c.row))
union all
-- find cells where left moves produce a match
select distinct a.*, 'l' as dir
from bejewelled a, bejewelled b, bejewelled c
where a.val = b.val
	and a.val = c.val
	and (
		(a.col = b.col - 1 and
			a.row = b.row - 1 and
			a.col = c.col - 1 and
			a.row = c.row - 2) or
		(a.col = b.col - 1 and
			a.row = b.row - 1 and
			a.col = c.col - 1 and 
			a.row = c.row + 1) or
		(a.col = b.col - 1 and 
			a.row = b.row + 1 and
			a.col = c.col - 1 and 
			a.row = c.row + 2) or
		(a.col = b.col - 2 and 
			a.row = b.row and
			a.col = c.col - 3 and 
			a.row = c.row))

The result set is:

row	col	val	dir
6	5	5	d
6	7	6	d
7	8	6	d
7	7	8	u
9	4	7	u
9	9	9	u
3	9	9	r
7	8	6	r
1	1	8	l
5	4	9	l
6	2	2	l
6	7	6	l

	

    
        

    
	

          
Subject: My whack at it...

          
Posted by: Rick Lowrey (not signed in)

          
Posted on: Friday, October 17, 2008 at 2:35 PM

          
Message: /* Create and populate a normalized table... */
create table #temp1 (rownum tinyint, colnum tinyint, value tinyint)

insert into #temp1
select [#], 1, [1] from dbo.bejeweled
union
select [#], 2, [2] from dbo.bejeweled
union
select [#], 3, [3] from dbo.bejeweled
union
select [#], 4, [4] from dbo.bejeweled
union
select [#], 5, [5] from dbo.bejeweled
union
select [#], 6, [6] from dbo.bejeweled
union
select [#], 7, [7] from dbo.bejeweled
union
select [#], 8, [8] from dbo.bejeweled
union
select [#], 9, [9] from dbo.bejeweled

/* Now the important stuff...  */
create table #temp2 (rownum tinyint, colnum tinyint, value tinyint, MoveDir varchar(20))

insert into #temp2
select chk.rownum , chk.colnum, chk.value,
case 
when chk.colnum < focus.colnum then 'Move Left' 
when chk.colnum > focus.colnum then 'Move Right' 
else 'Error!'
end as MoveDir
from #temp1 focus
inner join #temp1 north
on focus.rownum = north.rownum + 1
and focus.colnum = north.colnum
and focus.value = north.value
left join #temp1 chk
on chk.value = focus.value
and chk.rownum = focus.rownum + 1
and 
	(
	chk.colnum = focus.colnum - 1
	or 
	chk.colnum = focus.colnum + 1
	)
where chk.rownum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.colnum < focus.colnum then 'Move Left' 
when chk.colnum > focus.colnum then 'Move Right' 
else 'Error!'
end as MoveDir 
from #temp1 focus
inner join #temp1 south
on focus.rownum = south.rownum - 1
and focus.colnum = south.colnum
and focus.value = south.value
left join #temp1 chk
on chk.value = focus.value
and chk.rownum = focus.rownum - 1
and 
	(
	chk.colnum = focus.colnum - 1
	or 
	chk.colnum = focus.colnum + 1
	)
where chk.rownum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.colnum < focus.colnum then 'Move Left' 
when chk.colnum > focus.colnum then 'Move Right' 
else 'Error!'
end as MoveDir  
from #temp1 focus
inner join #temp1 south
on focus.rownum = south.rownum - 2
and focus.colnum = south.colnum
and focus.value = south.value
left join #temp1 chk
on chk.value = focus.value
and chk.rownum = focus.rownum + 1
and 
	(
	chk.colnum = focus.colnum - 1
	or 
	chk.colnum = focus.colnum + 1
	)
where chk.rownum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.rownum < focus.rownum then 'Move Up' 
when chk.rownum > focus.rownum then 'Move Down' 
else 'Error!'
end as MoveDir
from #temp1 focus
inner join #temp1 north
on focus.colnum = north.colnum + 1
and focus.rownum = north.rownum
and focus.value = north.value
left join #temp1 chk
on chk.value = focus.value
and chk.colnum = focus.colnum + 1
and 
	(
	chk.rownum = focus.rownum - 1
	or 
	chk.rownum = focus.rownum + 1
	)
where chk.colnum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.rownum < focus.rownum then 'Move Up' 
when chk.rownum > focus.rownum then 'Move Down' 
else 'Error!'
end as MoveDir 
from #temp1 focus
inner join #temp1 south
on focus.colnum = south.colnum - 1
and focus.rownum = south.rownum
and focus.value = south.value
left join #temp1 chk
on chk.value = focus.value
and chk.colnum = focus.colnum - 1
and 
	(
	chk.rownum = focus.rownum - 1
	or 
	chk.rownum = focus.rownum + 1
	)
where chk.colnum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.rownum < focus.rownum then 'Move Up' 
when chk.rownum > focus.rownum then 'Move Down' 
else 'Error!'
end as MoveDir  
from #temp1 focus
inner join #temp1 south
on focus.colnum = south.colnum - 2
and focus.rownum = south.rownum
and focus.value = south.value
left join #temp1 chk
on chk.value = focus.value
and chk.colnum = focus.colnum + 1
and 
	(
	chk.rownum = focus.rownum - 1
	or 
	chk.rownum = focus.rownum + 1
	)
where chk.colnum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.rownum < focus.rownum then 'Move Up' 
when chk.rownum > focus.rownum then 'Move Down' 
else 'Error!'
end as MoveDir
from #temp1 focus
inner join #temp1 north
on focus.rownum = north.rownum - 1
and focus.colnum = north.colnum
and focus.value = north.value
left join #temp1 chk
on chk.value = focus.value
and chk.colnum = focus.colnum
and 
	(
	chk.rownum = focus.rownum - 2
	or 
	chk.rownum = focus.rownum + 3
	)
where chk.rownum is not null
UNION
select chk.rownum , chk.colnum, chk.value,
case 
when chk.colnum < focus.rownum then 'Move Left' 
when chk.colnum > focus.rownum then 'Move Right' 
else 'Error!'
end as MoveDir
from #temp1 focus
inner join #temp1 north
on focus.colnum = north.colnum - 1
and focus.rownum = north.rownum
and focus.value = north.value
left join #temp1 chk
on chk.value = focus.value
and chk.rownum = focus.rownum
and 
	(
	chk.colnum = focus.colnum - 2
	or 
	chk.colnum = focus.colnum + 3
	)
where chk.colnum is not null
order by chk.rownum, chk.colnum

/* ...And clean up after yourself... */
drop table #temp1


select distinct RowNum, ColNum, Value from #temp2
select RowNum, ColNum, Value, MoveDir from #temp2
drop table #temp2

/*
Note that if you only want the cells and values to move, you wind up with 10 returned rows... 
and if you include the direction of the move, you wind up with 12 rows.

RowNum ColNum Value
------ ------ -----
1      1      8
3      9      9
5      4      9
6      2      2
6      5      5
6      7      6
7      7      8
7      8      6
9      4      7
9      9      9

(10 row(s) affected)

RowNum ColNum Value MoveDir
------ ------ ----- --------------------
1      1      8     Move Left
3      9      9     Move Right
5      4      9     Move Left
6      2      2     Move Left
6      5      5     Move Up
6      7      6     Move Left
6      7      6     Move Up
7      7      8     Move Down
7      8      6     Move Right
7      8      6     Move Up
9      4      7     Move Down
9      9      9     Move Down

(12 row(s) affected)
*/

	

    
        

    
	

          
Subject: BEJEWELED SOLUTION

          
Posted by: Steve Munson (sgmunson@charter.net or smunson@heritageacademies. (not signed in)

          
Posted on: Friday, October 17, 2008 at 3:04 PM

          
Message: Here's my code:

[code]
/* INITIAL SETUP PROVIDED, modified only to make more clear */
DECLARE @bejeweled TABLE (
 RN tinyint NULL,
 C1 tinyint NULL,
 C2 tinyint NULL,
 C3 tinyint NULL,
 C4 tinyint NULL,
 C5 tinyint NULL,
 C6 tinyint NULL,
 C7 tinyint NULL,
 C8 tinyint NULL,
 C9 tinyint NULL
)
INSERT INTO @bejeweled VALUES(1, 8, 5, 2, 8, 6, 8, 9, 9, 1);
INSERT INTO @bejeweled VALUES(2, 3, 8, 6, 4, 9, 3, 6, 9, 6);
INSERT INTO @bejeweled VALUES(3, 2, 8, 9, 3, 4, 3, 7, 4, 9);
INSERT INTO @bejeweled VALUES(4, 1, 9, 4, 5, 7, 9, 9, 5, 6);
INSERT INTO @bejeweled VALUES(5, 7, 6, 2, 9, 7, 9, 9, 6, 8);
INSERT INTO @bejeweled VALUES(6, 5, 2, 9, 6, 5, 8, 6, 8, 9);
INSERT INTO @bejeweled VALUES(7, 4, 4, 2, 5, 9, 5, 8, 6, 9);
INSERT INTO @bejeweled VALUES(8, 5, 9, 9, 3, 7, 7, 6, 2, 6);
INSERT INTO @bejeweled VALUES(9, 2, 3, 2, 7, 9, 6, 6, 2, 9);

/* TRANSLATE THIS TABLE INTO STRING FORMAT */
DECLARE @ROWS TABLE(
	RN tinyint,
	ROW char(9)
	PRIMARY KEY (RN, ROW)
)
INSERT INTO @ROWS (RN, ROW)
SELECT RN, CAST(C1 AS char(1)) + CAST(C2 AS char(1)) + CAST(C3 AS char(1)) + CAST(C4 AS char(1)) +
	CAST(C5 AS char(1)) + CAST(C6 AS char(1)) + CAST(C7 AS char(1)) + CAST(C8 AS char(1)) + CAST(C9 AS char(1))
FROM @bejeweled

/* CREATE A TABLE OF STRINGS THAT REPRESENT WAYS FOR A CANDIDATE ROW/COL TO MATCH */
DECLARE @MATCH_STRINGS TABLE (
	DIGIT tinyint,
	MS char(3),
	MP tinyint -- matching position (zero-based)
)
INSERT INTO @MATCH_STRINGS (DIGIT, MS, MP)
SELECT 1, '11_', 2 UNION ALL
SELECT 1, '_11', 0 UNION ALL
SELECT 1, '1_1', 1 UNION ALL
SELECT 2, '22_', 2 UNION ALL
SELECT 2, '_22', 0 UNION ALL
SELECT 2, '2_2', 1 UNION ALL
SELECT 3, '33_', 2 UNION ALL
SELECT 3, '_33', 0 UNION ALL
SELECT 3, '3_3', 1 UNION ALL
SELECT 4, '44_', 2 UNION ALL
SELECT 4, '_44', 0 UNION ALL
SELECT 4, '4_4', 1 UNION ALL
SELECT 5, '55_', 2 UNION ALL
SELECT 5, '_55', 0 UNION ALL
SELECT 5, '5_5', 1 UNION ALL
SELECT 6, '66_', 2 UNION ALL
SELECT 6, '_66', 0 UNION ALL
SELECT 6, '6_6', 1 UNION ALL
SELECT 7, '77_', 2 UNION ALL
SELECT 7, '_77', 0 UNION ALL
SELECT 7, '7_7', 1 UNION ALL
SELECT 8, '88_', 2 UNION ALL
SELECT 8, '_88', 0 UNION ALL
SELECT 8, '8_8', 1 UNION ALL
SELECT 9, '99_', 2 UNION ALL
SELECT 9, '_99', 0 UNION ALL
SELECT 9, '9_9', 1

/* DETERMINE CANDIDATE ROWS FOR A LEGAL MOVE INTO FROM ANOTHER ROW, & THE DESTINATION POSITIONS */
DECLARE @CANDIDATE_ROWS TABLE (
	DESTINATION_ROW tinyint,
	DESTINATION_POSITION tinyint,
	DIGIT tinyint,
	ROW_CONTENT char(9),
	CANDIDATE_ROW tinyint
)
INSERT INTO @CANDIDATE_ROWS (DESTINATION_ROW, DESTINATION_POSITION, DIGIT, ROW_CONTENT, CANDIDATE_ROW)
SELECT B.RN AS DESTINATION_ROW, PATINDEX('%'+M.MS+'%', B.ROW) + MP AS DESTINATION_POSITION,
	CAST(LEFT(REPLACE(M.MS,'_',''),1) AS tinyint) AS DIGIT, B.ROW AS ROW_CONTENT, CR.DGT AS CANDIDATE_ROW
FROM @ROWS AS B, @MATCH_STRINGS AS M, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 8) AS N,
	(SELECT DISTINCT CAST(DIGIT AS smallint) AS DGT FROM @MATCH_STRINGS) AS CR
WHERE B.ROW LIKE '%' + M.MS + '%' AND
	PATINDEX(M.MS, SUBSTRING(B.ROW, N.D,3)) > 0 AND
	ABS(CR.DGT - B.RN) = 1
ORDER BY DESTINATION_ROW, DESTINATION_POSITION, DIGIT, CANDIDATE_ROW

/* CREATE A TABLE OF STRINGS FOR THE COLUMNS */
DECLARE @COLS TABLE (
	CN tinyint,
	COL char(9)
)
/* POPULATE THE COLUMNS TABLE FROM THE STRING-BASED ROW TABLE */
DECLARE @COL AS varchar(9), @LOOPER AS tinyint
SET @LOOPER = 1
WHILE @LOOPER < 10
	BEGIN
	SET @COL = ''
	SELECT @COL = @COL + SUBSTRING(ROW,@LOOPER,1) FROM @ROWS
	INSERT INTO @COLS (CN, COL)
	SELECT @LOOPER, @COL
	SET @LOOPER = @LOOPER + 1
	END

/* DETERMINE CANDIDATE COLUMNS FOR A POSSIBLE LEGAL MOVE INTO FROM ANOTHER COLUMN, & THE DESTINATION POSITIONS */
DECLARE @CANDIDATE_COLS TABLE (
	DESTINATION_COLUMN tinyint,
	DESTINATION_POSITION tinyint,
	DIGIT tinyint,
	COLUMN_CONTENT char(9),
	CANDIDATE_COLUMN tinyint
)
INSERT INTO @CANDIDATE_COLS (DESTINATION_COLUMN, DESTINATION_POSITION, DIGIT, COLUMN_CONTENT, CANDIDATE_COLUMN)
SELECT B.CN AS DESTINATION_COLUMN, PATINDEX('%'+M.MS+'%', B.COL) + MP AS DESTINATION_POSITION,
	CAST(LEFT(REPLACE(M.MS,CHAR(95),''),1) AS tinyint) AS DIGIT, B.COL AS COLUMN_CONTENT, CC.DGT AS CANDIDATE_COLUMN
FROM @COLS AS B, @MATCH_STRINGS AS M, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 8) AS N,
	(SELECT DISTINCT CAST(DIGIT AS smallint) AS DGT FROM @MATCH_STRINGS) AS CC
WHERE B.COL LIKE '%' + M.MS + '%' AND
	PATINDEX(M.MS, SUBSTRING(B.COL, N.D,3)) > 0 AND
	ABS(CC.DGT - B.CN) = 1
ORDER BY DESTINATION_COLUMN, DESTINATION_POSITION, DIGIT, CANDIDATE_COLUMN

/* COMPARE CANDIDATE ROWS & COLUMNS WITH ACTUAL DATA FOR MATCHES */
SELECT CANDIDATE_ROW AS SOURCE_ROW, DESTINATION_POSITION AS SOURCE_COLUMN, DIGIT,
	DESTINATION_ROW, DESTINATION_POSITION AS DESTINATION_COLUMN
FROM @CANDIDATE_ROWS AS A, @ROWS AS B
WHERE CANDIDATE_ROW = RN AND
	DIGIT = CAST(SUBSTRING(ROW,DESTINATION_POSITION,1) AS tinyint)
UNION
SELECT DESTINATION_POSITION AS SOURCE_ROW, CANDIDATE_COLUMN AS SOURCE_COLUMN, DIGIT,
	DESTINATION_POSITION AS DESTINATION_ROW, DESTINATION_COLUMN
FROM @CANDIDATE_COLS AS A, @COLS AS B
WHERE CANDIDATE_COLUMN = CN AND
	DIGIT = CAST(SUBSTRING(COL,DESTINATION_POSITION,1) AS tinyint)
UNION
SELECT RN AS SOURCE_ROW,	/* ADD IN THE SAME ROW MOVES */
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', ROW)
		WHEN 2 THEN PATINDEX('%'+MS+'%', ROW) + 3
	END AS SOURCE_COLUMN,
	DIGIT, RN AS DESTINATION_ROW,
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', ROW) + 1
		WHEN 2 THEN PATINDEX('%'+MS+'%', ROW) + 2
	END AS DESTINATION_COLUMN
FROM @ROWS AS A, (
	SELECT DIGIT,
		CASE MP
			WHEN 0 THEN RIGHT(MS,1) + MS
			WHEN 2 THEN MS + LEFT(MS,1)
		END AS MS, MP
	FROM @MATCH_STRINGS
	WHERE MP <> 1) AS B, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 7) AS C
WHERE SUBSTRING(ROW,D,4) LIKE MS
UNION
SELECT			/* ADD IN THE SAME COLUMN MOVES */
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', COL)
		WHEN 2 THEN PATINDEX('%'+MS+'%', COL) + 3
	END AS SOURCE_ROW,
	CN AS SOURCE_COLUMN, DIGIT,
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', COL) + 1
		WHEN 2 THEN PATINDEX('%'+MS+'%', COL) + 2
	END AS DESTINATION_ROW,
	CN AS DESTINATION_COLUMN
FROM @COLS AS A, (
	SELECT DIGIT,
		CASE MP
			WHEN 0 THEN RIGHT(MS,1) + MS
			WHEN 2 THEN MS + LEFT(MS,1)
		END AS MS, MP
	FROM @MATCH_STRINGS
	WHERE MP <> 1) AS B, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 7) AS C
WHERE SUBSTRING(COL,D,4) LIKE MS
ORDER BY SOURCE_ROW, SOURCE_COLUMN
[/code]

It's perhaps a bit long, but it finds all the solutions.

	

    
        

    
	

          
Subject: Solution

          
Posted by: Sneh Agrawal (not signed in)

          
Posted on: Friday, October 17, 2008 at 3:40 PM

          
Message: Here's a simple solution:

declare @count int
declare @sqlstring varchar(1000)
declare @maxCount int

set @SqlString=' '
set @maxCount=(select max(#) from bejeweled )
set @count=1

while @count<=(@maxCount)
begin
set @sqlstring=@SqlString+'select # as RowNumber,'+cast(@count as varchar)+' as ColumnNumber, ['+cast(@count as varchar)+'] as Value from bejeweled '

	If @count<@maxCount
		begin
		set @sqlstring= @SqlString+'Union All '
		end
select @sqlstring
set @count=@count+1
end

exec (@sqlString)

	

    
        

    
	

          
Subject: Correction in the Above post

          
Posted by: Sneh Agrawal (not signed in)

          
Posted on: Friday, October 17, 2008 at 3:44 PM

          
Message: Please comment out the "Select @sqlString" statement after before Set @count=@count+1 :

declare @count int
declare @sqlstring varchar(1000)
declare @maxCount int

set @SqlString=' '
set @maxCount=(select max(#) from bejeweled )
set @count=1

while @count<=(@maxCount)
begin
set @sqlstring=@SqlString+'select # as RowNumber,'+cast(@count as varchar)+' as ColumnNumber, ['+cast(@count as varchar)+'] as Value from bejeweled '

	If @count<@maxCount
		begin
		set @sqlstring= @SqlString+'Union All '
		end
--select @sqlstring
set @count=@count+1
end

exec (@sqlString)

	

    
        

    
	

          
Subject: Bejeweled Solver

          
Posted by: John Arnott (not signed in)

          
Posted on: Friday, October 17, 2008 at 3:47 PM

          
Message: This was an enjoyable excuse to practice the use of the "unpivot" operator.  Thanks for the fun.

-- Create single dimension array in temp table #Jewels
SELECT convert(int,[#]) as Row,convert(int,Col) as Col, Val
into #Jewels
FROM 
    (SELECT [#], [1], [2], [3], [4], [5], [6], [7], [8], [9]
    FROM Bejeweled) p
UNPIVOT
    (Val FOR Col IN 
        ([1], [2], [3], [4], [5], [6], [7], [8], [9])
	)AS unpvt
go

-- Select cells that could be "moved"
--   from a three-way self join.  
Select distinct c.Row, c.Col, c.Val 
  from #Jewels a
  join #Jewels b on b.val = a.val and (b.row = a.row or b.col = a.col)
  join #Jewels c on c.val = a.val
 where (a.row = b.row								                    --matching jewels in same row
		and c.row in (a.row + 1, a.row - 1)                             --candidate jewel in adjacent row
		and (   (b.col - a.col = 2 and c.col = b.col - 1)               --matching jewels two col's apart and candidate is in between
			 or (b.col - a.col = 1 and c.col in (b.col + 1, a.col - 1)) --matching jewels in adjacent columns and candidate is to one side or the other
			)
		)
		or                 
	   (a.col = b.col													--matching jewels in same column
		and c.col in (a.col + 1, a.col - 1)								--candidate jewel in adjacent column
		and (   (b.row - a.row = 2 and c.row = b.row - 1)				--matching jewels two rows apart and candidate is in between
			 or (b.row - a.row = 1 and c.row in (b.row + 1, a.row - 1)) --matching jewels in adjacent rows and candidate is immediately above or below
			)
		)
Order by Row, Col
go
drop table #Jewels


Result:
Row         Col         Val
----------- ----------- ----
1           1           8
3           9           9
6           2           2
6           5           5
6           7           6
7           7           8
7           8           6
9           4           7

(8 row(s) affected)

	

    
        

    
	

          
Subject: List-driven solution

          
Posted by: RBarryYoung (not signed in)

          
Posted on: Saturday, October 18, 2008 at 12:30 AM

          
Message: --====== Create Table of Directions
IF EXISTS(SELECT * FROM sysobjects 
   WHERE ID = (OBJECT_ID('Directions')) AND xtype = 'U')
DROP TABLE Directions
GO
Create Table Directions(row smallint, col smallint)
GO
Insert into Directions Select 1, 0
Union All Select 0, -1
Union All Select -1, 0
Union All Select 0, 1

--====== UnRoll bejeweled into something Relational
IF EXISTS(SELECT * FROM sysobjects 
   WHERE ID = (OBJECT_ID('bejeweled_UR')) AND xtype = 'U')
DROP TABLE bejeweled_UR
GO
Create Table bejeweled_UR(row tinyint, col tinyint, val tinyint)
GO
Insert into bejeweled_UR Select [#], 1, [1] from bejeweled
Union All Select [#], 2, [2] from bejeweled
Union All Select [#], 3, [3] from bejeweled
Union All Select [#], 4, [4] from bejeweled
Union All Select [#], 5, [5] from bejeweled
Union All Select [#], 6, [6] from bejeweled
Union All Select [#], 7, [7] from bejeweled
Union All Select [#], 8, [8] from bejeweled
Union All Select [#], 9, [9] from bejeweled

--======
Select j3.row, j3.col, j3.val
 From bejeweled_UR j1
  Cross Join Directions d1
  Inner Join bejeweled_UR j2 
    ON j2.row = j1.row+d1.row
     And j2.col = j1.col+d1.col
     And j2.val = j1.val
  Inner Join Directions d2 ON d1.row <> -d2.row Or d1.col <> -d2.col
  Inner Join bejeweled_UR j3
    ON j3.row = j1.row+(2*d1.row)+d2.row
     And j3.col = j1.col+(2*d1.col)+d2.col
     And j3.val = j1.val
UNION --Distinct
Select j3.row, j3.col, j3.val
 From bejeweled_UR j1
  Cross Join Directions d1
  Inner Join bejeweled_UR j2 
    ON j2.row = j1.row+2*d1.row
     And j2.col = j1.col+2*d1.col
     And j2.val = j1.val
  Inner Join Directions d2 ON d1.row <> d2.row And d1.col <> d2.col
  Inner Join bejeweled_UR j3
    ON j3.row = j1.row+d1.row+d2.row
     And j3.col = j1.col+d1.col+d2.col
     And j3.val = j1.val

	

    
        

    
	

          
Subject: List-driven solution

          
Posted by: RBarryYoung (view profile)

          
Posted on: Saturday, October 18, 2008 at 12:33 AM

          
Message: --====== Create Table of Directions
IF EXISTS(SELECT * FROM sysobjects 
   WHERE ID = (OBJECT_ID('Directions')) AND xtype = 'U')
DROP TABLE Directions
GO
Create Table Directions(row smallint, col smallint)
GO
Insert into Directions Select 1, 0
Union All Select 0, -1
Union All Select -1, 0
Union All Select 0, 1

--====== UnRoll bejeweled into something Relational
IF EXISTS(SELECT * FROM sysobjects 
   WHERE ID = (OBJECT_ID('bejeweled_UR')) AND xtype = 'U')
DROP TABLE bejeweled_UR
GO
Create Table bejeweled_UR(row tinyint, col tinyint, val tinyint)
GO
Insert into bejeweled_UR Select [#], 1, [1] from bejeweled
Union All Select [#], 2, [2] from bejeweled
Union All Select [#], 3, [3] from bejeweled
Union All Select [#], 4, [4] from bejeweled
Union All Select [#], 5, [5] from bejeweled
Union All Select [#], 6, [6] from bejeweled
Union All Select [#], 7, [7] from bejeweled
Union All Select [#], 8, [8] from bejeweled
Union All Select [#], 9, [9] from bejeweled

--======
Select j3.row, j3.col, j3.val
 From bejeweled_UR j1
  Cross Join Directions d1
  Inner Join bejeweled_UR j2 
    ON j2.row = j1.row+d1.row
     And j2.col = j1.col+d1.col
     And j2.val = j1.val
  Inner Join Directions d2 ON d1.row <> -d2.row Or d1.col <> -d2.col
  Inner Join bejeweled_UR j3
    ON j3.row = j1.row+(2*d1.row)+d2.row
     And j3.col = j1.col+(2*d1.col)+d2.col
     And j3.val = j1.val
UNION --Distinct
Select j3.row, j3.col, j3.val
 From bejeweled_UR j1
  Cross Join Directions d1
  Inner Join bejeweled_UR j2 
    ON j2.row = j1.row+2*d1.row
     And j2.col = j1.col+2*d1.col
     And j2.val = j1.val
  Inner Join Directions d2 ON d1.row <> d2.row And d1.col <> d2.col
  Inner Join bejeweled_UR j3
    ON j3.row = j1.row+d1.row+d2.row
     And j3.col = j1.col+d1.col+d2.col
     And j3.val = j1.val

	

    
        

    
	

          
Subject: Holy Left Joins

          
Posted by: Garadin (view profile)

          
Posted on: Sunday, October 19, 2008 at 3:49 PM

          
Message: This grew a bit farther than I thought it would when I started, so it's not nearly as simple as I originally thought it would be.  Probably not the best solution presented thus far, but this also works.  Sorry I couldn't get it to color, but it kept saying the post was too long when I did.

---------------- SETUP --------------------------
-- Like Many others, I chose to change the table format
-- I also added a "few" fields
IF EXISTS(Select * from sysobjects where Name = 'BJ2') DROP TABLE BJ2

CREATE TABLE BJ2(
Col		int,
Row		int,
Value		int,
CF2		int,
CF3		int,
CB2		int,
CB3		int,
U2		int,
U3		int,
D2		int,
D3		int,
UB		int,
UB2		int,
UF		int,
UF2		int,
U2F		int,
U2B		int,
DB		int,
DB2		int,
DF		int,
DF2		int,
D2F		int,
D2B		int,
PRIMARY KEY CLUSTERED (Row, Col))

INSERT INTO BJ2(Col, Row, Value)
SELECT 1,#,[1] FROM Bejeweled UNION ALL
SELECT 2,#,[2] FROM Bejeweled UNION ALL
SELECT 3,#,[3] FROM Bejeweled UNION ALL
SELECT 4,#,[4] FROM Bejeweled UNION ALL
SELECT 5,#,[5] FROM Bejeweled UNION ALL
SELECT 6,#,[6] FROM Bejeweled UNION ALL
SELECT 7,#,[7] FROM Bejeweled UNION ALL
SELECT 8,#,[8] FROM Bejeweled UNION ALL
SELECT 9,#,[9] FROM Bejeweled 
-------------------------------------------------
-- Table is Updated with pertinent nearby values that could be matches

UPDATE BJ2
SET 	CF2 	= ISNULL(CF2.Value,0),
	CF3 	= ISNULL(CF3.Value,0),
	CB2	= ISNULL(CB2.Value,0),
	CB3	= ISNULL(CB3.Value,0),
	U2	= ISNULL(U2.Value,0),
	U3 	= ISNULL(U3.Value,0),
	D2	= ISNULL(D2.Value,0),
	D3	= ISNULL(D3.Value,0),
	UB	= ISNULL(UB.Value,0),
	UB2	= ISNULL(UB2.Value,0),
	UF	= ISNULL(UF.Value,0),
	UF2	= ISNULL(UF2.Value,0),
	U2F	= ISNULL(U2F.Value,0),
	U2B	= ISNULL(U2B.Value, 0),
	DB	= ISNULL(DB.Value,0),
	DB2	= ISNULL(DB2.Value,0),
	DF	= ISNULL(DF.Value,0),
	DF2	= ISNULL(DF2.Value,0),
	D2F	= ISNULL(D2F.Value,0),
	D2B	= ISNULL(D2B.Value,0)
FROM BJ2 
	LEFT JOIN BJ2 CF2 ON BJ2.Col + 2 = CF2.Col AND BJ2.Row = CF2.Row 	-- 2 Columns Forward (Right)
	LEFT JOIN BJ2 CF3 ON BJ2.Col + 3 = CF3.Col AND BJ2.Row = CF3.Row 	-- 3 Columns Forward (Right)
	LEFT JOIN BJ2 CB2 ON BJ2.Col - 2 = CB2.Col AND BJ2.Row = CB2.Row 	-- 2 Columns Backward (Left)
	LEFT JOIN BJ2 CB3 ON BJ2.Col - 3 = CB3.Col AND BJ2.Row = CB3.Row 	-- 3 Columns Backward (Left)
	LEFT JOIN BJ2 U2  ON BJ2.Col = U2.Col      AND BJ2.Row - 2 = U2.Row	-- Up 2
	LEFT JOIN BJ2 U3  ON BJ2.Col = U3.Col      AND BJ2.Row - 3 = U3.Row	-- Up 3
	LEFT JOIN BJ2 D2  ON BJ2.Col = D2.Col      AND BJ2.Row + 2 = D2.Row	-- Down 2
	LEFT JOIN BJ2 D3  ON BJ2.Col = D3.Col      AND BJ2.Row + 3 = D3.Row	-- Down 3
	LEFT JOIN BJ2 UB  ON BJ2.Col - 1 = UB.Col  AND BJ2.Row - 1 = UB.Row 	-- Up 1 Back 1
	LEFT JOIN BJ2 UB2 ON BJ2.Col - 2 = UB2.Col AND BJ2.Row - 1 = UB2.Row	-- Up 1 Back 2
	LEFT JOIN BJ2 UF  ON BJ2.Col + 1 = UF.Col  AND BJ2.Row - 1 = UF.Row	-- Up 1 Forward 1
	LEFT JOIN BJ2 UF2 ON BJ2.Col + 2 = UF2.Col AND BJ2.Row - 1 = UF2.Row	-- Up 1 Forward 2
	LEFT JOIN BJ2 U2F ON BJ2.Col + 1 = U2F.Col AND BJ2.Row - 2 = U2F.Row	-- Up 2 Forward 1
	LEFT JOIN BJ2 U2B ON BJ2.Col - 1 = U2B.Col AND BJ2.Row - 2 = U2B.Row	-- Up 2 Back 1
	LEFT JOIN BJ2 DB  ON BJ2.Col - 1 = DB.Col  AND BJ2.Row + 1 = DB.Row	-- Down 1 Back 1
	LEFT JOIN BJ2 DB2 ON BJ2.Col - 2 = DB2.Col AND BJ2.Row + 1 = DB2.Row	-- Down 1 Back 2
	LEFT JOIN BJ2 DF  ON BJ2.Col + 1 = DF.Col  AND BJ2.Row + 1 = DF.Row	-- Down 1 Forward 1
	LEFT JOIN BJ2 DF2 ON BJ2.Col + 2 = DF2.Col AND BJ2.Row + 1 = DF2.Row	-- Down 1 Forward 2
	LEFT JOIN BJ2 D2F ON BJ2.Col + 1 = D2F.Col AND BJ2.Row + 2 = D2F.Row	-- Down 2 Forward 1
	LEFT JOIN BJ2 D2B ON BJ2.Col - 1 = D2B.Col AND BJ2.Row + 2 = D2B.Row	-- Down 2 Back 1 

--- Any possible matches are selected.
SELECT Row, Col, Value 
FROM BJ2
WHERE 		(Value = CF2 AND Value = CF3) 	-- Move Right (Match Right)
	OR	(Value = UF  AND Value = DF )	-- Move Right (Match Top/Bot)   
	OR	(Value = UF  AND Value = U2F)	-- Move Right (Match Top)
	OR	(Value = DF  AND Value = D2F)	-- Move Right (Match Bot)
	OR 	(Value = CB2 AND Value = CB3)	-- Move Left  (Match Left)
	OR	(Value = UB  AND Value = DB )	-- Move Left  (Match Top/Bot)
	OR	(Value = UB  AND Value = U2B)	-- Move Left  (Match Top)
	OR	(Value = DB  AND Value = D2B)	-- Move Left  (Match Bot)
	OR 	(Value = UF  AND Value = UF2)	-- Move Up (Match Right)
	OR	(Value = UB  AND Value = UB2)	-- Move Up (Match Left)
	OR	(Value = U2  AND Value = U3)	-- Move Up (Match Up)
	OR	(Value = UF  AND Value = UB)	-- Move Up (Match Left/Right)
	OR	(Value = DF  AND Value = DF2)	-- Move Down (Match Right)
	OR	(Value = DB  AND Value = DB2)	-- Move Down (Match Left)
	OR	(Value = D2  AND Value = D3)	-- Move Down (Match Down)
	OR	(Value = DF  AND Value = DB)	-- Move Down (Match Left/Right) 
ORDER BY Row, Col, Value

----------  RESULTS  ---------------
--	Row	Col	Value
-- 	1	1	8
--	3	9	9
--	5	4	9
--	6	2	2
--	6	5	5
--	6	7	6
--	7	7	8
--	7	8	6
--	9	4	7
--	9	9	9

	

    
        

    
	

          
Subject: Holy Left Joins

          
Posted by: Garadin (view profile)

          
Posted on: Sunday, October 19, 2008 at 5:43 PM

          
Message: This grew a bit farther than I thought it would when I started, so it's not nearly as simple as I originally thought it would be.  Probably not the best solution presented thus far, but this also works.  Sorry I couldn't get it to color, but it kept saying the post was too long when I did.

---------------- SETUP --------------------------
-- Like Many others, I chose to change the table format
-- I also added a "few" fields
IF EXISTS(Select * from sysobjects where Name = 'BJ2') DROP TABLE BJ2

CREATE TABLE BJ2(
Col		int,
Row		int,
Value		int,
CF2		int,
CF3		int,
CB2		int,
CB3		int,
U2		int,
U3		int,
D2		int,
D3		int,
UB		int,
UB2		int,
UF		int,
UF2		int,
U2F		int,
U2B		int,
DB		int,
DB2		int,
DF		int,
DF2		int,
D2F		int,
D2B		int,
PRIMARY KEY CLUSTERED (Row, Col))

INSERT INTO BJ2(Col, Row, Value)
SELECT 1,#,[1] FROM Bejeweled UNION ALL
SELECT 2,#,[2] FROM Bejeweled UNION ALL
SELECT 3,#,[3] FROM Bejeweled UNION ALL
SELECT 4,#,[4] FROM Bejeweled UNION ALL
SELECT 5,#,[5] FROM Bejeweled UNION ALL
SELECT 6,#,[6] FROM Bejeweled UNION ALL
SELECT 7,#,[7] FROM Bejeweled UNION ALL
SELECT 8,#,[8] FROM Bejeweled UNION ALL
SELECT 9,#,[9] FROM Bejeweled 
-------------------------------------------------
-- Table is Updated with pertinent nearby values that could be matches

UPDATE BJ2
SET 	CF2 	= ISNULL(CF2.Value,0),
	CF3 	= ISNULL(CF3.Value,0),
	CB2	= ISNULL(CB2.Value,0),
	CB3	= ISNULL(CB3.Value,0),
	U2	= ISNULL(U2.Value,0),
	U3 	= ISNULL(U3.Value,0),
	D2	= ISNULL(D2.Value,0),
	D3	= ISNULL(D3.Value,0),
	UB	= ISNULL(UB.Value,0),
	UB2	= ISNULL(UB2.Value,0),
	UF	= ISNULL(UF.Value,0),
	UF2	= ISNULL(UF2.Value,0),
	U2F	= ISNULL(U2F.Value,0),
	U2B	= ISNULL(U2B.Value, 0),
	DB	= ISNULL(DB.Value,0),
	DB2	= ISNULL(DB2.Value,0),
	DF	= ISNULL(DF.Value,0),
	DF2	= ISNULL(DF2.Value,0),
	D2F	= ISNULL(D2F.Value,0),
	D2B	= ISNULL(D2B.Value,0)
FROM BJ2 
	LEFT JOIN BJ2 CF2 ON BJ2.Col + 2 = CF2.Col AND BJ2.Row = CF2.Row 	-- 2 Columns Forward (Right)
	LEFT JOIN BJ2 CF3 ON BJ2.Col + 3 = CF3.Col AND BJ2.Row = CF3.Row 	-- 3 Columns Forward (Right)
	LEFT JOIN BJ2 CB2 ON BJ2.Col - 2 = CB2.Col AND BJ2.Row = CB2.Row 	-- 2 Columns Backward (Left)
	LEFT JOIN BJ2 CB3 ON BJ2.Col - 3 = CB3.Col AND BJ2.Row = CB3.Row 	-- 3 Columns Backward (Left)
	LEFT JOIN BJ2 U2  ON BJ2.Col = U2.Col      AND BJ2.Row - 2 = U2.Row	-- Up 2
	LEFT JOIN BJ2 U3  ON BJ2.Col = U3.Col      AND BJ2.Row - 3 = U3.Row	-- Up 3
	LEFT JOIN BJ2 D2  ON BJ2.Col = D2.Col      AND BJ2.Row + 2 = D2.Row	-- Down 2
	LEFT JOIN BJ2 D3  ON BJ2.Col = D3.Col      AND BJ2.Row + 3 = D3.Row	-- Down 3
	LEFT JOIN BJ2 UB  ON BJ2.Col - 1 = UB.Col  AND BJ2.Row - 1 = UB.Row 	-- Up 1 Back 1
	LEFT JOIN BJ2 UB2 ON BJ2.Col - 2 = UB2.Col AND BJ2.Row - 1 = UB2.Row	-- Up 1 Back 2
	LEFT JOIN BJ2 UF  ON BJ2.Col + 1 = UF.Col  AND BJ2.Row - 1 = UF.Row	-- Up 1 Forward 1
	LEFT JOIN BJ2 UF2 ON BJ2.Col + 2 = UF2.Col AND BJ2.Row - 1 = UF2.Row	-- Up 1 Forward 2
	LEFT JOIN BJ2 U2F ON BJ2.Col + 1 = U2F.Col AND BJ2.Row - 2 = U2F.Row	-- Up 2 Forward 1
	LEFT JOIN BJ2 U2B ON BJ2.Col - 1 = U2B.Col AND BJ2.Row - 2 = U2B.Row	-- Up 2 Back 1
	LEFT JOIN BJ2 DB  ON BJ2.Col - 1 = DB.Col  AND BJ2.Row + 1 = DB.Row	-- Down 1 Back 1
	LEFT JOIN BJ2 DB2 ON BJ2.Col - 2 = DB2.Col AND BJ2.Row + 1 = DB2.Row	-- Down 1 Back 2
	LEFT JOIN BJ2 DF  ON BJ2.Col + 1 = DF.Col  AND BJ2.Row + 1 = DF.Row	-- Down 1 Forward 1
	LEFT JOIN BJ2 DF2 ON BJ2.Col + 2 = DF2.Col AND BJ2.Row + 1 = DF2.Row	-- Down 1 Forward 2
	LEFT JOIN BJ2 D2F ON BJ2.Col + 1 = D2F.Col AND BJ2.Row + 2 = D2F.Row	-- Down 2 Forward 1
	LEFT JOIN BJ2 D2B ON BJ2.Col - 1 = D2B.Col AND BJ2.Row + 2 = D2B.Row	-- Down 2 Back 1 

--- Any possible matches are selected.
SELECT Row, Col, Value 
FROM BJ2
WHERE 		(Value = CF2 AND Value = CF3) 	-- Move Right (Match Right)
	OR	(Value = UF  AND Value = DF )	-- Move Right (Match Top/Bot)   
	OR	(Value = UF  AND Value = U2F)	-- Move Right (Match Top)
	OR	(Value = DF  AND Value = D2F)	-- Move Right (Match Bot)
	OR 	(Value = CB2 AND Value = CB3)	-- Move Left  (Match Left)
	OR	(Value = UB  AND Value = DB )	-- Move Left  (Match Top/Bot)
	OR	(Value = UB  AND Value = U2B)	-- Move Left  (Match Top)
	OR	(Value = DB  AND Value = D2B)	-- Move Left  (Match Bot)
	OR 	(Value = UF  AND Value = UF2)	-- Move Up (Match Right)
	OR	(Value = UB  AND Value = UB2)	-- Move Up (Match Left)
	OR	(Value = U2  AND Value = U3)	-- Move Up (Match Up)
	OR	(Value = UF  AND Value = UB)	-- Move Up (Match Left/Right)
	OR	(Value = DF  AND Value = DF2)	-- Move Down (Match Right)
	OR	(Value = DB  AND Value = DB2)	-- Move Down (Match Left)
	OR	(Value = D2  AND Value = D3)	-- Move Down (Match Down)
	OR	(Value = DF  AND Value = DB)	-- Move Down (Match Left/Right) 
ORDER BY Row, Col, Value

----------  RESULTS  ---------------
--	Row	Col	Value
-- 	1	1	8
--	3	9	9
--	5	4	9
--	6	2	2
--	6	5	5
--	6	7	6
--	7	7	8
--	7	8	6
--	9	4	7
--	9	9	9

	

    
        

    
	

          
Subject: Another Solution

          
Posted by: AmandaS (view profile)

          
Posted on: Monday, October 20, 2008 at 1:45 AM

          
Message: DECLARE @tbl_bejewelled Table (RowNum int NOT NULL, ColumnNum int NOT NULL, Value int NOT NULL)
DECLARE @tbl_offsets Table (i int NOT NULL, j int NOT NULL, k int NOT NULL, l int NOT NULL)
DECLARE @tbl_results Table (RowNum int NOT NULL, ColumnNum int NOT NULL, Value int NOT NULL)
DECLARE @i int, @j int, @k int, @l int

-- Unpivoted version of table stored in table variable
INSERT INTO @tbl_bejewelled
	(RowNum, ColumnNum, Value)
SELECT # As RowNum, CAST(ColumnNum As int) As ColumnNum, Value
FROM bejeweled
UNPIVOT 
	(Value FOR ColumnNum IN ([1],[2],[3],[4],[5],[6],[7],[8],[9]))AS unpvt
-- Store various joining offsets required
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 0, -2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 0, 3)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 1, 2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, -1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, -1, 2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 2, 1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 2, -1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 2, 0)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -3, 0)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -2, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -2, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (2, 0, -1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (2, 0, -1, -1)
-- I don't really like using cursors but I'm trying to make the code concise
DECLARE offset_cursor CURSOR FOR 
SELECT i, j, k, l FROM @tbl_offsets

OPEN offset_cursor

FETCH NEXT FROM offset_cursor INTO @i, @j, @k, @l
WHILE @@FETCH_STATUS = 0
BEGIN
	INSERT INTO @tbl_results (RowNum, ColumnNum, Value)
	SELECT M.RowNum, M.ColumnNum, M.Value
	FROM
		@tbl_bejewelled As A
		JOIN
		@tbl_bejewelled As B
		On A.RowNum + @i = B.RowNum AND A.ColumnNum + @j = B.ColumnNum
		JOIN
		@tbl_bejewelled As M	
		On M.RowNum + @k = A.RowNum AND A.ColumnNum + @l = M.ColumnNum
	WHERE
		A.Value = B.Value AND A.Value = M.Value

	FETCH NEXT FROM offset_cursor INTO @i, @j, @k, @l
END

CLOSE offset_cursor
DEALLOCATE offset_cursor

SELECT Distinct * FROM @tbl_results

	

    
        

    
	

          
Subject: Solution Results

          
Posted by: AmandaS (view profile)

          
Posted on: Monday, October 20, 2008 at 1:49 AM

          
Message: RowNum      ColumnNum   Value
----------- ----------- -----------
1           1           8
3           9           9
5           4           9
6           2           2
6           5           5
6           7           6
7           7           8
7           8           6
9           4           7
9           9           9

	

    
        

    
	

          
Subject: Forgot to include results. Can't paste pretty version of code though: too long

          
Posted by: Stephen Munson (sgmunson@charter.net or smunson@heritageacademie (not signed in)

          
Posted on: Monday, October 20, 2008 at 10:32 AM

          
Message: SOURCE_ROW	SOURCE_COLUMN	DIGIT	DESTINATION_ROW	DESTINATION_COLUMN
1	1	8	1	2
3	9	9	3	8
5	4	9	5	5
6	2	2	6	3
6	5	5	7	5
6	7	6	6	8
6	7	6	7	7
7	7	8	6	7
7	8	6	7	7
7	8	6	8	8
9	4	7	8	4
9	9	9	8	9

	

    
        

    
	

          
Subject: BEJEWELED SOLUTION

          
Posted by: Steve Munson (sgmunson@charter.net or smunson@heritageacademies. (not signed in)

          
Posted on: Monday, October 20, 2008 at 10:37 AM

          
Message: Here's my code:

[code]
/* INITIAL SETUP PROVIDED, modified only to make more clear */
DECLARE @bejeweled TABLE (
 RN tinyint NULL,
 C1 tinyint NULL,
 C2 tinyint NULL,
 C3 tinyint NULL,
 C4 tinyint NULL,
 C5 tinyint NULL,
 C6 tinyint NULL,
 C7 tinyint NULL,
 C8 tinyint NULL,
 C9 tinyint NULL
)
INSERT INTO @bejeweled VALUES(1, 8, 5, 2, 8, 6, 8, 9, 9, 1);
INSERT INTO @bejeweled VALUES(2, 3, 8, 6, 4, 9, 3, 6, 9, 6);
INSERT INTO @bejeweled VALUES(3, 2, 8, 9, 3, 4, 3, 7, 4, 9);
INSERT INTO @bejeweled VALUES(4, 1, 9, 4, 5, 7, 9, 9, 5, 6);
INSERT INTO @bejeweled VALUES(5, 7, 6, 2, 9, 7, 9, 9, 6, 8);
INSERT INTO @bejeweled VALUES(6, 5, 2, 9, 6, 5, 8, 6, 8, 9);
INSERT INTO @bejeweled VALUES(7, 4, 4, 2, 5, 9, 5, 8, 6, 9);
INSERT INTO @bejeweled VALUES(8, 5, 9, 9, 3, 7, 7, 6, 2, 6);
INSERT INTO @bejeweled VALUES(9, 2, 3, 2, 7, 9, 6, 6, 2, 9);

/* TRANSLATE THIS TABLE INTO STRING FORMAT */
DECLARE @ROWS TABLE(
	RN tinyint,
	ROW char(9)
	PRIMARY KEY (RN, ROW)
)
INSERT INTO @ROWS (RN, ROW)
SELECT RN, CAST(C1 AS char(1)) + CAST(C2 AS char(1)) + CAST(C3 AS char(1)) + CAST(C4 AS char(1)) +
	CAST(C5 AS char(1)) + CAST(C6 AS char(1)) + CAST(C7 AS char(1)) + CAST(C8 AS char(1)) + CAST(C9 AS char(1))
FROM @bejeweled

/* CREATE A TABLE OF STRINGS THAT REPRESENT WAYS FOR A CANDIDATE ROW/COL TO MATCH */
DECLARE @MATCH_STRINGS TABLE (
	DIGIT tinyint,
	MS char(3),
	MP tinyint -- matching position (zero-based)
)
INSERT INTO @MATCH_STRINGS (DIGIT, MS, MP)
SELECT 1, '11_', 2 UNION ALL
SELECT 1, '_11', 0 UNION ALL
SELECT 1, '1_1', 1 UNION ALL
SELECT 2, '22_', 2 UNION ALL
SELECT 2, '_22', 0 UNION ALL
SELECT 2, '2_2', 1 UNION ALL
SELECT 3, '33_', 2 UNION ALL
SELECT 3, '_33', 0 UNION ALL
SELECT 3, '3_3', 1 UNION ALL
SELECT 4, '44_', 2 UNION ALL
SELECT 4, '_44', 0 UNION ALL
SELECT 4, '4_4', 1 UNION ALL
SELECT 5, '55_', 2 UNION ALL
SELECT 5, '_55', 0 UNION ALL
SELECT 5, '5_5', 1 UNION ALL
SELECT 6, '66_', 2 UNION ALL
SELECT 6, '_66', 0 UNION ALL
SELECT 6, '6_6', 1 UNION ALL
SELECT 7, '77_', 2 UNION ALL
SELECT 7, '_77', 0 UNION ALL
SELECT 7, '7_7', 1 UNION ALL
SELECT 8, '88_', 2 UNION ALL
SELECT 8, '_88', 0 UNION ALL
SELECT 8, '8_8', 1 UNION ALL
SELECT 9, '99_', 2 UNION ALL
SELECT 9, '_99', 0 UNION ALL
SELECT 9, '9_9', 1

/* DETERMINE CANDIDATE ROWS FOR A LEGAL MOVE INTO FROM ANOTHER ROW, & THE DESTINATION POSITIONS */
DECLARE @CANDIDATE_ROWS TABLE (
	DESTINATION_ROW tinyint,
	DESTINATION_POSITION tinyint,
	DIGIT tinyint,
	ROW_CONTENT char(9),
	CANDIDATE_ROW tinyint
)
INSERT INTO @CANDIDATE_ROWS (DESTINATION_ROW, DESTINATION_POSITION, DIGIT, ROW_CONTENT, CANDIDATE_ROW)
SELECT B.RN AS DESTINATION_ROW, PATINDEX('%'+M.MS+'%', B.ROW) + MP AS DESTINATION_POSITION,
	CAST(LEFT(REPLACE(M.MS,'_',''),1) AS tinyint) AS DIGIT, B.ROW AS ROW_CONTENT, CR.DGT AS CANDIDATE_ROW
FROM @ROWS AS B, @MATCH_STRINGS AS M, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 8) AS N,
	(SELECT DISTINCT CAST(DIGIT AS smallint) AS DGT FROM @MATCH_STRINGS) AS CR
WHERE B.ROW LIKE '%' + M.MS + '%' AND
	PATINDEX(M.MS, SUBSTRING(B.ROW, N.D,3)) > 0 AND
	ABS(CR.DGT - B.RN) = 1
ORDER BY DESTINATION_ROW, DESTINATION_POSITION, DIGIT, CANDIDATE_ROW

/* CREATE A TABLE OF STRINGS FOR THE COLUMNS */
DECLARE @COLS TABLE (
	CN tinyint,
	COL char(9)
)
/* POPULATE THE COLUMNS TABLE FROM THE STRING-BASED ROW TABLE */
DECLARE @COL AS varchar(9), @LOOPER AS tinyint
SET @LOOPER = 1
WHILE @LOOPER < 10
	BEGIN
	SET @COL = ''
	SELECT @COL = @COL + SUBSTRING(ROW,@LOOPER,1) FROM @ROWS
	INSERT INTO @COLS (CN, COL)
	SELECT @LOOPER, @COL
	SET @LOOPER = @LOOPER + 1
	END

/* DETERMINE CANDIDATE COLUMNS FOR A POSSIBLE LEGAL MOVE INTO FROM ANOTHER COLUMN, & THE DESTINATION POSITIONS */
DECLARE @CANDIDATE_COLS TABLE (
	DESTINATION_COLUMN tinyint,
	DESTINATION_POSITION tinyint,
	DIGIT tinyint,
	COLUMN_CONTENT char(9),
	CANDIDATE_COLUMN tinyint
)
INSERT INTO @CANDIDATE_COLS (DESTINATION_COLUMN, DESTINATION_POSITION, DIGIT, COLUMN_CONTENT, CANDIDATE_COLUMN)
SELECT B.CN AS DESTINATION_COLUMN, PATINDEX('%'+M.MS+'%', B.COL) + MP AS DESTINATION_POSITION,
	CAST(LEFT(REPLACE(M.MS,CHAR(95),''),1) AS tinyint) AS DIGIT, B.COL AS COLUMN_CONTENT, CC.DGT AS CANDIDATE_COLUMN
FROM @COLS AS B, @MATCH_STRINGS AS M, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 8) AS N,
	(SELECT DISTINCT CAST(DIGIT AS smallint) AS DGT FROM @MATCH_STRINGS) AS CC
WHERE B.COL LIKE '%' + M.MS + '%' AND
	PATINDEX(M.MS, SUBSTRING(B.COL, N.D,3)) > 0 AND
	ABS(CC.DGT - B.CN) = 1
ORDER BY DESTINATION_COLUMN, DESTINATION_POSITION, DIGIT, CANDIDATE_COLUMN

/* COMPARE CANDIDATE ROWS & COLUMNS WITH ACTUAL DATA FOR MATCHES */
SELECT CANDIDATE_ROW AS SOURCE_ROW, DESTINATION_POSITION AS SOURCE_COLUMN, DIGIT,
	DESTINATION_ROW, DESTINATION_POSITION AS DESTINATION_COLUMN
FROM @CANDIDATE_ROWS AS A, @ROWS AS B
WHERE CANDIDATE_ROW = RN AND
	DIGIT = CAST(SUBSTRING(ROW,DESTINATION_POSITION,1) AS tinyint)
UNION
SELECT DESTINATION_POSITION AS SOURCE_ROW, CANDIDATE_COLUMN AS SOURCE_COLUMN, DIGIT,
	DESTINATION_POSITION AS DESTINATION_ROW, DESTINATION_COLUMN
FROM @CANDIDATE_COLS AS A, @COLS AS B
WHERE CANDIDATE_COLUMN = CN AND
	DIGIT = CAST(SUBSTRING(COL,DESTINATION_POSITION,1) AS tinyint)
UNION
SELECT RN AS SOURCE_ROW,	/* ADD IN THE SAME ROW MOVES */
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', ROW)
		WHEN 2 THEN PATINDEX('%'+MS+'%', ROW) + 3
	END AS SOURCE_COLUMN,
	DIGIT, RN AS DESTINATION_ROW,
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', ROW) + 1
		WHEN 2 THEN PATINDEX('%'+MS+'%', ROW) + 2
	END AS DESTINATION_COLUMN
FROM @ROWS AS A, (
	SELECT DIGIT,
		CASE MP
			WHEN 0 THEN RIGHT(MS,1) + MS
			WHEN 2 THEN MS + LEFT(MS,1)
		END AS MS, MP
	FROM @MATCH_STRINGS
	WHERE MP <> 1) AS B, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 7) AS C
WHERE SUBSTRING(ROW,D,4) LIKE MS
UNION
SELECT			/* ADD IN THE SAME COLUMN MOVES */
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', COL)
		WHEN 2 THEN PATINDEX('%'+MS+'%', COL) + 3
	END AS SOURCE_ROW,
	CN AS SOURCE_COLUMN, DIGIT,
	CASE MP
		WHEN 0 THEN PATINDEX('%'+MS+'%', COL) + 1
		WHEN 2 THEN PATINDEX('%'+MS+'%', COL) + 2
	END AS DESTINATION_ROW,
	CN AS DESTINATION_COLUMN
FROM @COLS AS A, (
	SELECT DIGIT,
		CASE MP
			WHEN 0 THEN RIGHT(MS,1) + MS
			WHEN 2 THEN MS + LEFT(MS,1)
		END AS MS, MP
	FROM @MATCH_STRINGS
	WHERE MP <> 1) AS B, (SELECT DISTINCT DIGIT AS D FROM @MATCH_STRINGS WHERE DIGIT < 7) AS C
WHERE SUBSTRING(COL,D,4) LIKE MS
ORDER BY SOURCE_ROW, SOURCE_COLUMN
[/code]

It's perhaps a bit long, but it finds all the solutions.

	

    
        

    
	

          
Subject: Bejeweled Solution

          
Posted by: Dennis A (not signed in)

          
Posted on: Monday, October 20, 2008 at 10:49 AM

          
Message: There are some fantastic solutions here.  I came at the problem from the idea that I would have to solve again and again, so I wanted to make the solution finding as efficient as possible.  To that end, I create a table named Bejeweled_Moves that list all 888 possible moves on the board that could result in a match.

My solution has a lot of one time query script, so I will just show the solution, and then highlight the Bejeweled_Moves table.

-- Split the "table" into individual "cells" ----------------------------------
DECLARE @board table ( id int IDENTITY(1,1), row tinyint, col tinyint, value tinyint )

INSERT INTO @board ( row, col, value )
SELECT row, col, value
FROM (	  SELECT [#] AS row, 1 AS col, [1] AS value FROM dbo.Bejeweled
	UNION SELECT [#], 2, [2] FROM dbo.Bejeweled
	UNION SELECT [#], 3, [3] FROM dbo.Bejeweled
	UNION SELECT [#], 4, [4] FROM dbo.Bejeweled
	UNION SELECT [#], 5, [5] FROM dbo.Bejeweled
	UNION SELECT [#], 6, [6] FROM dbo.Bejeweled
	UNION SELECT [#], 7, [7] FROM dbo.Bejeweled
	UNION SELECT [#], 8, [8] FROM dbo.Bejeweled
	UNION SELECT [#], 9, [9] FROM dbo.Bejeweled
	) AS board
ORDER BY row, col


-- Find all if the moves that will result in a match --------------------------
SELECT mv.row, mv.col, mv.value
FROM dbo.Bejeweled_Moves AS m
INNER JOIN @board AS mv  ON mv.id = m.move
INNER JOIN @board AS k1v ON k1v.id = m.keep1
INNER JOIN @board AS k2v ON k2v.id = m.keep2
WHERE mv.value = k1v.value AND mv.value = k2v.value
ORDER BY mv.row ASC, mv.col ASC



CREATE TABLE dbo.Bejewled_Moves ( id int IDENTITY(1,1), move int, swap int, keep1 int, keep2 int )

-- one-time construction of moves table.
INSERT INTO dbo.Bejewled_Moves ( move, swap, keep1, keep2 )
SELECT 1 AS move, 10 AS swap, 11 AS keep1, 12 AS keep2
UNION SELECT 1, 10, 19, 28
UNION SELECT 1, 2, 11, 20
UNION SELECT 1, 2, 3, 4


And to build the query to discover and insert the moves, I used another query that analyzed the 16 possible styles of moves to find all valid combination for a 9x9 board.  The query clip below uses a table named @cells which is just a numbers table with [id] values between 1 and 81, matching the [id] values in the @board table in the solution. (again only the first is show because this is long enough already)

-- #1 move (up left) right, above 2 vertical
select 'union select ' + convert(varchar,m.id) + ', ' + convert(varchar,k1.id -9) + ', ' + convert(varchar,k1.id) + ', ' + convert(varchar,k2.id)
from @cells as k1
inner join @cells as k2 on k2.id = k1.id  +9 /* c1 is a matching cell directly above c2 */
inner join @cells as m  on  m.id = k1.id -10 /* m is up one row and left 1 column */
where k1.id % 9 != 1 /* note that the joins exclude other invalid locations for k1.id */


Cheers!

	

    
        

    
	

          
Subject: Oops!  Double posted the code by accident.   Here's the performance info:

          
Posted by: Stephen Munson (sgmunson@charter.net or smunson@heritageacademie (not signed in)

          
Posted on: Monday, October 20, 2008 at 10:54 AM

          
Message: My code ran in 33 milliseconds on a 2 cpu 32-bit SQL Server 2005 virtual machine instance.  RAM quantity is unknown.

	

    
        

    
	

          
Subject: Solution in stored procedure

          
Posted by: SkyBeaver (view profile)

          
Posted on: Monday, October 20, 2008 at 11:29 AM

          
Message: create proc ShowValidMoves
as

/*
** step 1 - store the table as rows and columns, so that we can handle
** NxN grids of arbitrary size.  Encode row, col as 100 * row + col
*/

declare @MyGrid table(
	Cell int not null primary key,
	Symbol tinyint not null
)

insert into @MyGrid(Cell, Symbol)
select [row] * 100 + [col], [symbol]
from

	(select [#] as row, [1], [2], [3], [4], [5], [6], [7], [8], [9]
	 from bejeweled) bj
unpivot
	(symbol for col in 
		([1], [2], [3], [4], [5], [6], [7], [8], [9])
	) as vt


/*
** Step 2 - find all pairs of nodes that may be candidates:  either vertically
** adjacent, horizontally adjacent, or two apart vertically or horizontally
*/

declare @Pairs table(
	Cell_1 int not null,
	Cell_2 int not null,
	Symbol tinyint not null
	primary key (Cell_1, Cell_2)
)

insert into @Pairs(Cell_1, Cell_2, Symbol)
select t1.Cell, t2.Cell, t1.Symbol
from @MyGrid t1
inner join @MyGrid t2 on
	t1.Symbol = t2.Symbol 
where
	(t1.Cell = t2.Cell - 1) or
	(t1.Cell = t2.Cell - 100) or
	(t1.Cell = t2.Cell - 2) or
	(t1.Cell = t2.Cell - 200)


/*
** step 3, iterate through and find whether there's a third node that completes the cluster
*/

declare @Sol table(Cell int not null)

declare @c1 int,
	    @c2 int,
        @s int

declare cx cursor for
select Cell_1, Cell_2, Symbol
from @Pairs


open cx
fetch cx into @c1, @c2, @s
while @@fetch_status = 0
begin
	if @c2 - @c1 = 1
	begin
		/* horizontal adjacency */
		insert into @Sol(Cell)
		select distinct Cell
		from @MyGrid
		where Symbol = @s and
		      Cell in (@c1 - 2, @c1 + 99, @c1 - 101,
		               @c2 + 2, @c2 + 101, @c2 - 99)
	end
	else if @c2 - @c1 = 2
	begin
		/* split horizontal */
		insert into @Sol(Cell)
		select distinct Cell
		from @MyGrid
		where Symbol = @s and
		      Cell in (@c1 - 99, @c1 + 101)
	end
	else if @c2 - @c1 = 100
	begin
		/* vertically adjacent */
		insert into @Sol(Cell)
		select distinct Cell
		from @MyGrid
		where Symbol = @s and
			  Cell in (@c1 - 101, @c1 - 99, @c1 - 200,
	                   @c2 + 200, @c2 + 99, @c2 + 101)
	end
	else if @c2 - @c1 = 200
	begin
		/* split vertical */
		insert into @Sol(Cell)
		select distinct Cell
		from @MyGrid
		where Symbol = @s and
		      Cell in (@c1 + 99, @c1 + 101)
	end

	fetch cx into @c1, @c2, @s
end

close cx
deallocate cx

select distinct s.Cell / 100 as Row, s.Cell % 100 as Col, g.Symbol as Symbol
from @Sol s
inner join @MyGrid g on
	s.Cell = g.Cell
order by 1, 2

go

/* results ....

Row         Col         Symbol
----------- ----------- ------
1           1           8
3           9           9
5           4           9
6           2           2
6           5           5
6           7           6
7           7           8
7           8           6
9           4           7
9           9           9

(10 row(s) affected)

*/

	

    
        

    
	

          
Subject: another way of doing it

          
Posted by: Roz (view profile)

          
Posted on: Monday, October 20, 2008 at 6:01 PM

          
Message: 
-- worktables 
Declare @Results Table(RowNumber Int, ColumnNumber Int, [Value] Int, HMove Bit Default (0), VMove Bit Default(0))
Declare @HMoves Table (RowNumber Int, ColumnOne Int, ColumnTwo Int, ColumnToSwap Int, ValueNeeded Int)
Declare @VMoves Table (ColumnNumber Int, RowOne Int, RowTwo Int, RowToSwap Int, ValueNeeded Int)

-- Unpivot the bejeweled table, to put it in a format more easily queried by SQL 
Insert @Results(RowNumber, ColumnNumber, [Value]) 
    Select RowNumber, ColumnNumber, [Value]
    From
        (Select [#] As RowNumber, [1], [2], [3], [4], [5], [6], [7], [8], [9]
         From bejeweled) bj
    UNPIVOT
       ([Value] For ColumnNumber In
          ([1], [2], [3], [4], [5], [6], [7], [8], [9])
    )As v
    Order By RowNumber, ColumnNumber

-- find possible horizontal swaps
Insert @HMoves(RowNumber, ColumnOne, ColumnTwo, ColumnToSwap, ValueNeeded)
    Select m1.RowNumber, 
           ColumnOne = Case When (m1.Value = m2.Value) Then m1.ColumnNumber
                            When (m1.Value = m3.Value) Then m1.ColumnNumber
                            Else m2.ColumnNumber
                       End,
           ColumnTwo = Case When (m1.Value = m2.Value) Then m2.ColumnNumber
                            When (m1.Value = m3.Value) Then m3.ColumnNumber
                            Else m3.ColumnNumber
                       End,
           ColumnToSwap = Case When (m1.Value = m2.Value) Then m3.ColumnNumber
                               When (m1.Value = m3.Value) Then m2.ColumnNumber
                               Else m1.ColumnNumber
                          End,
           ValueNeeded = Case  When (m1.Value = m2.Value) Then m1.Value
                               When (m1.Value = m3.Value) Then m1.Value
                               Else m2.Value
                          End
    From @Results m1
        Join @Results m2 On m2.RowNumber = m1.RowNumber 
                         And m2.ColumnNumber = m1.ColumnNumber + 1
        Join @Results m3 On m3.RowNumber = m1.RowNumber 
                         And m3.ColumnNumber = m1.ColumnNumber + 2
    Where  (m1.Value = m2.Value)
    OR     (m1.Value = m3.Value)
    OR     (m2.Value = m3.Value)

-- update the @Results table, where a swap is found 
Update u
Set    HMove = 1        
From   @Results u
Join   @HMoves hm  On  hm.ValueNeeded = u.Value
                   And hm.ColumnOne != u.ColumnNumber
                   And hm.ColumnTwo != u.ColumnNumber
Where  hm.RowNumber - u.RowNumber In (-1,0,1)
       And ( ((hm.RowNumber = u.RowNumber) And hm.ColumnToSwap - u.ColumnNumber In (-1,1))
              OR (hm.RowNumber - u.RowNumber In (-1,1) And hm.ColumnToSwap = u.ColumnNumber) 
           )
     

-- find possible vertical swaps
Insert @VMoves(ColumnNumber, RowOne, RowTwo, RowToSwap, ValueNeeded)
    Select m1.ColumnNumber, 
           RowOne = Case When (m1.Value = m2.Value) Then m1.RowNumber
                            When (m1.Value = m3.Value) Then m1.RowNumber
                            Else m2.RowNumber
                       End,
           RowTwo = Case When (m1.Value = m2.Value) Then m2.RowNumber
                            When (m1.Value = m3.Value) Then m3.RowNumber
                            Else m3.RowNumber
                       End,
           RowToSwap = Case When (m1.Value = m2.Value) Then m3.RowNumber
                               When (m1.Value = m3.Value) Then m2.RowNumber
                               Else m1.RowNumber
                          End,
           ValueNeeded = Case  When (m1.Value = m2.Value) Then m1.Value
                               When (m1.Value = m3.Value) Then m1.Value
                               Else m2.Value
                          End
    From @Results m1
        Join @Results m2 On m2.ColumnNumber = m1.ColumnNumber 
                         And m2.RowNumber = m1.RowNumber + 1
        Join @Results m3 On m3.ColumnNumber = m1.ColumnNumber 
                         And m3.RowNumber = m1.RowNumber + 2
    Where  (m1.Value = m2.Value)
    OR     (m1.Value = m3.Value)
    OR     (m2.Value = m3.Value)

-- update the @Results table, where a swap is found 
Update u
Set    VMove = 1       
From   @Results u
Join   @VMoves vm  On  vm.ValueNeeded = u.Value
                   And vm.RowOne != u.RowNumber
                   And vm.RowTwo != u.RowNumber
Where  vm.ColumnNumber - u.ColumnNumber In (-1,0,1)
       And ( ((vm.ColumnNumber = u.ColumnNumber) And vm.RowToSwap - u.RowNumber In (-1,1))
              OR (vm.ColumnNumber - u.ColumnNumber In (-1,1) And vm.RowToSwap = u.RowNumber) 
           )

Select RowNumber, ColumnNumber, Value
From @Results 
Where HMove = 1 
Or VMove = 1
GO

/**
Results: 
RowNumber	ColumnNumber	Value
1	1	8
3	9	9
5	4	9
6	2	2
6	5	5
6	7	6
7	7	8
7	8	6
9	4	7
9	9	9

**/

	

    
        

    
	

          
Subject: Solution 2 - Without The Cursor

          
Posted by: AmandaS (view profile)

          
Posted on: Monday, October 20, 2008 at 9:32 PM

          
Message: DECLARE @tbl_bejewelled Table (RowNum int NOT NULL, ColumnNum int NOT NULL, Value int NOT NULL)
DECLARE @tbl_offsets Table (i int NOT NULL, j int NOT NULL, k int NOT NULL, l int NOT NULL)
DECLARE @tbl_results Table (RowNum int NOT NULL, ColumnNum int NOT NULL, Value int NOT NULL)
DECLARE @i int, @j int, @k int, @l int

-- Unpivoted version of table stored in table variable
INSERT INTO @tbl_bejewelled (RowNum, ColumnNum, Value)
SELECT # As RowNum, CAST(ColumnNum As int) As ColumnNum, Value
FROM bejeweled
UNPIVOT 
	(Value FOR ColumnNum IN ([1],[2],[3],[4],[5],[6],[7],[8],[9]))AS unpvt

-- Store various joining offsets required
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 0, -2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 0, 3)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, 1, 2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, -1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 1, -1, 2)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 2, 1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (0, 2, -1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 2, 0)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -3, 0)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 1, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -2, -1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, 1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (1, 0, -2, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (2, 0, -1, 1)
INSERT INTO @tbl_offsets (i, j, k, l) VALUES (2, 0, -1, -1)

SELECT Distinct M.RowNum, M.ColumnNum, M.Value
FROM
	@tbl_bejewelled As A
	CROSS JOIN
	@tbl_offsets As O
	JOIN
	@tbl_bejewelled As B
	On A.RowNum + O.i = B.RowNum AND A.ColumnNum + O.j = B.ColumnNum
	JOIN
	@tbl_bejewelled As M	
	On M.RowNum + O.k = A.RowNum AND A.ColumnNum + O.l = M.ColumnNum
WHERE
	A.Value = B.Value AND A.Value = M.Value

	

    
        

    
	

          
Subject: My solution

          
Posted by: Alex Kozak (view profile)

          
Posted on: Saturday, October 25, 2008 at 10:20 PM

          
Message: Here is my solution.

1) First, I unpivoted table bejeweled.
As Chris Howarth noticed, this makes all further calculations much easier.

DROP TABLE unpvt
CREATE TABLE unpvt(row int, col int, val int);

INSERT INTO unpvt
SELECT # as ROW, COL, VAL 
 FROM bejeweled
 UNPIVOT
   (VAL FOR col IN([1],[2],[3],[4],[5],[6],[7],[8],[9])
) AS unpvt;

2) Then I found all the pairs of tokens of the same kind, which are located 
in the adjacent cells or in the cells with one gap between them.  
These pairs, combined with one possible move (swap), can build vertical or horizontal 
chains of three or more tokens of the same kind.

3) There are six possible moves around each horizontal (vertical) pair of adjacent cells. 
For the pairs with one gap, the number of relevant moves equal to two. 
The logic related to all the moves can be found in the rest of the query.

4) The vertically oriented and the horizontally oriented cells are processed separately. 
The UNION operator combines the results of both queries.



SELECT u4.* FROM
(SELECT u1.row minR, u2.row maxR, u1.col, u1.val 
FROM unpvt u1 INNER JOIN unpvt u2 on u1.val=u2.val 
AND u1.col=u2.col AND u2.row-u1.row IN(1,2)) u3 
INNER JOIN unpvt u4 
ON (u3.val = u4.val) AND (((maxR-minR=1) AND 
((u3.col=u4.col) AND (2 IN(minR-u4.row,u4.row-maxR)) OR
(abs(u4.col-u3.col)=1) AND (1 IN(minR-u4.row,u4.row-maxR))))
OR ((maxR-minR=2) AND (abs(u4.col-u3.col)=1) AND u4.row=minR+1))
UNION  
SELECT u4.* FROM
(SELECT u1.col minC, u2.col maxC, u1.row, u1.val 
FROM unpvt u1 INNER JOIN unpvt u2 ON u1.val=u2.val 
AND u1.row=u2.row AND u2.col-u1.col IN(1,2)) u3 
INNER JOIN unpvt u4
ON (u3.val = u4.val) AND (((maxC-minC=1) AND 
((u3.row=u4.row) AND (2 in(minC-u4.col,u4.col-maxC)) OR
(abs(u4.row-u3.row)=1) AND (1 in(minC-u4.col,u4.col-maxC))))
OR ((maxC-minC=2) AND (abs(u4.row-u3.row)=1) AND u4.col=minC+1))


Finally, I would like to say a few words about the submitted solutions.
Firstly, they are very different. Some of them are similar to my solution, 
some are better than mine and some are a little bit strange or surprising.
However, all the solutions are great and demonstrate the creativity and skills of the authors.

Thanks to everybody who contributed. I hope you all had fun.

The winner will be announced.

	

    
        

    
	

          
Subject: About announcement 

          
Posted by: Alex Kozak (view profile)

          
Posted on: Saturday, November 01, 2008 at 6:57 PM

          
Message: Hi Guys, 

One of you sent me a message asking whether I picked a winner for the Bejeweled contest. 
I tried to answer that message but could not. The message was sent through Simple-Talk and did not have the email address of a sender. In addition, the response-link provided in email did not work.

What I actually wanted to say in my answer is that I apologize for the missing announcement in the Simple-Talk newsletter on Oct 28. Unfortunately, this is out of my control – the announcement is in the competency of the editors.

I also wanted to say that I had a hard time trying to identify the best solution. 
Finally, I picked three equally brilliant solutions (the solution of the author of the letter among them). If I could, I would divide first place between these three solutions. However, that is probably not an option.

Let’s wait for the announcement for a few more days. I will try to contact the editors.

AK

	

    
        

    
	

          
Subject: Announcement

          
Posted by: Alex Kozak (view profile)

          
Posted on: Wednesday, November 12, 2008 at 12:17 PM

          
Message: This is just in case somebody missed the announcement.
It is in the body of the article, at the end.

Congratulations to the winners - Timothy Walters, Ryan Randall and DrLechter!
Thank you to everybody who participated!

	

    
        

    



         
      

  



            
 
            

                
    



    

    

        
    	        

    	              SQL Home 
    	        

            
                

            
    	        

    	              Learn SQL Server (36 articles)
    	        

            
                

            
    	        

    	              SQL Training 
    	        

            
                

            
    	        

    	              Database Administration (67 articles)
    	        

            
                

            
    	        

    	              T-SQL Programming (87 articles)
    	        

            
                

            
    	        

    	              Performance (18 articles)
    	        

            
                

            
    	        

    	              Backup and Recovery (18 articles)
    	        

            
                

            
    	        

    	              SQL Tools (44 articles)
    	        

            
                

            
    	        

    	              SSIS (12 articles)
    	        

            
                

            
    	        

    	              Reporting Services (12 articles)
    	        

            
    

    
  


    

        
        
        
        
              
        
        
        


    

    

        

			

            Phil Factor
            

	
                Finding Stuff in SQL Server Database DDL

                 You'd have thought that nothing would be easier than using  SQL Server Management Studio (SSMS) for searching... Read more...

                


            


            
			

			

             View the blog

        

    

    



        


    

    

        

            
                    Implementing User-Defined Hierarchies in SQL Server Analysis Services

                     To be able to drill into  multidimensional cube data at several levels, you must implement all of the... Read more...


                
                    Using the Filtering API with the SQL Comparison SDK

                     Red Gate's SQL Comparison SDK provides a means to compare and synchronize database schemas and data... Read more...


                
                    SQL Toolbelt 2008: Predominantly an Engineering Task

                     The conversion of the Red-Gate tools to be compatible with SQL Server 2008 might not seem, on first... Read more...


                
                    SQL Response: The dim sum interview

                     Richard Morris met David and Nigel of the SQL Response team, in a dim sum Restaurant in Cambridge. They... Read more...


                
                    Writing Efficient SQL: Set-Based Speed Phreakery

                     Phil Factor's SQL Speed Phreak challenge is an event where coders battle to produce the fastest code to... Read more...


                
        

    

    



        



    

    

        

            
                    Beginning SQL Server 2005 Reporting Services Part 1

                     Steve Joubert begins an in-depth tour of SQL Server 2005 Reporting Services with a step-by-step guide... Read more...


                
                    Ten Common Database Design Mistakes

                     Database design and implementation is the cornerstone of any data centric project (read 99.9% of... Read more...


                
                    Beginning SQL Server 2005 Reporting Services Part 2

                     Continuing his in-depth tour of SQL Server 2005 Reporting Services, Steve Joubert demonstrates the most... Read more...


                
                    SQL Server Full Text Search Language Features

                     SQL Full-text Search (SQL FTS) is an optional component of SQL Server 7 and later, which allows fast... Read more...


                
                    Creating CSV Files Using BCP and Stored Procedures

                     Nigel Rivett demonstrates some core techniques for extracting SQL Server data into CSV files, focussing... Read more...


                
        

    

    



        
      

        

        

          

		
		Over 150,000 Microsoft professionals subscribe to the Simple-Talk technical journal. Join today, it's fast, simple, free and secure.


		    
Join Simple Talk

          

        

        

      

    
    


                


            

            


            

                

                    Privacy policy |
                    Terms and conditions |
                    ©2005-2010 Red Gate Software
                

                

                    About |
                    Site map |
                    Become an author |
                    Newsletters |
                    Contact us