Jeff's SQL Server Blog

Random Thoughts & Cartesian Products with Microsoft SQL Server
posts - 157, comments - 2686, trackbacks - 64

My Links

Advertisement

News

Welcome to my weblog. My name is Jeff Smith, I am software developer in Boston, MA and I was recently named a 2009 SQL Server MVP. Check in frequently for tips, tricks, commentary and ideas on SQL Server and .NET programming.


Subscribe





Archives

Post Categories

Programming

Sports

SQL

Another SQL Suduko Solver

There's been quite a few posts out there with SQL implementations of Suduko puzzle solvers:

  • This one is a T-SQL solver, but it really doesn't do any set-based operations and doesn't really make use of SQL that much.
  • I found this one written in Oracle, which looks pretty short and is definitely set-based, but it doesn't solve a lot of puzzles.  The author admits that there are bugs and hasn't had time to fix them.  Aparently it is also pretty slow. 
  • Finally, this thread at SQLTeam lists lots of cool ideas and solutions.  I haven't gotten a chance to test them all or carefully look at them, but I am sure that there is some good stuff to see in this thread.

So, I'd like to add one more to the list.  Listed below is my T-SQL Set-Based Suduko solver.  I have yet to encounter a puzzle with 1 possible solution that takes more than 2 seconds to solve on my machine, so it's pretty quick and efficient.

Most of the work is done setting things up by creating 3 temp tables:

  • #Squares -- this table just stores the numbers in each square as the puzzle is solved.
  • #Eliminated -- this table keeps track of which numbers are eliminated as possibilities for each square
  • #Groups -- this table groups the row/columns into “groups”.  This is the key table which lets us know instantly which squares are in the same row, column or block, and in my opinion makes good use of a RDBMS.

Also, of course, we have the key to elegantly solving almost any SQL problem: a #Numbers table, simply storing values from 1-9.  Plus lots of CROSS JOINS!

The bulk of the solution is just 4 insert statements, executed over and over until none of them add any rows, in the WHILE loop.  All of the code before that loop is just set up to get things ready.  The #Groups table and #Numbers table could be permanent tables stored in the database if you like, instead of re-creating them as temp tables each time.

The key is to my algorithm is getting count's of 8.  If 8 values have been eliminated from a single square, we add the 9th value that square.  If 8 squares in a group have had a certain value eliminated, we add that value to the 9th square.  You can see this logic in the SELECT's with the HAVING COUNT(*)=8 clauses in steps 3 and 4. 

create Procedure SolvePuzzle(@puzzle char(81))
as
begin

set
nocount on
-- Set-based solution for Suduko puzzles.

-- Best part? The only variables used are for keep tracking of the # of passes need and row counts.
-- Plus, we use normalized tables. A true SQL solution, not
-- a procedural solution written in SQL. :)

-- Our Main working table:

create table #Squares (Row int, Col int, Value int, primary key (Row,Col))

-- We keep track of values that are eliminated:

create table #Eliminated (Row int, Col int, Value int, primary key (Row,Col,Value))

-- The best thing you can use to solve almost any SQL problem, a "numbers" table:

create Table #Numbers (n int primary key)

insert into #Numbers
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

-- The key to our set-based solution: a Groups table that
-- stores all sets of rows/cols into sets of GroupID's that

-- indicate which row/cols are grouped together.

-- (probably a bad explaination)


create table #Groups
(GroupID int, r int, c int, primary key (GroupID,r,c))

-- put in all horizontal lines in groups 1-9:

insert
into #Groups (GroupID, r, c)
select R.N, R.N, C.N
from #Numbers R
cross join #Numbers C

-- next, all vertical lines in groups 10-19:

insert
into #Groups (GroupID, r, c)
select C.N + 9, R.N, C.N
from #Numbers R
cross join #Numbers C

-- and all “blocks” in groups 20-29

insert into #Groups (GroupID, r, c)
select ((R.N-1)/3)*3 + (C.N-1)/3 + 19, R.N, C.N
from #Numbers R
cross join #Numbers C

-- Let's put starting the values into our Squares table:

