>Thanks Gregory - but as I said , my maths fail me - just thought someone could explain it in "plain english" - thanks anyway

Pete,


I knew it was a problem reduction 'thing'. A simple start state is easy to solve

Been thinking to come up with an algorithm that would solve any state (=configuration). Any state = any number of pegs and disks

I think I've got there - algorithm follows
ps: I had to test the algorithm - so I have coded it (in C#3)

I have given it a random config of 4 pegs and 20 disks. It analyzed and found 18 moves to do (eg move top 5 disks of peg 1 to peg 2) which after problem reduction resulted in 882513 simple moves (of one disk at a time). All 882513 moves have then been done - just in case

Sometimes it chockes - ie it takes time to find out what to do

If you are interested i can post the code

	- State.cs
		- holds a state (config of pegs and disks)
		- two constructors
			- with a list of lists, one list per peg, the other holds the disks
			- a random state of n pegs and m disks
		- analyse a problem and produce steps to solve it
		- interprete the steps and produce moves of one disk
	- Peg.cs
	- BatchCompares.cs (the Comparer to sort the batches)
	- MoveEventargs.cs (just the event class for a simple move)
	- StrategyEventargs.cs (the moves produced during the analysis)
	- program.cs (the test program)

update: this algorithm is not the fastest: better algorithm see message#1407738

Configuration

	·  A number of pegs, at least 3
	·   A number of disks 

		o   At least one disk
		o   Scattered over the pegs, in any order
		o   No disk can be on top of a smaller disk

General algorithm (Handbook of AI, Volume I, page 37)

To solve any simple state (say peg 1 contains n disks, peg 2 empty, peg 3 empty) the algorithm uses problem reduction, as follows

Move a stack of size n, from peg i to peg k:

Find a peg j where peg j is either empty or the top disk is bigger than the bottom disk of the stack that is being moved

	(1)    Move a stack of size n-1 from i to j
	(2)    Move a stack of size 1 from i to k
	(3)    Move a stack of size n-1 from j to k 

Problem (2) is a simple problem whereas problems (1) and (3) need to be broken down until n becomes 2.

Solving this is not that difficult, say we start from the config above, where n = 7

We have an Operator stack

An Operator has three components ( peg from, peg to, and size) { from, to, size }

As long as there is something on the stack

	-          Pop it

	-          If the size is one, we have a simple problem, ie we move the disk from >> to

	-          Otherwise

		o   We decompose the operator and push the parts in reverse order on the Operator stack, ie (3), (2), (1), so that (1) will be popped off before (2) and (3)



Solve any configuration
 

I’ve been thinking about that and have introduced the concept of a batch

A batch is a pile of disks on a peg  where the disks are in consecutive order, eg say we have (1,2,5,6 8) on a peg, it then contains 3 batches (1,2), (5,6) and (8)

With the batch concept, I came up with the following algorithm – I do not claim that it is the fastest

We need a stack of operators

As long as we do not have a goal state (ie all disks on the rightmost peg)

	-          Get a list of all batches + peg number, sorted in ascending batch order

	-          If( the number of batches equals one)

		o   We have a simple problem, 

			§  push onto the stack(peg number, rightmost peg number, size of batch)

		o   Continue

	-          If( the number of free pegs < 1 ) or (batches.Count > number of occupied pegs)

		o   Combine  top two batches (always possible)

			§  Push( peg of batch 1, peg of batch 2, size of batch 1)

		o   Continue

	-          If( last batch is on right peg)

		o    Move batch before last batch on top of it

			§  Push(peg number of batch before last batch, right peg, size of batch before last batch)

			§  Continue

	-          If( right peg is occupied )

		o   Make it empty

			§  If there is a tmp peg for the move

				·         Push the move

				·         Continue

			§  Else

				·         Combine  top two batches

				·         Continue

	-          If( right peg is empty )

		o   Move last batch to here

			§  If there’s a tmp peg available for the move

				·         Push the move

				·         Continue

			§  Else

			·         Combine top two batches

			·         Continue

	-          If we get here – program logic error


if( we have a goal state )
 	reverse the operator stack