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
Previous Page
Author Previous Topic Topic Next Topic
Page: of 2

ehorn
Flowing Fount of Yak Knowledge

USA
1631 Posts

Posted - 09/13/2004 :  15:38:42  Show Profile  Reply with Quote
The following article may help stimulate some thought for optimization techniques :)

http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/13/2004 :  17:50:23  Show Profile  Reply with Quote
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:


That's magic. Very impressive!

BTW what does: set @done = 2 do? I thought bits had to be 1 or 0.


--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 :  18:22:45  Show Profile  Reply with Quote
Very nice challenge Ken,
and also very impressive Jeff !!!

I went down a similar path to Ken's and calculated the manhattan distance for the whole board.
And at regular intervals pruned the table from the combinations with the "worst" distance.
Of course it didn't work out very well since the algorithm tended to run into the same dead end (J at pos 2).
I started weighting the manhattan distance calculation, but it didn't help much.

And then I managed to

overheat and crash my laptop!!

, just clicked and went black
(just before saving work of course)

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

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/13/2004 :  20:29:31  Show Profile  Reply with Quote
I don't expect I will do any better than Jeff so here was my try. Adding a few indexes reduced the time to solve to about 5 mintues.

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)

(Edit: Oh yeah it needs a numbers table...)
--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 20:33:01
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 09/13/2004 :  20:48:40  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
oops -- the setting the bit equal to 2 is a left over from a different approach i tried, in which done was an int and either 0,1, or 2. just pretend it says set @Done=1.

- Jeff
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/15/2004 :  05:28:10  Show Profile  Reply with Quote
I took a few ideas from the article ehorn posted and Jeff's soution and came up with a version that will generate a 50 move solution in 7 seconds. It runs into the same problem rockmoose had with Manhattan distances, (the J gets locked), so 50 is as good as I could make it do. The more I worked on it the closer it came to looking JUST like Jeff's solution so I figured I'd better stop before there was no difference (Thanks Jeff!)

--Optimal solution: HFKDNJCEDKODKGBLMNJAIMNBFOGJECAEBFJKCBFJOHLOKGHL

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

Edit: Some of you more mathmatically inclined could probably derive the ranking table. It's just distances on a grid with incrementing distances on diagonals (see ehorn's link).
--Ken
I want to die in my sleep like my grandfather, not screaming in terror like his passengers.

Edited by - kselvia on 09/15/2004 05:37:18
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 09/15/2004 :  09:36:28  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
WOW! i will have to check this out! that's what I had hoped, if we combine our various ideas together we'd come up with a good solid solution.

Very, very cool ! nice challenge!

- Jeff
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/21/2004 :  15:58:03  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
Ken - I have fixed the function so that it is generic for any destination board. I also moved it all to a SP... I couldn't speed it up any, but I do have some thoughs... It may be a while though

Very good work to both of you!!

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



Corey

Edited by - Seventhnight on 09/21/2004 16:55:37
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 09/21/2004 :  16:08:36  Show Profile  Reply with Quote
So, now we know what Corey has been doing the last few days *lol*
Corey's no quitter!
nice...nice...
10-11 seconds on my laptop.
The sad thing is that I actually think there are humans that can solve it faster and better than us(meaning you)

Unlearn what you have learnt
/rockmoose
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/21/2004 :  16:12:24  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
well I actually have a sliding tile puzzle and I can solve it faster... especially going -> 'ABCDEFGHIJKLMNO '

Thats why I say I'm not done...although when I solve it faster, I may not be doing the fastest solution

I'm still thinking on it, but I spent this weekend painting the nursery...

Corey
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 09/21/2004 :  16:24:02  Show Profile  Reply with Quote
Ok, let's try to implement the algorithm your brain uses when you solve it

So do you have kids or are about to have kids ?
I have two, age seven & eight, still haven't painted the nursery ...

/rockmoose

Edited by - rockmoose on 09/21/2004 16:25:27
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 09/21/2004 :  16:31:25  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
I'm having a kid.

Well, actually my wife is having a kid. I caused it.

Little girl should be here in early December, the nursery looks great and has a nice recliner in it, now it just needs a crib and what not.

As far as the algorithm goes... I haven't been able to work that out yet. With brute force it is simple to define the algorith as you are just quantifying the error and then working that error to zero. It may be very possible that the best possible solution does not immediately start decreasing the error. It may actually shift pieces around to get a large decrease at once. It makes great sense from ehorns link, but how to incorporate that concept... I'lll have to get back to ya!

Corey
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 09/21/2004 :  16:49:28  Show Profile  Reply with Quote
Kids are great, You have a lot to look forward to !
Wish your family all the best.
rockmoose
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/22/2004 :  11:44:34  Show Profile  Reply with Quote
Neat Corey. I had done some tests and the 48 move optimal solution does indeed require the board to become much more unordered (~30%) before it becomes ordered. That is too much error for any heuristic I thought of other than a contrived one designed to solve this specific problem.

I did figure out how to calculate the manhattan distances on the fly without a lookup table. (As you did in your even more sophisticated version.)

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 b1.p b1p, b2.p b2p, sum (abs(b2.x - b1.x) + abs(b2.y - b1.y) ) md
into #md
from #board b1, #board b2
group by b1.p, b2.p

But it was faster to store it as a varchar and use substring operations rather than table lookups:

declare @md varchar(256)
select @md = coalesce(@md,'') + cast(md as char(1)) from #md order by b1p, b2p

Or just hard code it:
set @md = '0123123423453456101221233234434521013212432354343210432154326543123401231234234521231012212332343212210132124323432132104321543223451234012312343234212310122123432332122101321254324321321043213456234512340123434532342123101254344323321221016543543243213210'

The rank function was also much faster if I hard coded the 1 thru 16 offsets rather than using a derived numbers table:

create function f_rank15 (@s char(16)) returns int
as
begin
DECLARE @md varchar(256)
set @md = '0123123423453456101221233234434521013212432354343210432154326543123401231234234521231012212332343212210132124323432132104321543223451234012312343234212310122123432332122101321254324321321043213456234512340123434532342123101254344323321221016543543243213210'
RETURN (select 0 +
substring (@md,Ascii(substring(@s,1,1)) - 64 ,1) +
substring (@md,Ascii(substring(@s,2,1)) - 48,1) +
substring (@md,Ascii(substring(@s,3,1)) - 32,1) +
substring (@md,Ascii(substring(@s,4,1)) - 16,1) +
substring (@md,Ascii(substring(@s,5,1)) ,1) +
substring (@md,Ascii(substring(@s,6,1)) + 16,1) +
substring (@md,Ascii(substring(@s,7,1)) + 32,1) +
substring (@md,Ascii(substring(@s,8,1)) + 48,1) +
substring (@md,Ascii(substring(@s,9,1)) + 64,1) +
substring (@md,Ascii(substring(@s,10,1)) + 80,1) +
substring (@md,Ascii(substring(@s,11,1)) + 96,1) +
substring (@md,Ascii(substring(@s,12,1)) + 112,1) +
substring (@md,Ascii(substring(@s,13,1)) + 128,1) +
substring (@md,Ascii(substring(@s,14,1)) + 144,1) +
substring (@md,Ascii(substring(@s,15,1)) + 160,1) +
substring (@md,Ascii(substring(@s,16,1)) + 176,1)
)
end

I didn't bother to post any of this since it didn't actually help. Nothing I did resulted in anything faster than 7 seconds or better than 50 moves.


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

ehorn
Flowing Fount of Yak Knowledge

USA
1631 Posts

Posted - 09/22/2004 :  14:00:13  Show Profile  Reply with Quote
Ken,

50 moves is quite impressive!!
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 09/22/2004 :  14:27:35  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
by the way -- i hope no one minds, I linked to this thread in my blog at sqlteam -- this is good stuff!



- Jeff
Go to Top of Page

kselvia
Aged Yak Warrior

526 Posts

Posted - 09/22/2004 :  15:20:11  Show Profile  Reply with Quote
I don't mind. The magic of the technique was your solution. Someone should clean up and post a final version that uses less cryptic variable and table names for anyone wanting to understand it someday

I guess Corey is still working on a final version so maybe he will do it

--Ken
I want to die in my sleep like my grandfather, not screaming in terror like his passengers.
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Previous 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.19 seconds. Powered By: Snitz Forums 2000