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

Our new SQL Server Forums are live! Come on over! We've restricted the ability to create new threads on these forums.

 SQL Server Forums Profile | Active Topics | Members | Search | Forum FAQ Register Now and get your question answered!
 All Forums  Site Related Forums  The Yak Corral  Reader Challenge - Sliding Tiles Puzzle Reply to Topic  Printer Friendly
Author  Topic
Page: of 2

ehorn
Flowing Fount of Yak Knowledge

USA
1632 Posts

 Posted - 09/13/2004 :  15:38:42 The following article may help stimulate some thought for optimization techniques :)http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf

kselvia
Aged Yak Warrior

526 Posts

 Posted - 09/13/2004 :  17:50:23 quote:Originally posted by jsmith8858This minor variation of the above idea will return a solution in 12 seconds, but it is a solution in 130 moves:That's magic. Very impressive! BTW what does: set @done = 2 do? I thought bits had to be 1 or 0.--KenI want to die in my sleep like my grandfather, not screaming in terror like his passengers.

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 09/13/2004 :  18:22:45
Very nice challenge Ken,
and also very impressive Jeff !!!

I went down a similar path to Ken's and calculated the manhattan distance for the whole board.
And at regular intervals pruned the table from the combinations with the "worst" distance.
Of course it didn't work out very well since the algorithm tended to run into the same dead end (J at pos 2).
I started weighting the manhattan distance calculation, but it didn't help much.

And then I managed to

## overheat and crash my laptop!!

, just clicked and went black
(just before saving work of course)

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

kselvia
Aged Yak Warrior

526 Posts

 Posted - 09/13/2004 :  20:29:31 I don't expect I will do any better than Jeff so here was my try. Adding a few indexes reduced the time to solve to about 5 mintues.``` set nocount on If Object_Id('tempdb..#board') Is Not Null drop table #board If Object_Id('tempdb..#d') Is Not Null drop table #d If Object_Id('tempdb..#b1') Is Not Null drop table #b1 select p = identity(int,1,1), x, y into #board from (select 0 x union select 1 union select 2 union select 3) x cross join (select 3 y union select 2 union select 1 union select 0 ) y order by y desc, x Select p1 = a.p, p2 = b.p, distance = sqrt(power((a.x-b.x),2)+power((a.y-b.y),2)) Into #d From #board A Cross Join #board B create table #b1 (bid int identity, s varchar(16), rank float, parent int, processed int) insert #b1 (s) select 'JCEONDKFAMGHILB ' create index b_xy_bp on #board (p) create index b_r_idx on #b1 (rank) create index b_s_idx on #b1 (s) create index d_p_d on #d (p1, distance) -- Solve it. @depth of 15000 will solve in 1 pass. (About 5 minutes) -- Code below can be rerun multiple times with smaller @depth's. declare @depth int, @start int, @p int, @v varchar(255),@n float, @s varchar(255), @answer varchar(300) set @depth = 15000 while 1 = 1 and @depth > 0 begin Update #b1 set Rank = distance from ( select s, sum(distance) distance from numbers n1, numbers n2, #d, #board B, #b1 where n1.id <= 16 and n2.id <= 16 and substring(s,n1.id,1) = substring('ABCDEFGHIJKLMNO ',n2.id,1) and B.p = #d.p1 and B.p = n1.id and p2 = n2.id and #b1.rank is null group by s ) x where #b1.s = x.s -- Process adjacent positions ordered by best rank select top 1 @start = bid, @s = '', @p = charindex(' ',s), @v = s , @n = rank from #b1 where processed is null order by rank asc --Solution found if @n = 0 break select @s=@s+substring(@v,#board.p,1) from #board, #board b2 cross join ( select p1, p2 from #board, #d where #board.p = #d.p1 and #board.p = @p and distance = 1 ) x where b2.p = case #board.p when x.p1 then x.p2 when x.p2 then x.p1 else #board.p end order by x.p2, b2.p insert #b1 (s,parent) Select x.val, @start From ( select substring(@s,id * 16 - 15,16) val from (select 1 id union select 2 union select 3 union select 4) n ) x Left Outer Join #b1 on x.val = #b1.s where #b1.s is null and val <> '' update #b1 set processed = 1 where bid = @start set @depth = @depth - 1 end --select top 100 * from #b1 order by rank asc --Optimal solution: HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL select top 1 @start = bid, @answer = '', @v = s from #b1 order by rank asc while 1 = 1 begin select @s = s from #b1 where bid = @start select @answer = @answer + substring(@s,charindex(' ',@v),1) select @v = @s if @start = (select min(bid) from #b1) break select @start = parent from #b1 where bid = @start end select reverse(@answer) [Current Solution] select ' +---------------+ | '+substring(s,1,1)+' | '+substring(s,2,1)+' | '+substring(s,3,1)+' | '+substring(s,4,1)+' | |---------------| | '+substring(s,5,1)+' | '+substring(s,6,1)+' | '+substring(s,7,1)+' | '+substring(s,8,1)+' | |---------------| | '+substring(s,9,1)+' | '+substring(s,10,1)+' | '+substring(s,11,1)+' | '+substring(s,12,1)+' | |---------------| | '+substring(s,13,1)+' | '+substring(s,14,1)+' | '+substring(s,15,1)+' | '+substring(s,16,1)+' | +---------------+' from #b1 where bid = (select top 1 bid from #b1 order by rank asc) ```(Edit: Oh yeah it needs a numbers table...)--KenI want to die in my sleep like my grandfather, not screaming in terror like his passengers. Edited by - kselvia on 09/13/2004 20:33:01

