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

 All Forums
 Site Related Forums
 The Yak Corral
 Reader Challenge - Sliding Tiles Puzzle

Author  Topic 

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-10 : 15:10:58
[code]
/*
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
[/code]

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

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-10 : 15:21:50
What do you mean by form HFK?
Can we change how the board is stored?

Corey
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-10 : 15:25:40
In the configuration I gave the board looks like:

+---------------+
| 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.
Go to Top of Page

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2004-09-10 : 15:51:44
An Optimal Solution is 48 moves : HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-10 : 15:55:56
How In the world did you come up with that? Are you cheating??

I haven't had a chance to try this one...

Oh well, I'll go wakeboarding.

Corey
Go to Top of Page

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2004-09-10 : 16:06:49
quote:
Originally posted by Seventhnight

How In the world did you come up with that? Are you cheating??
I have not provided a solution... Just an answer. So I do not believe I have cheated ;)

Though I am reminded of a professor in college who said:
quote:
it is not the answer which wins but the derivation...
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-10 : 16:08:40
quote:
Originally posted by ehorn

An Optimal Solution is 48 moves : HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL



You said an optimal solution, which is similar to efficient solution. How could you have the optimal solution without solving the problem?

Corey
Go to Top of Page

jhermiz

3564 Posts

Posted - 2004-09-11 : 00:13:15
I smell Google.



Jon
www.web-impulse.com

Can you dig it: http://www.thecenturoncompany.com/jhermiz/blog/
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-11 : 02:56:27
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.
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-11 : 04:48:17
Not trivial kselvia... thanx for giving me work this weekend! zzzzzzzzzzzzzzz
/sleepymoose
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-11 : 13:18:01
Glad to help out. Giving me something to do too :)

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

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-13 : 06:09:40
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.
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-13 : 06:15:35
So that is not the "b) most efficient solution" version then
I am not finished yet either....

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-13 : 08:35:36
I didn't have time to mess with this one yet, but I am back at work, so I should be able to squeeze a few lines of SQL out today

Corey
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-13 : 11:01:25
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


- Jeff
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-13 : 11:14:53
quote:
Originally posted by rockmoose

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


Nope but I thought it would be easier to do Figured I'd at least give you guys a less than perfect target to shoot for.


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

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-13 : 11:30:46
quote:
Originally posted by jsmith8858

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


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.
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-13 : 13:38:16
Jeff,
how did you manage to write such a monster??? :-)
I run it and did not see ' found solution!' (a ver.7.0 quirk?).
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-13 : 14:22:52
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.



- Jeff
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-13 : 15:05:36
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.
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-13 : 15:28:44
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 .

- Jeff
Go to Top of Page
    Next Page

- Advertisement -