« Go Back to Phase 2

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