Skip to content

Instantly share code, notes, and snippets.

@StachuDotNet
Created December 27, 2014 20:14
Show Gist options
  • Save StachuDotNet/d2eb8143cb167e7d36f8 to your computer and use it in GitHub Desktop.
Save StachuDotNet/d2eb8143cb167e7d36f8 to your computer and use it in GitHub Desktop.
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