/*
Here is a new puzzle. Solve this 'Sliding Tile' game.
I don't have the best answer or any constraints on how you must solve it.
I just figured you puzzlers would like something to chew on.
I know this configuration is solvable.
Try for a) fewest number of statements and b) most efficient solution.
*/
SET NOCOUNT ON
declare @board table (
c1 char, c2 char, c3 char, c4 char, c5 char, c6 char, c7 char, c8 char, c9 char,
c10 char, c11 char, c12 char, c13 char, c14 char, c15 char, c16 char)
insert @board
select 'J','C','E','O','N','D','K','F','A','M','G','H','I','L','B',' '
/*
Solve here by sliding adjacent letters into blank square to arrive at this result
+---------------+
| A | B | C | D |
|---------------|
| E | F | G | H |
|---------------|
| I | J | K | L |
|---------------|
| M | N | O | |
+---------------+
Print shortest solution in the form HFK...
*/
select '
+---------------+
| '+c1+' | '+c2+' | '+c3+' | '+c4+' |
|---------------|
| '+c5+' | '+c6+' | '+c7+' | '+c8+' |
|---------------|
| '+c9+' | '+c10+' | '+c11+' | '+c12+' |
|---------------|
| '+c13+' | '+c14+' | '+c15+' | '+c16+' |
+---------------+' from @board

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

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

You can move H or B first. Move H, then F, then K and so on for example to solve the puzzle.

Sure you can change how it is stored. (Edit: In fact I expect everyone will - that's part of the challenge - what is a good data structure for it for your solution.)

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

I suspect there are some online or downloadable versions of sovlers. I found a few java applets that would generate A solution but not the optimal solution. Solving it is not the problem, it's solving it with T-SQL and finding what kind of set-based operations can be applied to the problem.

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

If you are playing with this puzzle I thought I'd let you know I managed to partially solve it. I came up with a solution that solves it in about 20 minutes and it takes 297 moves. I think I can improve on that though so I'll wait to post my solution.

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

EDIT #1: had to make fix in code; i was missing a WHERE EDIT #2: had to add a GROUP BY to append only distinct Board configurations

The main problem is, i can't think of any algorithm that would be good at eliminating "bad" moves or anticipating what moves lead to a solution .... i will have to spend a little more time looking at it.

the best i can do so far is -- if a move leads to ANY board configuration that you previously analyzed, don't bother.

here's my "brute force" algorithm so far, with no optimization or anything. Set @MaxMovesToCheck equal to the # of moves to check before giving up. On my PC here at work, if I set it to over 14 or so it never seems to finish, meaning this approach probably will never come close to generating a valid answer.

Anyway, here's my code:

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

Without really thinking about it, I assumed it would be solvable by brute force when I suggested the puzzle. I realize now there are 653,837,184,000 possible board configurations, so a 4x4 square can't be brute forced. (At least not in T-SQL ) Maybe a 3x3 board would have been better (~32000 possibilities) I started with something capable of brute force then found a few optimizations that would lead to better choices, but my heuristics are still far from optimal.

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

no -- i can't imgagine it will ever find a solution. i just wanted to post the code so maybe some can work with it. it just keeps going and going until it might find a result, but as mentiond if you try more than 14 moves or so it never finishes as the temp table grows quite big.

so, i wouldn't call my post a solution, just some tools/ideas to work with.

there's got to be a way to "prune" the table periodically to remove invalid or inefficient paths, or a way to concentrate on best paths, but i don't think an algorithm exists for this type of puzzle. i may be wrong of course.

If you want to go down the path I went down, I treated it like the TSP problem and generated a matrix of distances from "home squares" based on coordinate points. The farther the sum of all tile distances were from home, the more "mixed up" they were, and I did not explore paths that were more than about 30% worse than the best ordering I had found thus far. My problem is that distances from "home squares" based purley on coordinates is not a good heuristic because a tile 2 squares from it's home is more or less "far" from home depending on where the blank is and how many boarders it has etc. That matrix is where I am going to focus on improvement. (Edit: I also realize that using this method may solve it a few mintes instead of 20 and 80 moves instead of 297 but I don't see how to get to an optimal solution from there...)

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

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

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

I tried to do some sorting and filtering, so that it would test "best" moves using the ORDER BY clause. really simple stuff. i don't think it helps lead to a good solution though. the things to tweak, i guess, would be the formula in the ORDER BY and the TOP x value .