insert
into #Squares (Col,Row, Value)
select Col, Row, Val
from
(select C.N as Col, R.N as Row,
substring
(@puzzle, (r.N-1) * 9 + c.N ,1) as Val
from #Numbers R
cross join #Numbers C
) x
where Val <>' ' and Val <>'0'

-- even though this is SQL, we must do a loop.


declare @Count integer;
declare @Pass integer;

set @pass = 0;
set @count = -1;

-- Here is where the work is done; it is simply 4 INSERT statements repeated until none of them
-- add any more rows. At that point, we are done and either have solved it, or need to give up.

while (@count <> 0)
begin

set
@pass = @pass + 1

-- Step 1: Eliminations Part I
-- anything that is already entered on a square eliminates all other possibilities
-- for that square:

insert into #Eliminated (row, Col, value)
select S.Row, S.Col, Vals.N
From #Squares S
cross join #Numbers Vals
LEFT OUTER JOIN
 #Eliminated E on
E.Row = S.Row and E.Col = S.Col and Vals.N = E.Value
where

E.Row is null

set @count = @@rowcount

-- Step 2: Elminations part II

-- Using our #groups table, which groups together all rows, columns and 'squares', we can
-- eliminate values for each group based on what is currently there:

insert
into #Eliminated (Row, Col, Value)
select Others.R, Others.C, #Squares.value
from
#Squares
inner
join
#Groups on #Groups.r = #Squares.row and #Groups.c = #Squares.col
inner join
#Groups Others on #Groups.GroupID = Others.GroupID
left outer join
#Eliminated on #Eliminated.Row = Others.r and #Eliminated.Col = Others.C

and
#Eliminated.Value = #Squares.Value
where
#Eliminated.Value is null
group
by Others.R, Others.C, #Squares.Value

set @count = @count + @@rowcount

-- Step 3: Add Squares Part I

-- Add numbers where there are 8 value eliminated for that row/col.

-- We add the one number *not* eliminated, of course:


insert
into #Squares (row,col,Value)
select OneLeft.row, OneLeft.col, Vals.N
from
( select row, col
from #Eliminated
group by row,col
having count(*)=8
) OneLeft
cross join
#Numbers Vals
left
outer join
#Eliminated E
on

OneLeft.Row = E.Row and OneLeft.Col = E.Col and Vals.N = E.Value
where

E.Value is null

set
@count = @count + @@rowcount

-- Step 4: Add Squares Part II
-- If a number has been eliminated in all squares in a group except for 1,

-- Add that number to the one square it has not been eliminated.

-- We only execute this if the previous code could not add any new squares to avoid
-- the need to update the #Elminated table again.

if (@count = 0)
insert into #Squares (row, col, value)
select distinct G.r as Row, G.c as Col, GroupElims.Value
from
(select groupID, Value
from #Eliminated E
inner join #Groups G
on E.row = G.r and E.Col = G.c
group by GroupID, Value
having
count(*) = 8
) GroupElims
inner join #Groups G
on G.GroupID = GroupElims.GroupID
left outer join #Eliminated E
on E.row = G.r and E.col = g.c and E.Value = GroupElims.Value
where

E.Value is null

set
@count = @count + @@rowcount

-- that's it. loop until all the steps add no rows.
end


set
nocount off

