## 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.

# Legacy Comments

Slick Shot
2006-04-07 |
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 |

Jeff
2006-04-08 |
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. |

rockmoose
2006-04-08 |
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 |

Jeff
2006-04-10 |
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 !!! |

Jon
2006-05-02 |
re: Another SQL Suduko Solver Where's the new version that solves multiple puzzles at once ? |

chary
2006-07-25 |
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' |