+---------------+
  | J | C | E | O |
  |---------------|
  | N | D | K | F |
  |---------------|
  | A | M | G | H |
  |---------------|
  | I | L | B |   |
  +---------------+

quote:

---

Originally posted by Seventhnight

How In the world did you come up with that? Are you cheating??

---

quote:

---

it is not the answer which wins but the derivation...

---

quote:

---

Originally posted by ehorn

An Optimal Solution is 48 moves : HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL

---

create table #MoveList  (OpenSpot int not null,
			[Move] int not null,
	constraint ML_PK primary key (OpenSpot, [Move]))

create table #Moves (MoveNumber int, Board char(16) primary key, MoveHistory varchar(100), OpenSpot integer)

go
insert into #MoveList
select 1,2 union
select 1,5 union
select 2,3 union
select 2,6 union
select 3,4 union
select 3,7 union
select 4,8 union
select 5,6 union
select 5,9 union
select 6,7 union
select 6,10 union
select 7,8 union 
select 7,11 union
select 8, 12 union
select 9,10 union
select 9,13 union
select 10,11 union
select 10,14 union
select 11,12 union
select 11,15 union
select 12,16 union
select 13,14 union
select 14,15 union
select 15,16

insert into #moveList
select [Move], [OpenSpot]
from #Movelist

declare @Start char(16)
declare @End char(16)
declare @MoveNumber int;
declare @Done bit;
declare @MaxMovesToCheck int;


set @Done = 0;    --bit flag
set @Start = 'JCEONDKFAMGHILB '
set @End =   'ABCDEFGHIJKLMNO '
set @MoveNumber = 0   -- starting move #
set @MaxMovesToCheck = 12
--

insert into #moves 
select @moveNumber, @Start,'', 16

-- Here's where we actually begin searching:

while (@done = 0)
begin
	set @MoveNumber = @MoveNumber + 1
	insert into #moves (MoveNumber, Board, MoveHistory, OpenSpot)
	select @MoveNumber, a.NewBoard, MIN(a.MoveHist), MIN(a.NewOpenSpot)
	from
	(
		select m.Board, 
                       stuff(stuff(Board, ml.Move, 1, ' '), ml.OpenSpot, 1, substring(Board,Move,1)) as NewBoard, 
                       MoveHistory + substring(Board,Move,1) as MoveHist, 
                       ml.[Move] as NewOpenSpot
		from #moves m
		inner join #MoveList ml
		on ml.OpenSpot = m.OpenSpot		
                where m.MoveNumber = @MoveNumber-1
	) a
	left outer join
		#Moves OldMoves
	on
		a.NewBoard = OldMoves.Board
	where
		OldMoves.Board is null
        group by a.NewBoard

	if exists (select * from #Moves where Board = @End)
		begin
		set @done = 1
		print ' found solution!'
		select * from #Moves where Board = @End
		end
	if @MoveNumber =@MaxMovesToCheck set @done= 1
end

--Show the board
--select * from #Moves where @MoveNumber = @MoveNumber

go

drop table #MoveList
drop table #Moves

quote:

---

Originally posted by rockmoose

So that is not the "b) most efficient solution" version then
I am not finished yet either....

---

quote:

---

Originally posted by jsmith8858

[b]...
here's my "brute force" algorithm so far

---

create table #MoveList  (OpenSpot int not null,
			[Move] int not null,
	constraint ML_PK primary key (OpenSpot, [Move]))

create table #Moves (MoveNumber int, Board char(16) primary key , MoveHistory varchar(300), OpenSpot integer)

go
insert into #MoveList
select 1,2 union
select 1,5 union
select 2,3 union
select 2,6 union
select 3,4 union
select 3,7 union
select 4,8 union
select 5,6 union
select 5,9 union
select 6,7 union
select 6,10 union
select 7,8 union 
select 7,11 union
select 8, 12 union
select 9,10 union
select 9,13 union
select 10,11 union
select 10,14 union
select 11,12 union
select 11,15 union
select 12,16 union
select 13,14 union
select 14,15 union
select 15,16

insert into #moveList
select [Move], [OpenSpot]
from #Movelist

declare @Start char(16)
declare @End char(16)
declare @MoveNumber int;
declare @Done bit;
declare @MaxMovesToCheck int;
declare @RC int;


set @Done = 0;    --bit flag
set @Start = 'JCEONDKFAMGHILB '
set @End =   'ABCDEFGHIJKLMNO '
set @MoveNumber = 0   -- starting move #
set @MaxMovesToCheck = 150
--

insert into #moves 
select @moveNumber, @Start,'', 16

-- here we go:
set nocount on

while (@done = 0)
begin
	set @MoveNumber = @MoveNumber + 1
	insert into #moves (MoveNumber, Board, MoveHistory, OpenSpot)
	select top 150 @MoveNumber, a.NewBoard, MIN(a.MoveHist), MIN(a.NewOpenSpot)
	from
	(
		select stuff(stuff(Board, ml.Move, 1, ' '), ml.OpenSpot, 1, substring(Board,Move,1)) as NewBoard, MoveHistory + substring(m.Board,ml.Move,1) as MoveHist, ml.[Move] as NewOpenSpot
		from #moves m
		inner join #MoveList ml
		on ml.OpenSpot = m.OpenSpot	
		where m.MoveNumber = @MoveNumber - 1	
	) a
	left outer join
		#Moves OldMoves
	on
		a.NewBoard = OldMoves.Board
	where
		OldMoves.Board is null
	group by
		NewBoard
	order by
		case when substring(NewBoard,1,1) < substring(NewBoard,2,1) then 1 else 0 end +		
		case when substring(NewBoard,2,1) < substring(NewBoard,3,1) then 1 else 0 end +
		case when substring(NewBoard,3,1) < substring(NewBoard,4,1) then 1 else 0 end +
		case when substring(NewBoard,4,1) < substring(NewBoard,5,1) then 1 else 0 end +
		case when substring(NewBoard,5,1) < substring(NewBoard,6,1) then 1 else 0 end +
		case when substring(NewBoard,6,1) < substring(NewBoard,7,1) then 1 else 0 end +
		case when substring(NewBoard,7,1) < substring(NewBoard,8,1) then 1 else 0 end +
		case when substring(NewBoard,8,1) < substring(NewBoard,9,1) then 1 else 0 end +
		case when substring(NewBoard,9,1) < substring(NewBoard,10,1) then 1 else 0 end +
		case when substring(NewBoard,10,1) < substring(NewBoard,11,1) then 1 else 0 end +
		case when substring(NewBoard,11,1) < substring(NewBoard,12,1) then 1 else 0 end +
		case when substring(NewBoard,12,1) < substring(NewBoard,13,1) then 1 else 0 end +
		case when substring(NewBoard,13,1) < substring(NewBoard,14,1) then 1 else 0 end +
		case when substring(NewBoard,14,1) < substring(NewBoard,15,1) then 1 else 0 end +
		case when substring(NewBoard,15,1) < substring(NewBoard,16,1) then 1 else 0 end desc

	if exists (select * from #Moves where Board = @End)
		begin
		set @done = 2
		print ' found solution in ' + convert(varchar(20), @MoveNumber) + ' Moves!!'
		select * from #Moves where Board = @End
		end
	if @MoveNumber =@MaxMovesToCheck set @done= 1
end



--show the board
--select * from #Moves where MoveNumber = @MoveNumber order by Board

go

drop table #MoveList
drop table #Moves