SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Site Related Forums
 The Yak Corral
 Reader Challenge - Sliding Tiles Puzzle
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/10/2004 :  15:10:58  Show Profile  Reply with Quote

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

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/10/2004 :  15:21:50  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
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 - 09/10/2004 :  15:25:40  Show Profile  Reply with Quote
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.

Edited by - kselvia on 09/10/2004 15:33:11
Go to Top of Page

ehorn
Flowing Fount of Yak Knowledge

USA
1630 Posts

Posted - 09/10/2004 :  15:51:44  Show Profile  Reply with Quote
An Optimal Solution is 48 moves : HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/10/2004 :  15:55:56  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
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

Edited by - Seventhnight on 09/10/2004 15:56:31
Go to Top of Page

ehorn
Flowing Fount of Yak Knowledge

USA
1630 Posts

Posted - 09/10/2004 :  16:06:49  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/10/2004 :  16:08:40  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

USA
3564 Posts

Posted - 09/11/2004 :  00:13:15  Show Profile  Visit jhermiz's Homepage  Reply with Quote
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 - 09/11/2004 :  02:56:27  Show Profile  Reply with Quote
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.

Edited by - kselvia on 09/11/2004 02:57:30
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

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

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/11/2004 :  13:18:01  Show Profile  Reply with Quote
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 - 09/13/2004 :  06:09:40  Show Profile  Reply with Quote
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

Sweden
3279 Posts

Posted - 09/13/2004 :  06:15:35  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/13/2004 :  08:35:36  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
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

USA
7423 Posts

Posted - 09/13/2004 :  11:01:25  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
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

Edited by - jsmith8858 on 09/13/2004 11:53:18
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/13/2004 :  11:14:53  Show Profile  Reply with Quote
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 - 09/13/2004 :  11:30:46  Show Profile  Reply with Quote
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 - 09/13/2004 :  13:38:16  Show Profile  Visit Stoad's Homepage  Reply with Quote
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

USA
7423 Posts

Posted - 09/13/2004 :  14:22:52  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
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

Edited by - jsmith8858 on 09/13/2004 15:17:29
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/13/2004 :  15:05:36  Show Profile  Reply with Quote
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.

Edited by - kselvia on 09/13/2004 15:10:15
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 09/13/2004 :  15:28:44  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
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

Edited by - jsmith8858 on 09/13/2004 15:30:29
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.17 seconds. Powered By: Snitz Forums 2000