if
((select count(*) from #Squares) <> 81) -- we have failed.
begin

print 'puzzle could not be solved! ... tried ' + convert(varchar(10), @Pass) + ' passes.'
end
else

begin

-- we *think* we have succeeded !

-- But we need to check. because this is SQL and we have our #Groups table, the check is quite easy:


if
exists(select GroupID, Value
from
#Squares S
inner join #Groups G
on S.row = G.r and S.col = G.c
group by GroupID, Value
having
count(*) != 1)

-- If this SELECT returns any rows, a single group has a number

-- repeated more than once.

print ' Error! the solution is not valid'
else
print
'Success in ' + convert(varchar(10), @Pass) + ' passes.'
end


-- show final results:

-- (cross-tabbing the result to make it more readable)


select row, sum(case when col=1 then value else 0 end) as Col1,
sum(case when col=2 then value else 0 end) as Col2,
sum(case when col=3 then value else 0 end) as Col3,
sum(case when col=4 then value else 0 end) as Col4,
sum(case when col=5 then value else 0 end) as Col5,
sum(case when col=6 then value else 0 end) as Col6,
sum(case when col=7 then value else 0 end) as Col7,
sum(case when col=8 then value else 0 end) as Col8,
sum(case when col=9 then value else 0 end) as Col9
from #Squares
group by row order by row

-- clean it up:
drop table #Squares
drop table #Eliminated
drop table #Groups
drop table #Numbers
end

My code can solve all of them except for the one labeled “tough”, above.  I suspect this means that there may be multiple solutions for it.  Of course, it could also mean I missed something or screwed something up! 

I feel that it is fairly elegant, and I like the fact that all of the logic is done through JOINS, which is what a SQL solution to this problem should be all about.

Print | posted on Thursday, April 06, 2006 1:55 PM | Filed Under [ T-SQL Techniques ]

Feedback

Gravatar

# re: Another SQL Suduko Solver

"I feel that it is fairly elegant..."

>Of course you do, you wrote it.

"So, I'd like to add one more to the list..."

>One year later....

"-- Best part? The only variables used are for keep tracking of the # of passes need and row counts.

-- Plus, we use normalized tables. A true SQL solution, not

-- a procedural hack written in SQL. :)"

>If that isn't pride I dont know what is

4/7/2006 4:12 PM | Slick Shot
Gravatar

# re: Another SQL Suduko Solver

Slick -- The only thing worse than pride is the opposite -- being an anonymous coward who is afraid to be accountable for his or her opinions.

However, you did raise a good point -- I meant the "hack" thing as a joke, but I think it doesn't come off that way. I re-worded the comment, so thanks for pointing that out.

Feel free to comment further on the actual code itself, but definitely consider having the self-respect to be accountable for what you write.
4/8/2006 1:21 PM | Jeff
Gravatar

# re: Another SQL Suduko Solver

The code was very fast, but failed to give solutions in many cases.

The tough one only has one solution.
(I believe I tried all possible solutions)

EXEC SolvePuzzle ' 2 6 8 58 97 4 37 5 6 4 8 13 2 98 36 3 6 9 ' -- tough
PuzzleSolved
------------
123678945
584239761
967145328
372461589
691583274
458792613
836924157
219857436
745316892

Try:
EXEC SolvePuzzle '2 7 17324 76 268 6 1 8 3 984 14 92568 3 5' -- 4 solutions

PuzzleSolved
------------
235461789
891732456
476589321
317945268
562178934
984623517
658397142
149256873
723814695

235461789
891732456
476985321
317549268
562178934
984623517
658397142
149256873
723814695

235469781
891732456
476581329
317945268
562178934
984623517
658397142
149256873
723814695

235964781
891732456
476815329
317549268
562178934
984623517
658397142
149256873
723481695
4/8/2006 1:39 PM | rockmoose
Gravatar

# re: Another SQL Suduko Solver

Ah, you are correct. Indeed, I found several more it could not solve. I will need to add some more logic to the routine.

I currently am working on a new version that solves multiple puzzles all at once, and I will try to incorporate a few more tricks into that one.

Thanks, Rockmoose !!!
4/10/2006 4:19 PM | Jeff
Gravatar

# re: Another SQL Suduko Solver

Where's the new version that solves multiple puzzles at once ?
5/2/2006 2:02 PM | Jon
Gravatar

# re: Another SQL Suduko Solver - error

i tried ur solution to solve easy puzzle n got the following error..
Server: Msg 2627, Level 14, State 1, Procedure SolvePuzzle, Line 150
Violation of PRIMARY KEY constraint 'PK__#Squares__7E8CC4B1'. Cannot insert duplicate key in object '#Squares____________________________________________________________________________________________________________000100000019'.
The statement has been terminated.
puzzle could not be solved! ... tried 7 passes.

puzzle:
EXEC SolvePuzzle '27 4 9 3 1 8 1 46 6 94 2 5 3 1 19 2 81 7 2 5 2 6 8 46'

7/25/2006 5:59 AM | chary
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET