So Duko bank holiday challenge

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

Site Related Forums

The Yak Corral

So Duko bank holiday challenge

Author

Topic

nr
SQLTeam MVY

12543 Posts

Posted - 2005-05-27 : 19:51:43

Heard of this?
It's in a lot of papers in the uk at the moment.
You have to fill a 9x9 grid with the numbers 1 to 9 such that the digits appear once and only once in each row, column and box (the 9x9 square is divided into 9 3x3 boxes)
You will receive a square with some numbers already filled in.

The challenge is to solve any puzzle using sql server.

The first part is to devise a notation suitable for the problem
Then to form the queries to solve it.

See
http://www.sudoku.org.uk/backpuzzles.htm
for sample puzzles

I'll post my attempt (which doesn't work all the time at the moment) later on.

My mistake - looks like it does work.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

nr
SQLTeam MVY

12543 Posts

Posted - 2005-05-27 : 20:04:59

p.s. I'm not very proud of my solution. It runs a few queries in a loop until it completes all obvious things then guesses repeatedly until it gets the solution - running the initial queries on each guess.

I'd like to put in more queries to remove more options but it gets a bit complicated.
Also the incentive isn't there once I have a solution.

Excluding the grid setup it's les than 100 lines.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2005-05-28 : 05:22:24

Not like this, then?


DECLARE @x tinyint, @y tinyint, @prefix varchar(40)
PRINT 'CREATE TABLE N (n tinyint PRIMARY KEY)'
SET @prefix = 'INSERT INTO N SELECT '
SET @x = 1
WHILE @x <= 9 BEGIN
  PRINT @prefix + CAST(@x AS varchar)
  SET @prefix = 'UNION ALL SELECT '
  SET @x = @x +1
END

PRINT ''
PRINT 'SELECT TOP 1 * FROM'
SET @y = 0
WHILE @y < 9 BEGIN
  SET @x = 0
  WHILE @x < 9 BEGIN
    PRINT '  (SELECT n AS n' + CAST(@y AS varchar) + CAST(@x AS varchar) +
      ' FROM N) AS N' + CAST(@y AS varchar) + CAST(@x AS varchar) +
      CASE WHEN @x = 8 AND @y = 8 THEN '' ELSE ',' END
    SET @x = @x + 1
  END
  SET @y = @y + 1
END

DECLARE @x1 tinyint, @y1 tinyint, @distinct varchar(300), @dsep char(1)
SET @prefix = 'WHERE'
SET @y = 0
WHILE @y < 9 BEGIN
  SET @x = 0
  WHILE @x < 9 BEGIN
    SET @distinct = ''
    SET @dsep = '('
    SET @y1 = @y
    WHILE @y1 < 9 BEGIN
      SET @x1 = @x
      WHILE @x1 < 9 BEGIN
        IF (NOT(@x1=@x) OR NOT(@y1=@y)) AND
           (@x1=@x OR @y1=@y OR (@x1/3 = @x/3 AND @y1/3 = @y/3)) BEGIN
          SET @distinct = @distinct + @dsep +
            'n' + CAST(@y1 AS varchar) + CAST(@x1 AS varchar)
          SET @dsep = ','
        END
        SET @x1 = @x1 + 1
      END
      SET @y1 = @y1 + 1
    END
    IF @distinct <> ''
      PRINT @prefix + ' n' + CAST(@y AS varchar) + CAST(@x AS varchar) +
        ' NOT IN ' + @distinct + ')'
    SET @prefix = '  AND'
    SET @x = @x + 1
  END
  SET @y = @y + 1
END

DECLARE @grid varchar(200)
SET @grid =
  '  5   7  ' +
  '  61 39  ' +
  '7   5   8' +
  ' 839 716 ' +
  '         ' +
  ' 218 439 ' +
  '3   9   6' +
  '  75 82  ' +
  '  8   4  '

SET @y = 0
WHILE @y < 9 BEGIN
  SET @x = 0
  WHILE @x < 9 BEGIN
    DECLARE @ns char(1)
    SET @ns = SUBSTRING(@grid, @y*9+@x+1, 1)
    IF ISNUMERIC(@ns) = 1
      PRINT '  AND n' + CAST(@y AS varchar) + CAST(@x AS varchar) + ' = ' + @ns
    SET @x = @x + 1
  END
  SET @y = @y + 1
END

nr
SQLTeam MVY

12543 Posts

Posted - 2005-05-28 : 05:49:34

Interesting - when I try to run the output from that it doesn't complete but uses all my cpu.
How long should it take?

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2005-05-28 : 06:27:21

quote:
How long should it take?

Probably until your computer stops working or you get bored and cancel it. While it may be good enough for finding Yaks, I don't think the query optimizer's up to the job of solving constraint satisfaction problems of that size.
So unless there are some other constraints (or ways of modeling the problem) that massively reduce the search space, I think this approach is a nonrunner.

nr
SQLTeam MVY

12543 Posts

Posted - 2005-05-28 : 07:43:20

Doesn't it find values that aren't in the other cells?
If so that doesn't get far in solving the problem.

I took the approach of finding values that couldn't be in cells - then checked different cases (well only 2 at the moment) until there was one value per cell.
It seems to work for the simple games but not for the more complicated.
The difficult one I use for testing I haven't solved myself sp don't know what tests to model.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2005-05-28 : 10:04:05

quote:
Doesn't it find values that aren't in the other cells?
If so that doesn't get far in solving the problem.

Oh, it would give you the right solution(s) if it ever finished. It's just not going to finish because it's searching too much of the problem space with an expectation that there are many solutions.

I've got a (sensible) partial solution that seems to have no difficulty on the 'gentle' and 'moderate' level, but it doesn't yet split the search space into multiple possibilities when it can't prune any more.

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2005-05-28 : 13:55:37

Ok, well here's what I have so far... getting a bit bored with the Daily Telegraph ones: they're not posing much of a problem!

First, some problems:


DROP VIEW SudokuProblemGrid
GO
DROP TABLE SudokuProblem
DROP TABLE N
GO

CREATE TABLE SudokuProblem (
  problemNo integer NOT NULL PRIMARY KEY,
  difficulty varchar(10) NOT NULL,
  notes varchar(200) NULL,
  settings char(81) NOT NULL
)

INSERT INTO SudokuProblem
SELECT 1, 'easy', 'can be done just applying prune',
  '  5   7  ' +
  '  61 39  ' +
  '7   5   8' +
  ' 839 716 ' +
  '         ' +
  ' 218 439 ' +
  '3   9   6' +
  '  75 82  ' +
  '  8   4  '
UNION ALL
SELECT 2, 'easy', 'this needs pick too',
  '  3    51' +
  '5 2  64  ' +
  '  7 5    ' +
  '   63 7  ' +
  '2  7 8  6' +
  '  4 21   ' +
  '    7 8  ' +
  '  81  6 9' +
  '17    5  '
UNION ALL
SELECT 3, 'tough', 'this one''s broken: there are 4 possible solutions',
  '2     7  ' +
  '  17324  ' +
  ' 76      ' +
  '      268' +
  ' 6 1 8 3 ' +
  '984      ' +
  '      14 ' +
  '  92568  ' +
  '  3     5'
UNION ALL
SELECT 4, 'diabolical', NULL,
  ' 2 6 8   ' +
  '58   97  ' +
  '    4    ' +
  '37    5  ' +
  '6       4' +
  '  8    13' +
  '    2    ' +
  '  98   36' +
  '   3 6 9 '
UNION ALL
SELECT 5, 'gentle', NULL,
  '4 9   7 8' +
  ' 562 391 ' +
  '1       5' +
  '   9 1   ' +
  ' 1  3  2 ' +
  '   6 8   ' +
  '3       9' +
  ' 918 567 ' +
  '6 8   5 2'
UNION ALL
SELECT 6, 'moderate', NULL,
  '83 1     ' +
  '  6 7 5  ' +
  '   9    8' +
  ' 6   5 9 ' +
  '4  6 9  3' +
  ' 9 7   5 ' +
  '9    2   ' +
  '  1 8 9  ' +
  '     6 87'
UNION ALL
SELECT 7, 'moderate', NULL,
  ' 3 6 2 8 ' +
  '  19 34  ' +
  '9       5' +
  '  7 3 5  ' +
  '1       8' +
  '  9 7 2  ' +
  '7       2' +
  '  83 46  ' +
  ' 4 5 7 9 '
UNION ALL
SELECT 8, 'moderate', NULL,
  '  356 9  ' +
  '  8     4' +
  '9  8  65 ' +
  ' 85 12   ' +
  '         ' +
  '   94 17 ' +
  ' 64  1  9' +
  '1     8  ' +
  '  2 963  '
UNION ALL
SELECT 9, 'gentle', NULL,
  '7   2   4' +
  '26     93' +
  '   9 5   ' +
  ' 8  7  61' +
  '  6   3  ' +
  '32  9  5 ' +
  '   1 2   ' +
  '19     75' +
  '8   3   6'
UNION ALL
SELECT 10, 'moderate', NULL,
  '  6   1  ' +
  '   7 2   ' +
  '95     82' +
  '  45 38  ' +
  '51     29' +
  '  91 86  ' +
  '86     53' +
  '   8 9   ' +
  '  5   4  '
UNION ALL
SELECT 11, 'moderate', NULL,
  '   56 421' +
  '    9  86' +
  '  2   7  ' +
  '8  4   1 ' +
  '  5   3  ' +
  ' 1   8  7' +
  '  1   9  ' +
  '47  2    ' +
  '639 41   '
UNION ALL
SELECT 12, 'tough', NULL,
  '      128' +
  '2 4  9 7 ' +
  ' 7  3 4  ' +
  '1   2  3 ' +
  ' 5     8 ' +
  ' 6  9   1' +
  '  7 6  1 ' +
  ' 9 2  3 7' +
  '528      '
UNION ALL
SELECT 13, 'diabolical', NULL,
  ' 125 487 ' +
  '         ' +
  '75     23' +
  '  41 87  ' +
  ' 2  5  4 ' +
  '  34 95  ' +
  '48     17' +
  '         ' +
  ' 357 169 '
UNION ALL
SELECT 49, 'diabolical', NULL,
  '   6   29' +
  ' 4 5   3 ' +
  '  7  14  ' +
  '7   54   ' +
  ' 53   24 ' +
  '   12   3' +
  '  54  1  ' +
  ' 6   8 5 ' +
  '82   5   '
UNION ALL
SELECT 55, 'diabolical', NULL,
  '2  3     ' +
  '8 4 62  3' +
  ' 138     ' +
  '      39 ' +
  '5 7   6 1' +
  ' 32      ' +
  '     914 ' +
  '6  25 8 9' +
  '     1  2'
UNION ALL
SELECT 62, 'diabolical', NULL,
  ' 4 6     ' +
  '51    9 6' +
  '  8 3   4' +
  '7 1 62   ' +
  ' 8     6 ' +
  '   47 5 1' +
  '3   4 6  ' +
  '1 2    38' +
  '     6 9 '
UNION ALL
SELECT 69, 'diabolical', NULL,
  '   81  65' +
  '51  67  8' +
  '         ' +
  ' 9   4 3 ' +
  ' 61   97 ' +
  ' 5 3   8 ' +
  '         ' +
  '6  78  93' +
  '17  59   '
UNION ALL
SELECT 76, 'diabolical', NULL,
  '  1    4 ' +
  '95     17' +
  '  78  56 ' +
  '4   97 5 ' +
  '    8    ' +
  ' 3 54   1' +
  ' 62  41  ' +
  '19     86' +
  ' 7    9  '

CREATE TABLE N (n tinyint PRIMARY KEY)
INSERT INTO N SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL
SELECT 8 UNION ALL SELECT 9
GO