jsmith8858
Dr. Cross Join

USA
7423 Posts

 Posted - 09/13/2004 :  20:48:40 oops -- the setting the bit equal to 2 is a left over from a different approach i tried, in which done was an int and either 0,1, or 2. just pretend it says set @Done=1. - Jeff

kselvia
Aged Yak Warrior

526 Posts

 Posted - 09/15/2004 :  05:28:10 I took a few ideas from the article ehorn posted and Jeff's soution and came up with a version that will generate a 50 move solution in 7 seconds. It runs into the same problem rockmoose had with Manhattan distances, (the J gets locked), so 50 is as good as I could make it do. The more I worked on it the closer it came to looking JUST like Jeff's solution so I figured I'd better stop before there was no difference (Thanks Jeff!)--Optimal solution: HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL``` create function f_rank15 (@s varchar(16)) returns int as begin declare @r varchar(16) select @r = replace(@s,' ','P') return (select Cast ( Substring ('0123123423453456',Ascii(substring(@r,1,1)) - 64, 1 ) As Int ) + Cast ( Substring ('1012212332344345',Ascii(substring(@r,2,1)) - 64, 1 ) As Int ) + Cast ( Substring ('2101321243235434',Ascii(substring(@r,3,1)) - 64, 1 ) As Int ) + Cast ( Substring ('3210432154326543',Ascii(substring(@r,4,1)) - 64, 1 ) As Int ) + Cast ( Substring ('1234012312342345',Ascii(substring(@r,5,1)) - 64, 1 ) As Int ) + Cast ( Substring ('2123101221233234',Ascii(substring(@r,6,1)) - 64, 1 ) As Int ) + Cast ( Substring ('3212210132124323',Ascii(substring(@r,7,1)) - 64, 1 ) As Int ) + Cast ( Substring ('4321321043215432',Ascii(substring(@r,8,1)) - 64, 1 ) As Int ) + Cast ( Substring ('2345123401231234',Ascii(substring(@r,9,1)) - 64, 1 ) As Int ) + Cast ( Substring ('3234212310122123',Ascii(substring(@r,10,1)) - 64, 1 ) As Int ) + Cast ( Substring ('4323321221013212',Ascii(substring(@r,11,1)) - 64, 1 ) As Int ) + Cast ( Substring ('5432432132104321',Ascii(substring(@r,12,1)) - 64, 1 ) As Int ) + Cast ( Substring ('3456234512340123',Ascii(substring(@r,13,1)) - 64, 1 ) As Int ) + Cast ( Substring ('4345323421231012',Ascii(substring(@r,14,1)) - 64, 1 ) As Int ) + Cast ( Substring ('5434432332122101',Ascii(substring(@r,15,1)) - 64, 1 ) As Int ) + Cast ( Substring ('6543543243213210',Ascii(substring(@r,16,1)) - 64, 1 ) As Int ) ) end go set nocount on create table #b1 (bid int identity, s varchar(16), rank float, history varchar(300), depth int, openspot int) create index b_r_idx on #b1(rank) insert #b1 (s, depth, rank, history, openspot) select start, 0, dbo.f_rank15(start),'', charindex(' ',start) From (select 'JCEONDKFAMGHILB ' start) x select p = identity(int,1,1), x, y into #board from (select 0 x union select 1 union select 2 union select 3) x cross join (select 3 y union select 2 union select 1 union select 0 ) y order by y desc, x create table #d (p1 int, p2 int constraint d_pk primary key (p1, p2)) insert #d (p1, p2) Select a.p, b.p From #board A Cross Join #board B where sqrt(power((a.x-b.x),2)+power((a.y-b.y),2)) = 1 declare @depth int select @depth = max(depth) from #b1 while (Select min(rank) from #b1) > 0 begin insert #b1 (rank, s, depth, history, openspot) select top 300 dbo.f_rank15(x.s) , x.s , @depth + 1, min(x.history), min(x.openspot) from ( select stuff(stuff(s,#d.p1,1,' '),#d.p2,1,substring(s,#d.p1,1)) s, history + substring(s,#d.p1,1) history, #d.p1 as openspot from #d, #b1 where #d.p2 = #b1.openspot and #b1.depth = @depth and #b1.rank < (select min(rank) + 20 from #b1) ) x left outer join #b1 on x.s = #b1.s where #b1.s is null group by x.s order by 1 asc set @depth = @depth + 1 end select top 1 len(history) Moves, rank, history Moves from #b1 order by rank asc drop table #board drop table #d drop table #b1 drop function f_rank15 ```Edit: Some of you more mathmatically inclined could probably derive the ranking table. It's just distances on a grid with incrementing distances on diagonals (see ehorn's link).--KenI want to die in my sleep like my grandfather, not screaming in terror like his passengers. Edited by - kselvia on 09/15/2004 05:37:18

jsmith8858
Dr. Cross Join

USA
7423 Posts

 Posted - 09/15/2004 :  09:36:28 WOW! i will have to check this out! that's what I had hoped, if we combine our various ideas together we'd come up with a good solid solution.Very, very cool ! nice challenge!- Jeff

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

 Posted - 09/21/2004 :  15:58:03 Ken - I have fixed the function so that it is generic for any destination board. I also moved it all to a SP... I couldn't speed it up any, but I do have some thoughs... It may be a while though Very good work to both of you!!quote:``` /* create function f_rank15 (@current varchar(16), @complete varchar(16)) returns int as begin Return( Select distance = sum(abs(a/4-b/4) + abs(a%4-b%4)) From ( Select a, b=charindex(substring(@current,a+1,1),@complete)-1 From (Select a = 0 Union 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 Union Select 10 Union Select 11 Union Select 12 Union Select 13 Union Select 14 Union Select 15) A ) Z ) end */ /* Create Procedure dbo.ShortestPath @start varchar(16), @correct varchar(16), @cap int As set nocount on create table #b1 (bid int identity, s varchar(16), rank float, history varchar(300), depth int, openspot int) create index b_r_idx on #b1(rank) insert #b1 (s, depth, rank, history, openspot) select start, 0, dbo.f_rank15(start,@correct),'', charindex(' ',start) From (select @start start) x select p = identity(int,1,1), x, y into #board from (select 0 x union select 1 union select 2 union select 3) x cross join (select 3 y union select 2 union select 1 union select 0 ) y order by y desc, x create table #d (p1 int, p2 int constraint d_pk primary key (p1, p2)) insert #d (p1, p2) Select a.p, b.p From #board A Cross Join #board B where sqrt(power((a.x-b.x),2)+power((a.y-b.y),2)) = 1 declare @depth int select @depth = max(depth) from #b1 while (Select min(rank) from #b1) > 0 begin insert #b1 (rank, s, depth, history, openspot) select top 300 dbo.f_rank15(x.s,@correct) , x.s , @depth + 1, min(x.history), min(x.openspot) from ( select stuff(stuff(s,#d.p1,1,' '),#d.p2,1,substring(s,#d.p1,1)) s, history + substring(s,#d.p1,1) history, #d.p1 as openspot from #d, #b1 where #d.p2 = #b1.openspot and #b1.depth = @depth and #b1.rank < (select min(rank) + @cap from #b1) ) x left outer join #b1 on x.s = #b1.s where #b1.s is null group by x.s order by 1 asc set @depth = @depth + 1 end select top 1 @start Start, @correct Correct, len(history) Moves, rank, history Moves from #b1 order by rank asc */ --Exec ShortestPath , , Exec ShortestPath 'JCEONDKFAMGHILB ', 'ABCDEFGHIJKLMNO ', 20 Exec ShortestPath 'ABCDEFGHIJKLMNO ', 'ACEGBDFHIKMOJLN ', 20 ```Corey Edited by - Seventhnight on 09/21/2004 16:55:37

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

 Posted - 09/21/2004 :  16:08:36 So, now we know what Corey has been doing the last few days *lol*Corey's no quitter! nice...nice...10-11 seconds on my laptop.The sad thing is that I actually think there are humans that can solve it faster and better than us(meaning you) Unlearn what you have learnt/rockmoose

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

 Posted - 09/21/2004 :  16:12:24 well I actually have a sliding tile puzzle and I can solve it faster... especially going -> 'ABCDEFGHIJKLMNO 'Thats why I say I'm not done...although when I solve it faster, I may not be doing the fastest solution I'm still thinking on it, but I spent this weekend painting the nursery... Corey

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

 Posted - 09/21/2004 :  16:24:02 Ok, let's try to implement the algorithm your brain uses when you solve it So do you have kids or are about to have kids ?I have two, age seven & eight, still haven't painted the nursery ... /rockmoose Edited by - rockmoose on 09/21/2004 16:25:27

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

 Posted - 09/21/2004 :  16:31:25 I'm having a kid.Well, actually my wife is having a kid. I caused it. Little girl should be here in early December, the nursery looks great and has a nice recliner in it, now it just needs a crib and what not. As far as the algorithm goes... I haven't been able to work that out yet. With brute force it is simple to define the algorith as you are just quantifying the error and then working that error to zero. It may be very possible that the best possible solution does not immediately start decreasing the error. It may actually shift pieces around to get a large decrease at once. It makes great sense from ehorns link, but how to incorporate that concept... I'lll have to get back to ya!Corey

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

 Posted - 09/21/2004 :  16:49:28 Kids are great, You have a lot to look forward to !Wish your family all the best.rockmoose

kselvia
Aged Yak Warrior

526 Posts

 Posted - 09/22/2004 :  11:44:34 Neat Corey. I had done some tests and the 48 move optimal solution does indeed require the board to become much more unordered (~30%) before it becomes ordered. That is too much error for any heuristic I thought of other than a contrived one designed to solve this specific problem.I did figure out how to calculate the manhattan distances on the fly without a lookup table. (As you did in your even more sophisticated version.)select p = identity(int,1,1), x, y into #board from (select 0 x union select 1 union select 2 union select 3) x cross join (select 3 y union select 2 union select 1 union select 0 ) y order by y desc, xselect b1.p b1p, b2.p b2p, sum (abs(b2.x - b1.x) + abs(b2.y - b1.y) ) mdinto #mdfrom #board b1, #board b2group by b1.p, b2.pBut it was faster to store it as a varchar and use substring operations rather than table lookups:declare @md varchar(256)select @md = coalesce(@md,'') + cast(md as char(1)) from #md order by b1p, b2pOr just hard code it:set @md = '0123123423453456101221233234434521013212432354343210432154326543123401231234234521231012212332343212210132124323432132104321543223451234012312343234212310122123432332122101321254324321321043213456234512340123434532342123101254344323321221016543543243213210'The rank function was also much faster if I hard coded the 1 thru 16 offsets rather than using a derived numbers table:create function f_rank15 (@s char(16)) returns intasbeginDECLARE @md varchar(256)set @md = '0123123423453456101221233234434521013212432354343210432154326543123401231234234521231012212332343212210132124323432132104321543223451234012312343234212310122123432332122101321254324321321043213456234512340123434532342123101254344323321221016543543243213210'RETURN (select 0 + substring (@md,Ascii(substring(@s,1,1)) - 64 ,1) +substring (@md,Ascii(substring(@s,2,1)) - 48,1) +substring (@md,Ascii(substring(@s,3,1)) - 32,1) +substring (@md,Ascii(substring(@s,4,1)) - 16,1) +substring (@md,Ascii(substring(@s,5,1)) ,1) +substring (@md,Ascii(substring(@s,6,1)) + 16,1) +substring (@md,Ascii(substring(@s,7,1)) + 32,1) +substring (@md,Ascii(substring(@s,8,1)) + 48,1) +substring (@md,Ascii(substring(@s,9,1)) + 64,1) +substring (@md,Ascii(substring(@s,10,1)) + 80,1) +substring (@md,Ascii(substring(@s,11,1)) + 96,1) +substring (@md,Ascii(substring(@s,12,1)) + 112,1) +substring (@md,Ascii(substring(@s,13,1)) + 128,1) +substring (@md,Ascii(substring(@s,14,1)) + 144,1) +substring (@md,Ascii(substring(@s,15,1)) + 160,1) +substring (@md,Ascii(substring(@s,16,1)) + 176,1) )endI didn't bother to post any of this since it didn't actually help. Nothing I did resulted in anything faster than 7 seconds or better than 50 moves.--KenI want to die in my sleep like my grandfather, not screaming in terror like his passengers.

ehorn
Flowing Fount of Yak Knowledge

USA
1632 Posts

 Posted - 09/22/2004 :  14:00:13 Ken,50 moves is quite impressive!!

jsmith8858
Dr. Cross Join

USA
7423 Posts

 Posted - 09/22/2004 :  14:27:35 by the way -- i hope no one minds, I linked to this thread in my blog at sqlteam -- this is good stuff!- Jeff

kselvia
Aged Yak Warrior

526 Posts

 Posted - 09/22/2004 :  15:20:11 I don't mind. The magic of the technique was your solution. Someone should clean up and post a final version that uses less cryptic variable and table names for anyone wanting to understand it someday I guess Corey is still working on a final version so maybe he will do it --KenI want to die in my sleep like my grandfather, not screaming in terror like his passengers.
Page: of 2  Topic
 Reply to Topic  Printer Friendly Jump To: Select Forum General SQL Server Forums       New to SQL Server Programming       New to SQL Server Administration       Script Library       Data Corruption Issues       Database Design and Application Architecture SQL Server 2012 Forums       Transact-SQL (2012)       SQL Server Administration (2012)       SSIS and Import/Export (2012)       Analysis Server and Reporting Services (2012)       Replication (2012)       Availability Groups and DR (2012)       Other SQL Server 2012 Topics SQL Server 2008 Forums       Transact-SQL (2008)       SQL Server Administration (2008)       SSIS and Import/Export (2008)       High Availability (2008)       Replication (2008)       Analysis Server and Reporting Services (2008)       Other SQL Server 2008 Topics SQL Server 2005 Forums       Transact-SQL (2005)       SQL Server Administration (2005)       .NET Inside SQL Server (2005)       SSIS and Import/Export (2005)       Service Broker (2005)       Replication (2005)       High Availability (2005)       Analysis Server and Reporting Services (2005)       Express Edition and Compact Edition (2005)       Other SQL Server Topics (2005) SQL Server 2000 Forums       SQL Server Development (2000)       SQL Server Administration (2000)       Import/Export (DTS) and Replication (2000)       Transact-SQL (2000)       Analysis Services (2000)       MSDE (2000) Development Tools       ASP.NET       Reporting Services Development       Other Development Tools Site Related Forums       Site Related Discussions       Article Discussion       Poll Discussion       The Yak Corral Other Forums       SQL Server 6.5 \ SQL Server 7.0       Other Topics       MS Access       ClearTrace Support Forum Old Forums       CLOSED - General SQL Server       CLOSED - SQL Server 2005/Yukon  -------------------- Home Active Topics Frequently Asked Questions Member Information Search Page
 SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC