February 20, 2018 at 11:56 pm
shaulbel - Tuesday, February 20, 2018 11:36 PMSeems it works now.I would like to understand the query
select RowNum, [1],[2],[3],[4],[5],[6],[7],[8],[9]
from
(select RowNum, ColumnNum, case when substring(@PuzzleIn,CoordinateID,1) != 0 then substring(@PuzzleIn,CoordinateID,1) end Value from #tGrid) as base
pivot
(min(Value) for ColumnNum in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as ptwhat is the meaning of !=0
Thanks
Hi Shaulbel
Since the puzzle is first parsed with 0 in the place of the unsolved cells they do need to be displayed hence the case statement.
Try replacing the case statement with
substring(@PuzzleIn,CoordinateID,1) Value
and it will show you the zeros too.
Cheers
Bevan
February 21, 2018 at 2:49 am
bevanward - Tuesday, February 20, 2018 7:01 AMHi Dude76
YES - there is an order by missing from the code that generates the select part of the statement. It should read
/*produces 81 values in row preference order a row is one permutation of possible values*/
SELECT @Select = stuff(
(select 'cross join'+'(select Value ['+CoordinateID+'] from #tOption where CoordinateID = '+CoordinateID+') ['+CoordinateID+']' from
(select distinct cast(CoordinateID as varchar(3)) CoordinateID from #tOption) b
order by cast(CoordinateID as int) FOR XML PATH('')), 1, 10, '')The current code displays as 1, 10, 11, etc so results are complete garbage!
Thanks for finding this - was a last minute change - clearly untested!!!
Thanks
Bevan
That's perfect. 🙂
I'm looking foreward to read the part 2 ^_^
February 21, 2018 at 2:45 pm
bevanward - Monday, February 19, 2018 10:29 PMComments posted to this topic are about the item Solve Sudoku with T-SQL - Part 1
Many years ago, I posted the solution in one query by Richard Romley. It enforced the basic rules of a Sodoku in case expressions. It was incredibly fast regardless of the size or complexity of the grid. What Richard did discover, however, was that many published sudoku puzzles had multiple solutions! His query would try to produce them all, because it was a very set oriented, logic-based answer. We don't like to admit it, but this is one of the disadvantages of set oriented languages; a lot of the time would be happy with the first workable solution that pops out so we don't have to wait for everything. For example, if you give the grid with the numbers one through nine across the top row, it'll try to produce all possible grids. This is several orders of magnitude larger than all the atoms in the universe, so you probably don't have enough computing power to bring them all out.
Please post DDL and follow ANSI/ISO standards when asking for help.
February 21, 2018 at 2:53 pm
jcelko212 32090 - Wednesday, February 21, 2018 2:45 PMMany years ago, I posted the solution in one query by Richard Romley. It enforced the basic rules of a Sodoku in case expressions. It was incredibly fast regardless of the size or complexity of the grid. What Richard did discover, however, was that many published sudoku puzzles had multiple solutions! His query would try to produce them all, because it was a very set oriented, logic-based answer. We don't like to admit it, but this is one of the disadvantages of set oriented languages; a lot of the time would be happy with the first workable solution that pops out so we don't have to wait for everything. For example, if you give the grid with the numbers one through nine across the top row, it'll try to produce all possible grids. This is several orders of magnitude larger than all the atoms in the universe, so you probably don't have enough computing power to bring them all out.
I like how you said "probably", just in case he happened to have something inter-dimensionally accessible...
-------------------------------------------------------------------------------------------------------------------------------------
Please follow Best Practices For Posting On Forums to receive quicker and higher quality responses
February 22, 2018 at 12:26 pm
This looks quite absolutely intriguing. I have written a Sudoku Solver in Excel, but I am really looking forward to getting some time to sit down with this SQL solution and check it out. And of course I will be among the throngs eagerly awaiting Part II, and any more Parts that Bevan should consider offering. Just for the record, I don't have access to any inter-dimensional computing capabilities.
February 22, 2018 at 9:06 pm
Bevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.
Rick
Disaster Recovery = Backup ( Backup ( Your Backup ) )
February 22, 2018 at 9:35 pm
jcelko212 32090 - Wednesday, February 21, 2018 2:45 PMbevanward - Monday, February 19, 2018 10:29 PMComments posted to this topic are about the item Solve Sudoku with T-SQL - Part 1Many years ago, I posted the solution in one query by Richard Romley. It enforced the basic rules of a Sodoku in case expressions. It was incredibly fast regardless of the size or complexity of the grid. What Richard did discover, however, was that many published sudoku puzzles had multiple solutions! His query would try to produce them all, because it was a very set oriented, logic-based answer. We don't like to admit it, but this is one of the disadvantages of set oriented languages; a lot of the time would be happy with the first workable solution that pops out so we don't have to wait for everything. For example, if you give the grid with the numbers one through nine across the top row, it'll try to produce all possible grids. This is several orders of magnitude larger than all the atoms in the universe, so you probably don't have enough computing power to bring them all out.
Hi Joe,
Glad to touch base again! Finding all possible solutions is not a disadvantage at all; it is a feature. Why wouldn't you want to know all of the solutions to a problem if there was more than one? You should have known that I would accept your challenge. All it takes to make this a solvable problem is to limit the number of solutions to a reasonable number. I chose 100. So the problem becomes: Show me 100 different solutions to a Sudoku puzzle which consists only of the top row populated with 1 through 9. It turns out that I DO have enough computing power to solve this. Actually it only takes 16 ms.
It looks like this...
declare @t datetime = getdate()
exec sp_sudoku
1,2,3,4,5,6,7,8,9,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0
print convert(varchar,datediff(ms,@t,getdate())) + ' ms'
See attached file for the solution(s)
All the best,
Richard
February 23, 2018 at 3:43 am
Amazing Richard! Inspirational stuff thanks for sharing!!
February 23, 2018 at 4:04 pm
skeleton567 - Thursday, February 22, 2018 9:06 PMBevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.
Hi Skeleton567
Glad that you are chasing the logic problems - I do find them enjoyable too. The math side certainly does not come naturally but I've been doing lots of course in Machine Learning and the like and it is showing me the value. It makes me wish I was smart enough to have studied more pure math but rocks were interesting too!! So to speed it up you can add set forceplan on - Richard Romley was kind enough to share a few pointers and this one makes the whole thing run much faster! Enjoy take care Bevan
February 23, 2018 at 4:23 pm
jcelko212 32090 - Wednesday, February 21, 2018 2:45 PMbevanward - Monday, February 19, 2018 10:29 PMComments posted to this topic are about the item Solve Sudoku with T-SQL - Part 1Many years ago, I posted the solution in one query by Richard Romley. It enforced the basic rules of a Sodoku in case expressions. It was incredibly fast regardless of the size or complexity of the grid. What Richard did discover, however, was that many published sudoku puzzles had multiple solutions! His query would try to produce them all, because it was a very set oriented, logic-based answer. We don't like to admit it, but this is one of the disadvantages of set oriented languages; a lot of the time would be happy with the first workable solution that pops out so we don't have to wait for everything. For example, if you give the grid with the numbers one through nine across the top row, it'll try to produce all possible grids. This is several orders of magnitude larger than all the atoms in the universe, so you probably don't have enough computing power to bring them all out.
Hi Joe
I appreciate the comments. The number of permutations is incredible and the fact that SQL Server can get through so many joins is remarkable. I started stepping through the process but did not take long to realize that it would not come out by writing huge numbers of rows to disk! I'm just showing the top 1 solution however all solutions are written to the #solutions table. There must be a method to test a puzzle for having only one solution based on the arrangement of the unsolved cells but that is not one for today. The huge number of exclusions from the join I'm creating base on a single operator of <> throughselect @Exclusion = @Exclusion + ' and ['+cast(l.CoordinateID as varchar(5))+'] <> ['+cast(r.CoordinateID as varchar(5))+']'
from #tGrid l cross join #tGrid r
where (l.RowNum = r.RowNum or l.ColumnNum = r.ColumnNum or l.BlockNum = r.BlockNum) and r.CoordinateID > l.CoordinateID
Richard has been kind enough to walk me through his logic and explain that in using the forceplan on option the SQL runs as written without any additional attempted optimisation. I think until now what I've been fighting and the interesting patterns and relationships I have been producing are to do with the optimiser setting an execution path.
Hope that you and Richard are working on some more puzzle code. You guys have been inspirational to many around the world over the years - many thanks!!
Regards
Bevan
February 23, 2018 at 4:40 pm
bevanward - Friday, February 23, 2018 4:04 PMskeleton567 - Thursday, February 22, 2018 9:06 PMBevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.Hi Skeleton567
Glad that you are chasing the logic problems - I do find them enjoyable too. The math side certainly does not come naturally but I've been doing lots of course in Machine Learning and the like and it is showing me the value. It makes me wish I was smart enough to have studied more pure math but rocks were interesting too!! So to speed it up you can add set forceplan on - Richard Romley was kind enough to share a few pointers and this one makes the whole thing run much faster! Enjoy take care Bevan
Hi Bevan,
Just for the record - Using FORCEPLAN is almost always a very bad idea and is frowned upon by the SQL Server community. The Sudoku query is clearly a very unique and unusual situation and one of the few examples I'm aware of where it happens to make sense. But I'd be very reluctant to suggest it as a normal performance-enhancing tool. And I'd always accompany any such recommendation with appropriate warnings.
Richard
February 23, 2018 at 6:38 pm
rsromley - Friday, February 23, 2018 4:40 PMbevanward - Friday, February 23, 2018 4:04 PMskeleton567 - Thursday, February 22, 2018 9:06 PMBevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.Hi Skeleton567
Glad that you are chasing the logic problems - I do find them enjoyable too. The math side certainly does not come naturally but I've been doing lots of course in Machine Learning and the like and it is showing me the value. It makes me wish I was smart enough to have studied more pure math but rocks were interesting too!! So to speed it up you can add set forceplan on - Richard Romley was kind enough to share a few pointers and this one makes the whole thing run much faster! Enjoy take care BevanHi Bevan,
Just for the record - Using FORCEPLAN is almost always a very bad idea and is frowned upon by the SQL Server community. The Sudoku query is clearly a very unique and unusual situation and one of the few examples I'm aware of where it happens to make sense. But I'd be very reluctant to suggest it as a normal performance-enhancing tool. And I'd always accompany any such recommendation with appropriate warnings.
Richard
Hi Richard
I left one puzzle run and it actually took 17 days to complete until this option was added from your suggestion. Then it completed in 400ms!
February 23, 2018 at 6:53 pm
bevanward - Friday, February 23, 2018 6:38 PMrsromley - Friday, February 23, 2018 4:40 PMbevanward - Friday, February 23, 2018 4:04 PMskeleton567 - Thursday, February 22, 2018 9:06 PMBevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.Hi Skeleton567
Glad that you are chasing the logic problems - I do find them enjoyable too. The math side certainly does not come naturally but I've been doing lots of course in Machine Learning and the like and it is showing me the value. It makes me wish I was smart enough to have studied more pure math but rocks were interesting too!! So to speed it up you can add set forceplan on - Richard Romley was kind enough to share a few pointers and this one makes the whole thing run much faster! Enjoy take care BevanHi Bevan,
Just for the record - Using FORCEPLAN is almost always a very bad idea and is frowned upon by the SQL Server community. The Sudoku query is clearly a very unique and unusual situation and one of the few examples I'm aware of where it happens to make sense. But I'd be very reluctant to suggest it as a normal performance-enhancing tool. And I'd always accompany any such recommendation with appropriate warnings.
RichardHi Richard
I left one puzzle run and it actually took 17 days to complete until this option was added from your suggestion. Then it completed in 400ms!
HI Bevan,
Any time the optimizer spends more time optimizing a query plan than it will save at execution time, it is a net loss and it would be better if it did nothing at all. That's the situation here. Also - you need to keep that in mind when you attempt to dynamically construct the WHERE clauses to maximize performance - Unless you can accomplish that task in less time than you will save, you'd be better off doing nothing at all. The problem for the optimizer in this example is the huge number of possible plans it's trying to evaluate - and it's all wasted for the next query anyway because the ideal execution plan is totally dependent on the data for a particular puzzle. I don't know how difficult it would be for the optimizer to determine that its most effective approach is to do nothing but that logic is either missing (or not working) in the SQL Server. Therefore, the need to manually intervene with FORCEPLAN. But it's important to understand that this really is an exception to what is normally good practice.
Richard
February 23, 2018 at 7:34 pm
rsromley - Friday, February 23, 2018 6:53 PMbevanward - Friday, February 23, 2018 6:38 PMrsromley - Friday, February 23, 2018 4:40 PMbevanward - Friday, February 23, 2018 4:04 PMskeleton567 - Thursday, February 22, 2018 9:06 PMBevan, thanks for the article and the code. It's past 11 pm here, and I can't get my old brain around this tonight, but I'll be playing with this later. You are obviously much more of a mathematical guy than I ever was. I love working with logic even though I've been retired for nearly 10 years. I still enjoy all the SSC articles and comments and the regular emails.Hi Skeleton567
Glad that you are chasing the logic problems - I do find them enjoyable too. The math side certainly does not come naturally but I've been doing lots of course in Machine Learning and the like and it is showing me the value. It makes me wish I was smart enough to have studied more pure math but rocks were interesting too!! So to speed it up you can add set forceplan on - Richard Romley was kind enough to share a few pointers and this one makes the whole thing run much faster! Enjoy take care BevanHi Bevan,
Just for the record - Using FORCEPLAN is almost always a very bad idea and is frowned upon by the SQL Server community. The Sudoku query is clearly a very unique and unusual situation and one of the few examples I'm aware of where it happens to make sense. But I'd be very reluctant to suggest it as a normal performance-enhancing tool. And I'd always accompany any such recommendation with appropriate warnings.
RichardHi Richard
I left one puzzle run and it actually took 17 days to complete until this option was added from your suggestion. Then it completed in 400ms!HI Bevan,
Any time the optimizer spends more time optimizing a query plan than it will save at execution time, it is a net loss and it would be better if it did nothing at all. That's the situation here. Also - you need to keep that in mind when you attempt to dynamically construct the WHERE clauses to maximize performance - Unless you can accomplish that task in less time than you will save, you'd be better off doing nothing at all. The problem for the optimizer in this example is the huge number of possible plans it's trying to evaluate - and it's all wasted for the next query anyway because the ideal execution plan is totally dependent on the data for a particular puzzle. I don't know how difficult it would be for the optimizer to determine that its most effective approach is to do nothing but that logic is either missing (or not working) in the SQL Server. Therefore, the need to manually intervene with FORCEPLAN. But it's important to understand that this really is an exception to what is normally good practice.
Richard
Hi Richard
That all makes sense - I think before you mentioned this option I had thought my only option was to pre-solve segments, enhance indexes, etc however the issue is even when solving segments if there are lots of possibilities, then using that outcome has a huge penalty for maybe only reducing a few options for one cell which in most cases is not worth the time spent. I already have the option counts per cell so that is available for the ordering with no penalty - I'll post what I come up with once my machine is free.
Thanks Bevan
Viewing 14 posts - 16 through 28 (of 28 total)
You must be logged in to reply to this topic. Login to reply