| Author |
 Topic  |
|
nr
SQLTeam MVY
United Kingdom
12543 Posts |
 Posted - 05/27/2005 : 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. |
Edited by - nr on 05/27/2005 19:56:09
|
|
|
nr
SQLTeam MVY
United Kingdom
12543 Posts |
Posted - 05/27/2005 : 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. |
Edited by - nr on 05/27/2005 20:06:27 |
 |
|
|
Arnold Fribble
Yak-finder General
United Kingdom
1961 Posts |
Posted - 05/28/2005 : 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
United Kingdom
12543 Posts |
Posted - 05/28/2005 : 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. |
Edited by - nr on 05/28/2005 05:50:00 |
|
|
|
Arnold Fribble
Yak-finder General
United Kingdom
1961 Posts |
Posted - 05/28/2005 : 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.
|
Edited by - Arnold Fribble on 05/28/2005 06:29:42 |
|
|
|
nr
SQLTeam MVY
United Kingdom
12543 Posts |
Posted - 05/28/2005 : 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
United Kingdom
1961 Posts |
Posted - 05/28/2005 : 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
United Kingdom
1961 Posts |
Posted - 05/28/2005 : 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
United Kingdom
12543 Posts |
Posted - 05/28/2005 : 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. |
Edited by - nr on 05/28/2005 18:10:59 |
|
|
|
Seventhnight
Flowing Fount of Yak Knowledge
USA
2878 Posts |
Posted - 05/31/2005 : 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
Flowing Fount of Yak Knowledge
USA
2878 Posts |
Posted - 05/31/2005 : 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
Sweden
3279 Posts |
Posted - 05/31/2005 : 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
Flowing Fount of Yak Knowledge
USA
5469 Posts |
Posted - 07/09/2005 : 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 |
Edited by - TG on 07/15/2005 13:54:28 |
|
|
|
rockmoose
SQL Natt Alfen
Sweden
3279 Posts |
Posted - 07/09/2005 : 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
Flowing Fount of Yak Knowledge
United Kingdom
2039 Posts |
Posted - 07/12/2005 : 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
Flowing Fount of Yak Knowledge
USA
5469 Posts |
Posted - 07/15/2005 : 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 |
Edited by - TG on 07/15/2005 13:56:22 |
|
|
|
rockmoose
SQL Natt Alfen
Sweden
3279 Posts |
Posted - 07/15/2005 : 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
United Kingdom
22191 Posts |
Posted - 01/03/2006 : 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
Sweden
3279 Posts |
Posted - 01/03/2006 : 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
Flowing Fount of Yak Knowledge
USA
2878 Posts |
Posted - 01/03/2006 : 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
United Kingdom
22191 Posts |
Posted - 01/04/2006 : 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
|
|
|
|
Topic |
|
|
|
So Duko bank holiday challenge
