The single-best explanation of a Tree Search that I've found comes from Jaap's page here.

The basic idea is:

Given a scrambled cube and a maximum depth to search, try all possible combinations of moves, up to the max depth, branching out as you go.

In psuedocode:

``````function Treesearch( position p; depth d )
if p is solved then
Hooray!
elseif d>0 then
for each available move m
Treesearch( result of m applied to p; d-1 )
endfor
endif
endfunction
``````

My implementation of such is:

``````let BasicTreeSearch scrambledState maxDepth (movesAllowed: CubeTransformation list) =

let solutions = ref []

let rec BasicTreeSearch_Internal cubeState d (movesSoFar : string list) =
if cubeState = solvedCube then
solutions:= (movesSoFar |> String.concat " " ) :: !solutions

elif d > 0 then
movesAllowed
|> List.iter
(fun move ->
BasicTreeSearch_Internal (cubeState |> Execute move.Transformation) (d-1) (move.Label :: movesSoFar)
)

BasicTreeSearch_Internal scrambledState maxDepth []
solutions.Value
``````

One unfortunate downside of this method, to note, is that while a cube might be able to be solved in only 3 moves, if you supply a max depth of 7, it may try many more positions than it needs to, as it checks "depth-first"

One basic test:

``````[<Fact>]
let ``Scrambled cube should be solvable`` () =
let depth = 3

let scrambledCube = Scramble solvedCube Movesets.MoveSets.All depth
let actualCube = fst scrambledCube

let response =  IDASearch actualCube depth Movesets.MoveSets.All
(response |> List.length) > 0 |> should equal true
``````