Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
module CubeSolver
// Represent the state of a Rubik's Cube
type CubeState =
{ EdgePositions : int array
EdgeFlips : int array
CornerPositions : int array
CornerTwists : int array }
// Represent the solved state of a Rubik's Cube
let solvedCube : CubeState =
{ EdgePositions = [| 0 .. 11 |];
EdgeFlips = Array.create 12 0;
CornerPositions = [| 0 .. 7 |]
CornerTwists = Array.create 8 0 }
// Helper type for usage later.
type CubeTransformation = { Label : string; Transformation : CubeState }
// Performing a transformation on a Rubik's Cube.
let Execute cubeState t =
{ EdgePositions = [| for a in 0 .. 11 do yield cubeState.EdgePositions.[t.EdgePositions.[a]] |]
EdgeFlips = [| for a in 0 .. 11 do yield (cubeState.EdgeFlips.[t.EdgePositions.[a]] + t.EdgeFlips.[a]) % 2 |]
CornerPositions = [| for a in 0 .. 7 do yield cubeState.CornerPositions.[t.CornerPositions.[a]] |]
CornerTwists = [| for a in 0 .. 7 do yield (cubeState.CornerTwists.[t.CornerPositions.[a]] + t.CornerTwists.[a]) % 3 |] }
let rec ExecuteN cubeState transformation n =
match n with
| 0 -> cubeState
| 1 -> Execute cubeState transformation
| n when n > 1 -> ( ExecuteN cubeState transformation (n-1) ) |> Execute transformation
| _ -> failwith "need moar n"
// The basic 18 transformations on a Rubik's Cube.
let R =
{ EdgePositions = [| 0; 10; 2; 3; 4; 8; 6; 7; 1; 9; 5; 11 |]
EdgeFlips = Array.create 12 0
CornerPositions = [| 1; 7; 2; 3; 0; 5; 6; 4 |]
CornerTwists = [| 1; 2; 0; 0; 2; 0; 0; 1 |] }
let U =
{ EdgePositions = [| 3; 0; 1; 2; 4; 5; 6; 7; 8; 9; 10; 11|]
EdgeFlips = Array.create 12 0
CornerPositions = [| 3; 0; 1; 2; 4; 5; 6; 7 |]
CornerTwists = Array.create 8 0 }
let F =
{ EdgePositions = [| 8; 1; 2; 3; 9; 5; 6; 7; 4; 0; 10; 11 |]
EdgeFlips = [| 1; 0; 0; 0; 1; 0; 0; 0; 1; 1; 0; 0 |]
CornerPositions = [| 4; 1; 2; 0; 5; 3; 6; 7 |]
CornerTwists = [| 2; 0; 0; 1; 1; 2; 0; 0 |] }
let L =
{ EdgePositions = [| 0; 1; 2; 9; 4; 5; 6; 11; 8; 7; 10; 3 |]
EdgeFlips = Array.create 12 0
CornerPositions= [| 0; 1; 3; 5; 4; 6; 2; 7 |]
CornerTwists = [| 0; 0; 1; 2; 0; 1; 2; 0 |] }
let D =
{ EdgePositions = [| 0; 1; 2; 3; 5; 6; 7; 4; 8; 9; 10; 11 |]
EdgeFlips = Array.create 12 0
CornerPositions = [| 0; 1; 2; 3; 7; 4; 5; 6 |]
CornerTwists = Array.create 8 0 }
let B =
{ EdgePositions = [| 0; 1; 11; 3; 4; 5; 10; 7; 8; 9; 2; 6 |]
EdgeFlips = [| 0; 0; 1; 0; 0; 0; 1; 0; 0; 0; 1; 1 |]
CornerPositions = [| 0; 2; 6; 3; 4; 5; 7; 1 |]
CornerTwists = [| 0; 1; 2; 0; 0; 0; 1; 2 |] }
let R2 = ExecuteN solvedCube R 2
let R' = ExecuteN solvedCube R 3
let U2 = ExecuteN solvedCube U 2
let U' = ExecuteN solvedCube U 3
let F2 = ExecuteN solvedCube F 2
let F' = ExecuteN solvedCube F 3
let L2 = ExecuteN solvedCube L 2
let L' = ExecuteN solvedCube L 3
let D2 = ExecuteN solvedCube D 2
let D' = ExecuteN solvedCube D 3
let B2 = ExecuteN solvedCube B 2
let B' = ExecuteN solvedCube B 3
type MoveSets =
static member All =
[ { Label = "F"; Transformation = F };
{ Label = "F'"; Transformation = F' };
{ Label = "F2"; Transformation = F2 };
{ Label = "U"; Transformation = U };
{ Label = "U'"; Transformation = U' };
{ Label = "U2"; Transformation = U2 };
{ Label = "R"; Transformation = R };
{ Label = "R'"; Transformation = R' };
{ Label = "R2"; Transformation = R2 };
{ Label = "L"; Transformation = L };
{ Label = "L'"; Transformation = L' };
{ Label = "L2"; Transformation = L2 };
{ Label = "D"; Transformation = D };
{ Label = "D'"; Transformation = D' };
{ Label = "D2"; Transformation = D2 };
{ Label = "B"; Transformation = B };
{ Label = "B'"; Transformation = B' };
{ Label = "B2"; Transformation = B2 }; ]
// A scrambler (currently buggy!)
// TODO: Fix bugs.
let Scramble cubeState (movesAllowed : CubeTransformation list) n =
let rnd = new System.Random()
let mutable scrambledCube = cubeState
let mutable movesPerformed = []
for i = 1 to n do
let nextMove = movesAllowed.[rnd.Next(movesAllowed.Length)]
scrambledCube <- scrambledCube |> Execute nextMove.Transformation
movesPerformed <- nextMove.Label :: movesPerformed
(scrambledCube, System.String.Join(" ", movesPerformed))
// A very basic tree search.
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
// Some very basic tests
open Xunit
open FsUnit.Xunit
[<Fact>]
let ``Scrambled cube should be solvable`` () =
let depth = 3
let scrambledCube = Scramble solvedCube MoveSets.All depth
let actualCube = fst scrambledCube
let response = BasicTreeSearch actualCube depth MoveSets.All
(response |> List.length) > 0 |> should equal true
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.