Use T-SQL to solve a puzzle from a popular game show

Advertisement

Use T-SQL to solve a puzzle from a popular game show

Advertisement

Since the size of the board is fixed and there are a fixed number of winning paths, I'd probably pre-calculate and encode all possible winning paths, then see if one of them is satisfied. It would be faster than manually walking each path each time the state of the board changes.
Do the hard work up front, then benefit from it with each state change.
Think of it as an OLAP-ish approach to the problem.

The reason for the Hexagons in the original game grid is that this was based on the game Hex, (http://en.wikipedia.org/wiki/Hex_game). It was invented independently by John Nash and Piet Hein. It had a fad in Europe and there were hex problems in daily newspapers.
When the sides of the grid are equal, the game favors the first player, but there is a winning strategy for non-symmetrical n×m boards. Obviously, a completed path by one player blocks the other player. John Nash proved there can be no ties.

I have a solution,but I cannot post it because of size limits. It is graph theory based . Technically, ROW is a reserved word in ANSI/ISO Standard SQL and should not be a column name. I want to change the DDL to remove NULLs and the DML to add a full grid into the table. Hey, it is only 25 cells in the grid.
CREATE TABLE Blockbusters
(row SMALLINT NOT NULL
CHECK (row BETWEEN 1 AND 5),
col SMALLINT NOT NULL
CHECK (col BETWEEN 1 AND 5),
player CHAR(1) NOT NULL
CHECK (player IN ('V', 'H', ' ')),
PRIMARY KEY(row, col),
UNIQUE (player, row, col));
DELETE FROM Blockbusters;
INSERT INTO Blockbusters(row, col, player)
VALUES (1, 1, 'H'), (1, 3, 'H'), (1, 4, 'H'), (1, 5, 'V'),
(2, 2, 'H'), (2, 3, 'H'), (2, 4, 'H'), (2, 5, 'V'),
(3, 2, 'H'), (3, 3, 'V'), (3, 4, 'V'), (3, 5, 'V'),
(4, 1, 'H'), (4, 2, 'H'), (4, 3, 'V'), (4, 4, 'H'), (4, 5, 'V'),
(5, 2, 'H'), (5, 3, 'H'), (5, 4, 'H'), (5, 5, 'H'),
-- add empty cells
(1, 2, ' '), (2, 1, ' '), (3, 1, ' '), (5, 1, ' ');
I am also going to change your problem statement slightly. Instead of trying to write a BIT function (ugh!) to find a winner, let's write code to find, if a path exists, for one of the players; call them Mr. Horizontal and Ms. Vertical after the gender convention for players in Game Theory.
But what we need is Graph Theory since this is a path problem. By symmetry, we can convert a solution for Mr. Horizontal to one for or Ms. Vertical with a simple rotation. I will leave that as a exercise for the reader. There are there three outcomes; Ms. Vertical wins and Mr. Horizontal loses, Mr. Horizontal wins and Ms. Vertical loses or nobody wins. The first two cases are easy to imagine; the winning path of one player blocks all possible paths of the other player. An example of the third case might be a checker board of 'H' and 'V' tokens, if both players co-operated.
If Mr. Horizontal has a win, then he has
1) At least five tokens on the grid.
2) At least one token in each of the five colum

What about a rowset based solution like this:
CREATE FUNCTION dbo.IsCompleted(@player AS CHAR(1), @size AS INT) RETURNS BIT
AS
BEGIN
DECLARE @i bit;
set @i=0;
IF (@player='H')
BEGIN
WITH t AS
(select b.row,b.col,0 as prev_row,0 as prev_col
from Blockbusters b
where
player='H'
and b.col=1
UNION ALL
SELECT b.row,b.col,t.row, t.col
from Blockbusters b
INNER JOIN t ON (b.row<>t.prev_row or b.col<> t.prev_col) and ((b.row in (t.row-1,t.row+1) and b.col=t.col) OR (b.row=t.row AND b.col=t.col+1) )
WHERE b.player='H'
)
select TOP(1) @i=1 from t
where t.col=@size
END
ELSE IF (@player='V')
BEGIN
WITH t AS
(select b.row,b.col,0 as prev_row,0 as prev_col
from Blockbusters b
where
player='V'
and b.row=1
UNION ALL
SELECT b.row,b.col,t.row, t.col
from Blockbusters b
INNER JOIN t ON (b.row<>t.prev_row or b.col<> t.prev_col) and ((b.col in (t.col-1,t.col+1) and b.row=t.row) OR (b.col=t.col AND b.row=t.row+1) )
WHERE b.player='V'
)
select TOP(1) @i=1 from t
where t.row=@size
END
RETURN @i
END
GO

Sponsored Introduction Continue on to (or wait seconds) ×