CREATE VIEW SudokuProblemGrid AS
SELECT problemNo, x, y, CAST(n AS tinyint) AS n
FROM (
    SELECT SP.problemNo, X.n AS x, Y.n AS y,
      SUBSTRING(SP.settings, (Y.n-1)*9+X.n ,1) AS n
    FROM SudokuProblem AS SP, N AS X, N AS Y
 ) AS G
WHERE ISNUMERIC(n) = 1


DROP TABLE S

CREATE TABLE S (
  s int NOT NULL,
  x tinyint NOT NULL,
  y tinyint NOT NULL,
  b tinyint NOT NULL,
  n tinyint NOT NULL,
  PRIMARY KEY (s, y, x, n)
)

-- all possibilities for all cells
INSERT INTO S (s, x, y, b, n)
SELECT 0, X.n, Y.n, (Y.n-1)/3*3+(X.n-1)/3+1, N.n
FROM N AS X, N AS Y, N

-- fill in problem
DELETE FROM S
FROM S
INNER JOIN SudokuProblemGrid AS G
  ON S.x = G.x AND S.y = G.y AND S.n <> G.n
WHERE G.problemNo = 49

WHILE 1=1 BEGIN
  WHILE 1=1 BEGIN
    DECLARE @prune int, @pick int
    -- prune any possibilities that conflict with known values
    DELETE FROM S
    FROM S
    INNER JOIN (
        SELECT s, x, y, b, MIN(n) AS n
        FROM S
        GROUP BY s, x, y, b
        HAVING COUNT(*) = 1
      ) AS K
      ON S.s = K.s AND S.n = K.n AND (S.x = K.x OR S.y = K.y OR S.b = K.b)
     AND NOT(S.x = K.x AND S.y = K.y)
  
    SET @prune = @@ROWCOUNT
  
    -- pick any values that only occur once in row, column or block
    DELETE FROM S
    WHERE EXISTS (
        SELECT *
        FROM S AS S0
        WHERE S.s = S0.s AND S.x = S0.x AND S.y = S0.y AND S.n <> S0.n AND (
          NOT EXISTS(
            SELECT *
            FROM S AS S1
            WHERE S0.s = S1.s AND S0.n = S1.n AND S0.x = S1.x AND S0.y <> S1.y
          ) OR NOT EXISTS(
            SELECT *
            FROM S AS S1
            WHERE S0.s = S1.s AND S0.n = S1.n AND S0.x <> S1.x AND S0.y = S1.y
          ) OR NOT EXISTS(
            SELECT *
            FROM S AS S1
            WHERE S0.s = S1.s AND S0.n = S1.n
              AND NOT(S0.x = S1.x AND S0.y = S1.y) AND S0.b = S1.b
          )
        )
      )
  
    SET @pick = @@ROWCOUNT
  
    IF @prune = 0 AND @pick = 0 BREAK
  END

  -- delete failed spaces
  DELETE FROM S
  WHERE s IN (
      SELECT s
      FROM (SELECT s FROM S GROUP BY s, x, y) AS A
      GROUP BY s
      HAVING COUNT(*) < 81
    )

  -- if no live spaces left, we're done
  IF NOT EXISTS(SELECT * FROM S GROUP BY s, x, y HAVING COUNT(*) > 1)
    BREAK

  -- renumber possible spaces to make duplicate numbering easier
  UPDATE S1 SET s = 2*(SELECT COUNT(DISTINCT s) FROM S AS S0 WHERE S0.s < S1.s)
  FROM S AS S1

  -- duplicate live spaces
  INSERT INTO S
  SELECT s+1, x, y, b, n
  FROM S
  WHERE s IN (SELECT s FROM S GROUP BY s, x, y HAVING COUNT(*) > 1)

  -- find a cell to split in each pair of live spaces
  -- choose that value in even spaces and exclude it in odd spaces
  DELETE FROM S
  FROM S
  INNER JOIN (
      SELECT s, agg/100 AS y, agg/10%10 AS x, agg%10 AS n
      FROM (
          SELECT s, MIN(y*100+x*10+n) AS agg
          FROM (
              SELECT s, x, y, MIN(n) AS n
              FROM S
              GROUP BY s, x, y
              HAVING COUNT(*) > 1
            ) AS A
          GROUP BY s
        ) AS A
     ) AS SP
     ON S.s = SP.s AND S.x = SP.x AND S.y = SP.y
    AND ((S.s % 2 = 1 AND S.n = SP.n) OR
         (S.s % 2 = 0 AND S.n <> SP.n))
END

SELECT s, y,
  MAX(CASE WHEN x = 1 THEN n END) +
  MAX(CASE WHEN x = 2 THEN n END) +
  MAX(CASE WHEN x = 3 THEN n END) +
  MAX(CASE WHEN x = 4 THEN n END) +
  MAX(CASE WHEN x = 5 THEN n END) +
  MAX(CASE WHEN x = 6 THEN n END) +
  MAX(CASE WHEN x = 7 THEN n END) +
  MAX(CASE WHEN x = 8 THEN n END) +
  MAX(CASE WHEN x = 9 THEN n END) AS row
FROM (SELECT s, x, y, CAST(n AS char(1)) AS n FROM S) AS A
GROUP BY s, y
ORDER BY s, y

nr
SQLTeam MVY

12543 Posts

Posted - 2005-05-28 : 18:07:43

I borrowed your means of inputting the data.
It solvess the ones that I had but needs to guess on the one I got from your list (still solves it though). Might look into that later but not sure how to define another rule.


