quote:

---

Originally posted by jsmith8858

This minor variation of the above idea will return a solution in 12 seconds, but it is a solution in 130 moves:

---

overheat and crash my laptop!!

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)

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

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

---