« Go Back to Phase 2

One noted issue with a basic tree search algorithm is that:

Given a cube that is only 3 moves scrambled, and given a max depth of 7 to look into, a tree search would commonly try far too many potential solutions.

One way to solve this issue is to use an iterative deepening solution. Essentially, it's just a small wrapper around the basic tree search, raising the max depth provided by 1 in each call and hoping for some solutions.

let IDASearch scrambledState maxDepth (movesAllowed: CubeTransformation list) =

    let mutable solutions = []

    for a in 1 .. maxDepth do
        if solutions.IsEmpty then

            let treeSearchResponse = BasicTreeSearch scrambledState a movesAllowed

            if not treeSearchResponse.IsEmpty then
                solutions <- treeSearchResponse

    solutions

Relevant Tests:

[<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