create proc #s_DispGrid
as
-- display grid
select r.i, 
[1] = (select n from #a where r = r.i and c = 1) ,
[2] = (select n from #a where r = r.i and c = 2) ,
[3] = (select n from #a where r = r.i and c = 3) ,
[4] = (select n from #a where r = r.i and c = 4) ,
[5] = (select n from #a where r = r.i and c = 5) ,
[6] = (select n from #a where r = r.i and c = 6) ,
[7] = (select n from #a where r = r.i and c = 7) ,
 = (select n from #a where r = r.i and c = 8) ,
[9] = (select n from #a where r = r.i and c = 9)
from (select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) r
go

set nocount on
drop table #a
go
drop table #b
go

create table #a (c int, r int, b int, n varchar(9))
create table #b (c int, r int, b int, n varchar(9))
declare @b int, @c int, @r int, @n int, @nums float, @cnt int
-- c = col, r = row, n = possible numbers in slot, b = box number

-- initialise grid
insert #a (c, r, b, n) 
select i.i, j.j, 0, '123456789'
from (select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) i
cross join (select j=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) j

update #a set b = 1 where c between 1 and 3 and r between 1 and 3
update #a set b = 2 where c between 4 and 6 and r between 1 and 3
update #a set b = 3 where c between 7 and 9 and r between 1 and 3
update #a set b = 4 where c between 1 and 3 and r between 4 and 6
update #a set b = 5 where c between 4 and 6 and r between 4 and 6
update #a set b = 6 where c between 7 and 9 and r between 4 and 6
update #a set b = 7 where c between 1 and 3 and r between 7 and 9
update #a set b = 8 where c between 4 and 6 and r between 7 and 9
update #a set b = 9 where c between 7 and 9 and r between 7 and 9

-- set values
declare @grid varchar(81)
select @grid = 	  ' 1 42   5'
		+ '  2 71 39'
		+ '       4 '
		+ '2 71    6'
		+ '    4    '
		+ '6    74 3'
		+ ' 7       '
		+ '12 73 5  '
		+ '3   82 7 '
--goto run
select @grid = 	  '2  4 8 1 '
		+ ' 8   1  3'
		+ '  1 7 5  '
		+ ' 1  2  64'
		+ '  43  2  '
		+ '59  8  7 '
		+ '  7 9 4  '
		+ '6  7   38'
		+ ' 5 1 3  7'
--goto run
SELECT @grid =
  '  1    4 ' +
  '95     17' +
  '  78  56 ' +
  '4   97 5 ' +
  '    8    ' +
  ' 3 54   1' +
  ' 62  41  ' +
  '19     86' +
  ' 7    9  '

run:
	-- set up grid
	select @r = 1, @c = 1
	while @r <= 9 
	begin
		update #a 
		set n = substring(@grid, ((@r-1) * 9) + @c, 1) 
		where substring(@grid, ((@r-1) * 9) + @c, 1) <> ' '
		and r = @r
		and c = @c
		select @c = @c + 1
		if @c = 10
			select @r = @r + 1, @c = 1
	end
exec #s_DispGrid

declare @vanilla int ,
	@attempt int
select 	@vanilla = 0 ,
	@attempt = 0
test:
select @cnt = 0
while @cnt <> (select sum(len(n)) from #a)	-- loop until no change
begin
	select @cnt = sum(len(n)) from #a
	
	-- set all those where there are single instances of values
	update 	a
	set	n = num.i
	from 	#a a
	cross join 
	(select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num
		left join #a ar
			on 	(a.r = ar.r)
			and 	(a.r <> ar.r or a.c <> ar.c)
			and	ar.n like '%' + convert(varchar(1), num.i) + '%'
		left join #a ac
			on 	(a.c = ac.c)
			and 	(a.r <> ac.r or a.c <> ac.c)
			and	ac.n like '%' + convert(varchar(1), num.i) + '%'
		left join #a ab
			on 	(a.b = ab.b)
			and 	(a.r <> ab.r or a.c <> ab.c)
			and	ab.n like '%' + convert(varchar(1), num.i) + '%'
	where ar.r is null
	or ac.r is null
	or ab.r is null
	
	-- remove all those where there are single values
	update t1 set n = replace(t1.n, t2.n, '')
	from #a t1
	cross join 
	(select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num
	join #a t2
	on (t1.r = t2.r or t1.c = t2.c or t1.b = t2.b)
	and (t1.r <> t2.r or t1.c <> t2.c)
	where len(t2.n) = 1
	and t1.n like '%' + t2.n + '%'
	and t2.n = convert(varchar(1),num.i) 

	-- remove all those where there are two values twice
	update t1 set n = replace(replace(t1.n, left(t2.n,1), ''), right(t2.n,1), '')
	from #a t1
	cross join 
	(select type = 'r' union select 'c' union select 'b') type
	cross join
	(	select i = convert(varchar(1),num1.i)+convert(varchar(1),num2.i)
		from
			(select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num1
				join (select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num2
					on num1.i < num2.i
	) num
	join #a t2
		on 	(	(t1.r = t2.r and type.type = 'r')
			or 	(t1.c = t2.c and type.type = 'c')
			or 	(t1.b = t2.b and type.type = 'b')
			)
		and t2.n = num.i
	join #a t3
		on 	(	(t3.r = t2.r and type.type = 'r')
			or 	(t3.c = t2.c and type.type = 'c')
			or 	(t3.b = t2.b and type.type = 'b')
			)
		and (t3.r <> t2.r or t3.c <> t2.c)
		and t3.n = t2.n
	where patindex('%[' + num.i + ']%', t1.n) <> 0
	and (t1.r <> t2.r or t1.c <> t2.c)
	and (t1.r <> t3.r or t1.c <> t3.c)
	
	-- remove all those where there are three values thrice
	update t1 set n = replace(replace(t1.n, left(t2.n,1), ''), right(t2.n,1), '')
	from #a t1
	cross join 
	(select type = 'r' union select 'c' union select 'b') type
	cross join
	(	select i = convert(varchar(1),num1.i)+convert(varchar(1),num2.i)+convert(varchar(1),num3.i)
		from
			(select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num1
				join (select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num2
					on num1.i < num2.i
					join (select i=1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9) num3
						on num2.i < num3.i
	) num
	join #a t2
		on 	(	(t2.r = t1.r and type.type = 'r')
			or 	(t2.c = t1.c and type.type = 'c')
			or 	(t2.b = t1.b and type.type = 'b')
			)
		and t2.n = num.i
		and (t2.r <> t1.r or t2.c <> t1.c)
	join #a t3
		on 	(	(t3.r = t1.r and type.type = 'r')
			or 	(t3.c = t1.c and type.type = 'c')
			or 	(t3.b = t1.b and type.type = 'b')
			)
		and t3.n = num.i
		and (t3.r <> t1.r or t3.c <> t1.c)
		and (t3.r <> t2.r or t3.c <> t2.c)
	join #a t4
		on 	(	(t4.r = t1.r and type.type = 'r')
			or 	(t4.c = t1.c and type.type = 'c')
			or 	(t4.b = t1.b and type.type = 'b')
			)
		and t4.n = num.i
		and (t4.r <> t1.r or t4.c <> t1.c)
		and (t4.r <> t2.r or t4.c <> t2.c)
		and (t4.r <> t3.r or t4.c <> t3.c)
	where patindex('%[' + num.i + ']%', t1.n) <> 0
	
end

if @attempt > 20 goto oops
if 	81 <> (select sum(len(n)) from #a) 
or 	exists (select * from #a where n = '')	-- not complete
begin
	exec #s_DispGrid
	select 'no solution - guessing'
	if @attempt = 0
		insert #b select * from #a

	select @attempt = @attempt + 1
	if exists(select * from #a where n = '')	-- failed
	begin
		delete #a
		insert #a select * from #b
	end
	
	select 	@r = r, @c = c
	from	(	select 	top 1 r,c
			from 	#a
			where 	len(n) > 1
			order by newid()
		) a
	
	update 	#a
	set	n = substring(n, convert(int,len(n) * rand() + 1), 1)
	where	r = @r and c = @c
	select @r, @c
	select @attempt
	exec #s_DispGrid
	goto test
end
oops:	
-- display grid
exec #s_DispGrid
 
go

drop proc #s_DispGrid
go

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2005-05-31 : 14:48:22

We all know I won't pass up a good puzzle. So here is my shot at it all. I mimcked the input method shown above (except I added a 'step' column). This loop solves all the puzzles at one time, and takes ~26 seconds on my box. Let me know what you all think.


DROP TABLE #SudokuProblem
GO

CREATE TABLE #SudokuProblem (
  problemNo integer NOT NULL,
  step int not null,
  difficulty varchar(10) NOT NULL,
  notes varchar(200) NULL,
  settings char(81) NOT NULL
  PRIMARY KEY (problemNo, step, settings)
)

INSERT INTO #SudokuProblem

SELECT 1, 0, 'easy', 'can be done just applying prune',
  '  5   7  ' +
  '  61 39  ' +
  '7   5   8' +
  ' 839 716 ' +
  '         ' +
  ' 218 439 ' +
  '3   9   6' +
  '  75 82  ' +
  '  8   4  '
UNION ALL
SELECT 2, 0, 'easy', 'this needs pick too',
  '  3    51' +
  '5 2  64  ' +
  '  7 5    ' +
  '   63 7  ' +
  '2  7 8  6' +
  '  4 21   ' +
  '    7 8  ' +
  '  81  6 9' +
  '17    5  '
UNION ALL
SELECT 3, 0, 'tough', 'this one''s broken: there are 4 possible solutions',
  '2     7  ' +
  '  17324  ' +
  ' 76      ' +
  '      268' +
  ' 6 1 8 3 ' +
  '984      ' +
  '      14 ' +
  '  92568  ' +
  '  3     5'
UNION ALL
SELECT 4, 0, 'diabolical', NULL,
  ' 2 6 8   ' +
  '58   97  ' +
  '    4    ' +
  '37    5  ' +
  '6       4' +
  '  8    13' +
  '    2    ' +
  '  98   36' +
  '   3 6 9 '
UNION ALL
SELECT 5, 0, 'gentle', NULL,
  '4 9   7 8' +
  ' 562 391 ' +
  '1       5' +
  '   9 1   ' +
  ' 1  3  2 ' +
  '   6 8   ' +
  '3       9' +
  ' 918 567 ' +
  '6 8   5 2'
UNION ALL
SELECT 6, 0, 'moderate', NULL,
  '83 1     ' +
  '  6 7 5  ' +
  '   9    8' +
  ' 6   5 9 ' +
  '4  6 9  3' +
  ' 9 7   5 ' +
  '9    2   ' +
  '  1 8 9  ' +
  '     6 87'
UNION ALL
SELECT 7, 0, 'moderate', NULL,
  ' 3 6 2 8 ' +
  '  19 34  ' +
  '9       5' +
  '  7 3 5  ' +
  '1       8' +
  '  9 7 2  ' +
  '7       2' +
  '  83 46  ' +
  ' 4 5 7 9 '
UNION ALL
SELECT 8, 0, 'moderate', NULL,
  '  356 9  ' +
  '  8     4' +
  '9  8  65 ' +
  ' 85 12   ' +
  '         ' +
  '   94 17 ' +
  ' 64  1  9' +
  '1     8  ' +
  '  2 963  '
UNION ALL
SELECT 9, 0, 'gentle', NULL,
  '7   2   4' +
  '26     93' +
  '   9 5   ' +
  ' 8  7  61' +
  '  6   3  ' +
  '32  9  5 ' +
  '   1 2   ' +
  '19     75' +
  '8   3   6'
UNION ALL
SELECT 10, 0, 'moderate', NULL,
  '  6   1  ' +
  '   7 2   ' +
  '95     82' +
  '  45 38  ' +
  '51     29' +
  '  91 86  ' +
  '86     53' +
  '   8 9   ' +
  '  5   4  '
UNION ALL
SELECT 11, 0, 'moderate', NULL,
  '   56 421' +
  '    9  86' +
  '  2   7  ' +
  '8  4   1 ' +
  '  5   3  ' +
  ' 1   8  7' +
  '  1   9  ' +
  '47  2    ' +
  '639 41   '
UNION ALL
SELECT 12, 0, 'tough', NULL,
  '      128' +
  '2 4  9 7 ' +
  ' 7  3 4  ' +
  '1   2  3 ' +
  ' 5     8 ' +
  ' 6  9   1' +
  '  7 6  1 ' +
  ' 9 2  3 7' +
  '528      '
UNION ALL
SELECT 13, 0, 'diabolical', NULL,
  ' 125 487 ' +
  '         ' +
  '75     23' +
  '  41 87  ' +
  ' 2  5  4 ' +
  '  34 95  ' +
  '48     17' +
  '         ' +
  ' 357 169 '
UNION ALL
SELECT 49, 0, 'diabolical', NULL,
  '   6   29' +
  ' 4 5   3 ' +
  '  7  14  ' +
  '7   54   ' +
  ' 53   24 ' +
  '   12   3' +
  '  54  1  ' +
  ' 6   8 5 ' +
  '82   5   '
UNION ALL
SELECT 55, 0, 'diabolical', NULL,
  '2  3     ' +
  '8 4 62  3' +
  ' 138     ' +
  '      39 ' +
  '5 7   6 1' +
  ' 32      ' +
  '     914 ' +
  '6  25 8 9' +
  '     1  2'
UNION ALL
SELECT 62, 0, 'diabolical', NULL,
  ' 4 6     ' +
  '51    9 6' +
  '  8 3   4' +
  '7 1 62   ' +
  ' 8     6 ' +
  '   47 5 1' +
  '3   4 6  ' +
  '1 2    38' +
  '     6 9 '
UNION ALL
SELECT 69, 0, 'diabolical', NULL,
  '   81  65' +
  '51  67  8' +
  '         ' +
  ' 9   4 3 ' +
  ' 61   97 ' +
  ' 5 3   8 ' +
  '         ' +
  '6  78  93' +
  '17  59   '
UNION ALL
SELECT 76, 0, 'diabolical', NULL,
  '  1    4 ' +
  '95     17' +
  '  78  56 ' +
  '4   97 5 ' +
  '    8    ' +
  ' 3 54   1' +
  ' 62  41  ' +
  '19     86' +
  ' 7    9  '


Declare @rPos int,
	@rNum int,
	@rCnt int,
	@cPos int,
	@cNum int,
	@cCnt int,
	@step int

Set @step = 0

While @step < 100
Begin
	-- get possible entries (from the row point of view)
	Select
		problemNo,
		rPos, 
		rNum = Y.Number,
		rCnt = count(*)
	Into #rCntsPrep
	From
		(
		Select problemNo, step, difficulty, notes,
			rPos = B.number,
			cPos = C.number,
			row = substring(Settings,1+9*(B.number-1),9),
			col = substring(Settings,C.number+9*0,1) + substring(Settings,C.number+9*1,1) + substring(Settings,C.number+9*2,1) +
				substring(Settings,C.number+9*3,1) + substring(Settings,C.number+9*4,1) + substring(Settings,C.number+9*5,1) +
				substring(Settings,C.number+9*6,1) + substring(Settings,C.number+9*7,1) + substring(Settings,C.number+9*8,1),
			settings
		From #SudokuProblem A, admin.dbo.getsequence(1,9,1) B, admin.dbo.getsequence(1,9,1) C
		Where step=@step
		) Z, admin.dbo.getsequence(1,9,1) Y
	Where substring(row,cPos,1)=''
	and row not like '%'+convert(varchar,Y.number)+'%'
	and col not like '%'+convert(varchar,Y.number)+'%'
	Group By problemNo, rPos, Y.number
	order by count(*)

	-- filter to get the most reliable position (from the row point of view)
	Select Z.problemNo, Z.rPos, rNum=min(Z.rNum), Z.rCnt
	Into #rCnts
	From #rCntsPrep Z
	Inner Join
		(
		Select A.problemNo, rPos=min(A.rPos), A.rCnt
		From #rCntsPrep A
		Inner Join (Select problemNo, rCnt = min(rCnt) From #rCntsPrep Group By problemNo) B
		On A.problemNo = B.problemNo
		and A.rCnt = B.rCnt
		Group By A.problemNo, A.rCnt
		) Y
	On Z.problemNo = Y.problemNo
	and Z.rCnt = Y.rCnt
	and Z.rPos = Y.rPos
	Group By Z.problemNo, Z.rPos, Z.rCnt

--	Select * From #rCnts

	-- get possible entries (from the column point of view)
	Select
		problemNo,
		cPos, 
		cNum = Y.Number,
		cCnt = count(*)
	Into #cCntsPrep
	From
		(
		Select problemNo, step, difficulty, notes,
			rPos = B.number,
			cPos = C.number,
			row = substring(Settings,1+9*(B.number-1),9),
			col = substring(Settings,C.number+9*0,1) + substring(Settings,C.number+9*1,1) + substring(Settings,C.number+9*2,1) +
				substring(Settings,C.number+9*3,1) + substring(Settings,C.number+9*4,1) + substring(Settings,C.number+9*5,1) +
				substring(Settings,C.number+9*6,1) + substring(Settings,C.number+9*7,1) + substring(Settings,C.number+9*8,1),
			settings
		From #SudokuProblem A, admin.dbo.getsequence(1,9,1) B, admin.dbo.getsequence(1,9,1) C
		Where step=@step
		) Z, admin.dbo.getsequence(1,9,1) Y
	Where substring(row,cPos,1)=''
	and row not like '%'+convert(varchar,Y.number)+'%'
	and col not like '%'+convert(varchar,Y.number)+'%'
	Group By problemNo, cPos, Y.number
	order by count(*)

	-- filter to get the most reliable position (from the column point of view)
	Select Z.problemNo, Z.cPos, cNum=min(Z.cNum), Z.cCnt
	Into #cCnts
	From #cCntsPrep Z
	Inner Join
		(
		Select A.problemNo, cPos=min(A.cPos), A.cCnt
		From #cCntsPrep A
		Inner Join (Select problemNo, cCnt = min(cCnt) From #cCntsPrep Group By problemNo) B
		On A.problemNo = B.problemNo
		and A.cCnt = B.cCnt
		Group By A.problemNo, A.cCnt
		) Y
	On Z.problemNo = Y.problemNo
	and Z.cCnt = Y.cCnt
	and Z.cPos = Y.cPos
	Group By Z.problemNo, Z.cPos, Z.cCnt

--	Select * From #cCnts

	-- insert next possible steps for all problems
	Insert Into #SudokuProblem
	Select 
		Z.problemNo, 
		step=step+1,
		Z.difficulty,
		Z.notes,
		settings = stuff(settings,9*(Z.rPos-1)+Z.cPos,1,convert(varchar,Y.number))
	From
		(
		Select problemNo, step, difficulty, notes,
			rPos = B.number,
			cPos = C.number,
			row = substring(Settings,1+9*(B.number-1),9),
			col = substring(Settings,C.number+9*0,1) + substring(Settings,C.number+9*1,1) + substring(Settings,C.number+9*2,1) +
				substring(Settings,C.number+9*3,1) + substring(Settings,C.number+9*4,1) + substring(Settings,C.number+9*5,1) +
				substring(Settings,C.number+9*6,1) + substring(Settings,C.number+9*7,1) + substring(Settings,C.number+9*8,1),
			settings
		From #SudokuProblem A, admin.dbo.getsequence(1,9,1) B, admin.dbo.getsequence(1,9,1) C
		Where step=@step
		) Z, admin.dbo.getsequence(1,9,1) Y, #rCnts X, #cCnts W
	Where substring(row,Z.cPos,1)=''
	and row not like '%'+convert(varchar,Y.number)+'%'
	and col not like '%'+convert(varchar,Y.number)+'%'
	and Z.problemNo = X.problemNo and Z.problemNo = W.problemNo 
	and
	(
		((case when X.rCnt<=W.cCnt then 1 else 0 end)=1 and Z.rPos=X.rPos and Y.number=X.rNum)
		or
		((case when X.rCnt<=W.cCnt then 1 else 0 end)=0 and Z.cPos=W.cPos and Y.number=W.cNum)
	)


	-- cleanup temp tables
	Drop Table #rCntsPrep
	Drop Table #rCnts

	Drop Table #cCntsPrep
	Drop Table #cCnts

	--Select * From #SudokuProblem where step=@step

	Set @step = @step + 1

	-- if you want to see all of the steps comment out the following delete statement
	Delete A 
	From #SudokuProblem A
	Inner Join (Select problemNo, step = max(step) From #SudokuProblem Group by problemNo) B
	On A.problemNo = B.problemNo
	Where A.step < B.step
End

Select * From #SudokuProblem

Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2005-05-31 : 16:19:33

Just noticed mine has a few issues still... be back soon.

Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-05-31 : 22:18:13

This evaluates all solutions to a problem.
I am not sure if the filter for selecting all valid solutions is 100% proof,
it might give "faulty" answers, but I don't think so, just can't prove it.
Anyway, it will give all correct ones as well.
( I was to lazy to write out all the inequalities

)


------------- SETUP --------------
------------- need arnold's #SudokuProblem table ------------------
------------- Actually Corey's temporary verison... ---------------

drop table n
GO
drop table triple
GO
drop table #hgrid
GO
drop table #vgrid
GO
drop table #sqrs
GO

create table n(n tinyint primary key)
GO

insert n
select 1 union select 2 union select 3 union select 4 union select 5
union select 6 union select 7 union select 8 union select 9

create table triple (a tinyint, b tinyint, c tinyint, primary key(a,b,c))
GO

insert triple
select * from n n1, n n2, n n3
where n1.n <> n2.n and n1.n <> n3.n and n2.n <> n3.n


create table #hgrid(line tinyint primary key, nbrs varchar(9))
GO
create table #vgrid(line tinyint primary key, nbrs varchar(9))
GO
create table #sqrs(s int, a int, b int, c int, d int, e int, f int, g int, h int, i int)
GO

------------------ END SETUP ---------------------
------------------ RUN FROM HERE AFTER SETUP -----

truncate table #sqrs
truncate table #hgrid
truncate table #vgrid

-- select * from #SudokuProblem
insert #hgrid(line,nbrs)
select n ,substring(settings,1 + (n-1)*9,9)
from #SudokuProblem cross join n
where problemNo = 49	----------------<-------------------- CHOOSE PROBLEM

declare @nbrs varchar(9), @i int, @h int, @v int
set @i = 1
while @i < 10
begin
	set @nbrs = ''
	select @nbrs = @nbrs  +  substring(nbrs,@i,1) from #hgrid
	insert #vgrid(line,nbrs)
	select @i, @nbrs
	set @i = @i  +  1
end

set @i = 1

while @i < 10
begin
	select @h = 3*((@i-1)%3), @v = 3*((@i-1)/3)

	insert #sqrs
	select 	@i as s, t1.a a ,t1.b b ,t1.c c, t2.a d ,t2.b e ,t2.c f, t3.a g ,t3.b h ,t3.c i
	from
		triple t1
		join triple t2
			on (t1.a <> t2.a and t1.a <> t2.b and t1.a <> t2.c)
			and (t1.b <> t2.a and t1.b <> t2.b and t1.b <> t2.c)
			and (t1.c <> t2.a and t1.c <> t2.b and t1.c <> t2.c)
		join triple t3
			on (t1.a <> t3.a and t1.a <> t3.b and t1.a <> t3.c)
			and (t1.b <> t3.a and t1.b <> t3.b and t1.b <> t3.c)
			and (t1.c <> t3.a and t1.c <> t3.b and t1.c <> t3.c)
			and (t2.a <> t3.a and t2.a <> t3.b and t2.a <> t3.c)
			and (t2.b <> t3.a and t2.b <> t3.b and t2.b <> t3.c)
			and (t2.c <> t3.a and t2.c <> t3.b and t2.c <> t3.c)
		join #hgrid h1 on h1.line = 1 + @v
		join #vgrid v1 on v1.line = 1 + @h
		join #hgrid h2 on h2.line = 2 + @v
		join #vgrid v2 on v2.line = 2 + @h
		join #hgrid h3 on h3.line = 3 + @v
		join #vgrid v3 on v3.line = 3 + @h
	where
		( cast(t1.a as char(1)) = substring(h1.nbrs,1 + @h,1) or (substring(h1.nbrs,1 + @h,1) = '' and charindex(cast(t1.a as char(1)),h1.nbrs)  +  charindex(cast(t1.a as char(1)),v1.nbrs) = 0))
		and( cast(t1.b as char(1)) = substring(h1.nbrs,2 + @h,1) or (substring(h1.nbrs,2 + @h,1) = '' and charindex(cast(t1.b as char(1)),h1.nbrs)  +  charindex(cast(t1.b as char(1)),v2.nbrs) = 0))
		and( cast(t1.c as char(1)) = substring(h1.nbrs,3 + @h,1) or (substring(h1.nbrs,3 + @h,1) = '' and charindex(cast(t1.c as char(1)),h1.nbrs)  +  charindex(cast(t1.c as char(1)),v3.nbrs) = 0))
		and( cast(t2.a as char(1)) = substring(h2.nbrs,1 + @h,1) or (substring(h2.nbrs,1 + @h,1) = '' and charindex(cast(t2.a as char(1)),h2.nbrs)  +  charindex(cast(t2.a as char(1)),v1.nbrs) = 0))
		and( cast(t2.b as char(1)) = substring(h2.nbrs,2 + @h,1) or (substring(h2.nbrs,2 + @h,1) = '' and charindex(cast(t2.b as char(1)),h2.nbrs)  +  charindex(cast(t2.b as char(1)),v2.nbrs) = 0))
		and( cast(t2.c as char(1)) = substring(h2.nbrs,3 + @h,1) or (substring(h2.nbrs,3 + @h,1) = '' and charindex(cast(t2.c as char(1)),h2.nbrs)  +  charindex(cast(t2.c as char(1)),v3.nbrs) = 0))
		and( cast(t3.a as char(1)) = substring(h3.nbrs,1 + @h,1) or (substring(h3.nbrs,1 + @h,1) = '' and charindex(cast(t3.a as char(1)),h3.nbrs)  +  charindex(cast(t3.a as char(1)),v1.nbrs) = 0))
		and( cast(t3.b as char(1)) = substring(h3.nbrs,2 + @h,1) or (substring(h3.nbrs,2 + @h,1) = '' and charindex(cast(t3.b as char(1)),h3.nbrs)  +  charindex(cast(t3.b as char(1)),v2.nbrs) = 0))
		and( cast(t3.c as char(1)) = substring(h3.nbrs,3 + @h,1) or (substring(h3.nbrs,3 + @h,1) = '' and charindex(cast(t3.c as char(1)),h3.nbrs)  +  charindex(cast(t3.c as char(1)),v3.nbrs) = 0))
	set @i = @i  +  1
end


select
	cast(s1.a as char(1))+cast(s1.b as char(1))+cast(s1.c as char(1))+cast(s2.a as char(1))+cast(s2.b as char(1))+cast(s2.c as char(1))+cast(s3.a as char(1))+cast(s3.b as char(1))+cast(s3.c as char(1))+
	char(10)+cast(s1.d as char(1))+cast(s1.e as char(1))+cast(s1.f as char(1))+cast(s2.d as char(1))+cast(s2.e as char(1))+cast(s2.f as char(1))+cast(s3.d as char(1))+cast(s3.e as char(1))+cast(s3.f as char(1))+
	char(10)+cast(s1.g as char(1))+cast(s1.h as char(1))+cast(s1.i as char(1))+cast(s2.g as char(1))+cast(s2.h as char(1))+cast(s2.i as char(1))+cast(s3.g as char(1))+cast(s3.h as char(1))+cast(s3.i as char(1))+
	char(10)+cast(s4.a as char(1))+cast(s4.b as char(1))+cast(s4.c as char(1))+cast(s5.a as char(1))+cast(s5.b as char(1))+cast(s5.c as char(1))+cast(s6.a as char(1))+cast(s6.b as char(1))+cast(s6.c as char(1))+
	char(10)+cast(s4.d as char(1))+cast(s4.e as char(1))+cast(s4.f as char(1))+cast(s5.d as char(1))+cast(s5.e as char(1))+cast(s5.f as char(1))+cast(s6.d as char(1))+cast(s6.e as char(1))+cast(s6.f as char(1))+
	char(10)+cast(s4.g as char(1))+cast(s4.h as char(1))+cast(s4.i as char(1))+cast(s5.g as char(1))+cast(s5.h as char(1))+cast(s5.i as char(1))+cast(s6.g as char(1))+cast(s6.h as char(1))+cast(s6.i as char(1))+
	char(10)+cast(s7.a as char(1))+cast(s7.b as char(1))+cast(s7.c as char(1))+cast(s8.a as char(1))+cast(s8.b as char(1))+cast(s8.c as char(1))+cast(s9.a as char(1))+cast(s9.b as char(1))+cast(s9.c as char(1))+
	char(10)+cast(s7.d as char(1))+cast(s7.e as char(1))+cast(s7.f as char(1))+cast(s8.d as char(1))+cast(s8.e as char(1))+cast(s8.f as char(1))+cast(s9.d as char(1))+cast(s9.e as char(1))+cast(s9.f as char(1))+
	char(10)+cast(s7.g as char(1))+cast(s7.h as char(1))+cast(s7.i as char(1))+cast(s8.g as char(1))+cast(s8.h as char(1))+cast(s8.i as char(1))+cast(s9.g as char(1))+cast(s9.h as char(1))+cast(s9.i as char(1))
	+char(10) as grid
from
(select * from #sqrs where s = 1) s1
join (select * from #sqrs where s = 2) s2
	on 1 = 1
join (select * from #sqrs where s = 3) s3
	on s1.a + s1.b + s1.c + s2.a + s2.b + s2.c + s3.a + s3.b + s3.c = 45
	and s1.d + s1.e + s1.f + s2.d + s2.e + s2.f + s3.d + s3.e + s3.f = 45
	and s1.g + s1.h + s1.i + s2.g + s2.h + s2.i + s3.g + s3.h + s3.i = 45
	and s1.a * s1.b * s1.c * s2.a * s2.b * s2.c * s3.a * s3.b * s3.c = 362880
	and s1.d * s1.e * s1.f * s2.d * s2.e * s2.f * s3.d * s3.e * s3.f = 362880
	and s1.g * s1.h * s1.i * s2.g * s2.h * s2.i * s3.g * s3.h * s3.i = 362880
join (select * from #sqrs where s = 4) s4
	on 1 = 1
join (select * from #sqrs where s = 5) s5
	on 1 = 1
join (select * from #sqrs where s = 6) s6
	on s4.a + s4.b + s4.c + s5.a + s5.b + s5.c + s6.a + s6.b + s6.c = 45
	and s4.d + s4.e + s4.f + s5.d + s5.e + s5.f + s6.d + s6.e + s6.f = 45
	and s4.g + s4.h + s4.i + s5.g + s5.h + s5.i + s6.g + s6.h + s6.i = 45
	and s4.a * s4.b * s4.c * s5.a * s5.b * s5.c * s6.a * s6.b * s6.c = 362880
	and s4.d * s4.e * s4.f * s5.d * s5.e * s5.f * s6.d * s6.e * s6.f = 362880
	and s4.g * s4.h * s4.i * s5.g * s5.h * s5.i * s6.g * s6.h * s6.i = 362880
join (select * from #sqrs where s = 7) s7
	on 1 = 1
join (select * from #sqrs where s = 8) s8
	on 1 = 1
join (select * from #sqrs where s = 9) s9
	on s7.a + s7.b + s7.c + s8.a + s8.b + s8.c + s9.a + s9.b + s9.c = 45
	and s7.d + s7.e + s7.f + s8.d + s8.e + s8.f + s9.d + s9.e + s9.f = 45
	and s7.g + s7.h + s7.i + s8.g + s8.h + s8.i + s9.g + s9.h + s9.i = 45
	and s7.a * s7.b * s7.c * s8.a * s8.b * s8.c * s9.a * s9.b * s9.c = 362880
	and s7.d * s7.e * s7.f * s8.d * s8.e * s8.f * s9.d * s9.e * s9.f = 362880
	and s7.g * s7.h * s7.i * s8.g * s8.h * s8.i * s9.g * s9.h * s9.i = 362880
where
	s1.a + s1.d + s1.g + s4.a + s4.d + s4.g + s7.a + s7.d + s7.g = 45
	and s1.b + s1.e + s1.h + s4.b + s4.e + s4.h + s7.b + s7.e + s7.h = 45
	and s1.c + s1.f + s1.i + s4.c + s4.f + s4.i + s7.c + s7.f + s7.i = 45
	and s2.a + s2.d + s2.g + s5.a + s5.d + s5.g + s8.a + s8.d + s8.g = 45
	and s2.b + s2.e + s2.h + s5.b + s5.e + s5.h + s8.b + s8.e + s8.h = 45
	and s2.c + s2.f + s2.i + s5.c + s5.f + s5.i + s8.c + s8.f + s8.i = 45
	and s3.a + s3.d + s3.g + s6.a + s6.d + s6.g + s9.a + s9.d + s9.g = 45
	and s3.b + s3.e + s3.h + s6.b + s6.e + s6.h + s9.b + s9.e + s9.h = 45
	and s3.c + s3.f + s3.i + s6.c + s6.f + s6.i + s9.c + s9.f + s9.i = 45
	and s1.a * s1.d * s1.g * s4.a * s4.d * s4.g * s7.a * s7.d * s7.g = 362880
	and s1.b * s1.e * s1.h * s4.b * s4.e * s4.h * s7.b * s7.e * s7.h = 362880
	and s1.c * s1.f * s1.i * s4.c * s4.f * s4.i * s7.c * s7.f * s7.i = 362880
	and s2.a * s2.d * s2.g * s5.a * s5.d * s5.g * s8.a * s8.d * s8.g = 362880
	and s2.b * s2.e * s2.h * s5.b * s5.e * s5.h * s8.b * s8.e * s8.h = 362880
	and s2.c * s2.f * s2.i * s5.c * s5.f * s5.i * s8.c * s8.f * s8.i = 362880
	and s3.a * s3.d * s3.g * s6.a * s6.d * s6.g * s9.a * s9.d * s9.g = 362880
	and s3.b * s3.e * s3.h * s6.b * s6.e * s6.h * s9.b * s9.e * s9.h = 362880
	and s3.c * s3.f * s3.i * s6.c * s6.f * s6.i * s9.c * s9.f * s9.i = 362880

rockmoose

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2005-07-09 : 16:18:39

I hope you folks don't mind that I re awakened this thread. My local paper (Washington Post) just started printing these puzzles. I did a few of them the old fasioned way (instead of my usual crossword) and decided to try to create a programmatic tsql version of the algorithm I used to do them manually. It ended up to be variations of Arnold's and Corey's versions. It only solves for the first solution it finds but it works pretty quickly (the easy ones are sub-second and tough ones are between 1 and 3 seconds on my laptop depending on the luck of random choices for whatIf scenarios). Anyway, here it is:

EDIT: (new version)


set nocount on

declare @numbers table (n int)
declare @p table (r int, c int, q int, v int, vType varchar(15))
declare @possibleVals table (r int, c int, q int, v int)
declare @selectedVals table (r int, c int, q int, v int)
declare @distinctVals table (v int)

declare @i tinyint
	,@row int
	,@col int
	,@quad int
	,@val int
	,@vType varchar(15)
	,@pStr varchar(90)
	,@valcount int
	,@lastcount int
	,@origCount int
	,@loopCount int
	,@whatIfAttempts int
	,@puzzleResult varchar(9)

insert @numbers
select 1 union
select 2 union
select 3 union
select 4 union
select 5 union
select 6 union
select 7 union
select 8 union
select 9

--============================================================
--Set up the puzzle

--pretty easy one from Washington Post
set @pStr =
'-7-1-2-9-' +
'---564---' +
'--6---1--' +
'--4---9--' +
'-157-832-' +
'--7---6--' +
'--9---2--' +
'---359---' +
'-4-6-7-8-'

--No 1 from Arnold/Corey posts (easy)
set @pStr =
  '  5   7  ' +
  '  61 39  ' +
  '7   5   8' +
  ' 839 716 ' +
  '         ' +
  ' 218 439 ' +
  '3   9   6' +
  '  75 82  ' +
  '  8   4  '

--No 76 from Arnold/Corey posts (diabolical)
set @pStr =
  '  1    4 ' +
  '95     17' +
  '  78  56 ' +
  '4   97 5 ' +
  '    8    ' +
  ' 3 54   1' +
  ' 62  41  ' +
  '19     86' +
  ' 7    9  '

--medium easy one from Washington Post
set @pStr =
'1------45' +
'2--7--8--' +
'-8--69---' +
'--2-5--1-' +
'--41-37--' +
'-1--4-5--' +
'---98--3-' +
'--6--1--8' +
'84------1'

--No 76 from Arnold/Corey posts (diabolical)
set @pStr =
  '  1    4 ' +
  '95     17' +
  '  78  56 ' +
  '4   97 5 ' +
  '    8    ' +
  ' 3 54   1' +
  ' 62  41  ' +
  '19     86' +
  ' 7    9  '

--virtually empty, many possible solutions
set @pStr = 
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '1        '

--invalid setup test
set @pStr = 
  '         ' +
  '         ' +
  '1        ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '         ' +
  '1        '

--No 69 from Arnold/Corey posts (diabolical)
set @pStr =
  '   81  65' +
  '51  67  8' +
  '         ' +
  ' 9   4 3 ' +
  ' 61   97 ' +
  ' 5 3   8 ' +
  '         ' +
  '6  78  93' +
  '17  59   '

set @pStr = replace(@pStr, ' ', '-')

select	@vType = 'Original'
	,@i = 1
while @i < 82
begin
	select	@row = ceiling(@i/9.00)
		,@col = isnull(nullif(@i%9,0),9)
		,@quad = 
			case 
			when @row between 1 and 3 then
				case
				when @col between 1 and 3 then 1
				when @col between 4 and 6 then 2
				when @col between 7 and 9 then 3
				end
			when @row between 4 and 6 then
				case
				when @col between 1 and 3 then 4
				when @col between 4 and 6 then 5
				when @col between 7 and 9 then 6
				end
			when @row between 7 and 9 then
				case
				when @col between 1 and 3 then 7
				when @col between 4 and 6 then 8
				when @col between 7 and 9 then 9
				end
			end
		,@val = nullif(substring(@pStr,@i,1),'-')
		,@i = @i+1

	insert @p (r,c,q,v,vType)
	values (@row, @col, @quad, @val, @vType)
	
end


--find out if puzzle can be solved (invalid setup)
if exists(select 'tg' from @p where v is not null group by r,v having count(*) > 1)
or exists(select 'tg' from @p where v is not null group by c,v having count(*) > 1)
or exists(select 'tg' from @p where v is not null group by q,v having count(*) > 1)
begin
	print 'puzzle has invalid set up.  It violates the rules'
	return
end

--print puzzle setup
set @pStr = ''
set @i = 1
while @i < 82
begin
	select	@row = ceiling(@i/9.00)
		,@col = isnull(nullif(@i%9,0),9)
		,@i = @i+1

	select @val = v from @p where r = @row and c = @col

	select	@pStr = @pStr + isNull(convert(varchar,v),'-')
	from	@p
	where	r = @row 
	and	c = @col

	if @col = 9 set @pStr = @pStr + char(13)
end

select @pStr [puzzleSetup]

--============================================================
--solve the puzzle

select	@origCount = count(*)
	,@loopcount = 0
	,@whatIfAttempts = 0
from	@p 
where v is not null

--For different whatif scenario, start over from here
TryAgain:

if @WhatIfAttempts > 10
	goto cutprint

--set/reset puzzle to point before 1st whatIf scenario
update @p set 
	v = null
	,vType = 'Original'
where vType like 'WhatIf%'

select @valCount = count(*)
	,@lastCount = 0
	,@vType = 'Original'
from	@p
where	v is not null

--start loop to solve
while (@valcount <> @lastcount and @valcount < 81) or @valcount = 0
begin
	--reinitialize vars for next loop
	select	@lastcount = @valcount
		,@loopCount = @loopCount + 1
		,@vType = case when @vType like 'WhatIf%' then 'WhatIfOneValue' else 'OneValue' end

	--reinitialize tabel vars for next loop
	delete @possibleVals
	delete @selectedVals
	delete @distinctVals

	--insert all possible values for each position to @possibleVals table
	--based on known values in each row, column, and quadrant
	insert @possibleVals (r,c,q,v)
	select	a.r, a.c, a.q, b.n
	from	@p a
	cross join @numbers b
	where	b.n not in
		(
		select	v
		from	@p
		where	r = a.r
		and	v is not null
		union
		select	v
		from	@p
		where	c = a.c
		and	v is not null
		union
		select	v
		from	@p
		where	q = a.q
		and	v is not null
		)
	and	v is null

	if @@rowcount = 0
	begin
		--this could happen for an incorrect WhatIf scenario
		set @whatIfAttempts = @whatIfAttempts + 1
		goto tryAgain
	end

	--------------------------------------------------------------------
	--all sections must solve for only one possible solution at a time
	--if this puzzle has multiple solutions, don't allow a column, row, 
	--or quadrant to have a repeated value.

	--get a distinct list of possible values
	insert @distinctVals
	select	distinct v
	from	(--get all values where the position has only one possible value
		select	min(v) v
		from	@possibleVals
		group by r,c
		having count(*) = 1
		) a


	--------------------------------------------------------------------
	--This section sets the value for all positions where there is 
	--only one possible value based on known values in the position's 
	--row, column, or quadrant.

	while @@rowcount > 0
	begin
		--get 1 position for each distinct value
		insert	@selectedVals (r,c,q,v)
		select	a.r, a.c, a.q, a.v
		from	@possibleVals a
		join	(--only one position for each distinct value
			select	min( (r*10)+c ) rc, a.v
			from	@distinctVals a	
			join	(--only positions with 1 possible value
				select r, c, min(v) v
				from	@possibleVals
				group by r,c
				having count(*) = 1
				) b
					on a.v = b.v
			group by a.v
			) b
				on a.v = b.v
				and (a.r*10)+a.c = rc
		where	not exists (
				select	'tg'
				from	@selectedVals
				where	v = a.v
				and	(r = a.r or c = a.c or q = a.q)
				)
	end

	--@selectedVals now contains every position that
	--has only 1 possible value for this possible solution tree.
	update a set
		a.v = b.v
		,a.vType = @vType
	from	@p a
	join	@selectedVals b
			on a.r = b.r
			and a.c = b.c
	where	a.v is null

	--increment counts from last statement and get new valuecount
	select	@valcount = count(*) 
	from	@p 
	where	v is not null

	--------------------------------------------------------------------
	--This section sets the value for all positions where there are
	--at least 2 possible values.  Check for any position in a given 
	--row, column, or quadrant that is the only position in that rol, 
	--column or quadrant that could be set to a single value. 
	--(gotta be this value) only do this section if the previous section
	--set no new values.

	if @valcount = @lastcount
	and exists (select 'tg' from @p where v is null)
	begin
		set @vType = case when @vType like 'WhatIf%' then 'WhatIfGottaBee' else 'GottaBee' end

		-------------------------------------------
		--get gottabees by column
		insert @selectedVals (r,c,q,v)
		select	a.r, a.c, a.q, b.v
		from	@possibleVals a
		join	(--
			select	c, v
			from	@possibleVals
			group by c,v
			having count(*) = 1
			) b
				on a.c = b.c
				and a.v = b.v

		--get gottabees by row
		insert @selectedVals (r,c,q,v)
		select	a.r, a.c, a.q, b.v
		from	@possibleVals a
		join	(
			select	r, v
			from	@possibleVals
			group by r,v
			having count(*) = 1
			) b
				on a.r = b.r
				and a.v = b.v
		where not exists (
			select 'tg'
			from	@selectedVals
			where	v = b.v
			and	r = a.r
			and	c = a.c
			and	q = a.q)

		--get gottabees by quadrant
		insert @selectedVals (r,c,q,v)
		select	a.r, a.c, a.q, b.v
		from	@possibleVals a
		join	(
			select	q, v
			from	@possibleVals
			group by q,v
			having count(*) = 1
			) b
				on a.q = b.q
				and a.v = b.v
		where not exists (
			select 'tg'
			from	@selectedVals
			where	v = b.v
			and	r = a.r
			and	c = a.c
			and	q = a.q)

		update a set
			a.v = b.v
			,a.vType = @vType
		from	@p a
		join	@selectedVals b
				on a.r = b.r
				and a.c = b.c

		select	@valcount = count(*) 
		from	@p 
		where	v is not null
		-------------------------------------------
	end

	--------------------------------------------------------------------
	--If no new values have been set by the previous 2 sections and the
	--puzzle is not yet solved then set 1 position value to one of its
	--possible values as a Wwhat If Scenario.
	if @valcount = @lastcount
	and exists (select 'tg' from @p where v is null)
	begin
		select	@vType = 'WhatIf'
			,@WhatIfAttempts = isnull(nullif(@WhatIfAttempts,0),1)

		insert @selectedVals (r,c,v)
		select top 1 b.r, b.c, b.v
		from	(--find a random position that has(or is tied for) the fewest possible values
			select top 1 r,c
			from	@possibleVals
			group by r, c
			order by count(*), newid()
			) a
		join	@possibleVals b
				on a.r = b.r
				and a.c = b.c
		order by newid()

		update a set
			a.v = b.v
			,a.vType = @vType
		from	@p a
		join	@SelectedVals b
				on a.r = b.r
				and a.c = b.c
	end

	select @valcount = count(*) from @p where v is not null
end

--couldn't solve the puzzle so try again with a different what if scenario
if @valcount < 81
begin
	set @whatIfAttempts = @whatIfAttempts + 1
	goto TryAgain
end


--============================================================
--print solved puzzle and solving statistics

CutPrint:

set @pStr = ''
set @i = 1
while @i < 82
begin
	select	@row = ceiling(@i/9.00)
		,@col = isnull(nullif(@i%9,0),9)
		,@i = @i+1

	select @val = v from @p where r = @row and c = @col

	select	@pStr = @pStr + isNull(convert(varchar,v),'-')
	from	@p
	where	r = @row 
	and	c = @col

	if @col = 9 set @pStr = @pStr + char(13)
end

--print puzzle
select @pStr [PuzzleSolved]

--find out if its correct or not
if exists(select 'tg' from @p group by r having sum(v) <> 45 or count(distinct v) <> 9)
or exists(select 'tg' from @p group by c having sum(v) <> 45 or count(distinct v) <> 9)
or exists(select 'tg' from @p group by q having sum(v) <> 45 or count(distinct v) <> 9)
	set @puzzleResult = 'Incorrect'
else
	set @puzzleResult = 'Correct'

--print stats
select	Category, result
from	(
	select	1 rowid, 'PuzzleResult' category, @PuzzleResult result
	union
	select	2, 'TotalLoopsToSolve', convert(varchar,@loopcount)
	union
	select	3, 'WhatIfScenarioCount', convert(varchar,@WhatIfAttempts)
	union
	select	case 
		when vType = 'Original' then 4
		when vType = 'OneValue' then 5
		when vType = 'GottaBee' then 6
		when vType = 'WhatIf' then 7
		when vType = 'WhatIfOneValue' then 8
		else 9
		end
		,case
		when vType = 'Original' then 'OriginalValueCount'
		when vType = 'OneValue' then 'OnePossibleVal-Count'
		when vType = 'GottaBee' then 'GottaBee-Count'
		when vType = 'WhatIf' then 'WhatIf-Count'
		when vType = 'WhatIfOneValue' then 'WhatIfOneValue-Count'
		else 'WhatIfGottaBee-count'
		end
		,convert(varchar,count(*))
	from	@p 
	group by vType
	) a
order by rowid

Be One with the Optimizer
TG

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-07-09 : 21:15:02

TG, very fast.
For scenario 69, the results are a bit random on my computer.
Sometimes a correct, and sometimes an incorrect solution is given, example wrong solution of #69 on my pc:

puzzleSetup
-----------
---81--65
51--67--8
---------
-9---4-3-
-61---97-
-5-3---8-
---------
6--78--93
17--59---


PuzzleSolved
------------
749813265
514967328
836245719
298174536
361528974
457396182
984432657
625781493
173659842

TotalLoopsToSolve
-----------------
41

A repost with more Formatted Code, than my previous post, somewhat rewritten:
This runs in 5 sec on my PC.
Given the number of combinations of the 9 table crossjoin (18.114.969.600), and the "neat" where clause,
The query optimizer is very very good at shortcircuiting the # of evaluated combinations,
the vast majority are discarded very early in the process.

drop table triple
drop table #sqrs
DROP TABLE #SudokuProblem
GO

create table #SudokuProblem (
	problemNo int PRIMARY KEY,
	difficulty varchar(10) NOT NULL,
	notes varchar(200) NOT NULL,
	settings char(81) NOT NULL UNIQUE )

insert #SudokuProblem
select 1,'easy','can be done just applying prune','  5   7    61 39  7   5   8 839 716           218 439 3   9   6  75 82    8   4  '
union all select 2,'easy','this needs pick too','  3    515 2  64    7 5       63 7  2  7 8  6  4 21       7 8    81  6 917    5  '
union all select 3,'tough','this one''s broken: there are 4 possible solutions','2     7    17324   76            268 6 1 8 3 984            14   92568    3     5'
union all select 4,'diabolical','',' 2 6 8   58   97      4    37    5  6       4  8    13    2      98   36   3 6 9 '
union all select 5,'gentle','','4 9   7 8 562 391 1       5   9 1    1  3  2    6 8   3       9 918 567 6 8   5 2'
union all select 6,'moderate','','83 1       6 7 5     9    8 6   5 9 4  6 9  3 9 7   5 9    2     1 8 9       6 87'
union all select 7,'moderate','',' 3 6 2 8   19 34  9       5  7 3 5  1       8  9 7 2  7       2  83 46   4 5 7 9 '
union all select 8,'moderate','','  356 9    8     49  8  65  85 12               94 17  64  1  91     8    2 963  '
union all select 9,'gentle','','7   2   426     93   9 5    8  7  61  6   3  32  9  5    1 2   19     758   3   6'
union all select 10,'moderate','','  6   1     7 2   95     82  45 38  51     29  91 86  86     53   8 9     5   4  '
union all select 11,'moderate','','   56 421    9  86  2   7  8  4   1   5   3   1   8  7  1   9  47  2    639 41   '
union all select 12,'tough','','      1282 4  9 7  7  3 4  1   2  3  5     8  6  9   1  7 6  1  9 2  3 7528      '
union all select 13,'diabolical','',' 125 487          75     23  41 87   2  5  4   34 95  48     17          357 169 '
union all select 49,'diabolical','','   6   29 4 5   3   7  14  7   54    53   24    12   3  54  1   6   8 5 82   5   '
union all select 55,'diabolical','','2  3     8 4 62  3 138           39 5 7   6 1 32           914 6  25 8 9     1  2'
union all select 62,'diabolical','',' 4 6     51    9 6  8 3   47 1 62    8     6    47 5 13   4 6  1 2    38     6 9 '
union all select 69,'diabolical','','   81  6551  67  8          9   4 3  61   97  5 3   8          6  78  9317  59   '
union all select 76,'diabolical','','  1    4 95     17  78  56 4   97 5     8     3 54   1 62  41  19     86 7    9  '
union all select 101,'diabolical','pretty easy one from Washington Post',' 7 1 2 9    564     6   1    4   9   157 832   7   6    9   2     359    4 6 7 8 '
union all select 141,'diabolical','medium easy one from Washington Post','1      452  7  8   8  69     2 5  1   41 37   1  4 5     98  3   6  1  884      1'

declare @problemNo int
set @problemNo = 69	----------------<-------------------- CHOOSE PROBLEM

declare @n table(n tinyint primary key)
declare @hgrid table(line tinyint primary key, nbrs varchar(9))
declare @vgrid table(line tinyint primary key, nbrs varchar(9))
create table #sqrs(s int, a int, b int, c int, d int, e int, f int, g int, h int, i int)
create table triple(a tinyint, b tinyint, c tinyint, primary key(a,b,c))

insert @n
select 1 union select 2 union select 3 union select 4 union select 5
union select 6 union select 7 union select 8 union select 9

insert triple
select * from @n n1, @n n2, @n n3
where n1.n <> n2.n and n1.n <> n3.n and n2.n <> n3.n


insert @hgrid(line,nbrs)
select n ,substring(settings,1 + (n-1)*9,9)
from #SudokuProblem cross join @n
where problemNo = @problemNo

declare @nbrs varchar(9), @i int, @h int, @v int
set @i = 1
while @i < 10
begin
	set @nbrs = ''
	select @nbrs = @nbrs  +  substring(nbrs,@i,1) from @hgrid
	insert @vgrid(line,nbrs)
	select @i, @nbrs
	set @i = @i  +  1
end

set @i = 1
while @i < 10
begin
	select @h = 3*((@i-1)%3), @v = 3*((@i-1)/3)

	insert #sqrs
	select 	@i as s, t1.a a ,t1.b b ,t1.c c, t2.a d ,t2.b e ,t2.c f, t3.a g ,t3.b h ,t3.c i
	from
		triple t1
		join triple t2
			on (t1.a <> t2.a and t1.a <> t2.b and t1.a <> t2.c)
			and (t1.b <> t2.a and t1.b <> t2.b and t1.b <> t2.c)
			and (t1.c <> t2.a and t1.c <> t2.b and t1.c <> t2.c)
		join triple t3
			on (t1.a <> t3.a and t1.a <> t3.b and t1.a <> t3.c)
			and (t1.b <> t3.a and t1.b <> t3.b and t1.b <> t3.c)
			and (t1.c <> t3.a and t1.c <> t3.b and t1.c <> t3.c)
			and (t2.a <> t3.a and t2.a <> t3.b and t2.a <> t3.c)
			and (t2.b <> t3.a and t2.b <> t3.b and t2.b <> t3.c)
			and (t2.c <> t3.a and t2.c <> t3.b and t2.c <> t3.c)
		join @hgrid h1 on h1.line = 1 + @v
		join @vgrid v1 on v1.line = 1 + @h
		join @hgrid h2 on h2.line = 2 + @v
		join @vgrid v2 on v2.line = 2 + @h
		join @hgrid h3 on h3.line = 3 + @v
		join @vgrid v3 on v3.line = 3 + @h
	where
		( cast(t1.a as char(1)) = substring(h1.nbrs,1 + @h,1) or (substring(h1.nbrs,1 + @h,1) = '' and charindex(cast(t1.a as char(1)),h1.nbrs)  +  charindex(cast(t1.a as char(1)),v1.nbrs) = 0))
		and( cast(t1.b as char(1)) = substring(h1.nbrs,2 + @h,1) or (substring(h1.nbrs,2 + @h,1) = '' and charindex(cast(t1.b as char(1)),h1.nbrs)  +  charindex(cast(t1.b as char(1)),v2.nbrs) = 0))
		and( cast(t1.c as char(1)) = substring(h1.nbrs,3 + @h,1) or (substring(h1.nbrs,3 + @h,1) = '' and charindex(cast(t1.c as char(1)),h1.nbrs)  +  charindex(cast(t1.c as char(1)),v3.nbrs) = 0))
		and( cast(t2.a as char(1)) = substring(h2.nbrs,1 + @h,1) or (substring(h2.nbrs,1 + @h,1) = '' and charindex(cast(t2.a as char(1)),h2.nbrs)  +  charindex(cast(t2.a as char(1)),v1.nbrs) = 0))
		and( cast(t2.b as char(1)) = substring(h2.nbrs,2 + @h,1) or (substring(h2.nbrs,2 + @h,1) = '' and charindex(cast(t2.b as char(1)),h2.nbrs)  +  charindex(cast(t2.b as char(1)),v2.nbrs) = 0))
		and( cast(t2.c as char(1)) = substring(h2.nbrs,3 + @h,1) or (substring(h2.nbrs,3 + @h,1) = '' and charindex(cast(t2.c as char(1)),h2.nbrs)  +  charindex(cast(t2.c as char(1)),v3.nbrs) = 0))
		and( cast(t3.a as char(1)) = substring(h3.nbrs,1 + @h,1) or (substring(h3.nbrs,1 + @h,1) = '' and charindex(cast(t3.a as char(1)),h3.nbrs)  +  charindex(cast(t3.a as char(1)),v1.nbrs) = 0))
		and( cast(t3.b as char(1)) = substring(h3.nbrs,2 + @h,1) or (substring(h3.nbrs,2 + @h,1) = '' and charindex(cast(t3.b as char(1)),h3.nbrs)  +  charindex(cast(t3.b as char(1)),v2.nbrs) = 0))
		and( cast(t3.c as char(1)) = substring(h3.nbrs,3 + @h,1) or (substring(h3.nbrs,3 + @h,1) = '' and charindex(cast(t3.c as char(1)),h3.nbrs)  +  charindex(cast(t3.c as char(1)),v3.nbrs) = 0))
	set @i = @i  +  1
end


select replace(substring(settings,1+(n-1)*9,9),' ','-') as puzzleSetup
from #SudokuProblem, @n
where problemNo = @problemNo
order by n

select cast(exp(sum(log(cnt))) as bigint) as NoOfCombinations
from (select s,count(*) as cnt from #sqrs group by s) t

select
	cast(s1.a as char(1))+cast(s1.b as char(1))+cast(s1.c as char(1))+cast(s2.a as char(1))+cast(s2.b as char(1))+cast(s2.c as char(1))+cast(s3.a as char(1))+cast(s3.b as char(1))+cast(s3.c as char(1))+
	char(10)+cast(s1.d as char(1))+cast(s1.e as char(1))+cast(s1.f as char(1))+cast(s2.d as char(1))+cast(s2.e as char(1))+cast(s2.f as char(1))+cast(s3.d as char(1))+cast(s3.e as char(1))+cast(s3.f as char(1))+
	char(10)+cast(s1.g as char(1))+cast(s1.h as char(1))+cast(s1.i as char(1))+cast(s2.g as char(1))+cast(s2.h as char(1))+cast(s2.i as char(1))+cast(s3.g as char(1))+cast(s3.h as char(1))+cast(s3.i as char(1))+
	char(10)+cast(s4.a as char(1))+cast(s4.b as char(1))+cast(s4.c as char(1))+cast(s5.a as char(1))+cast(s5.b as char(1))+cast(s5.c as char(1))+cast(s6.a as char(1))+cast(s6.b as char(1))+cast(s6.c as char(1))+
	char(10)+cast(s4.d as char(1))+cast(s4.e as char(1))+cast(s4.f as char(1))+cast(s5.d as char(1))+cast(s5.e as char(1))+cast(s5.f as char(1))+cast(s6.d as char(1))+cast(s6.e as char(1))+cast(s6.f as char(1))+
	char(10)+cast(s4.g as char(1))+cast(s4.h as char(1))+cast(s4.i as char(1))+cast(s5.g as char(1))+cast(s5.h as char(1))+cast(s5.i as char(1))+cast(s6.g as char(1))+cast(s6.h as char(1))+cast(s6.i as char(1))+
	char(10)+cast(s7.a as char(1))+cast(s7.b as char(1))+cast(s7.c as char(1))+cast(s8.a as char(1))+cast(s8.b as char(1))+cast(s8.c as char(1))+cast(s9.a as char(1))+cast(s9.b as char(1))+cast(s9.c as char(1))+
	char(10)+cast(s7.d as char(1))+cast(s7.e as char(1))+cast(s7.f as char(1))+cast(s8.d as char(1))+cast(s8.e as char(1))+cast(s8.f as char(1))+cast(s9.d as char(1))+cast(s9.e as char(1))+cast(s9.f as char(1))+
	char(10)+cast(s7.g as char(1))+cast(s7.h as char(1))+cast(s7.i as char(1))+cast(s8.g as char(1))+cast(s8.h as char(1))+cast(s8.i as char(1))+cast(s9.g as char(1))+cast(s9.h as char(1))+cast(s9.i as char(1))
	+char(10) as PuzzleSolved
from
	#sqrs s1, #sqrs s2, #sqrs s3, #sqrs s4, #sqrs s5, #sqrs s6, #sqrs s7, #sqrs s8, #sqrs s9
where
	(s1.s=1 and s2.s=2 and s3.s=3 and s4.s=4 and s5.s=5 and s6.s=6 and s7.s=7 and s8.s=8 and s9.s=9)
	and
	(s1.a + s1.b + s1.c + s2.a + s2.b + s2.c + s3.a + s3.b + s3.c = 45
	and s1.d + s1.e + s1.f + s2.d + s2.e + s2.f + s3.d + s3.e + s3.f = 45
	and s1.g + s1.h + s1.i + s2.g + s2.h + s2.i + s3.g + s3.h + s3.i = 45
	and s4.a + s4.b + s4.c + s5.a + s5.b + s5.c + s6.a + s6.b + s6.c = 45
	and s4.d + s4.e + s4.f + s5.d + s5.e + s5.f + s6.d + s6.e + s6.f = 45
	and s4.g + s4.h + s4.i + s5.g + s5.h + s5.i + s6.g + s6.h + s6.i = 45
	and s7.a + s7.b + s7.c + s8.a + s8.b + s8.c + s9.a + s9.b + s9.c = 45
	and s7.d + s7.e + s7.f + s8.d + s8.e + s8.f + s9.d + s9.e + s9.f = 45
	and s7.g + s7.h + s7.i + s8.g + s8.h + s8.i + s9.g + s9.h + s9.i = 45
	and s1.a + s1.d + s1.g + s4.a + s4.d + s4.g + s7.a + s7.d + s7.g = 45
	and s1.b + s1.e + s1.h + s4.b + s4.e + s4.h + s7.b + s7.e + s7.h = 45
	and s1.c + s1.f + s1.i + s4.c + s4.f + s4.i + s7.c + s7.f + s7.i = 45
	and s2.a + s2.d + s2.g + s5.a + s5.d + s5.g + s8.a + s8.d + s8.g = 45
	and s2.b + s2.e + s2.h + s5.b + s5.e + s5.h + s8.b + s8.e + s8.h = 45
	and s2.c + s2.f + s2.i + s5.c + s5.f + s5.i + s8.c + s8.f + s8.i = 45
	and s3.a + s3.d + s3.g + s6.a + s6.d + s6.g + s9.a + s9.d + s9.g = 45
	and s3.b + s3.e + s3.h + s6.b + s6.e + s6.h + s9.b + s9.e + s9.h = 45
	and s3.c + s3.f + s3.i + s6.c + s6.f + s6.i + s9.c + s9.f + s9.i = 45)
	and
	(s1.a * s1.b * s1.c * s2.a * s2.b * s2.c * s3.a * s3.b * s3.c = 362880
	and s1.d * s1.e * s1.f * s2.d * s2.e * s2.f * s3.d * s3.e * s3.f = 362880
	and s1.g * s1.h * s1.i * s2.g * s2.h * s2.i * s3.g * s3.h * s3.i = 362880
	and s4.a * s4.b * s4.c * s5.a * s5.b * s5.c * s6.a * s6.b * s6.c = 362880
	and s4.d * s4.e * s4.f * s5.d * s5.e * s5.f * s6.d * s6.e * s6.f = 362880
	and s4.g * s4.h * s4.i * s5.g * s5.h * s5.i * s6.g * s6.h * s6.i = 362880
	and s7.a * s7.b * s7.c * s8.a * s8.b * s8.c * s9.a * s9.b * s9.c = 362880
	and s7.d * s7.e * s7.f * s8.d * s8.e * s8.f * s9.d * s9.e * s9.f = 362880
	and s7.g * s7.h * s7.i * s8.g * s8.h * s8.i * s9.g * s9.h * s9.i = 362880
	and s1.a * s1.d * s1.g * s4.a * s4.d * s4.g * s7.a * s7.d * s7.g = 362880
	and s1.b * s1.e * s1.h * s4.b * s4.e * s4.h * s7.b * s7.e * s7.h = 362880
	and s1.c * s1.f * s1.i * s4.c * s4.f * s4.i * s7.c * s7.f * s7.i = 362880
	and s2.a * s2.d * s2.g * s5.a * s5.d * s5.g * s8.a * s8.d * s8.g = 362880
	and s2.b * s2.e * s2.h * s5.b * s5.e * s5.h * s8.b * s8.e * s8.h = 362880
	and s2.c * s2.f * s2.i * s5.c * s5.f * s5.i * s8.c * s8.f * s8.i = 362880
	and s3.a * s3.d * s3.g * s6.a * s6.d * s6.g * s9.a * s9.d * s9.g = 362880
	and s3.b * s3.e * s3.h * s6.b * s6.e * s6.h * s9.b * s9.e * s9.h = 362880
	and s3.c * s3.f * s3.i * s6.c * s6.f * s6.i * s9.c * s9.f * s9.i = 362880)

rockmoose

elwoos
Master Smack Fu Yak Hacker

2052 Posts

Posted - 2005-07-12 : 04:10:58

I always wondered if these could be solved using matrix manipulation/linear programming type techniques, aren't they "just" a set of simultaneous linear equations with some contraints?

steve

Alright Brain, you don't like me, and I don't like you. But lets just do this, and I can get back to killing you with beer.

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2005-07-15 : 13:52:39

quote:
TG, very fast.
For scenario 69, the results are a bit random on my computer.
Sometimes a correct, and sometimes an incorrect solution is given, example wrong solution of #69 on my pc:

Yep, the Washington Post puzzles only have 1 possible solution so when I wrote
my version I didn't think about the possibility of multiple solutions.
I've beefed up my verion to only solve for one solution at a time. If it
hits a wall it tries a different "what if" scenario.

I also added a puzzle with only 1 pre-set value. It still finishes pretty
quickly (about 7 seconds). I think that one is a killer for the brute force
versions like Rockmoose's. Although, I am very impressed with the approach
and the efficiency his considering the extreme number of possible combinations.

Because of the length of the code I'm just going to update my original, flawed
post with the corrected version. What a fun waste of time this has been (Thanks nr!)

Be One with the Optimizer
TG

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-07-15 : 14:25:09

>> I think that one is a killer for the brute force versions like Rockmoose's

Yes, it will definitely not work.
However, to find an answer, You can always add any random pre-sets You want,
as long as You don't change the originals, it will give a correct answer if any answer is found.

I did a test, for fun, by removing some pre-sets, I aborted this after 15 min, it had found ~ 70 Answers by then.
here are the first 3...

[/code]puzzleSetup
-----------
1------45
2--7--8--
-8--69---
--2-5--1-
--41-37--
-1--4-5--
---98----
---------
---------

select 7*9888*108*6*96*32*6*11304*56*6*100 as NoOfCombinations
--------------------------------------------------------------
Server: Msg 8115, Level 16, State 2, Line 112
Arithmetic overflow error converting expression to data type bigint.

Answer is : 313.996.922.537.272.934.400

PuzzleSolved
--------------------------------------------------------------------
179328645
246715839
385469127
932857416
564193782
718246593
651982374
897634251
423571968

179328645
246715839
385469127
932857416
564193782
718246593
651982374
827634951
493571268

179328645
246715839
385469127
932857416
654193782
718246593
561982374
897634251
423571968[/code]

rockmoose

Kristen
Test

22859 Posts

Posted - 2006-01-03 : 12:14:16

New Scientist published an article on Sudoku (24/31 December 2005) that gave three examples:

-- New Scientist - minimum usage of 17 "hints" (a)
set @pStr =
'1-----7--' +
'2--------' +
'---3-----' +
'78--6----' +
'---4---3-' +
'---------' +
'-341---5-' +
'-5--786--' +
'--7---1--'

-- New Scientist - minimum usage of 17 "hints" (b)
set @pStr =
'------6-1' +
'-4-2-----' +
'---------' +
'---7---2-' +
'13-------' +
'5--4-----' +
'4-2-1----' +
'----563--' +
'-------8-'

-- New Scientist - Max. hints with no solution
set @pStr =
'281675934' +
'96--81572' +
'57--29816' +
'725148693' +
'316792458' +
'849536721' +
'197863245' +
'438257169' +
'652914387'

which talks about software to generate a puzzle AND establish the level of difficulty in solving it, whilst at the same time making puzzles which are as fun to solve as the human generated one in the newspapers / books etc.

So some SQL to generate interesting-to-solve puzzles would be good chaps ...

Kristen

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2006-01-03 : 15:24:06

Don't tell me you're still solving soduko puzzles after this thread Kristen

!?

I don't think they have solved/proved the smallest number of hints necessary to make a solvable puzzle.
Is 17 the smallest known still?
Excuse my poor search engine skills...

rockmoose

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-01-03 : 18:02:04

Oh.... by the way... I built a new solver... it usually only takes 8-10 steps, and solves all but the tough and diabolical. I'll figure that out later


Drop Table #SudokuProblem
Drop Table #SudokuGrid
GO

create table #SudokuProblem (
	problemNo int PRIMARY KEY,
	difficulty varchar(10) NOT NULL,
	notes varchar(200) NOT NULL,
	settings char(81) NOT NULL UNIQUE )

insert #SudokuProblem
select 1,'easy','can be done just applying prune','  5   7    61 39  7   5   8 839 716           218 439 3   9   6  75 82    8   4  '
union all select 2,'easy','this needs pick too','  3    515 2  64    7 5       63 7  2  7 8  6  4 21       7 8    81  6 917    5  '
union all select 200,'easy','this needs pick too','  3 8  515 2 164    7 5       6347  2  798  6  4521       7 8  3 814 6 9179 6 5  '
union all select 3,'tough','this one''s broken: there are 4 possible solutions','2     7    17324   76            268 6 1 8 3 984            14   92568    3     5'
union all select 4,'diabolical','',' 2 6 8   58   97      4    37    5  6       4  8    13    2      98   36   3 6 9 '
union all select 5,'gentle','','4 9   7 8 562 391 1       5   9 1    1  3  2    6 8   3       9 918 567 6 8   5 2'
union all select 6,'moderate','','83 1       6 7 5     9    8 6   5 9 4  6 9  3 9 7   5 9    2     1 8 9       6 87'
union all select 7,'moderate','',' 3 6 2 8   19 34  9       5  7 3 5  1       8  9 7 2  7       2  83 46   4 5 7 9 '
union all select 8,'moderate','','  356 9    8     49  8  65  85 12               94 17  64  1  91     8    2 963  '
union all select 9,'gentle','','7   2   426     93   9 5    8  7  61  6   3  32  9  5    1 2   19     758   3   6'
union all select 10,'moderate','','  6   1     7 2   95     82  45 38  51     29  91 86  86     53   8 9     5   4  '
union all select 11,'moderate','','   56 421    9  86  2   7  8  4   1   5   3   1   8  7  1   9  47  2    639 41   '
union all select 12,'tough','','      1282 4  9 7  7  3 4  1   2  3  5     8  6  9   1  7 6  1  9 2  3 7528      '
union all select 13,'diabolical','',' 125 487          75     23  41 87   2  5  4   34 95  48     17          357 169 '
union all select 49,'diabolical','','   6   29 4 5   3   7  14  7   54    53   24    12   3  54  1   6   8 5 82   5   '
union all select 55,'diabolical','','2  3     8 4 62  3 138           39 5 7   6 1 32           914 6  25 8 9     1  2'
union all select 62,'diabolical','',' 4 6     51    9 6  8 3   47 1 62    8     6    47 5 13   4 6  1 2    38     6 9 '
union all select 69,'diabolical','','   81  6551  67  8          9   4 3  61   97  5 3   8          6  78  9317  59   '
union all select 76,'diabolical','','  1    4 95     17  78  56 4   97 5     8     3 54   1 62  41  19     86 7    9  '
union all select 101,'diabolical','pretty easy one from Washington Post',' 7 1 2 9    564     6   1    4   9   157 832   7   6    9   2     359    4 6 7 8 '
union all select 141,'diabolical','medium easy one from Washington Post','1      452  7  8   8  69     2 5  1   41 37   1  4 5     98  3   6  1  884      1'

declare @problemNo int
set @problemNo = 141	----------------<-------------------- CHOOSE PROBLEM

declare @n table(n tinyint primary key)

insert @n
select 1 union select 2 union select 3 union select 4 union select 5
union select 6 union select 7 union select 8 union select 9

Delete From #SudokuProblem Where problemNo <> @problemNo

Select 
	row = Row.n, 
	col = Col.n, 
	grid = ((Col.n-1)/3+1)*10 + ((Row.n-1)/3+1),
	Data = convert(int,nullif(substring(settings,(Row.n-1)*9 + Col.n,1),' '))
Into #SudokuGrid
From #SudokuProblem
Cross Join @n Col
Cross Join @n Row

Declare @counter int,
	@currentGrid varchar(1000)
Set @counter = 0

Select count(*) From #SudokuGrid Where Data is null

Set @currentGrid = null
Select @currentGrid = isnull(@currentGrid,'') + isnull(convert(varchar,Data),' ') From #SudokuGrid Order by row, col
Select 
	Step=@counter, 
	Unsolved = count(*), 
	@currentGrid 
From #SudokuGrid 
Where Data is null

Set @counter = @counter + 1

While (@counter < 20 and (Select count(*) From #SudokuGrid Where Data is null)>0)
Begin
	Drop Table #options

	Select 
		Z.row, 
		Z.col,
		Z.grid,
		Z.Data,
		n = Y.n,
		Y = Y.n,
		X = X.n,
		W = W.n
	Into #options
	From (Select A.* From #SudokuGrid A Where Data is null) Z
	Inner Join (
		Select A.row, n 
		From (Select distinct row, n From #SudokuGrid, @n) A 
		Left Join (Select row, Data From #SudokuGrid Where Data is not null) B 
		On A.row = B.row
		and A.n = B.Data 
		Where B.data is null
		) Y
	On Z.row = Y.row
	Inner Join (
		Select A.col, n 
		From (Select distinct col, n From #SudokuGrid, @n) A 
		Left Join (Select col, Data From #SudokuGrid Where Data is not null) B 
		On A.col = B.col
		and A.n = B.Data 
		Where B.data is null
		) X
	On Z.col = X.col
	Inner Join (
		Select A.grid, n 
		From (Select distinct Grid, n From #SudokuGrid, @n) A 
		Left Join (Select grid, Data From #SudokuGrid Where Data is not null) B 
		On A.grid = B.grid
		and A.n = B.Data 
		Where B.data is null
		) W
	On Z.grid = W.grid
	Where Y.n = X.n and X.n = W.n

	Update #SudokuGrid
	Set Data = n
	From #SudokuGrid Z
	Inner Join
		(
		Select Z.* 
		From #options Z
		Inner Join
			(
			Select grid, n
			From #options A
			Group By grid, n
			Having count(*) = 1
			) Y
		On Z.grid = Y.grid 
		and Z.n = Y.n
		Union
		Select Z.* 
		From #options Z
		Inner Join
			(
			Select col, n
			From #options A
			Group By col, n
			Having count(*) = 1
			) Y
		On Z.col = Y.col
		and Z.n = Y.n
		Union
		Select Z.* 
		From #options Z
		Inner Join
			(
			Select row, n
			From #options A
			Group By row, n
			Having count(*) = 1
			) Y
		On Z.row = Y.row
		and Z.n = Y.n
		Union
		Select A.* 
		From #options A
		Inner Join 
			(
			Select row, col
			From #options
			Group by row, col
			having count(*) = 1
			) B
		On A.row = B.row
		and A.col = B.col
		) Y	
	On Z.row = Y.row 
	and Z.col = Y.col
		

	Set @currentGrid = null
	Select @currentGrid = isnull(@currentGrid,'') + isnull(convert(varchar,Data),' ') From #SudokuGrid Order by row, col
	/*
	--Step by step solution
	Select 
		Step=@counter, 
		Unsolved = count(*), 
		@currentGrid 
	From #SudokuGrid 
	Where Data is null
	*/

	Select @Counter = @Counter + 1 
End

	Select 
		Step=@counter-1, 
		Unsolved = count(*), 
		@currentGrid 
	From #SudokuGrid 
	Where Data is null

--Select * From #SudokuGrid

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

Kristen
Test

22859 Posts

Posted - 2006-01-04 : 08:08:56

"I don't think they have solved/proved the smallest number of hints necessary to make a solvable puzzle.
Is 17 the smallest known still?"

Haven't got the New Scientist in front of me, but IIRC the article said that 17 was the fewest possible number of hints, but that 17 hints didn't imply difficultly - I think their two examples were of Easy / Hard, but the article wasn't clear on why they gave two 17-hint examples.

Kristen

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources