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.

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 */

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...) --Ken I want to die in my sleep like my grandfather, not screaming in terror like his passengers.

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.

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!)

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). --Ken I want to die in my sleep like my grandfather, not screaming in terror like his passengers.

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 <Starting Board>, <Complete Board>, <Max Rank OffSet>
Exec ShortestPath 'JCEONDKFAMGHILB ', 'ABCDEFGHIJKLMNO ', 20
Exec ShortestPath 'ABCDEFGHIJKLMNO ', 'ACEGBDFHIKMOJLN ', 20

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)

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!

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, x

select b1.p b1p, b2.p b2p, sum (abs(b2.x - b1.x) + abs(b2.y - b1.y) ) md into #md from #board b1, #board b2 group by b1.p, b2.p

But 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, b2p

Or 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:

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

--Ken I want to die in my sleep like my grandfather, not screaming in terror like his passengers.