commit 0e8d73bb3edcc8bdff6e3ded442b66f68265059a
parent 4e359b44ce111b04cc4d2b28033fba4ab4e6e989
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Sun, 21 Jun 2020 23:01:57 +0200
First push
Diffstat:
38 files changed, 4242 insertions(+), 1 deletion(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,2 @@
+backup
+src/dbg_compile.sh
diff --git a/README.md b/README.md
@@ -1,2 +1,39 @@
# nissy
-A Rubik's cube solver and FMC assistant
+A Rubik's cube solver and FMC assistant.
+
+## Just another cube solver?
+Yes, pretty much. I wanted to write one and I started coding without any
+specific goal in mind. It is not more efficient than [CubeExplorer](http://kociemba.org/cube.htm), nor it is
+particularly user-friendly.
+
+## But does it do something unique?
+Yes, actually it does, but only for a very small niche of people. It allows to produce step-by-step solutions using DR
+([Thistlethwaite](/https://www.speedsolving.com/wiki/index.php/Thistlethwaite%27s_algorithm)/[Kociemba](https://www.speedsolving.com/wiki/index.php/Kociemba%27s_Algorithm) algorithm)
+combined with [NISS](https://www.speedsolving.com/wiki/index.php/Fewest_Moves_techniques). This makes it somewhat useful for [FMC](https://www.speedsolving.com/wiki/index.php/Fewest_Moves_Challenge) solvers who want to analyze a scramble and see if they missed something,
+or what was the optimal way to solve a certain substep at a given point, and so on.
+
+## How to use it
+Check out the help pages in the docs folder. They are also available from
+within nissy with the command "help".
+
+I will add more examples and maybe screenshots when I feel like.
+
+## Installation
+For now you have to download all the files and compile the source
+code yourself. Remember to tell your
+compiler to use the [C99 standard](https://en.wikipedia.org/wiki/C99). For
+example, on a Linux system with GCC installed:
+
+```
+cd path/to/nissy/src
+gcc -O3 -std=c99 -o ../nissy *.c
+cd ..
+./nissy
+```
+
+You can also use the script compile.sh in the src folder, which executes that
+gcc line (with a few extra options).
+
+## Tips
+You can use a tool such as [rlwrap](https://github.com/hanslub42/rlwrap) to allow
+for infinte command history within nissy!
diff --git a/TODO b/TODO
@@ -0,0 +1,13 @@
+NEXT VERSION:
+- solver: improve logic. check after each dr?
+- add checks for sequences >255 moves
+- cat!
+- niss for direct DR
+ - prune for CO using CO+CP state
+- Option: exactly N moves (or lower bound); exactly optimal?
+- CO (also from EO), direct corners solve
+- scramble shortner (solve + invert)
+- RUF-ify
+
+FUTURE IDEAS:
+- sort before branching dfs
diff --git a/docs/add.txt b/docs/add.txt
@@ -0,0 +1,18 @@
+
+HELP PAGE FOR COMMAND add
+
+SYNTAX
+add [MOVES|$ID1|@ID1] $ID2
+
+DESCRIPTION
+Appends either MOVES, the scramble memorized under $ID1 or the output sequence
+memorized under @ID1 at the end of the scramble memorized under $ID2. If none
+of MOVES, $ID1 or @ID1 is specified, the user will be asked to type the moves.
+Menmonic: "add x to y" or just "add to y".
+
+EXAMPLES
+add $1
+ The user is required to type the moves that will be appended to $1.
+add F R B $1
+ Appends the moves F R B to scramble $1. Now scramble $1 ends with F R B.
+
diff --git a/docs/change.txt b/docs/change.txt
@@ -0,0 +1,21 @@
+
+HELP PAGE FOR COMMAND change
+
+SYNTAX
+change $ID1 [MOVES|$ID2|@ID2]
+
+DESCRIPTION
+Changes the scramble $ID1 to either MOVES, the scramble $ID2, the output @ID2
+or, if none is specified, the moves entered by the user. The scramble that was
+memorized under $ID1 is then lost.
+Mnemonic: "change x to y", or just "change x".
+
+EXAMPLES
+change $1
+ The user is required to type the moves that will replace $1.
+change $2 $3
+ Saves the scramble that was saved under $3 in $2. Now $2 and $3 are the same
+ scrambles, and the old $2 is lost.
+change $1 U R
+ Saves U R as scramble $1.
+
diff --git a/docs/dr.txt b/docs/dr.txt
@@ -0,0 +1,45 @@
+
+HELP PAGE FOR COMMAND dr
+
+SYNTAX
+dr [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Solves DR for a given scramble. A scramble can be given as last argument of the
+command, or an ID of a saved scramble can be provided. If none of the two is
+given, a prompt will ask the user to input a new scramble.
+If the option "from" is given (see below), it solves DR from an EO (if edges
+are oriented) without breaking that EO.
+The first time this command is called without the option from (and, to some
+extent, also the first time it is called with the option from), nissy loads
+some pruning tables that were not loaded on startup, causing a small but
+noticeable delay.
+
+OPTIONS
+axis={fb,rl,ud} Specify the axis for the DR. One to three axes can be given,
+ comma separated, no spaces.
+ Default: DR on any of the three axis (omitting the option is
+ the same as specifying axis=fb,rl,ud).
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+h Show hidden DRs.
+ Default, if an DR ending in e.g. R is shown, the equivalent
+ one ending in R' is hidden.
+from {fb|rl|ud} Solve DR from the specified EO, which must be solved,
+ without breaking the EO.
+niss Use NISS. It works only if solving DR from EO.
+ Default: does not use NISS.
+n=N Specify a maximum number of EOs to be output. N must be a
+ number.
+ Default value: 1.
+
+EXAMPLES
+dr from rl axis=ud $1
+ Finds optimal DR on ud, starting from EO on rl, for the first saved scramble.
+
+dr niss from fb n=10 m=6 F2 R L B' F D U' R2 L' F D B
+ Finds up to 10 DRs of length at most 6 from EO on fb, possibly using NISS.
+
+dr n=100 axis=ud h
+ Finds 100 DRs on ud, including "hidden" DRs.
+
diff --git a/docs/drcorners.txt b/docs/drcorners.txt
@@ -0,0 +1,34 @@
+
+HELP PAGE FOR COMMAND drcorners
+
+SYNTAX
+drcorners [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Similar to drfinish, but only solves corners. CO must be solved. The scramble
+can be given as the last argument of the command, or it may be given as an $ID
+or @ID, or it can be typed out on the following line.
+
+OPTIONS
+from {ud|fb|rl} Allows to specify on which axis the CO is solved. It is
+ usually not necessary, since nissy will find a CO on any
+ axis.
+i Ignores E-layer centers. By default cornersare solved
+ relatively to centers; this options allows for solutions
+ which solve corners relatively to each other and to the
+ U and D sides, but not to the E layer (or any equivalent
+ if the CO is not on U/D).
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+n=N Specify a maximum number of solutions to be output. N must
+ be a number.
+ Default value: 1.
+
+EXAMPLES
+drcorners n=3 R' D R2 D' R' U2 R D R' U2 R' D' R
+ Produces the following output:
+Found 3 results.
+@1: U' F2 U R2 U2 F2 U F2 U R2 (10)
+@2: U' F2 U R2 U2 B2 U R2 D R2 (10)
+@3: U' F2 U R2 U2 B2 U L2 U L2 (10)
+
diff --git a/docs/drfinish.txt b/docs/drfinish.txt
@@ -0,0 +1,29 @@
+
+HELP PAGE FOR COMMAND drfinish
+
+SYNTAX
+drfinish [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Solves the given scramble using the DR moveset. DR must be solved. The scramble
+can be given as the last argument of the command, or it may be given as an $ID
+or @ID, or it can be typed out on the following line.
+
+OPTIONS
+from {ud|fb|rl} Allows to specify on which axis the DR is solved. It is
+ usually not necessary, since nissy will find a DR on any
+ axis, but it can be useful if one want to e.g. solve an HTR
+ state allowing quarter-turns from a specific DR.
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+n=N Specify a maximum number of solutions to be output. N must
+ be a number.
+ Default value: 1.
+
+EXAMPLES
+dr from ud R L' U2 R' L F2
+ Solves the given scramble using the moveset <U,D,R2,L2,F2,B2>. In this case:
+@1: U2 R2 F2 R2 U2 R2 F2 R2 (8)
+drfinish b=7 n=10 $1
+ Finds (at most) 10 solutions of length at most 7 for the scramble $1.
+
diff --git a/docs/eo.txt b/docs/eo.txt
@@ -0,0 +1,38 @@
+
+HELP PAGE FOR COMMAND eo
+
+SYNTAX
+eo [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Solves EO for a given scramble. A scramble can be given as last argument of the
+command, or an ID of a saved scramble can be provided. If none of the two is
+given, a prompt will ask the user to input a new scramble.
+
+OPTIONS
+axis={fb,rl,ud} Specify the axis for the EO. One to three axes can be given,
+ comma separated, no spaces.
+ Default: EO on any of the three axis (omitting the option is
+ the same as specifying axis=fb,rl,ud).
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+h Show hidden EOs.
+ Default, if an EO ending in e.g. F is shown, the equivalent
+ one ending in F' is hidden.
+niss Use NISS.
+ Default: does not use NISS.
+n=N Specify a maximum number of EOs to be output. N must be a
+ number.
+ Default value: 1.
+
+EXAMPLES
+eo axis=fb $1
+ Finds one optimal EO on fb for the first saved scramble.
+
+eo n=5 b=4 U R F
+ Finds up to 5 EOs of length at most 4 for scramble U R F.
+
+eo n=100 b=5 niss axis=fb,ud h R' U' F L R'U'F
+ Finds up to 100 EOs of lenth at most 4, possibly using NISS, including
+ "hidden" EOs, excluding the rl axis.
+
diff --git a/docs/exit.txt b/docs/exit.txt
@@ -0,0 +1,9 @@
+
+HELP PAGE FOR COMMAND exit
+
+SYNTAX
+exit
+
+DESCRIPTION
+Exits nissy.
+
diff --git a/docs/help.txt b/docs/help.txt
@@ -0,0 +1,15 @@
+
+HELP PAGE FOR COMMAND help
+
+SYNTAX
+help [nissy|COMMAND]
+
+DESCRIPTION
+'help nissy' prints a general user manual. 'help COMMAND' prints a detailed
+help page for the command COMMAND, if it exists. 'help' prints a list of all
+available commands a short description for each.
+
+EXAMPLES
+help help
+ Prints this help page.
+
diff --git a/docs/htr.txt b/docs/htr.txt
@@ -0,0 +1,30 @@
+
+HELP PAGE FOR COMMAND htr
+
+SYNTAX
+htr [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Finds HTR for a given scramble. DR must be solved. A scramble can be given as
+last argument of the command, or an ID of a saved scramble can be provided. If
+none of the two is given, a prompt will ask the user to input a new scramble.
+
+OPTIONS
+from {ud|fb|rl} Allows to specify on which axis the DR is. This is usually
+ not needed, since nissy will automatically find it out.
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+h Show hidden HTRs.
+ Default, if an HTR ending in e.g. R is shown, the equivalent
+ one ending in R' is hidden.
+niss Use NISS.
+ Default: does not use NISS.
+n=N Specify a maximum number of HTRs to be output. N must be a
+ number.
+ Default value: 1.
+
+EXAMPLES
+eo n=10 b=7 niss $1
+ Finds up to 100 HTRs of lenth at most 7, possibly using NISS, including
+ "hidden" HTRs, for scramble $1. DR must be solved.
+
diff --git a/docs/htrfinish.txt b/docs/htrfinish.txt
@@ -0,0 +1,23 @@
+
+HELP PAGE FOR COMMAND htrfinish
+
+SYNTAX
+htrfinish [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Similar to drfinish, but uses the moveset <U2,D2,R2,L2,F2,B2>. HTR must be
+solved. The scramble can be given as the last argument of the command, or it
+may be given as an $ID or @ID, or it can be typed out on the following line.
+
+OPTIONS
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+n=N Specify a maximum number ofsolutions to be output. N must be
+ a number.
+ Default value: 1.
+
+EXAMPLES
+htrfinish R L' U2 R' L F2
+ Produces the following solution:
+@1: U2 R2 F2 R2 U2 R2 F2 R2 (8)
+
diff --git a/docs/invert.txt b/docs/invert.txt
@@ -0,0 +1,14 @@
+
+HELP PAGE FOR COMMAND invert
+
+SYNTAX
+invert [MOVES|$ID|@ID]
+
+DESCRIPTION
+Inverts a sequence of moves, which can be given also as $ID or @ID. The given
+sequence must not use NISS (if it does, use the command unniss first).
+
+EXAMPLES
+invert F R D'
+ Prints D R' F'
+
diff --git a/docs/nissy.txt b/docs/nissy.txt
@@ -0,0 +1,88 @@
+
+*******************************************************************************
+********************* NISSY: a cube solver and FMC helper *********************
+*******************************************************************************
+
+If you just want to solve the cube, type 'solve' followed by the scramble. This
+will not always give you an optimal solution, unless it is 10 moves or less or
+you use the "o" option. Finding the optimal solution might take very long if it
+is 16 moves or more, especially for the first time.
+
+Now the fun stuff. With nissy you can save and manipulate move sequences, for
+example:
+
+nissy-# save R' U' F
+$1: R' U' F
+nissy-# add L2D' $1
+$1: R' U' F L2 D'
+
+You can then ask nissy to solve certain substepson a saved scramble:
+
+nissy-# eo axis=rl $1
+@1: U D F' R (4)
+
+And of course it uses also NISS, if you ask:
+
+nissy-# eo niss axis=rl $1
+@1: (R) (1)
+
+Notice that the sequences you save are marked with a $, while the "output"
+sequences are marked with @. The difference between these two type of sequences
+is that those marked with @ are temporary and get lost once you get new output.
+Most commands accept as input either a move sequence typed out, a $-sequence or
+a @-sequence. For example, you can however save a @-sequence and make it
+persistent:
+
+nissy-# save @1
+$2: (R)
+
+Nissy also understands NISS. Let's see a more complicated example where you
+save a scramble, ask for some EOs (using NISS) and then a DR on inverse:
+
+nissy-# save R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F
+$3: R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F
+nissy-# eo n=10 niss axis=fb,rl $3
+Found 10 results.
+@1: (U' L B D F) (5)
+@2: (U' L B' D F) (5)
+@3: (L B U D F) (5)
+@4: (L B' U D F) (5)
+@5: R U B U L (5)
+@6: R U' L (B L) (5)
+@7: R U' B U L (5)
+@8: R L (L B L) (5)
+@9: R (U2 D' F R) (5)
+@10: R (U2 F D' R) (5)
+nissy-# add @6 $3
+$3: R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F R U' L (B L)
+nissy-# unniss $3
+@1: L' B' R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F R U' L
+nissy-# invert @1
+@1: L' U R' F' U R F2 U2 D' R D' R' U D' B D2 R2 U' L2 U' R2 D' R2 F2 R2 U' R' F' U R B L
+nissy-# save @1
+$5: L' U R' F' U R F2 U2 D' R D' R' U D' B D2 R2 U' L2 U' R2 D' R2 F2 R2 U' R' F' U R B L
+nissy-# dr from rl $5
+@1: F2 U D2 F' B D B (7)
+nissy-#
+
+If you ask nissy to solve a substep (or the whole cube) using a sequence with
+NISS as scramble, it will first un-NISS it (but without saving the unNISSed
+scramble anywhere):
+
+print $3
+$3: R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F R U' L (B L)
+nissy-# solve $3
+@1: F U' R2 F2 U2 F U2 R2 L2 D R2 U B2 D' L2 D B2 D2 (18)
+
+Nissy knows how to solve certain common sub-steps for DR (or Thistlethwaite /
+Kociemba algorithms). For now it does know more common speedsolving methods.
+
+For a full list of commands type "help". For a more detailed help on a specific
+command, type "help (command)". The help pages can also be found in the docs
+folder.
+
+If you want to report a bug (I'm sure there are many!) or give a suggestion,
+you can send an email to sebastiano.tronto@gmail.com.
+
+Have fun!
+
diff --git a/docs/pic.txt b/docs/pic.txt
@@ -0,0 +1,20 @@
+
+HELP PAGE FOR COMMAND pic
+
+SYNTAX
+pic [MOVES|$ID|@ID]
+
+DESCRIPTION
+Prints the cube state after applying the given scramble.
+
+EXAMPLES
+pic R' U' F R U R2 F2 R2 D R2 U L2 U R2 D2 B' D U' R D R' D U2 F2 R' U' F
+ Gives the following output:
+ UF UL UB UR DF DL DB DR FR FL BL BR
+EP: FR UL FL UR UF DB DR BL UB BR DL DF
+EO(F/B): x x x x x x x x
+
+ UFR UFL UBL UBR DFR DFL DBL DBR
+CP: UBR UFR DFL DBL UFL UBL DBR DFR
+CO(U/D): ccw cw ccw cw
+
diff --git a/docs/pre.txt b/docs/pre.txt
@@ -0,0 +1,18 @@
+
+HELP PAGE FOR COMMAND pre
+
+SYNTAX
+pre [MOVES|$ID1|@ID1] $ID2
+
+DESCRIPTION
+Prepends either MOVES, the scramble memorized under $ID1 or the output sequence
+memorized under @ID1 at the beginning of the scramble memorized under $ID2. If
+none of MOVES, $ID1 or @ID1 is specified, the user will be asked to type the
+moves.
+Menmonic: "pre(pend) x to y" or just "pre(pend) to y".
+
+EXAMPLES
+add $1
+ The user is required to type the moves that will be prepended to $1.
+add F R B $1
+ Prepends the moves F R B to scramble $1. Now scramble $1 begins with F R B.
diff --git a/docs/print.txt b/docs/print.txt
@@ -0,0 +1,19 @@
+
+HELP PAGE FOR COMMAND print
+
+SYNTAX
+print [$ID|@ID]
+
+DESCRIPTION
+Prints memorized sequences. If no argument is given, it prints all memorized
+scrambles ($ only). If $ID or @ID is specified, it only prints the relative
+memorized sequence.
+
+EXAMPLES
+print
+ Prints a list of all memorized scrambles (only $).
+print $2
+ Prints the second memorized scramble.
+print @13
+ Prints the 13th sequence that was part of the output of the last command.
+
diff --git a/docs/quit.txt b/docs/quit.txt
@@ -0,0 +1,9 @@
+
+HELP PAGE FOR COMMAND quit
+
+SYNTAX
+quit
+
+DESCRIPTION
+Exits nissy.
+
diff --git a/docs/replace.txt b/docs/replace.txt
@@ -0,0 +1,22 @@
+
+HELP PAGE FOR COMMAND replace
+
+SYNTAX
+eo [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Looks for non-optimal subsequences and replaces them to shorten the given
+sequence. By default it tries to shorten every subsequence of up to 10 moves,
+but this can be change with the "b" option.
+It outputs at most 10 equivalent optimal sequences for each replaceable part.
+
+OPTIONS
+b=N Finds non-optimal subsequences of up to N moves.
+
+EXAMPLES
+replace D2 F' D2 U2 F' L2 R2 U' D B2 D B2 U B2 F L2 R' F' D U'
+ Produces the following output:
+Replace [ R2 U' D B2 D B2 ] (moves 7-12) with: [ D R2 D U' ] (-6+4)
+Replace [ R2 U' D B2 D B2 U ] (moves 7-13) with: [ D R2 D ] (-7+3)
+Replace [ U' D B2 D B2 U ] (moves 8-13) with: [ R2 D R2 D ] (-6+4)
+
diff --git a/docs/save.txt b/docs/save.txt
@@ -0,0 +1,22 @@
+
+HELP PAGE FOR COMMAND save
+
+SYNTAX
+save [MOVES|@ID|$ID]
+
+DESCRIPTION
+Memorizes the scramble specified by MOVES, given as input or temporarily saved
+as @ID, where ID is a number ('help nissy' for for more on IDs). If an $ID is
+given, it makes a copy of the scramble. An identifier of the form $ID, where ID
+is a number, is assigned to the memorized scramble.
+
+EXAMPLES
+save R U R' U'
+ Saves the scramble R U R' U'.
+save F (B)
+ Saves the scramble F (B) (NISS notation).
+save @3
+ Saves the third output sequence of the last command.
+save $2
+ Makes a copy of the second saved scramble.
+
diff --git a/docs/solve.txt b/docs/solve.txt
@@ -0,0 +1,33 @@
+
+HELP PAGE FOR COMMAND solve
+
+SYNTAX
+solve [MOVES|$ID|@ID]
+
+DESCRIPTION
+Solves the given scramble, which can be given as a sequence of moves or as $ID
+or @ID. If none is given, the user can type it on the next line.
+The algorithm first tries to find a short (<=10 moves) solution, and then
+switches to a 2-step algorithm (unless the option "o" is specified, in which
+case it keeps looking for an optimal solution).
+The first time it uses the 2-step algorithm it needs to load some tables, which
+can take a few seconds. It runs much faster after that. If the option "o" is
+specified, the first time it loads some large tables, which can take a minute
+or two.
+
+OPTIONS
+b=N Only looks for solutions up to N moves.
+n=N Tries to find multiple solutions, at most N. Multiple
+ Solutions will only be found if they are <=10 moves.
+o Looks for optimal solution.
+
+
+EXAMPLES
+solve R' U' F
+ Solves the scramble R' U' F.
+solve o b=14 $1
+ Tries to solve the scramble $1 optimally, but stops if no solution of 14
+ moves or shorter is found.
+solve n=16 R L' U2 R' L F2
+ Finds the 16 shortest solutions for the scramble above.
+
diff --git a/docs/unniss.txt b/docs/unniss.txt
@@ -0,0 +1,14 @@
+
+HELP PAGE FOR COMMAND unniss
+
+SYNTAX
+unniss [MOVES|$ID|@ID]
+
+DESCRIPTION
+Removes NISS from a sequence of moves, which can be given also as $ID or @ID.
+A sequence of the form A (B) is translated to B' A.
+
+EXAMPLES
+invert F R (D' L2)
+ Prints L2 D F R
+
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/src/compile.sh b/src/compile.sh
@@ -0,0 +1 @@
+gcc -Wall -Wextra -O3 -std=c99 -o ../nissy -g *.c
diff --git a/src/coordinates.c b/src/coordinates.c
@@ -0,0 +1,288 @@
+/* blabla */
+
+#include <stdio.h>
+
+#include "utils.h"
+#include "coordinates.h"
+
+/* Names of pieces and moves. */
+char edge_string_list[12][5] = {
+ "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR"
+};
+
+char corner_string_list[8][5] = {
+ "UFR", "UFL", "UBL", "UBR", "DFR", "DFL", "DBL", "DBR"
+};
+
+char move_string_list[19][5] = {
+ "-",
+ "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'",
+ "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'"
+};
+
+int inverse_move[19] = {
+ -1, U3, U2, U, D3, D2, D, R3, R2, R, L3, L2, L, F3, F2, F, B3, B2, B
+};
+
+/* Convert piece representation from integer to array.
+ * Come convertions are not "perfect": for example, and epud type of piece
+ * is represented by a permutation index in 8! elements, but it as an array
+ * it is converted to the first 8 elements of a 12 elements ep array (with
+ * meaningless values for the other 4 elements). */
+
+void ep_int_to_array(int ep, int a[12]) {
+ index_to_perm(ep, 12, a);
+}
+
+void epud_int_to_array(int epud, int a[12]) {
+ index_to_perm(epud, 8, a); /* Last 4 elements are left untouched. */
+}
+
+void epfb_int_to_array(int epfb, int a[12]) {
+ int edges[] = {UF, UB, DF, DB, FR, FL, BL, BR};
+ int b[8];
+ index_to_perm(epfb, 8, b);
+ for (int i = 0; i < 8; i++)
+ a[edges[i]] = edges[b[i]];
+}
+
+void eprl_int_to_array(int eprl, int a[12]) {
+ int edges[] = {UL, UR, DL, DR, FR, FL, BL, BR};
+ int b[8];
+ index_to_perm(eprl, 8, b);
+ for (int i = 0; i < 8; i++)
+ a[edges[i]] = edges[b[i]];
+}
+
+void epose_int_to_array(int epos, int a[12]) {
+ int edges[] = {FR, FL, BL, BR};
+ index_to_subset(epos, 12, 4, a);
+ for (int i = 0, j = 0; i < 12; i++)
+ a[i] = (a[i] == 1) ? edges[j++] : -1;
+}
+
+void eposs_int_to_array(int epos, int a[12]) {
+ int edges[] = {UL, UR, DL, DR};
+ index_to_subset(epos, 12, 4, a);
+ for (int i = 0, j = 0; i < 12; i++)
+ a[i] = (a[i] == 1) ? edges[j++] : -1;
+ /* Swap with last 4, so 0 is alway solved state */
+ for (int i = 0; i < 4; i++)
+ swap(&a[edges[i]], &a[i+8]);
+}
+
+void eposm_int_to_array(int epos, int a[12]) {
+ int edges[] = {UF, UB, DF, DB};
+ index_to_subset(epos, 12, 4, a);
+ for (int i = 0, j = 0; i < 12; i++)
+ a[i] = (a[i] == 1) ? edges[j++] : -1;
+ /* Swap with last 4, so 0 is alway solved state */
+ for (int i = 0; i < 4; i++)
+ swap(&a[edges[i]], &a[i+8]);
+}
+
+void epe_int_to_array(int epe, int a[12]) {
+ index_to_perm(epe, 4, a+8);
+ for (int i = 0; i < 4; i++)
+ a[i+8] += 8;
+}
+
+void eps_int_to_array(int eps, int a[12]) {
+ int edges[] = {UL, UR, DL, DR};
+ int b[4];
+ index_to_perm(eps, 4, b);
+ for (int i = 0; i < 4; i++)
+ a[edges[i]] = edges[b[i]];
+}
+
+void epm_int_to_array(int epm, int a[12]) {
+ int edges[] = {UF, UB, DF, DB};
+ int b[4];
+ index_to_perm(epm, 4, b);
+ for (int i = 0; i < 4; i++)
+ a[edges[i]] = edges[b[i]];
+}
+
+void emslices_int_to_array(int emslices, int a[12]) {
+ int b[] = {0,0,0,0,0,0,0,0};
+ int eslice[] = {FR, FL, BL, BR};
+ int mslice[] = {UF, UB, DF, DB};
+
+ index_to_subset(emslices % binom12on4, 12, 4, a);
+ index_to_subset(emslices / binom12on4, 8, 4, b);
+
+ if (emslices % binom12on4 == 0) {
+ swap(&b[UF], &b[DL]);
+ swap(&b[UB], &b[DR]);
+ /*for (int i = 0; i < 4; i++)
+ swap(&b[mslice[i]], &b[i+4]);*/
+ }
+
+ for (int i = 0, j = 0; j < 8; i++, j++) {
+ while (a[i])
+ i++;
+ a[i] = b[j] ? 2 : -1;
+ }
+ for (int i = 0, j1 = 0, j2 = 0; i < 12; i++) {
+ if (a[i] == 1)
+ a[i] = eslice[j1++];
+ if (a[i] == 2)
+ a[i] = mslice[j2++];
+ }
+}
+
+void cp_int_to_array(int cp, int a[8]) {
+ index_to_perm(cp, 8, a);
+}
+
+void eo_11bits_to_array(int eo, int a[12]) {
+ int_to_sum_zero_array(eo, 2, 12, a);
+}
+
+void co_7trits_to_array(int co, int a[8]) {
+ int_to_sum_zero_array(co, 3, 8, a);
+}
+
+
+
+
+
+int ep_array_to_int(int ep[12]) {
+ return perm_to_index(ep, 12);
+}
+
+int epud_array_to_int(int ep[12]) {
+ return perm_to_index(ep, 8); /* Last 4 elements are ignored */
+}
+
+int epfb_array_to_int(int ep[12]) {
+ int index[] = {0, -1, 1, -1, 2, -1, 3, -1, 4, 5, 6, 7};
+ int b[8];
+ for (int i = 0; i < 12; i++)
+ if (index[i] != -1)
+ b[index[i]] = index[ep[i]];
+ return perm_to_index(b, 8);
+}
+
+int eprl_array_to_int(int ep[12]) {
+ int index[] = {-1, 0, -1, 1, -1, 2, -1, 3, 4, 5, 6, 7};
+ int b[8];
+ for (int i = 0; i < 12; i++)
+ if (index[i] != -1)
+ b[index[i]] = index[ep[i]];
+ return perm_to_index(b, 8);
+}
+
+int epose_array_to_int(int ep[12]) {
+ int a[12];
+ for (int i = 0; i < 12; i++)
+ a[i] = (ep[i] >= FR);
+ return subset_to_index(a, 12, 4);
+}
+
+int eposs_array_to_int(int ep[12]) {
+ int a[12];
+ int edges[] = {UL, UR, DL, DR};
+ for (int i = 0; i < 12; i++)
+ a[i] = (ep[i] == UL || ep[i] == UR || ep[i] == DL || ep[i] == DR);
+ /* Swap with last 4, so 0 is alway solved state */
+ for (int i = 0; i < 4; i++)
+ swap(&a[edges[i]], &a[i+8]);
+ return subset_to_index(a, 12, 4);
+}
+
+int eposm_array_to_int(int ep[12]) {
+ int a[12];
+ int edges[] = {UF, UB, DF, DB};
+ for (int i = 0; i < 12; i++)
+ a[i] = (ep[i] == UF || ep[i] == UB || ep[i] == DF || ep[i] == DB);
+ /* Swap with last 4, so 0 is alway solved state */
+ for (int i = 0; i < 4; i++)
+ swap(&a[edges[i]], &a[i+8]);
+ return subset_to_index(a, 12, 4);
+}
+
+int epe_array_to_int(int ep[12]) {
+ int b[4];
+ for (int i = 0; i < 4; i++)
+ b[i] = ep[i+8] - 8;
+ return perm_to_index(b, 4);
+}
+
+int eps_array_to_int(int ep[12]) {
+ int index[] = {-1, 0, -1, 1, -1, 2, -1, 3, -1, -1, -1, -1};
+ int b[4];
+ for (int i = 0; i < 12; i++)
+ if (index[i] != -1)
+ b[index[i]] = index[ep[i]];
+ return perm_to_index(b, 4);
+}
+
+int epm_array_to_int(int ep[12]) {
+ int index[] = {0, -1, 1, -1, 2, -1, 3, -1, -1, -1, -1, -1};
+ int b[4];
+ for (int i = 0; i < 12; i++)
+ if (index[i] != -1)
+ b[index[i]] = index[ep[i]];
+ return perm_to_index(b, 4);
+}
+
+int emslices_array_to_int(int ep[12]) {
+ int a[12], b[12], c[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+ /*int edges[] = {UF, UB, DF, DB};*/
+ for (int i = 0; i < 12; i++) {
+ a[i] = (ep[i] >= FR) ? 1 : 0;
+ b[i] = (ep[i] == UF || ep[i] == UB || ep[i] == DF || ep[i] == DB) ? 1 : 0;
+ }
+
+ /*for ( int i = 0; i < 12; i++)
+ printf("%d ", ep[i]);
+ printf("\n");*/
+
+ for (int i = 0, j = 0; i < 12; i++, j++) {
+ if (a[i])
+ j--;
+ if (b[i])
+ c[j] = 1;
+ }
+
+ int epose = subset_to_index(a, 12, 4);
+
+ /*if (epose == 0) {
+ printf("Before: ");
+ for (int i = 0; i < 8; i++)
+ printf("%d ", c[i]);
+ printf("\n");
+ for (int i = 0; i < 4; i++)
+ swap(&c[edges[i]], &c[i+4]);
+ printf("After: ");
+ for (int i = 0; i < 8; i++)
+ printf("%d ", c[i]);
+ printf("\n");
+ }*/
+ if (epose == 0) {
+ swap(&c[UF], &c[DL]);
+ swap(&c[UB], &c[DR]);
+ }
+
+ /*for ( int i = 0; i < 8; i++)
+ printf("%d ", c[i]);
+ printf("\n");*/
+ int eposm = subset_to_index(c, 8, 4);
+
+ return epose + 495*eposm;
+}
+
+
+int cp_array_to_int(int cp[8]) {
+ return perm_to_index(cp, 8);
+}
+
+int eo_array_to_11bits(int a[12]) {
+ return digit_array_to_int(a, 11, 2);
+}
+
+int co_array_to_7trits(int a[8]) {
+ return digit_array_to_int(a, 7, 3);
+}
+
diff --git a/src/coordinates.h b/src/coordinates.h
@@ -0,0 +1,92 @@
+/* General rule for piece numbering (visually nicer):
+ *
+ * 0 1 2 3 4 5 6 7 8 9 10 11
+ * UF UL UB UR DF DL DB DR FR FL BL BR
+ * UFR UFL UBL UBR DFR DFL DBL DBR
+ *
+ * The order of moves is
+ * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
+ * - U U2 U' D D2 D' R R2 R' L L2 L' F F2 F' B B2 B'
+ * (0 is reserved for no move) */
+
+#define UF 0
+#define UL 1
+#define UB 2
+#define UR 3
+#define DF 4
+#define DL 5
+#define DB 6
+#define DR 7
+#define FR 8
+#define FL 9
+#define BL 10
+#define BR 11
+
+#define UFR 0
+#define UFL 1
+#define UBL 2
+#define UBR 3
+#define DFR 4
+#define DFL 5
+#define DBL 6
+#define DBR 7
+
+#define U 1
+#define U2 2
+#define U3 3
+#define D 4
+#define D2 5
+#define D3 6
+#define R 7
+#define R2 8
+#define R3 9
+#define L 10
+#define L2 11
+#define L3 12
+#define F 13
+#define F2 14
+#define F3 15
+#define B 16
+#define B2 17
+#define B3 18
+
+extern char edge_string_list[12][5];
+extern char corner_string_list[8][5];
+extern char move_string_list[19][5];
+extern int inverse_move[19];
+
+/* Convert piece representation from integer to array.
+ * Come convertions are not "perfect": for example, and epud type of piece
+ * is represented by a permutation index in 8! elements, but it as an array
+ * it is converted to the first 8 elements of a 12 elements ep array (with
+ * meaningless values for the other 4 elements). */
+
+void ep_int_to_array(int ep, int a[12]);
+void epud_int_to_array(int epud, int a[12]);
+void epfb_int_to_array(int epfb, int a[12]);
+void eprl_int_to_array(int eprl, int a[12]);
+void epose_int_to_array(int epos, int a[12]);
+void eposs_int_to_array(int epos, int a[12]);
+void eposm_int_to_array(int epos, int a[12]);
+void epe_int_to_array(int epe, int a[12]);
+void epm_int_to_array(int epe, int a[12]);
+void eps_int_to_array(int epe, int a[12]);
+void emslices_int_to_array(int emslices, int a[12]);
+void cp_int_to_array(int cp, int a[8]);
+void eo_11bits_to_array(int eo, int a[12]);
+void co_7trits_to_array(int co, int a[8]);
+
+int ep_array_to_int(int ep[12]);
+int epud_array_to_int(int ep[12]);
+int epfb_array_to_int(int ep[12]);
+int eprl_array_to_int(int ep[12]);
+int epose_array_to_int(int ep[12]);
+int eposs_array_to_int(int ep[12]);
+int eposm_array_to_int(int ep[12]);
+int epe_array_to_int(int epe[12]);
+int epm_array_to_int(int epe[12]);
+int eps_array_to_int(int epe[12]);
+int emslices_array_to_int(int ep[12]);
+int cp_array_to_int(int cp[8]);
+int eo_array_to_11bits(int a[12]);
+int co_array_to_7trits(int a[8]);
diff --git a/src/io.c b/src/io.c
@@ -0,0 +1,232 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "coordinates.h"
+#include "moves.h"
+#include "utils.h"
+
+/* Functions for nice output */
+char *edge_string(int i) {
+ return (i > -1 && i < 12) ? edge_string_list[i] : "-";
+}
+
+char *corner_string(int i) {
+ return (i > -1 && i < 8) ? corner_string_list[i] : "-";
+}
+
+char *move_string(int i) {
+ return (i > -1 && i < 19) ? move_string_list[i] : "err";
+}
+
+void print_ep_array(int ep[12]) {
+ for (int i = 0; i < 12; i++)
+ printf(" %s ", edge_string(ep[i]));
+}
+
+void print_ep_int(int ep) {
+ int aux[12];
+ ep_int_to_array(ep, aux);
+ print_ep_array(aux);
+}
+
+void print_cp_array(int cp[8]) {
+ for (int i = 0; i < 8; i++)
+ printf(" %s ", corner_string(cp[i]));
+}
+
+void print_cp_int(int cp) {
+ int aux[8];
+ cp_int_to_array(cp, aux);
+ print_cp_array(aux);
+}
+
+void print_eo_array(int eo[12]) {
+ for (int i = 0; i < 12; i++) {
+ if (eo[i])
+ printf(" x ");
+ else
+ printf(" ");
+ }
+}
+
+void print_eo_int(int eo) {
+ int aux[12];
+ eo_11bits_to_array(eo, aux);
+ print_eo_array(aux);
+}
+
+void print_co_array(int co[8]) {
+ for (int i = 0; i < 8; i++) {
+ if (co[i] == 0)
+ printf(" ");
+ if (co[i] == 1)
+ printf(" cw ");
+ if (co[i] == 2)
+ printf(" ccw ");
+ }
+}
+
+void print_co_int(int co) {
+ int aux[8];
+ co_7trits_to_array(co, aux);
+ print_co_array(aux);
+}
+
+void print_cube_scram(int *scram) {
+ int ep = 0, cp = 0, eofb = 0, coud = 0;
+ for (int i = 0; scram[i]; i++) {
+ ep = apply_move_ep_int(scram[i], ep);
+ cp = cp_transition_table[cp][scram[i]];
+ eofb = eofb_transition_table[eofb][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+ }
+ printf("\t\t"); print_ep_int(0); printf("\n");
+ printf("EP:\t\t"); print_ep_int(ep); printf("\n");
+ printf("EO(F/B):\t"); print_eo_int(eofb); printf("\n");
+ printf("\n");
+ printf("\t\t"); print_cp_int(0); printf("\n");
+ printf("CP:\t\t"); print_cp_int(cp); printf("\n");
+ printf("CO(U/D):\t"); print_co_int(coud); printf("\n");
+}
+
+
+void copy_moves(int *src, int *dst) {
+ for (int i = 0; (dst[i] = src[i]); i++);
+}
+
+void append_moves(int *src, int *dst) {
+ int n = 0;
+ for (; dst[n]; n++);
+ copy_moves(src, dst+n);
+}
+
+/* Parse a string and saves the move in a. Supports NISS notation.
+ * Returns the number of moves, or -1 in case of error. */
+int read_moves(char *str, int *a) {
+ int count = 0;
+ int niss = 0;
+ for (int i = 0; str[i] && str[i] != '\n'; i++) {
+ while (str[i] == ' ' || str[i] == '\t') i++;
+ switch (str[i]) {
+ case 'U':
+ a[count++] = niss ? -U : U;
+ break;
+ case 'D':
+ a[count++] = niss ? -D : D;
+ break;
+ case 'R':
+ a[count++] = niss ? -R : R;
+ break;
+ case 'L':
+ a[count++] = niss ? -L : L;
+ break;
+ case 'F':
+ a[count++] = niss ? -F : F;
+ break;
+ case 'B':
+ a[count++] = niss ? -B : B;
+ break;
+ case '(':
+ if (niss)
+ return -1;
+ else
+ niss = 1;
+ break;
+ case ')':
+ if (!niss)
+ return -1;
+ else
+ niss = 0;
+ break;
+ default:
+ return -1;
+ }
+ switch (str[++i]) {
+ case '2':
+ a[count-1] += niss ? -1 : 1;
+ break;
+ case '\'':
+ case '3':
+ a[count-1] += niss ? -2 : 2;
+ break;
+ case '1':
+ default:
+ --i;
+ }
+ }
+ a[count] = 0;
+ return count;
+}
+
+/* Read moves from standard input, after a prompt. */
+int read_moves_from_prompt(int *a) {
+ char str[1000];
+ printf("Enter moves: ");
+ if (fgets(str, 1000, stdin) == NULL)
+ return -1;
+ return read_moves(str, a);
+}
+
+/* Read moves from a list of token, each containing one or more moves. */
+int read_moves_from_tok(int n, char tok[][100], int *a) {
+ char str[1000] = "";
+ for (int i = 0; i < n; i++)
+ strcat(str, tok[i]);
+ return read_moves(str, a);
+}
+
+/* Checks if a sequence of moves uses NISS */
+int uses_niss(int *str) {
+ for (int i = 0; str[i]; i++)
+ if (str[i] < 0)
+ return 1;
+ return 0;
+}
+
+/* A (B) -> B' A */
+int unniss(int *src, int *dst) {
+ int n = 0;
+ for (int i = 0; src[i]; i++)
+ if (src[i] < 0)
+ n++;
+
+ int norm_count = n, inv_count = n-1;
+ for (int i = 0; src[i]; i++)
+ if (src[i] > 0)
+ dst[norm_count++] = src[i];
+ else
+ dst[inv_count--] = inverse_move[-src[i]];
+
+ dst[norm_count] = 0;
+
+ return n;
+}
+
+int invert(int *src, int *dst) {
+ int aux[255];
+ for (int i = 0; (aux[i] = -src[i]); i++);
+ return unniss(aux, dst);
+}
+
+int len(int *scram) {
+ int m;
+ for (m = 0; scram[m]; m++);
+ return m;
+}
+
+void print_moves(int moves_list[]) {
+ int niss = 0;
+ for (int i = 0; moves_list[i]; i++) {
+ if (!niss && moves_list[i] < 0) {
+ printf("(");
+ niss = 1;
+ }
+ printf("%s", move_string_list[abs(moves_list[i])]);
+ if (niss && moves_list[i+1] >= 0) {
+ niss = 0;
+ printf(")");
+ }
+ printf(" ");
+ }
+}
diff --git a/src/io.h b/src/io.h
@@ -0,0 +1,21 @@
+#include <stdint.h>
+
+char *edge_string(int edge);
+char *corner_string(int edge);
+char *move_string(int move);
+
+void print_cube_scram(int *scram);
+
+void copy_moves(int *src, int *dst);
+void append_moves(int *src, int *dst);
+
+int read_moves(char *str, int *a);
+int read_moves_from_prompt(int *a);
+int read_moves_from_tok(int n, char tok[][100], int *a);
+
+int uses_niss(int *str);
+int unniss(int *src, int *dst);
+int invert(int *src, int *dst);
+int len(int *scram);
+
+void print_moves(int move_list[]);
diff --git a/src/main.c b/src/main.c
@@ -0,0 +1,801 @@
+/* blabla */
+#include <stdio.h>
+#include <stdlib.h>
+#include "utils.h"
+#include "coordinates.h"
+#include "io.h"
+#include "moves.h"
+#include "solver.h"
+#include "string.h"
+
+char *commands[][10] = {
+ {"help", "[COMMAND]",
+ "Print this help, or a help page for COMMAND."},
+ {"save", "[MOVES|@ID|$ID]",
+ "Save or copy a scramble."},
+ {"change", "$ID1 [MOVES|$ID2|@ID2]",
+ "Change a memorized scramble."},
+ {"print", "[$ID|@ID]",
+ "Print memorized sequences."},
+ {"add", "[MOVES|$ID1|@ID1] $ID2",
+ "Add moves at the end of a memorized scramble."},
+ {"invert", "[MOVES|$ID|@ID]",
+ "Inverts the given sequence of moves."},
+ {"unniss", "[MOVES|$ID|@ID]}",
+ "Removes NISS: A (B) -> B\' A."},
+ {"pic", "[MOVES|$ID|@ID]",
+ "Show a text description of the scrambled cube."},
+ {"solve", "[MOVES|$ID|@ID]",
+ "Solves a scramble."},
+ {"replace", "[MOVES|$ID|@ID]",
+ "Find non-optimal subsequences."},
+ {"eo", "[MOVES|$ID|@ID]",
+ "Solves EO."},
+ {"dr", "[MOVES|$ID|@ID]",
+ "Solves DR, either directly or from eo."},
+ {"htr", "[MOVES|$ID|@ID]",
+ "Solves HTR from DR."},
+ {"drfinish", "[MOVES|$ID|@ID]",
+ "Solves the cube after DR."},
+ {"htrfinish", "[MOVES|$ID|@ID]",
+ "Solves the cube using only half turns."},
+ {"drcorners", "[MOVES|$ID|@ID]",
+ "Solves corners after DR."},
+ {"exit", "",
+ "Exit nissy."},
+ {"quit", "",
+ "Exit nissy."},
+ {"", "", ""}
+};
+
+/* Saved sequences of moves */
+int scr_count=1, tmp_count=1, max_tmp=999;
+int scrambles[255][255], tmp[1000][255];
+
+int read_moves_from_variable(char *id, int *dst) {
+ char c = id[0];
+ if (c != '$' && c != '@')
+ return -1;
+ int n = atoi(id+1);
+ if (n <= 0 || n >= (c == '$' ? scr_count : tmp_count))
+ return -1;
+ copy_moves(c == '$' ? scrambles[n] : tmp[n], dst);
+ return n;
+}
+
+int read_moves_from_argument(int n, char tok[][100], int *dst) {
+ int r = read_moves_from_variable(tok[0], dst);
+ return (r != -1) ? r : read_moves_from_tok(n, tok, dst);
+}
+
+void print_results(int n, int res[][21]) {
+ if (n == -1)
+ printf("Pre-conditions not satisfied (or other error).\n");
+
+ if (n == 0)
+ printf("No result found (try different bounds).\n");
+
+ if (n > 1)
+ printf("Found %d results.\n", n);
+ tmp_count = 1; /* Reset temporary count */
+ for (int i = 0; i < n; i++) {
+ if (i < max_tmp) {
+ copy_moves(res[i], tmp[tmp_count]);
+ printf("@%d:\t", tmp_count++);
+ } else {
+ printf(" \t");
+ }
+ print_moves(res[i]);
+ printf("(%d)\n", len(res[i]));
+ }
+}
+
+/* Removes extra white spaces from the input string */
+int parsecmd(char *cmd, char cmdtok[][100]) {
+ char *i = cmd, *j = cmd;
+ while (*j != '\n' && *j != EOF) {
+ *i = *j;
+ if (*i == ' ' || *i == '\t')
+ *i = ' ';
+ ++j;
+ if (*i == ' ' || *i == '\t')
+ while (*j == ' ' || *j == '\t')
+ ++j;
+ ++i;
+ }
+ if (*(i-1) == ' ')
+ *(i-1) = 0;
+ else
+ *i = 0;
+
+ int n = 0;
+ char *s = strtok(cmd, " ");
+ while (s != NULL) {
+ strcpy(cmdtok[n++], s);
+ s = strtok(NULL, " ");
+ }
+ return n;
+}
+
+void help_cmd(int n, char cmdtok[][100]) {
+ if (n == 1) {
+ printf("\n");
+ for (int i = 0; commands[i][0][0]; i++)
+ printf("%-10s%-20s%s\n", commands[i][0], commands[i][1], commands[i][2]);
+ printf("\n");
+ printf("Type \'help\' followed by a command for a detailed help page.\n");
+ printf("Type \'help nissy\' for a general user guide.\n");
+ } else if (n == 2) {
+ char fname[255], line[255] = "";
+ FILE *file;
+ sprintf(fname, "docs/%s.txt", cmdtok[1]);
+ file = fopen(fname, "r");
+ if (file == NULL) {
+ printf("No help file for %s.\n", cmdtok[1]);
+ return;
+ }
+ while (fgets(line, 255, file) != NULL)
+ printf("%s", line);
+ } else {
+ printf("help: wrong syntax.\n");
+ }
+}
+
+void save_cmd(int n, char cmdtok[][100]) {
+ int scram[255];
+ if (n == 1) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("save: error reading moves. Not saved.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
+ printf("save: error reading moves or ID. Not saved.\n");
+ return;
+ }
+
+ copy_moves(scram, scrambles[scr_count]);
+
+ printf("$%d:\t", scr_count);
+ print_moves(scrambles[scr_count]);
+ printf("\n");
+ scr_count++;
+}
+
+void change_cmd(int n, char cmdtok[][100]) {
+ int id, scram[255];
+ if (n == 1) {
+ printf("change: you must specify an $ID.\n");
+ return;
+ } else if (cmdtok[1][0] != '$') {
+ printf("change: invalid $ID.\n");
+ return;
+ } else {
+ id = atoi(cmdtok[1]+1);
+ if (id <= 0 || id >= scr_count) {
+ printf("change: invalid $ID.\n");
+ return;
+ }
+ if (n == 2) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("change: error reading moves.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-2, cmdtok+2, scram) == -1 ) {
+ printf("change: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ copy_moves(scram, scrambles[id]);
+
+ printf("$%d:\t", id);
+ print_moves(scrambles[id]);
+ printf("\n");
+}
+
+void print_cmd(int n, char cmdtok[][100]) {
+ if (n == 1) {
+ for (int i = 1; i < scr_count; i++) {
+ printf("$%d:\t", i);
+ print_moves(scrambles[i]);
+ printf("\n");
+ }
+ } else if (n == 2) {
+ int i = atoi(cmdtok[1]+1);
+ char sign = cmdtok[1][0];
+ if (sign != '$' && sign != '@') {
+ printf("print: invalid ID (must start with $ or @).\n");
+ return;
+ }
+ if (i > 0 && i < (sign == '$' ? scr_count : tmp_count)) {
+ printf("%c%d:\t", sign, i);
+ print_moves(sign == '$' ? scrambles[i] : tmp[i]);
+ printf("\n");
+ } else {
+ printf("print: invalid ID.\n");
+ return;
+ }
+ } else {
+ printf("print: wrong syntax.\n");
+ }
+}
+
+void add_cmd(int n, char cmdtok[][100]) {
+ int id, scram[255];
+ if (n == 1) {
+ printf("add: you must specify a destination $ID.\n");
+ return;
+ } else if (cmdtok[n-1][0] != '$') {
+ printf("add: invalid destination $ID.\n");
+ return;
+ } else {
+ id = atoi(cmdtok[n-1]+1);
+ if (id <= 0 || id >= scr_count) {
+ printf("add: invalid destination $ID.\n");
+ return;
+ }
+ if (n == 2) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("add: error reading moves.\n");
+ return;
+ }
+ } else {
+ if (read_moves_from_argument(n-2, cmdtok+1, scram) == -1) {
+ printf("add: error reading moves or ID.\n");
+ return;
+ }
+ }
+ }
+
+ append_moves(scram, scrambles[id]);
+
+ printf("$%d:\t", id);
+ print_moves(scrambles[id]);
+ printf("\n");
+}
+
+void invert_cmd(int n, char cmdtok[][100]) {
+ int scram[255];
+ if (n == 1) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("invert: error reading moves.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
+ printf("invert: error reading moves or ID.\n");
+ return;
+ }
+
+ if (uses_niss(scram)) {
+ printf("invert: cannot invert NISS.\n");
+ return;
+ }
+
+ invert(scram, tmp[1]);
+ tmp_count = 2;
+
+ printf("@1:\t");
+ print_moves(tmp[1]);
+ printf("\n");
+}
+
+void unniss_cmd(int n, char cmdtok[][100]) {
+ int scram[255];
+ if (n == 1) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("unniss: error reading moves.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
+ printf("unniss: error reading moves or ID.\n");
+ return;
+ }
+
+ unniss(scram, tmp[1]);
+ tmp_count = 2;
+
+ printf("@1:\t");
+ print_moves(tmp[1]);
+ printf("\n");
+}
+
+void pic_cmd(int n, char cmdtok[][100]) {
+ int scram[255];
+ if (n == 1) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("pic: error reading moves.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
+ printf("pic: error reading moves or ID.\n");
+ return;
+ }
+ print_cube_scram(scram);
+}
+
+void solve_cmd(int n, char cmdtok[][100]) {
+ int m = 1, b = 20, optimal = 0;
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("solve: bad option b.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("solve: bad option n.\n");
+ return;
+ }
+ } else if (!strcmp(cmdtok[i], "o")) {
+ optimal = 1;
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("solve: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("solve: error reading moves.\n");
+ return;
+ }
+ }
+
+ /* Call solver and print results */
+ unniss(scram, scram_unnissed);
+ int sol[m+2][21];
+ int s = solve_scram(scram_unnissed, sol, m, b, optimal);
+ print_results(s, sol);
+}
+
+void replace_cmd(int n, char cmdtok[][100]) {
+ int m = 10; /* max length */
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strncmp(cmdtok[i], "b=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("replace: bad option n.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("replace: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("replace: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+ int l = len(scram_unnissed);
+ int aux1[255], aux2[15][21], aux3[21];
+ for (int i = 0; i < l; i++) {
+ for (int j = 2; j <= m && i + j <= l; j++) {
+ copy_moves(scram_unnissed+i, aux1);
+ aux1[j] = 0;
+ int s = solve_scram(aux1, aux2, 10, j-1, 1);
+ for (int k = 0; k < s; k++) {
+ invert(aux2[k], aux3);
+ /* TODO: the following part should also chek for the case when
+ * the last moves are R L or similar. */
+ if (aux3[0] != aux1[0] && aux3[len(aux3)-1] != aux1[len(aux1)-1]) {
+ printf("Replace [ ");
+ print_moves(aux1);
+ printf("] (moves %d-%d) with: [ ", i+1, i+j);
+ print_moves(aux3);
+ printf("] (-%d+%d)\n", j, len(aux3));
+ }
+ }
+ }
+ }
+}
+
+void eo_cmd(int n, char cmdtok[][100]) {
+
+ /* Default values */
+ int m = 1, b = 20;
+ int niss = 0, hide = 1;
+ int fb = 1, rl = 1, ud = 1;
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strcmp(cmdtok[i], "h")) {
+ hide = 0;
+ } else if (!strcmp(cmdtok[i], "niss")) {
+ niss = 1;
+ } else if (!strncmp(cmdtok[i], "axis=", 5)) {
+ fb = rl = ud = 0;
+ if (strstr(cmdtok[i], "fb") != NULL)
+ fb = 1;
+ if (strstr(cmdtok[i], "rl") != NULL)
+ rl = 1;
+ if (strstr(cmdtok[i], "ud") != NULL)
+ ud = 1;
+ if (fb + rl + ud == 0) {
+ printf("eo: bad axis option.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("eo: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("eo: bad option b.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("eo: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("eo: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver and print results */
+ int eo_list[m+5][21];
+ int neo = eo_scram_spam(scram_unnissed, eo_list, fb, rl, ud, m, b, niss,
+ hide);
+ print_results(neo, eo_list);
+}
+
+void dr_cmd(int n, char cmdtok[][100]) {
+
+ /* Default values */
+ int m = 1, b = 20;
+ int niss = 0, hide = 1;
+ int from = 0; /* 0: direct dr; {1,2,3}: from {eofb,eorl,eoud} */
+ int fb = 1, rl = 1, ud = 1;
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strcmp(cmdtok[i], "h")) {
+ hide = 0;
+ } else if (!strcmp(cmdtok[i], "niss")) {
+ niss = 1;
+ } else if (!strncmp(cmdtok[i], "axis=", 5)) {
+ fb = rl = ud = 0;
+ if (strstr(cmdtok[i], "fb") != NULL)
+ fb = 1;
+ if (strstr(cmdtok[i], "rl") != NULL)
+ rl = 1;
+ if (strstr(cmdtok[i], "ud") != NULL)
+ ud = 1;
+ if (fb + rl + ud == 0) {
+ printf("dr: bad axis option.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("dr: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("dr: bad option b.\n");
+ return;
+ }
+ } else if (!strcmp(cmdtok[i], "from")) {
+ i++;
+ char x[3][3] = {"fb", "rl", "ud"};
+ for (int j = 0; j < 3; j++)
+ if (!strcmp(cmdtok[i], x[j]))
+ from = j+1;
+ if (!from) {
+ printf("dr: bad from option.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("dr: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("dr: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver */
+ int dr_list[m+5][21], ndr;
+ if (from) {
+ ndr = drfrom_scram_spam(scram_unnissed, dr_list, from, fb, rl, ud,
+ m, b, niss, hide);
+ if (ndr == -1) {
+ printf("dr: from given, but EO not found (possibly other error).\n");
+ return;
+ }
+ } else {
+ if (niss)
+ printf("Warning: not using NISS for direct DR.\n");
+ ndr = dr_scram_spam(scram_unnissed, dr_list, fb, rl, ud, m, b, hide);
+ }
+ print_results(ndr, dr_list);
+}
+
+void htr_cmd(int n, char cmdtok[][100]) {
+
+ /* Default values */
+ int m = 1, b = 20;
+ int niss = 0, hide = 1;
+ int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strcmp(cmdtok[i], "h")) {
+ hide = 0;
+ } else if (!strcmp(cmdtok[i], "niss")) {
+ niss = 1;
+ } else if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("htr: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("htr: bad option b.\n");
+ return;
+ }
+ } else if (!strcmp(cmdtok[i], "from")) {
+ i++;
+ char x[3][3] = {"ud", "fb", "rl"};
+ for (int j = 0; j < 3; j++)
+ if (!strcmp(cmdtok[i], x[j]))
+ from = j+1;
+ if (!from) {
+ printf("htr: bad from option.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("htr: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("htr: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver */
+ int htr_list[m+5][21], nhtr;
+ nhtr = htr_scram_spam(scram_unnissed, htr_list, from, m, b, niss, hide);
+ print_results(nhtr, htr_list);
+}
+
+void drfinish_cmd(int n, char cmdtok[][100]) {
+ /* Default values */
+ int m = 1, b = 20;
+ int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("drfinish: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("drfinish: bad option b.\n");
+ return;
+ }
+ } else if (!strcmp(cmdtok[i], "from")) {
+ i++;
+ char x[3][3] = {"ud", "fb", "rl"};
+ for (int j = 0; j < 3; j++)
+ if (!strcmp(cmdtok[i], x[j]))
+ from = j+1;
+ if (!from) {
+ printf("drfinish: bad from option.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("drfinish: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("drfinish: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver */
+ int c_list[m+5][21], nc;
+ nc = dr_finish_scram_spam(scram_unnissed, c_list, from, m, b);
+ print_results(nc, c_list);
+}
+
+void htrfinish_cmd(int n, char cmdtok[][100]) {
+ /* Default values */
+ int m = 1, b = 20;
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("htrfinish: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("htrfinish: bad option b.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("htrfinish: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("htrfinish: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver */
+ int c_list[m+5][21], nc;
+ nc = htr_finish_scram_spam(scram_unnissed, c_list, m, b);
+ print_results(nc, c_list);
+}
+
+void drcorners_cmd(int n, char cmdtok[][100]) {
+ /* Default values */
+ int m = 1, b = 20, ignore=0;
+ int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("drcorners: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("drcorners: bad option b.\n");
+ return;
+ }
+ } else if (!strcmp(cmdtok[i], "i")) {
+ ignore = 1;
+ } else if (!strcmp(cmdtok[i], "from")) {
+ i++;
+ char x[3][3] = {"ud", "fb", "rl"};
+ for (int j = 0; j < 3; j++)
+ if (!strcmp(cmdtok[i], x[j]))
+ from = j+1;
+ if (!from) {
+ printf("drcorners: bad from option.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("drcorners: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("drcorners: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver */
+ int c_list[m+5][21], nc;
+ nc = dr_corners_scram_spam(scram_unnissed, c_list, from, m, b, ignore);
+ print_results(nc, c_list);
+}
+
+
+void exit_quit_cmd(int n, char cmdtok[][100]) {
+ if (n == 1)
+ exit(0);
+ else
+ printf("%s: wrong synstax.\n", cmdtok[0]);
+}
+
+void (*cmd_list[])(int n, char cmdtok[][100]) = {
+ help_cmd, save_cmd, change_cmd, print_cmd,
+ add_cmd, invert_cmd, unniss_cmd, pic_cmd,
+ solve_cmd, replace_cmd,
+ eo_cmd, dr_cmd, htr_cmd,
+ drfinish_cmd, htrfinish_cmd, drcorners_cmd,
+ exit_quit_cmd, exit_quit_cmd, NULL
+};
+
+void execcmd(int n, char cmdtok[][100]) {
+ int i = 0;
+ while (strcmp(commands[i][0], cmdtok[0]) && strcmp(commands[i][0], ""))
+ i++;
+ if (strcmp(commands[i][0], ""))
+ (*cmd_list[i])(n, cmdtok);
+ else
+ printf("%s: not a command.\n", cmdtok[0]);
+}
+
+int main() {
+ init_transition_table();
+ init_possible_next();
+
+ printf("Type help for a list of commands.\n");
+
+ char cmd[1000] = "";
+ while (1) {
+ printf("nissy-# ");
+ if (fgets(cmd, 1000, stdin) == NULL)
+ break;
+ char cmdtok[100][100];
+ int n = parsecmd(cmd, cmdtok);
+ if (n == 0)
+ continue;
+ execcmd(n, cmdtok);
+ }
+
+ return 0;
+}
diff --git a/src/moves.c b/src/moves.c
@@ -0,0 +1,526 @@
+/* This is a simple program to solve the Rubik's Cube.
+ * No idea how many features I am going to implement.
+ * Open source license and whatnot.
+ * I am trying to follow the C99 standard. */
+
+/* This file contains the definitions of the basic moves of the cube.
+ * There is no object or type representing the cube.
+ * Data about the cube can be represented by arrays (describing the position
+ * of pieces of certain types), integers (representing for example a bitmask
+ * for the orientation of pieces of certain type, or the permutation index of
+ * an array representing the permutation of pieces).
+ * Each of the moves functions operates on one such piece of data.
+ *
+ * For example, a way of representing the cube can be:
+ * - An integer eo, which is a bitmask for the orientation of the edges.
+ * - An integer co, same for corners.
+ * - An array ep[12], where a[i]=j means that the edge j is in place i.
+ * - An integer cp representing the permutation index of a permutation array
+ * which is the analogue of that described for edges.
+ *
+ * Different representations will be used for different use-cases. */
+
+#include "coordinates.h"
+#include "moves.h"
+
+/* possible_next[i][j] is a bitmask representing the possible
+ * next moves we can apply. For example, if the last moves a 0 R then it does
+ * not make sense to apply R, R2 or R'. If they are U D2 it does not make
+ * sense to apply any U* or D*. */
+int possible_next[19][19];
+
+int parallel(int m1, int m2) {
+ if (m1 == 0 || m2 == 0) return 0;
+ return ((m1-1)/6 == (m2-1)/6);
+}
+
+int compute_possible_next(int last1, int last2) {
+ if (last1 == 0) return move_mask_all;
+
+ /* Removes the 2 or ' (e.g. turns U2 to U, R' to R). */
+ last2 = (last2 == 0) ? last2 : 3*((last2-1)/3) + 1;
+ last1 = 3*((last1-1)/3) + 1;
+
+ int mask = move_mask_all ^ (7 << last1);
+
+ if (parallel(last1, last2))
+ mask ^= 7 << last2;
+ else if (last1 % 6 == 4) /*Always U before D, R before L, F before B*/
+ mask ^= 7 << (last1-3);
+
+ return mask;
+}
+
+void init_possible_next() {
+ for (int i = 0; i < 19; i++)
+ for (int j = 0; j < 19; j++)
+ possible_next[i][j] = compute_possible_next(i, j);
+}
+
+/* Piece cycles depending on the move. For example edge_cycle[U2][UF]
+ * gives the piece in position UF after applying U2 to a solved cube */
+
+int edge_cycle[19][12] = {
+ {UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR}, /* - */
+ {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR}, /* U */
+ {UB, UR, UF, UL, DF, DL, DB, DR, FR, FL, BL, BR}, /* U2 */
+ {UL, UB, UR, UF, DF, DL, DB, DR, FR, FL, BL, BR}, /* U' */
+ {UF, UL, UB, UR, DL, DB, DR, DF, FR, FL, BL, BR}, /* D */
+ {UF, UL, UB, UR, DB, DR, DF, DL, FR, FL, BL, BR}, /* D2 */
+ {UF, UL, UB, UR, DR, DF, DL, DB, FR, FL, BL, BR}, /* D' */
+ {UF, UL, UB, FR, DF, DL, DB, BR, DR, FL, BL, UR}, /* R */
+ {UF, UL, UB, DR, DF, DL, DB, UR, BR, FL, BL, FR}, /* R2 */
+ {UF, UL, UB, BR, DF, DL, DB, FR, UR, FL, BL, DR}, /* R' */
+ {UF, BL, UB, UR, DF, FL, DB, DR, FR, UL, DL, BR}, /* L */
+ {UF, DL, UB, UR, DF, UL, DB, DR, FR, BL, FL, BR}, /* L2 */
+ {UF, FL, UB, UR, DF, BL, DB, DR, FR, DL, UL, BR}, /* L' */
+ {FL, UL, UB, UR, FR, DL, DB, DR, UF, DF, BL, BR}, /* F */
+ {DF, UL, UB, UR, UF, DL, DB, DR, FL, FR, BL, BR}, /* F2 */
+ {FR, UL, UB, UR, FL, DL, DB, DR, DF, UF, BL, BR}, /* F' */
+ {UF, UL, BR, UR, DF, DL, BL, DR, FR, FL, UB, DB}, /* B */
+ {UF, UL, DB, UR, DF, DL, UB, DR, FR, FL, BR, BL}, /* B2 */
+ {UF, UL, BL, UR, DF, DL, BR, DR, FR, FL, DB, UB} /* B' */
+};
+
+int corner_cycle[19][8] = {
+ {UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR}, /* - */
+ {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR}, /* U */
+ {UBL, UBR, UFR, UFL, DFR, DFL, DBL, DBR}, /* U2 */
+ {UFL, UBL, UBR, UFR, DFR, DFL, DBL, DBR}, /* U' */
+ {UFR, UFL, UBL, UBR, DFL, DBL, DBR, DFR}, /* D */
+ {UFR, UFL, UBL, UBR, DBL, DBR, DFR, DFL}, /* D2 */
+ {UFR, UFL, UBL, UBR, DBR, DFR, DFL, DBL}, /* D' */
+ {DFR, UFL, UBL, UFR, DBR, DFL, DBL, UBR}, /* R */
+ {DBR, UFL, UBL, DFR, UBR, DFL, DBL, UFR}, /* R2 */
+ {UBR, UFL, UBL, DBR, UFR, DFL, DBL, DFR}, /* R' */
+ {UFR, UBL, DBL, UBR, DFR, UFL, DFL, DBR}, /* L */
+ {UFR, DBL, DFL, UBR, DFR, UBL, UFL, DBR}, /* L2 */
+ {UFR, DFL, UFL, UBR, DFR, DBL, UBL, DBR}, /* L' */
+ {UFL, DFL, UBL, UBR, UFR, DFR, DBL, DBR}, /* F */
+ {DFL, DFR, UBL, UBR, UFL, UFR, DBL, DBR}, /* F2 */
+ {DFR, UFR, UBL, UBR, DFL, UFL, DBL, DBR}, /* F' */
+ {UFR, UFL, UBR, DBR, DFR, DFL, UBL, DBL}, /* B */
+ {UFR, UFL, DBR, DBL, DFR, DFL, UBR, UBL}, /* B2 */
+ {UFR, UFL, DBL, UBL, DFR, DFL, DBR, UBR}, /* U' */
+};
+
+/* Transition tables */
+
+int eofb_transition_table[pow2to11][19];
+int eorl_transition_table[pow2to11][19];
+int eoud_transition_table[pow2to11][19];
+int coud_transition_table[pow3to7][19];
+int cofb_transition_table[pow3to7][19];
+int corl_transition_table[pow3to7][19];
+int epud_transition_table[factorial8][19];
+int eprl_transition_table[factorial8][19];
+int epfb_transition_table[factorial8][19];
+int epose_transition_table[binom12on4][19];
+int eposs_transition_table[binom12on4][19];
+int eposm_transition_table[binom12on4][19];
+int epe_transition_table[factorial4][19];
+int eps_transition_table[factorial4][19];
+int epm_transition_table[factorial4][19];
+int emslices_transition_table[binom12on4*binom8on4][19];
+int cp_transition_table[factorial8][19];
+
+/***/
+/* Functions for permuting pieces (given in array format) */
+/***/
+
+void apply_move_ep_array(int move, int ep[12]) {
+ int aux[12];
+ for (int i = 0; i < 12; i++)
+ aux[i] = ep[i];
+ for (int i = 0; i < 12; i++)
+ ep[i] = aux[edge_cycle[move][i]];
+}
+
+void apply_move_cp_array(int move, int cp[8]) {
+ int aux[8];
+ for (int i = 0; i < 8; i++)
+ aux[i] = cp[i];
+ for (int i = 0; i < 8; i++)
+ cp[i] = aux[corner_cycle[move][i]];
+}
+
+/***/
+/* Functions for permuting pieces (given in integer format) */
+/***/
+
+int apply_move_ep_int(int move, int ep) {
+ int a[12];
+ ep_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return ep_array_to_int(a);
+}
+
+int apply_move_epud_int(int move, int ep) {
+ int a[12];
+ epud_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return epud_array_to_int(a);
+}
+
+int apply_move_eprl_int(int move, int ep) {
+ int a[12];
+ eprl_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return eprl_array_to_int(a);
+}
+
+int apply_move_epfb_int(int move, int ep) {
+ int a[12];
+ epfb_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return epfb_array_to_int(a);
+}
+
+int apply_move_epose_int(int move, int ep) {
+ int a[12];
+ epose_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return epose_array_to_int(a);
+}
+
+int apply_move_eposs_int(int move, int ep) {
+ int a[12];
+ eposs_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return eposs_array_to_int(a);
+}
+
+int apply_move_eposm_int(int move, int ep) {
+ int a[12];
+ eposm_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return eposm_array_to_int(a);
+}
+
+int apply_move_epe_int(int move, int ep) {
+ int a[12];
+ epe_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return epe_array_to_int(a);
+}
+
+int apply_move_eps_int(int move, int ep) {
+ int a[12];
+ eps_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return eps_array_to_int(a);
+}
+
+int apply_move_epm_int(int move, int ep) {
+ int a[12];
+ epm_int_to_array(ep, a);
+ apply_move_ep_array(move, a);
+ return epm_array_to_int(a);
+}
+
+int apply_move_emslices_int(int move, int e) {
+ int a[12];
+ emslices_int_to_array(e, a);
+ apply_move_ep_array(move, a);
+ return emslices_array_to_int(a);
+}
+
+int apply_move_cp_int(int move, int cp) {
+ int a[8];
+ cp_int_to_array(cp, a);
+ apply_move_cp_array(move, a);
+ return cp_array_to_int(a);
+}
+
+int apply_move_eofb_int(int move, int eo) {
+ int a[12];
+ eo_11bits_to_array(eo, a);
+ apply_move_ep_array(move, a);
+ /* Change edge orientation */
+ if (move == F || move == F3) {
+ a[UF] = 1 - a[UF];
+ a[DF] = 1 - a[DF];
+ a[FR] = 1 - a[FR];
+ a[FL] = 1 - a[FL];
+ }
+ if (move == B || move == B3) {
+ a[UB] = 1 - a[UB];
+ a[DB] = 1 - a[DB];
+ a[BL] = 1 - a[BL];
+ a[BR] = 1 - a[BR];
+ }
+ return eo_array_to_11bits(a);
+}
+
+int apply_move_eorl_int(int move, int eo) {
+ int a[12];
+ eo_11bits_to_array(eo, a);
+ apply_move_ep_array(move, a);
+ /* Change edge orientation */
+ if (move == R || move == R3) {
+ a[UR] = 1 - a[UR];
+ a[DR] = 1 - a[DR];
+ a[FR] = 1 - a[FR];
+ a[BR] = 1 - a[BR];
+ }
+ if (move == L || move == L3) {
+ a[UL] = 1 - a[UL];
+ a[DL] = 1 - a[DL];
+ a[FL] = 1 - a[FL];
+ a[BL] = 1 - a[BL];
+ }
+ return eo_array_to_11bits(a);
+}
+
+int apply_move_eoud_int(int move, int eo) {
+ int a[12];
+ eo_11bits_to_array(eo, a);
+ apply_move_ep_array(move, a);
+ /* Change edge orientation */
+ if (move == U || move == U3) {
+ a[UF] = 1 - a[UF];
+ a[UL] = 1 - a[UL];
+ a[UB] = 1 - a[UB];
+ a[UR] = 1 - a[UR];
+ }
+ if (move == D || move == D3) {
+ a[DF] = 1 - a[DF];
+ a[DL] = 1 - a[DL];
+ a[DB] = 1 - a[DB];
+ a[DR] = 1 - a[DR];
+ }
+ return eo_array_to_11bits(a);
+}
+
+int apply_move_coud_int(int move, int co) {
+ int a[8];
+ co_7trits_to_array(co, a);
+ apply_move_cp_array(move, a);
+ /* Change corner orientation */
+ if (move == R || move == R3) {
+ a[UFR] = (a[UFR] + 2) % 3;
+ a[UBR] = (a[UBR] + 1) % 3;
+ a[DBR] = (a[DBR] + 2) % 3;
+ a[DFR] = (a[DFR] + 1) % 3;
+ }
+ if (move == L || move == L3) {
+ a[UBL] = (a[UBL] + 2) % 3;
+ a[UFL] = (a[UFL] + 1) % 3;
+ a[DFL] = (a[DFL] + 2) % 3;
+ a[DBL] = (a[DBL] + 1) % 3;
+ }
+ if (move == F || move == F3) {
+ a[UFL] = (a[UFL] + 2) % 3;
+ a[UFR] = (a[UFR] + 1) % 3;
+ a[DFR] = (a[DFR] + 2) % 3;
+ a[DFL] = (a[DFL] + 1) % 3;
+ }
+ if (move == B || move == B3) {
+ a[UBR] = (a[UBR] + 2) % 3;
+ a[UBL] = (a[UBL] + 1) % 3;
+ a[DBL] = (a[DBL] + 2) % 3;
+ a[DBR] = (a[DBR] + 1) % 3;
+ }
+ return co_array_to_7trits(a);
+}
+
+int apply_move_cofb_int(int move, int co) {
+ int a[8];
+ co_7trits_to_array(co, a);
+ apply_move_cp_array(move, a);
+ /* Change corner orientation */
+ if (move == R || move == R3) {
+ a[UFR] = (a[UFR] + 1) % 3;
+ a[UBR] = (a[UBR] + 2) % 3;
+ a[DBR] = (a[DBR] + 1) % 3;
+ a[DFR] = (a[DFR] + 2) % 3;
+ }
+ if (move == L || move == L3) {
+ a[UBL] = (a[UBL] + 1) % 3;
+ a[UFL] = (a[UFL] + 2) % 3;
+ a[DFL] = (a[DFL] + 1) % 3;
+ a[DBL] = (a[DBL] + 2) % 3;
+ }
+ if (move == U || move == U3) {
+ a[UFL] = (a[UFL] + 1) % 3;
+ a[UFR] = (a[UFR] + 2) % 3;
+ a[UBL] = (a[UBL] + 2) % 3;
+ a[UBR] = (a[UBR] + 1) % 3;
+ }
+ if (move == D || move == D3) {
+ a[DFL] = (a[DFL] + 2) % 3;
+ a[DFR] = (a[DFR] + 1) % 3;
+ a[DBL] = (a[DBL] + 1) % 3;
+ a[DBR] = (a[DBR] + 2) % 3;
+ }
+ return co_array_to_7trits(a);
+}
+
+int apply_move_corl_int(int move, int co) {
+ int a[8];
+ co_7trits_to_array(co, a);
+ apply_move_cp_array(move, a);
+ /* Change corner orientation */
+ if (move == F || move == F3) {
+ a[UFR] = (a[UFR] + 2) % 3;
+ a[UFL] = (a[UFL] + 1) % 3;
+ a[DFL] = (a[DFL] + 2) % 3;
+ a[DFR] = (a[DFR] + 1) % 3;
+ }
+ if (move == B || move == B3) {
+ a[UBL] = (a[UBL] + 2) % 3;
+ a[UBR] = (a[UBR] + 1) % 3;
+ a[DBR] = (a[DBR] + 2) % 3;
+ a[DBL] = (a[DBL] + 1) % 3;
+ }
+ if (move == U || move == U3) {
+ a[UFL] = (a[UFL] + 2) % 3;
+ a[UFR] = (a[UFR] + 1) % 3;
+ a[UBL] = (a[UBL] + 1) % 3;
+ a[UBR] = (a[UBR] + 2) % 3;
+ }
+ if (move == D || move == D3) {
+ a[DFL] = (a[DFL] + 1) % 3;
+ a[DFR] = (a[DFR] + 2) % 3;
+ a[DBL] = (a[DBL] + 2) % 3;
+ a[DBR] = (a[DBR] + 1) % 3;
+ }
+ return co_array_to_7trits(a);
+}
+
+
+
+/* Initialize transition tables */
+
+void init_epud_transition_table() {
+ for (int i = 0; i < factorial8; i++)
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drud & (1 << j))
+ epud_transition_table[i][j] = apply_move_epud_int(j, i);
+}
+
+void init_eprl_transition_table() {
+ for (int i = 0; i < factorial8; i++)
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drrl & (1 << j))
+ eprl_transition_table[i][j] = apply_move_eprl_int(j, i);
+}
+
+void init_epfb_transition_table() {
+ for (int i = 0; i < factorial8; i++)
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drfb & (1 << j))
+ epfb_transition_table[i][j] = apply_move_epfb_int(j, i);
+}
+
+void init_epose_transition_table() {
+ for (int i = 0; i < binom12on4; i++)
+ for (int j = 0; j < 19; j++)
+ epose_transition_table[i][j] = apply_move_epose_int(j, i);
+}
+
+void init_eposs_transition_table() {
+ for (int i = 0; i < binom12on4; i++)
+ for (int j = 0; j < 19; j++)
+ eposs_transition_table[i][j] = apply_move_eposs_int(j, i);
+}
+
+void init_eposm_transition_table() {
+ for (int i = 0; i < binom12on4; i++)
+ for (int j = 0; j < 19; j++)
+ eposm_transition_table[i][j] = apply_move_eposm_int(j, i);
+}
+
+void init_epe_transition_table() {
+ for (int i = 0; i < factorial4; i++) {
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drud & (1 << j))
+ epe_transition_table[i][j] = apply_move_epe_int(j, i);
+ }
+}
+
+void init_eps_transition_table() {
+ for (int i = 0; i < factorial4; i++) {
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drfb & (1 << j))
+ eps_transition_table[i][j] = apply_move_eps_int(j, i);
+ }
+}
+
+void init_epm_transition_table() {
+ for (int i = 0; i < factorial4; i++) {
+ for (int j = 0; j < 19; j++)
+ if (move_mask_drrl & (1 << j))
+ epm_transition_table[i][j] = apply_move_epm_int(j, i);
+ }
+}
+
+void init_emslices_transition_table() {
+ for (int i = 0; i < binom12on4*binom8on4; i++) {
+ for (int j = 0; j < 19; j++)
+ emslices_transition_table[i][j] = apply_move_emslices_int(j, i);
+ }
+}
+
+void init_cp_transition_table() {
+ for (int i = 0; i < factorial8; i++)
+ for (int j = 0; j < 19; j++)
+ cp_transition_table[i][j] = apply_move_cp_int(j, i);
+}
+
+void init_eofb_transition_table() {
+ for (int i = 0; i < pow2to11; i++)
+ for (int j = 0; j < 19; j++)
+ eofb_transition_table[i][j] = apply_move_eofb_int(j, i);
+}
+
+void init_eorl_transition_table() {
+ for (int i = 0; i < pow2to11; i++)
+ for (int j = 0; j < 19; j++)
+ eorl_transition_table[i][j] = apply_move_eorl_int(j, i);
+}
+
+void init_eoud_transition_table() {
+ for (int i = 0; i < pow2to11; i++)
+ for (int j = 0; j < 19; j++)
+ eoud_transition_table[i][j] = apply_move_eoud_int(j, i);
+}
+
+void init_coud_transition_table() {
+ for (int i = 0; i < pow3to7; i++)
+ for (int j = 0; j < 19; j++ )
+ coud_transition_table[i][j] = apply_move_coud_int(j, i);
+}
+
+void init_cofb_transition_table() {
+ for (int i = 0; i < pow3to7; i++)
+ for (int j = 0; j < 19; j++ )
+ cofb_transition_table[i][j] = apply_move_cofb_int(j, i);
+}
+
+void init_corl_transition_table() {
+ for (int i = 0; i < pow3to7; i++)
+ for (int j = 0; j < 19; j++ )
+ corl_transition_table[i][j] = apply_move_corl_int(j, i);
+}
+
+void init_transition_table() {
+ init_epud_transition_table();
+ init_eprl_transition_table();
+ init_epfb_transition_table();
+ init_epose_transition_table();
+ init_eposs_transition_table();
+ init_eposm_transition_table();
+ init_epe_transition_table();
+ init_eps_transition_table();
+ init_epm_transition_table();
+ init_emslices_transition_table();
+ init_cp_transition_table();
+ init_eofb_transition_table();
+ init_eorl_transition_table();
+ init_eoud_transition_table();
+ init_coud_transition_table();
+ init_cofb_transition_table();
+ init_corl_transition_table();
+}
+
diff --git a/src/moves.h b/src/moves.h
@@ -0,0 +1,83 @@
+#include "utils.h"
+
+/* Bitmask that define certain movesets. */
+#define move_mask_all 524287 /* Reverse 1111111111111111111 */
+#define move_mask_eofb 155647 /* Reverse 1111111111111010010 */
+#define move_mask_eorl 518527 /* Reverse 1111111010101111111 */
+#define move_mask_eoud 524197 /* Reverse 1010010111111111111 */
+#define move_mask_drud 149887 /* Reverse 1111111010010010010 */
+#define move_mask_drfb 518437 /* Reverse 1010010010010111111 */
+#define move_mask_drrl 155557 /* Reverse 1010010111111010010 */
+#define move_mask_htr 149797 /* Reverse 1010010010010010010 */
+
+extern int possible_next[19][19];
+
+int parallel(int m1, int m2);
+void init_possible_next();
+
+/* Transition tables */
+extern int eofb_transition_table[pow2to11][19];
+extern int eorl_transition_table[pow2to11][19];
+extern int eoud_transition_table[pow2to11][19];
+extern int coud_transition_table[pow3to7][19];
+extern int cofb_transition_table[pow3to7][19];
+extern int corl_transition_table[pow3to7][19];
+extern int epud_transition_table[factorial8][19];
+extern int epfb_transition_table[factorial8][19];
+extern int eprl_transition_table[factorial8][19];
+extern int epose_transition_table[binom12on4][19];
+extern int eposs_transition_table[binom12on4][19];
+extern int eposm_transition_table[binom12on4][19];
+extern int epe_transition_table[factorial4][19];
+extern int eps_transition_table[factorial4][19];
+extern int epm_transition_table[factorial4][19];
+extern int emslices_transition_table[binom12on4*binom8on4][19];
+extern int cp_transition_table[factorial8][19];
+
+
+/* Functions for permuting pieces (given in array format) */
+
+void apply_move_ep_array(int move, int ep[12]);
+void apply_move_cp_array(int move, int cp[8]);
+
+/* Functions for permuting pieces (given in integer format) */
+
+int apply_move_ep_int(int move, int ep);
+int apply_move_epud_int(int move, int ep);
+int apply_move_epfb_int(int move, int ep);
+int apply_move_eprl_int(int move, int ep);
+int apply_move_epose_int(int move, int ep);
+int apply_move_eposs_int(int move, int ep);
+int apply_move_eposm_int(int move, int ep);
+int apply_move_epe_int(int move, int ep);
+int apply_move_eps_int(int move, int ep);
+int apply_move_epm_int(int move, int ep);
+int apply_move_cp_int(int move, int cp);
+int apply_move_eofb_int(int move, int eo);
+int apply_move_eorl_int(int move, int eo);
+int apply_move_eoud_int(int move, int eo);
+int apply_move_coud_int(int move, int co);
+int apply_move_cofb_int(int move, int co);
+int apply_move_corl_int(int move, int co);
+
+/* Initialize transition tables */
+
+void init_epud_transition_table();
+void init_epfb_transition_table();
+void init_eprl_transition_table();
+void init_epose_transition_table();
+void init_eposs_transition_table();
+void init_eposm_transition_table();
+void init_epe_transition_table();
+void init_eps_transition_table();
+void init_epm_transition_table();
+void init_cp_transition_table();
+void init_eofb_transition_table();
+void init_eorl_transition_table();
+void init_eoud_transition_table();
+void init_coud_transition_table();
+void init_cofb_transition_table();
+void init_corl_transition_table();
+
+void init_transition_table();
+
diff --git a/src/pruning_tables.c b/src/pruning_tables.c
@@ -0,0 +1,483 @@
+#include <stdint.h>
+#include "pruning_tables.h"
+#include "moves.h"
+
+/* The data contained in e.g. eofb pruning table is the same that is contained
+ * in eolr pruning table and so on. For small tables the memory wasted is not
+ * too much and it makes things easier. I may change this when I implement
+ * bigger tables. */
+int eofb_pruning_table[pow2to11];
+int eorl_pruning_table[pow2to11];
+int eoud_pruning_table[pow2to11];
+int coud_pruning_table[pow3to7];
+int cofb_pruning_table[pow3to7];
+int corl_pruning_table[pow3to7];
+int cp_pruning_table[factorial8];
+
+int eorl_from_eofb_pruning_table[pow2to11];
+int eoud_from_eofb_pruning_table[pow2to11];
+int eoud_from_eorl_pruning_table[pow2to11];
+int eofb_from_eorl_pruning_table[pow2to11];
+int eofb_from_eoud_pruning_table[pow2to11];
+int eorl_from_eoud_pruning_table[pow2to11];
+
+int coud_from_eofb_pruning_table[pow3to7];
+int coud_from_eorl_pruning_table[pow3to7];
+int cofb_from_eorl_pruning_table[pow3to7];
+int cofb_from_eoud_pruning_table[pow3to7];
+int corl_from_eoud_pruning_table[pow3to7];
+int corl_from_eofb_pruning_table[pow3to7];
+
+int cp_drud_pruning_table[factorial8];
+int cp_drfb_pruning_table[factorial8];
+int cp_drrl_pruning_table[factorial8];
+int epud_pruning_table[factorial8];
+int epfb_pruning_table[factorial8];
+int eprl_pruning_table[factorial8];
+
+int cp_htr_pruning_table[factorial8];
+
+int cpud_to_htr_pruning_table[factorial8];
+int cpfb_to_htr_pruning_table[factorial8];
+int cprl_to_htr_pruning_table[factorial8];
+
+
+/* About 1Mb each */
+int8_t eofb_epose_pruning_table[pow2to11][binom12on4];
+int8_t eorl_eposs_pruning_table[pow2to11][binom12on4];
+int8_t eoud_eposm_pruning_table[pow2to11][binom12on4];
+
+/* About 4.5Mb each */
+int8_t eofb_coud_pruning_table[pow2to11][pow3to7];
+int8_t eofb_corl_pruning_table[pow2to11][pow3to7];
+int8_t eorl_coud_pruning_table[pow2to11][pow3to7];
+int8_t eorl_cofb_pruning_table[pow2to11][pow3to7];
+int8_t eoud_cofb_pruning_table[pow2to11][pow3to7];
+int8_t eoud_corl_pruning_table[pow2to11][pow3to7];
+
+/* About 1Mb each */
+int8_t coud_epose_from_eofb_pruning_table[pow3to7][binom12on4];
+int8_t cofb_eposs_from_eorl_pruning_table[pow3to7][binom12on4];
+int8_t corl_eposm_from_eoud_pruning_table[pow3to7][binom12on4];
+int8_t coud_epose_from_eorl_pruning_table[pow3to7][binom12on4];
+int8_t cofb_eposs_from_eoud_pruning_table[pow3to7][binom12on4];
+int8_t corl_eposm_from_eofb_pruning_table[pow3to7][binom12on4];
+
+
+/* Firs one is 88Mb, second one is 71Mb */
+int8_t cp_co_pruning_table[factorial8][pow3to7];
+int8_t triple_eo_pruning_table[pow2to11][binom12on4*binom8on4];
+
+int initialized_small = 0;
+int initialized_directdr = 0;
+int initialized_drfromeo = 0;
+int initialized_huge = 0;
+
+void init_single_table(int n, int t_tab[][19], int p_tab[n], int mask) {
+ int state[n];
+ state[0] = 0; /* 0 should always be the solved state. */
+ p_tab[0] = 0;
+ int state_count = 1;
+ for (int i = 0; i < state_count; i++) {
+ for (int m = 1; m < 19; m++) {
+ int next = t_tab[state[i]][m];
+ if (mask & (1<<m) && !p_tab[next] && next) {
+ p_tab[next] = p_tab[state[i]] + 1;
+ state[state_count++] = next;
+ }
+ }
+ }
+}
+
+/* Similar to single table, but specific to "cp to htr".
+ * The idea is that we are considering the distance not necessarily to the
+ * solved state, but to any state that is either solved or reachable from
+ * cp_pruning_table. */
+void init_cptohtr_table(int n, int t_tab[][19], int p_tab[n], int mask) {
+
+ for (int i = 0; i < n; i++)
+ p_tab[i] = 21;
+
+ /* List of htr states */
+ int good[n]; good[0] = 0;
+ int good_count = 1;
+ for (int i = 0; i < n; i++)
+ if (cp_htr_pruning_table[i])
+ good[good_count++] = i;
+
+ /* Init pruning table starting from each possible state */
+ int state[n];
+ for (int j = 0; j < good_count; j++) {
+ state[0] = good[j];
+ p_tab[state[0]] = 0;
+ int state_count = 1;
+ for (int i = 0; i < state_count; i++) {
+ for (int m = 1; m < 19; m++) {
+ int next = t_tab[state[i]][m];
+ if (mask & (1<<m) && (p_tab[next] > p_tab[state[i]] + 1) && next) {
+ p_tab[next] = p_tab[state[i]] + 1;
+ state[state_count++] = next;
+ }
+ }
+ }
+ }
+}
+
+void init_double_table(int n1, int n2,
+ int t_table1[n1][19], int t_table2[n2][19],
+ int8_t p_table[n1][n2], int mask) {
+ static int state1[factorial8*pow3to7], state2[factorial8*pow3to7];
+ state1[0] = 0;
+ state2[0] = 0;
+ p_table[0][0] = 0;
+ int state_count = 1;
+ for (int i = 0; i < state_count; i++) {
+ for (int m = 1; m < 19; m++) {
+ int next1 = t_table1[state1[i]][m];
+ int next2 = t_table2[state2[i]][m];
+ if (mask & (1<<m) && !p_table[next1][next2] && (next1 || next2)) {
+ p_table[next1][next2] = p_table[state1[i]][state2[i]] + 1;
+ state1[state_count] = next1;
+ state2[state_count] = next2;
+ state_count++;
+ }
+ }
+ }
+}
+
+void init_eofb_pruning_table() {
+ init_single_table(pow2to11, eofb_transition_table, eofb_pruning_table,
+ move_mask_all);
+}
+
+void init_eorl_pruning_table() {
+ init_single_table(pow2to11, eorl_transition_table, eorl_pruning_table,
+ move_mask_all);
+}
+
+void init_eoud_pruning_table() {
+ init_single_table(pow2to11, eoud_transition_table, eoud_pruning_table,
+ move_mask_all);
+}
+
+void init_coud_pruning_table() {
+ init_single_table(pow3to7, coud_transition_table, coud_pruning_table,
+ move_mask_all);
+}
+
+void init_cofb_pruning_table() {
+ init_single_table(pow3to7, cofb_transition_table, cofb_pruning_table,
+ move_mask_all);
+}
+
+void init_corl_pruning_table() {
+ init_single_table(pow3to7, corl_transition_table, corl_pruning_table,
+ move_mask_all);
+}
+
+void init_cp_pruning_table() {
+ init_single_table(factorial8, cp_transition_table, cp_pruning_table,
+ move_mask_all);
+}
+
+/* The following tables use the eo moveset */
+void init_eorl_from_eofb_pruning_table() {
+ init_single_table(pow2to11, eorl_transition_table,
+ eorl_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_eoud_from_eofb_pruning_table() {
+ init_single_table(pow2to11, eoud_transition_table,
+ eoud_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_eoud_from_eorl_pruning_table() {
+ init_single_table(pow2to11, eoud_transition_table,
+ eoud_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_eofb_from_eorl_pruning_table() {
+ init_single_table(pow2to11, eofb_transition_table,
+ eofb_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_eofb_from_eoud_pruning_table() {
+ init_single_table(pow2to11, eofb_transition_table,
+ eofb_from_eoud_pruning_table, move_mask_eoud);
+}
+
+void init_eorl_from_eoud_pruning_table() {
+ init_single_table(pow2to11, eorl_transition_table,
+ eorl_from_eoud_pruning_table, move_mask_eoud);
+}
+
+void init_coud_from_eofb_pruning_table() {
+ init_single_table(pow3to7, coud_transition_table,
+ coud_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_corl_from_eofb_pruning_table() {
+ init_single_table(pow3to7, corl_transition_table,
+ corl_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_coud_from_eorl_pruning_table() {
+ init_single_table(pow3to7, coud_transition_table,
+ coud_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_cofb_from_eorl_pruning_table() {
+ init_single_table(pow3to7, cofb_transition_table,
+ cofb_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_corl_from_eoud_pruning_table() {
+ init_single_table(pow3to7, corl_transition_table,
+ corl_from_eoud_pruning_table, move_mask_eoud);
+}
+
+void init_cofb_from_eoud_pruning_table() {
+ init_single_table(pow3to7, cofb_transition_table,
+ cofb_from_eoud_pruning_table, move_mask_eoud);
+}
+
+/* The following tables always use DR moveset */
+void init_epud_pruning_table() {
+ init_single_table(factorial8, epud_transition_table, epud_pruning_table,
+ move_mask_drud);
+}
+
+void init_epfb_pruning_table() {
+ init_single_table(factorial8, epfb_transition_table, epfb_pruning_table,
+ move_mask_drfb);
+}
+
+void init_eprl_pruning_table() {
+ init_single_table(factorial8, eprl_transition_table, eprl_pruning_table,
+ move_mask_drrl);
+}
+
+void init_cp_drud_pruning_table() {
+ init_single_table(factorial8, cp_transition_table, cp_drud_pruning_table,
+ move_mask_drud);
+}
+
+void init_cp_drfb_pruning_table() {
+ init_single_table(factorial8, cp_transition_table, cp_drfb_pruning_table,
+ move_mask_drfb);
+}
+
+void init_cp_drrl_pruning_table() {
+ init_single_table(factorial8, cp_transition_table, cp_drrl_pruning_table,
+ move_mask_drrl);
+}
+
+void init_cp_htr_table() {
+ init_single_table(factorial8, cp_transition_table, cp_htr_pruning_table,
+ move_mask_htr);
+}
+
+void init_cpud_to_htr_table() {
+ init_cptohtr_table(factorial8, cp_transition_table,
+ cpud_to_htr_pruning_table, move_mask_drud);
+}
+
+void init_cpfb_to_htr_table() {
+ init_cptohtr_table(factorial8, cp_transition_table,
+ cpfb_to_htr_pruning_table, move_mask_drfb);
+}
+
+void init_cprl_to_htr_table() {
+ init_cptohtr_table(factorial8, cp_transition_table,
+ cprl_to_htr_pruning_table, move_mask_drrl);
+}
+
+
+void init_eofb_epose_pruning_table() {
+ init_double_table(pow2to11, binom12on4,
+ eofb_transition_table, epose_transition_table,
+ eofb_epose_pruning_table, move_mask_all);
+}
+
+void init_eorl_eposs_pruning_table() {
+ init_double_table(pow2to11, binom12on4,
+ eorl_transition_table, eposs_transition_table,
+ eorl_eposs_pruning_table, move_mask_all);
+}
+
+void init_eoud_eposm_pruning_table() {
+ init_double_table(pow2to11, binom12on4,
+ eoud_transition_table, eposm_transition_table,
+ eoud_eposm_pruning_table, move_mask_all);
+}
+
+
+
+void init_eofb_coud_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eofb_transition_table, coud_transition_table,
+ eofb_coud_pruning_table, move_mask_all);
+}
+
+void init_eofb_corl_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eofb_transition_table, corl_transition_table,
+ eofb_corl_pruning_table, move_mask_all);
+}
+
+void init_eorl_coud_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eorl_transition_table, coud_transition_table,
+ eorl_coud_pruning_table, move_mask_all);
+}
+
+void init_eorl_cofb_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eorl_transition_table, cofb_transition_table,
+ eorl_cofb_pruning_table, move_mask_all);
+}
+
+void init_eoud_corl_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eoud_transition_table, corl_transition_table,
+ eoud_corl_pruning_table, move_mask_all);
+}
+
+void init_eoud_cofb_pruning_table() {
+ init_double_table(pow2to11, pow3to7,
+ eoud_transition_table, cofb_transition_table,
+ eoud_cofb_pruning_table, move_mask_all);
+}
+
+void init_coud_epose_from_eofb_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ coud_transition_table, epose_transition_table,
+ coud_epose_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_cofb_eposs_from_eorl_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ cofb_transition_table, eposs_transition_table,
+ cofb_eposs_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_corl_eposm_from_eoud_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ corl_transition_table, eposm_transition_table,
+ corl_eposm_from_eoud_pruning_table, move_mask_eoud);
+}
+
+void init_coud_epose_from_eorl_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ coud_transition_table, epose_transition_table,
+ coud_epose_from_eorl_pruning_table, move_mask_eorl);
+}
+
+void init_cofb_eposs_from_eoud_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ cofb_transition_table, eposs_transition_table,
+ cofb_eposs_from_eoud_pruning_table, move_mask_eoud);
+}
+
+void init_corl_eposm_from_eofb_pruning_table() {
+ init_double_table(pow3to7, binom12on4,
+ corl_transition_table, eposm_transition_table,
+ corl_eposm_from_eofb_pruning_table, move_mask_eofb);
+}
+
+void init_cp_co_pruning_table() {
+ init_double_table(factorial8, pow3to7,
+ cp_transition_table, coud_transition_table,
+ cp_co_pruning_table, move_mask_all);
+}
+
+void init_triple_eo_pruning_table() {
+ init_double_table(pow2to11, binom12on4*binom8on4,
+ eofb_transition_table, emslices_transition_table,
+ triple_eo_pruning_table, move_mask_all);
+}
+
+
+void init_small_pruning_tables() {
+ if (initialized_small)
+ return;
+
+ init_eofb_pruning_table();
+ init_eorl_pruning_table();
+ init_eoud_pruning_table();
+ init_coud_pruning_table();
+ init_cofb_pruning_table();
+ init_corl_pruning_table();
+ init_cp_pruning_table();
+
+ init_eorl_from_eofb_pruning_table();
+ init_eoud_from_eofb_pruning_table();
+ init_eoud_from_eorl_pruning_table();
+ init_eofb_from_eorl_pruning_table();
+ init_eofb_from_eoud_pruning_table();
+ init_eorl_from_eoud_pruning_table();
+
+ init_coud_from_eofb_pruning_table();
+ init_corl_from_eofb_pruning_table();
+ init_coud_from_eorl_pruning_table();
+ init_cofb_from_eorl_pruning_table();
+ init_cofb_from_eoud_pruning_table();
+ init_corl_from_eoud_pruning_table();
+
+ init_epud_pruning_table();
+ init_epfb_pruning_table();
+ init_eprl_pruning_table();
+ init_cp_drud_pruning_table();
+ init_cp_drfb_pruning_table();
+ init_cp_drrl_pruning_table();
+
+ init_cp_htr_table();
+ init_cpud_to_htr_table();
+ init_cpfb_to_htr_table();
+ init_cprl_to_htr_table();
+
+ initialized_small = 1;
+}
+
+void init_directdr_pruning_tables() {
+ if (initialized_directdr)
+ return;
+
+ init_eofb_epose_pruning_table();
+ init_eorl_eposs_pruning_table();
+ init_eoud_eposm_pruning_table();
+
+ init_eofb_coud_pruning_table();
+ init_eofb_corl_pruning_table();
+ init_eorl_coud_pruning_table();
+ init_eorl_cofb_pruning_table();
+ init_eoud_cofb_pruning_table();
+ init_eoud_corl_pruning_table();
+
+ initialized_directdr = 1;
+}
+
+void init_drfromeo_pruning_tables() {
+ if (initialized_drfromeo)
+ return;
+
+ init_coud_epose_from_eofb_pruning_table();
+ init_cofb_eposs_from_eorl_pruning_table();
+ init_corl_eposm_from_eoud_pruning_table();
+ init_coud_epose_from_eorl_pruning_table();
+ init_cofb_eposs_from_eoud_pruning_table();
+ init_corl_eposm_from_eofb_pruning_table();
+
+ initialized_drfromeo = 1;
+}
+
+void init_huge_pruning_tables() {
+ if (initialized_huge)
+ return;
+
+ init_cp_co_pruning_table();
+ init_triple_eo_pruning_table();
+
+ initialized_huge = 1;
+}
+
diff --git a/src/pruning_tables.h b/src/pruning_tables.h
@@ -0,0 +1,66 @@
+#include <stdint.h>
+#include "utils.h"
+
+extern int eofb_pruning_table[pow2to11];
+extern int eorl_pruning_table[pow2to11];
+extern int eoud_pruning_table[pow2to11];
+extern int coud_pruning_table[pow3to7];
+extern int cofb_pruning_table[pow3to7];
+extern int corl_pruning_table[pow3to7];
+extern int cp_pruning_table[factorial8];
+
+extern int eorl_from_eofb_pruning_table[pow2to11];
+extern int eoud_from_eofb_pruning_table[pow2to11];
+extern int eoud_from_eorl_pruning_table[pow2to11];
+extern int eofb_from_eorl_pruning_table[pow2to11];
+extern int eofb_from_eoud_pruning_table[pow2to11];
+extern int eorl_from_eoud_pruning_table[pow2to11];
+
+extern int coud_from_eofb_pruning_table[pow3to7];
+extern int coud_from_eorl_pruning_table[pow3to7];
+extern int cofb_from_eorl_pruning_table[pow3to7];
+extern int cofb_from_eoud_pruning_table[pow3to7];
+extern int corl_from_eoud_pruning_table[pow3to7];
+extern int corl_from_eofb_pruning_table[pow3to7];
+
+extern int cp_drud_pruning_table[factorial8];
+extern int cp_drfb_pruning_table[factorial8];
+extern int cp_drrl_pruning_table[factorial8];
+extern int epud_pruning_table[factorial8];
+extern int epfb_pruning_table[factorial8];
+extern int eprl_pruning_table[factorial8];
+
+extern int cp_htr_pruning_table[factorial8];
+extern int cpud_to_htr_pruning_table[factorial8];
+extern int cpfb_to_htr_pruning_table[factorial8];
+extern int cprl_to_htr_pruning_table[factorial8];
+
+/* About 1Mb each */
+extern int8_t eofb_epose_pruning_table[pow2to11][binom12on4];
+extern int8_t eorl_eposs_pruning_table[pow2to11][binom12on4];
+extern int8_t eoud_eposm_pruning_table[pow2to11][binom12on4];
+
+/* About 4.5Mb each */
+extern int8_t eofb_coud_pruning_table[pow2to11][pow3to7];
+extern int8_t eofb_corl_pruning_table[pow2to11][pow3to7];
+extern int8_t eorl_coud_pruning_table[pow2to11][pow3to7];
+extern int8_t eorl_cofb_pruning_table[pow2to11][pow3to7];
+extern int8_t eoud_cofb_pruning_table[pow2to11][pow3to7];
+extern int8_t eoud_corl_pruning_table[pow2to11][pow3to7];
+
+/* About 1Mb each */
+extern int8_t coud_epose_from_eofb_pruning_table[pow3to7][binom12on4];
+extern int8_t cofb_eposs_from_eorl_pruning_table[pow3to7][binom12on4];
+extern int8_t corl_eposm_from_eoud_pruning_table[pow3to7][binom12on4];
+extern int8_t coud_epose_from_eorl_pruning_table[pow3to7][binom12on4];
+extern int8_t cofb_eposs_from_eoud_pruning_table[pow3to7][binom12on4];
+extern int8_t corl_eposm_from_eofb_pruning_table[pow3to7][binom12on4];
+
+/* First one 88Mb, second one 21Mb */
+extern int8_t cp_co_pruning_table[factorial8][pow3to7];
+extern int8_t triple_eo_pruning_table[pow2to11][binom12on4*binom8on4];
+
+void init_small_pruning_tables();
+void init_directdr_pruning_tables();
+void init_drfromeo_pruning_tables();
+void init_huge_pruning_tables();
diff --git a/src/solver.c b/src/solver.c
@@ -0,0 +1,893 @@
+#include <stdint.h>
+#include <stdio.h>
+
+#include "utils.h"
+#include "coordinates.h"
+#include "moves.h"
+#include "io.h"
+#include "pruning_tables.h"
+
+/* Applies inverse of moves, inverse of prev_moves and then inverse of scramble
+ * and returns a coordinate determined by t_table. */
+int premoves_inverse(int moves[21], int scramble[], int prev_moves[21],
+ int t_table[][19]) {
+ int nprevmoves, nmoves, nscramble, coord = 0;
+
+ for (nmoves = 0; moves[nmoves]; nmoves++);
+ for (nprevmoves = 0; prev_moves[nprevmoves]; nprevmoves++);
+ for (nscramble = 0; scramble[nscramble]; nscramble++);
+
+ for (int i = nmoves - 1; i >= 0; i--)
+ coord = t_table[coord][inverse_move[moves[i]]];
+ for (int i = nprevmoves - 1; i >= 0; i--)
+ coord = t_table[coord][inverse_move[prev_moves[i]]];
+ for (int i = nscramble - 1; i >= 0; i--)
+ coord = t_table[coord][inverse_move[scramble[i]]];
+
+ return coord;
+}
+
+
+/******/
+/* EO */
+/******/
+void niss_eo_dfs(int eo, int scramble[], int eo_list[][21], int *eo_count,
+ int t_table[pow2to11][19], int p_table[pow2to11],
+ int last1, int last2, int moves, int m, int d, int niss,
+ int can_use_niss, int hide) {
+
+ if (*eo_count >= m || moves > d ||
+ ((!can_use_niss || niss) && moves + p_table[eo] > d))
+ return;
+
+ eo_list[*eo_count][moves] = 0;
+
+ if (eo == 0) {
+ /* If an early EO is found, or if "case F2 B", or if hide is on. */
+ if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
+ (hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ return;
+ /* Copy moves for the next solution */
+ if (*eo_count < m - 1)
+ copy_moves(eo_list[*eo_count], eo_list[(*eo_count)+1]);
+ (*eo_count)++;
+ return;
+ }
+
+ if (moves + p_table[eo] <= d) {
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ eo_list[*eo_count][moves] = niss ? -i : i;
+ niss_eo_dfs(t_table[eo][i], scramble, eo_list, eo_count, t_table,
+ p_table, i, last1, moves+1, m, d, niss,
+ can_use_niss, hide);
+ }
+ }
+ }
+
+ eo_list[*eo_count][moves] = 0;
+
+ /* If not nissing already and we either have not done any move yet or
+ * the last move was F/F' etc, and if I am allowed to niss, try niss! */
+ if (!niss && (last1 == 0 || t_table[0][last1] != 0) && can_use_niss &&
+ !(hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0)))) {
+ int aux[] = {0,0};
+ niss_eo_dfs(premoves_inverse(eo_list[*eo_count], scramble, aux, t_table),
+ scramble, eo_list, eo_count, t_table, p_table,
+ 0, 0, moves, m, d, 1, can_use_niss, hide);
+ }
+}
+
+int eo_scram_spam(int scram[], int eo_list[][21], int fb, int rl, int ud,
+ int m, int b, int niss, int h) {
+
+ init_small_pruning_tables();
+
+ int n = 0, eofb = 0, eorl = 0, eoud = 0;
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+ }
+ for (int i = 0; i <= b; i++) {
+ if (fb)
+ niss_eo_dfs(eofb, scram, eo_list, &n, eofb_transition_table,
+ eofb_pruning_table, 0, 0, 0, m, i, 0, niss, h);
+ if (rl)
+ niss_eo_dfs(eorl, scram, eo_list, &n, eorl_transition_table,
+ eorl_pruning_table, 0, 0, 0, m, i, 0, niss, h);
+ if (ud)
+ niss_eo_dfs(eoud, scram, eo_list, &n, eoud_transition_table,
+ eoud_pruning_table, 0, 0, 0, m, i, 0, niss, h);
+ }
+ return n;
+}
+
+
+/**************/
+/* DR from EO */
+/**************/
+
+
+/* Scramble includes premoves for previous EO */
+void niss_dr_from_eo_dfs(int co, int epos, int scramble[], int eo_moves[21],
+ int dr_list[][21], int *dr_count,
+ int co_t_table[pow3to7][19],
+ int epos_t_table[binom12on4][19],
+ int8_t p_table[pow3to7][binom12on4], int mask,
+ int last1, int last2, int last1_inv, int last2_inv,
+ int moves, int m, int d, int niss,
+ int can_use_niss, int hide) {
+
+ if (*dr_count >= m || moves > d ||
+ ((!can_use_niss || niss) && moves + p_table[co][epos] > d))
+ return;
+
+ dr_list[*dr_count][moves] = 0;
+
+ if (co == 0 && epos == 0) {
+ if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
+ (hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ return;
+ /* Copy moves for the next solution */
+ if (*dr_count < m - 1)
+ copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
+ (*dr_count)++;
+ return;
+ }
+
+ if (moves + p_table[co][epos] <= d) {
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i) & mask) {
+ dr_list[*dr_count][moves] = niss ? -i : i;
+ niss_dr_from_eo_dfs(co_t_table[co][i], epos_t_table[epos][i],
+ scramble, eo_moves, dr_list, dr_count,
+ co_t_table, epos_t_table, p_table, mask,
+ i, last1, last1_inv, last2_inv,
+ moves+1, m, d, niss, can_use_niss, hide);
+ }
+ }
+ }
+
+ dr_list[*dr_count][moves] = 0;
+
+ /* If not nissing already and we either have not done any move yet or
+ * the last move was F/F' etc and I am allowed to niss, try niss! */
+ if (!niss && (last1 == 0 || co_t_table[0][last1] != 0) && can_use_niss &&
+ !(hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ niss_dr_from_eo_dfs(premoves_inverse(dr_list[*dr_count], scramble,
+ eo_moves, co_t_table),
+ premoves_inverse(dr_list[*dr_count], scramble,
+ eo_moves, epos_t_table),
+ scramble, eo_moves, dr_list, dr_count,
+ co_t_table, epos_t_table, p_table,
+ mask, last1_inv, last2_inv, 0, 0,
+ moves, m, d, 1, can_use_niss, hide);
+}
+
+int drfrom_scram_spam(int scram[], int dr_list[][21], int from, int fb,
+ int rl, int ud, int m, int b, int niss, int hide) {
+
+ init_drfromeo_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int epose = 0, eposm = 0, eposs = 0;
+ int coud = 0, corl = 0, cofb = 0;
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+
+ epose = epose_transition_table[epose][scram[i]];
+ eposm = eposm_transition_table[eposm][scram[i]];
+ eposs = eposs_transition_table[eposs][scram[i]];
+ }
+
+ int fake_eom[2] = {0, 0}; /* Fake EO moves */
+
+ if (from == 1) {
+ if (eofb)
+ return -1;
+ for (int i = 0; i <= b; i++) {
+ if (ud)
+ niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
+ coud_transition_table, epose_transition_table,
+ coud_epose_from_eofb_pruning_table, move_mask_eofb,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ if (rl)
+ niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
+ corl_transition_table, eposm_transition_table,
+ corl_eposm_from_eofb_pruning_table, move_mask_eofb,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else if (from == 2) {
+ if (eorl)
+ return -1;
+ for (int i = 0; i <= b; i++) {
+ if (fb)
+ niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
+ cofb_transition_table, eposs_transition_table,
+ cofb_eposs_from_eorl_pruning_table, move_mask_eorl,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ if (ud)
+ niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
+ coud_transition_table, epose_transition_table,
+ coud_epose_from_eorl_pruning_table, move_mask_eorl,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else if (from == 3) {
+ if (eoud)
+ return -1;
+ for (int i = 0; i <= b; i++) {
+ if (rl)
+ niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
+ corl_transition_table, eposm_transition_table,
+ corl_eposm_from_eoud_pruning_table, move_mask_eoud,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ if (fb)
+ niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
+ cofb_transition_table, eposs_transition_table,
+ cofb_eposs_from_eoud_pruning_table, move_mask_eoud,
+ 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else {
+ return -1;
+ }
+ return n;
+}
+
+
+/***************/
+/* HTR from DR */
+/***************/
+
+/* Scramble includes premoves for previous DR */
+void niss_htr_from_dr_dfs(int cp, int eo3, int scramble[], int eodr_moves[21],
+ int htr_list[][21], int *htr_count,
+ int eo3_t_table[pow2to11][19],
+ int cp_to_htr_pruning_table[factorial8],
+ int cp_htr_pruning_table[factorial8],
+ int cp_finish_pruning_table[factorial8],
+ int mask, int last1, int last2,
+ int last1_inv, int last2_inv, int moves,
+ int m, int d, int niss,
+ int can_use_niss, int hide) {
+
+ if (*htr_count >= m || moves > d ||
+ ((!can_use_niss || niss) && moves + cp_to_htr_pruning_table[cp] > d) ||
+ moves + cp_finish_pruning_table[cp] - 4 > d)
+ return;
+
+ htr_list[*htr_count][moves] = 0;
+
+ if ((cp == 0 || cp_htr_pruning_table[cp]) && eo3 == 0) {
+ if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
+ (hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ return;
+ /* Copy moves for the next solution */
+ if (*htr_count < m - 1)
+ copy_moves(htr_list[*htr_count], htr_list[(*htr_count)+1]);
+ (*htr_count)++;
+ return;
+ }
+
+ if (moves + cp_htr_pruning_table[cp] <= d) {
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i) & mask) {
+ htr_list[*htr_count][moves] = niss ? -i : i;
+ niss_htr_from_dr_dfs(cp_transition_table[cp][i], eo3_t_table[eo3][i],
+ scramble, eodr_moves, htr_list, htr_count,
+ eo3_t_table, cp_to_htr_pruning_table,
+ cp_htr_pruning_table, cp_finish_pruning_table,
+ mask, i, last1, last1_inv, last2_inv,
+ moves+1, m, d, niss, can_use_niss, hide);
+ }
+ }
+ }
+
+ htr_list[*htr_count][moves] = 0;
+
+ /* If not nissing already and we either have not done any move yet or
+ * the last move was a quarter turn and I am allowed to niss, try niss! */
+ if (!niss && last1 % 3 != 2 && can_use_niss &&
+ !(hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ niss_htr_from_dr_dfs(premoves_inverse(htr_list[*htr_count], scramble,
+ eodr_moves, cp_transition_table),
+ premoves_inverse(htr_list[*htr_count], scramble,
+ eodr_moves, eo3_t_table),
+ scramble, eodr_moves, htr_list, htr_count,
+ eo3_t_table, cp_to_htr_pruning_table,
+ cp_htr_pruning_table, cp_finish_pruning_table,
+ mask, last1_inv, last2_inv,
+ 0, 0, moves, m, d, 1, can_use_niss, hide);
+}
+
+int htr_scram_spam(int scram[], int htr_list[][21], int from,
+ int m, int b, int niss, int hide) {
+
+ init_small_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int coud = 0, corl = 0, cofb = 0;
+ int cp = 0;
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+
+ cp = cp_transition_table[cp][scram[i]];
+ }
+
+ int fake_drm[2] = {0, 0}; /* Fake DR moves */
+
+ if ((from == 1 || from == 0) && (!eofb && !eorl && !coud)) {
+ for (int i = 0; i <= b; i++) {
+ niss_htr_from_dr_dfs(cp, eoud, scram, fake_drm, htr_list, &n,
+ eoud_transition_table, cpud_to_htr_pruning_table,
+ cp_htr_pruning_table, cp_drud_pruning_table,
+ move_mask_drud, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb)) {
+ for (int i = 0; i <= b; i++) {
+ niss_htr_from_dr_dfs(cp, eofb, scram, fake_drm, htr_list, &n,
+ eofb_transition_table, cpfb_to_htr_pruning_table,
+ cp_htr_pruning_table, cp_drfb_pruning_table,
+ move_mask_drfb, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else if ((from == 3 || from == 0) && (!eoud && !eofb && !corl)) {
+ for (int i = 0; i <= b; i++) {
+ niss_htr_from_dr_dfs(cp, eorl, scram, fake_drm, htr_list, &n,
+ eorl_transition_table, cprl_to_htr_pruning_table,
+ cp_htr_pruning_table, cp_drrl_pruning_table,
+ move_mask_drrl, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
+ }
+ } else {
+ return -1;
+ }
+ return n;
+}
+
+
+/***********************/
+/* Direct DR (no NISS) */
+/***********************/
+void dr_dfs(int eo, int eo2, int eslice, int co,
+ int dr_list[][21], int *dr_count,
+ int eo_t_table[pow2to11][19], int eo2_t_table[pow2to11][19],
+ int eslice_t_table[binom12on4][19], int co_t_table[pow3to7][19],
+ int8_t eo_eslice_p_table[pow2to11][binom12on4],
+ int8_t eo_co_p_table[pow2to11][pow3to7],
+ int8_t eo2_co_p_table[pow2to11][pow3to7],
+ int last1, int last2, int moves, int max_sol,
+ int depth, int hide) {
+ if (*dr_count >= max_sol || moves + eo_eslice_p_table[eo][eslice] > depth ||
+ moves + eo_co_p_table[eo][co] > depth ||
+ moves + eo2_co_p_table[eo2][co] > depth)
+ return;
+
+ dr_list[*dr_count][moves] = 0;
+
+ if (eo == 0 && eslice == 0 && co == 0) {
+ /* If an early DR is found, or if "case R2 L". */
+ if (moves != depth || (parallel(last1, last2) && last2 % 3 == 2) ||
+ (hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ return;
+ /* Copy moves for the next solution */
+ if (*dr_count < max_sol - 1)
+ copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
+ (*dr_count)++;
+ return;
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ dr_list[*dr_count][moves] = i;
+ dr_dfs(eo_t_table[eo][i], eo2_t_table[eo2][i],
+ eslice_t_table[eslice][i], co_t_table[co][i],
+ dr_list, dr_count,
+ eo_t_table, eo2_t_table, eslice_t_table, co_t_table,
+ eo_eslice_p_table, eo_co_p_table, eo2_co_p_table,
+ i, last1, moves+1, max_sol, depth, hide);
+ }
+ }
+}
+
+int dr_scram_spam(int scram[], int dr_list[][21], int fb, int rl, int ud,
+ int m, int b, int h) {
+
+ init_directdr_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int epose = 0, eposm = 0, eposs = 0;
+ int coud = 0, corl = 0, cofb = 0;
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+
+ epose = epose_transition_table[epose][scram[i]];
+ eposm = eposm_transition_table[eposm][scram[i]];
+ eposs = eposs_transition_table[eposs][scram[i]];
+ }
+
+ for (int i = 0; i <= b; i++) {
+ if (ud)
+ dr_dfs(eofb, eorl, epose, coud, dr_list, &n,
+ eofb_transition_table, eorl_transition_table,
+ epose_transition_table, coud_transition_table,
+ eofb_epose_pruning_table, eofb_coud_pruning_table,
+ eorl_coud_pruning_table, 0, 0, 0, m, i, h);
+ if (fb)
+ dr_dfs(eorl, eoud, eposs, cofb, dr_list, &n,
+ eorl_transition_table, eoud_transition_table,
+ eposs_transition_table, cofb_transition_table,
+ eorl_eposs_pruning_table, eorl_cofb_pruning_table,
+ eoud_cofb_pruning_table, 0, 0, 0, m, i, h);
+ if (rl)
+ dr_dfs(eoud, eofb, eposm, corl, dr_list, &n,
+ eoud_transition_table, eofb_transition_table,
+ eposm_transition_table, corl_transition_table,
+ eoud_eposm_pruning_table, eoud_corl_pruning_table,
+ eofb_corl_pruning_table, 0, 0, 0, m, i, h);
+ }
+ return n;
+}
+
+
+/*************/
+/* DR finish */
+/*************/
+void dr_finish_dfs(int cp, int ep8, int ep4, int sol[][21], int *sol_count,
+ int ep8_t_table[factorial8][19],
+ int ep4_t_table[factorial4][19],
+ int cp_p_table[factorial8],
+ int ep8_p_table[factorial8],
+ int mask, int last1, int last2, int moves, int m, int d) {
+
+
+ if (*sol_count >= m || moves + cp_p_table[cp] > d ||
+ moves + ep8_p_table[ep8] > d)
+ return;
+
+ sol[*sol_count][moves] = 0;
+
+ if (cp == 0 && ep8 == 0 && ep4 == 0) {
+ if (moves != d)
+ return;
+ /* Copy moves for the next solution */
+ if (*sol_count < m - 1)
+ copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
+ (*sol_count)++;
+ return;
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i) & mask) {
+ sol[*sol_count][moves] = i;
+ dr_finish_dfs(cp_transition_table[cp][i], ep8_t_table[ep8][i],
+ ep4_t_table[ep4][i], sol, sol_count,
+ ep8_t_table, ep4_t_table,
+ cp_p_table, ep8_p_table,
+ mask, i, last1, moves+1, m, d);
+ }
+ }
+
+ return;
+}
+
+int dr_finish_scram_spam(int scram[], int sol[][21], int from, int m, int b) {
+
+ init_small_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int coud = 0, corl = 0, cofb = 0;
+ int cp = 0;
+ int ep[12];
+ ep_int_to_array(0, ep);
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+
+ cp = cp_transition_table[cp][scram[i]];
+ apply_move_ep_array(scram[i], ep);
+ }
+
+ if ((from == 1 && (eofb || eorl || coud)) ||
+ (from == 2 && (eorl || eoud || cofb)) ||
+ (from == 3 && (eoud || eofb || corl)) ||
+ ((eofb || eorl || coud) && (eorl || eoud ||cofb) && (eoud ||eofb || corl)))
+ return -1;
+
+ for (int i = 0; i <= b; i++) {
+ if ((from == 1 || from == 0) && (!eofb && !eorl && !coud))
+ dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
+ sol, &n, epud_transition_table, epe_transition_table,
+ cp_drud_pruning_table, epud_pruning_table,
+ move_mask_drud, 0, 0, 0, m, i);
+ if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb))
+ dr_finish_dfs(cp, epfb_array_to_int(ep), eps_array_to_int(ep),
+ sol, &n, epfb_transition_table, eps_transition_table,
+ cp_drfb_pruning_table, epfb_pruning_table,
+ move_mask_drfb, 0, 0, 0, m, i);
+ if ((from == 3 || from == 0) && (!eoud && !eofb && !corl))
+ dr_finish_dfs(cp, eprl_array_to_int(ep), epm_array_to_int(ep),
+ sol, &n, eprl_transition_table, epm_transition_table,
+ cp_drrl_pruning_table, eprl_pruning_table,
+ move_mask_drrl, 0, 0, 0, m, i);
+ }
+
+ return n;
+}
+
+int htr_finish_scram_spam(int scram[], int sol[][21], int m, int b) {
+
+ init_small_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int coud = 0, cp = 0;
+ int ep[12];
+ ep_int_to_array(0, ep);
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ coud = coud_transition_table[coud][scram[i]];
+
+ cp = cp_transition_table[cp][scram[i]];
+ apply_move_ep_array(scram[i], ep);
+ }
+
+ if (eofb || eorl || eoud || coud || cpud_to_htr_pruning_table[cp] != 0)
+ return -1;
+
+ for (int i = 0; i <= b; i++)
+ dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
+ sol, &n, epud_transition_table, epe_transition_table,
+ cp_drud_pruning_table, epud_pruning_table,
+ move_mask_htr, 0, 0, 0, m, i);
+
+ return n;
+}
+
+
+/**************/
+/* DR corners */
+/**************/
+void dr_corners_dfs(int cp, int sol[][21], int *sol_count,
+ int cp_p_table[factorial8], int mask, int last1, int last2,
+ int moves, int m, int d, int ignore) {
+
+ if (*sol_count >= m || (!ignore && moves + cp_p_table[cp] > d) ||
+ (ignore && moves + cp_p_table[cp] - 2 > d))
+ return;
+
+
+ sol[*sol_count][moves] = 0;
+
+ if (cp == 0 || (ignore &&
+ (cp_transition_table[cp_transition_table[cp][U]][D3] == 0 ||
+ cp_transition_table[cp_transition_table[cp][U2]][D2] == 0 ||
+ cp_transition_table[cp_transition_table[cp][U3]][D] == 0 ))) {
+ if (moves != d)
+ return;
+ /* Copy moves for the next solution */
+ if (*sol_count < m - 1)
+ copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
+ (*sol_count)++;
+ return;
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i) & mask) {
+ sol[*sol_count][moves] = i;
+ dr_corners_dfs(cp_transition_table[cp][i], sol, sol_count,
+ cp_p_table, mask, i, last1, moves+1, m, d, ignore);
+ }
+ }
+}
+
+int dr_corners_scram_spam(int scram[], int sol[][21], int from, int m, int b,
+ int ignore) {
+
+ init_small_pruning_tables();
+
+ int n = 0;
+ int eofb = 0, eorl = 0, eoud = 0;
+ int coud = 0, corl = 0, cofb = 0;
+ int cp = 0;
+
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+
+ cp = cp_transition_table[cp][scram[i]];
+ }
+
+ if ((from == 1 && coud) || (from == 2 && cofb) || (from == 3 && corl) ||
+ (coud && cofb && corl))
+ return -1;
+
+ for (int i = 0; i <= b; i++) {
+ if ((from == 1 || from == 0) && !coud)
+ dr_corners_dfs(cp, sol, &n, cp_drud_pruning_table, move_mask_drud,
+ 0, 0, 0, m, i, ignore);
+ if ((from == 2 || from == 0) && !cofb)
+ dr_corners_dfs(cp, sol, &n, cp_drfb_pruning_table, move_mask_drfb,
+ 0, 0, 0, m, i, ignore);
+ if ((from == 3 || from == 0) && !corl)
+ dr_corners_dfs(cp, sol, &n, cp_drrl_pruning_table, move_mask_drrl,
+ 0, 0, 0, m, i, ignore);
+ }
+
+ return n;
+}
+
+/***************/
+/* Full solver */
+/***************/
+
+int is_ep_solved(int ep, int moves[21]) {
+ int ep_arr[12];
+ ep_int_to_array(ep, ep_arr);
+ for (int i = 0; moves[i]; i++)
+ apply_move_ep_array(moves[i], ep_arr);
+ return !ep_array_to_int(ep_arr);
+}
+
+/* Solves directly using only small tables. Suitable for short solutions. */
+void small_optimal_dfs(int eofb, int eorl, int eoud, int ep,
+ int coud, int cofb, int corl, int cp,
+ int sol[][21], int *sol_count, int last1, int last2,
+ int moves, int m, int d) {
+ if (moves + eofb_pruning_table[eofb] > d ||
+ moves + eorl_pruning_table[eorl] > d ||
+ moves + eoud_pruning_table[eoud] > d ||
+ moves + coud_pruning_table[coud] > d ||
+ moves + cofb_pruning_table[cofb] > d ||
+ moves + corl_pruning_table[corl] > d ||
+ moves + cp_pruning_table[cp] > d ||
+ *sol_count >= m)
+ return;
+
+ sol[*sol_count][moves] = 0;
+
+ if (eofb == 0 && coud == 0 && cp == 0) {
+ if (is_ep_solved(ep, sol[*sol_count])) {
+ if (moves != d)
+ return;
+ if (*sol_count < m - 1)
+ copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
+ (*sol_count)++;
+ return;
+ }
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ sol[*sol_count][moves] = i;
+ small_optimal_dfs(eofb_transition_table[eofb][i],
+ eorl_transition_table[eorl][i],
+ eoud_transition_table[eoud][i], ep,
+ coud_transition_table[coud][i],
+ cofb_transition_table[cofb][i],
+ corl_transition_table[corl][i],
+ cp_transition_table[cp][i],
+ sol, sol_count, i, last1, moves+1, m, d);
+ }
+ }
+}
+
+/* Solves directly using only medium tables. Suitable for short solutions. */
+void medium_optimal_dfs(int eofb, int eorl, int eoud,
+ int epose, int eposs, int eposm, int ep,
+ int coud, int cofb, int corl, int cp,
+ int sol[][21], int *sol_count, int last1, int last2,
+ int moves, int m, int d) {
+ if (moves + eofb_epose_pruning_table[eofb][epose] > d ||
+ moves + eorl_eposs_pruning_table[eorl][eposs] > d ||
+ moves + eoud_eposm_pruning_table[eoud][eposm] > d ||
+ moves + eofb_coud_pruning_table[eofb][coud] > d ||
+ moves + eofb_corl_pruning_table[eofb][corl] > d ||
+ moves + eorl_coud_pruning_table[eorl][coud] > d ||
+ moves + eorl_cofb_pruning_table[eorl][cofb] > d ||
+ moves + eoud_cofb_pruning_table[eoud][cofb] > d ||
+ moves + eoud_corl_pruning_table[eoud][corl] > d ||
+ moves + cp_pruning_table[cp] > d ||
+ *sol_count >= m)
+ return;
+
+ sol[*sol_count][moves] = 0;
+
+ if (eofb == 0 && coud == 0 && cp == 0) {
+ if (is_ep_solved(ep, sol[*sol_count])) {
+ if (moves != d)
+ return;
+ if (*sol_count < m - 1)
+ copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
+ (*sol_count)++;
+ return;
+ }
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ sol[*sol_count][moves] = i;
+ medium_optimal_dfs(eofb_transition_table[eofb][i],
+ eorl_transition_table[eorl][i],
+ eoud_transition_table[eoud][i],
+ epose_transition_table[epose][i],
+ eposs_transition_table[eposs][i],
+ eposm_transition_table[eposm][i], ep,
+ coud_transition_table[coud][i],
+ cofb_transition_table[cofb][i],
+ corl_transition_table[corl][i],
+ cp_transition_table[cp][i],
+ sol, sol_count, i, last1, moves+1, m, d);
+ }
+ }
+}
+
+/* Uses huge tables */
+int optimal_dfs(int ep, int cp, int eo, int co, int emslices,
+ int sol[][21], int last1, int last2, int moves, int d) {
+ if (moves + cp_co_pruning_table[cp][co] > d ||
+ moves + triple_eo_pruning_table[eo][emslices] > d)
+ return 0;
+
+ sol[0][moves] = 0;
+
+ /* If solved, no need to check the depth */
+ if (cp == 0 && co == 0 && eo == 0 && emslices == 0)
+ if (is_ep_solved(ep, sol[0]))
+ return 1;
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ sol[0][moves] = i;
+ if (optimal_dfs(ep, cp_transition_table[cp][i],
+ eofb_transition_table[eo][i],
+ coud_transition_table[co][i],
+ emslices_transition_table[emslices][i],
+ sol, i, last1, moves+1, d))
+ return 1;
+ }
+ }
+ return 0;
+}
+
+int solve_scram(int scram[], int sol[][21], int m, int b, int optimal) {
+
+ /* Initialize pieces. */
+ int eofb = 0, eorl = 0, eoud = 0, ep = 0;
+ int epose = 0, eposs = 0, eposm = 0;
+ int coud = 0, cofb = 0, corl = 0, cp = 0;
+ int emslices = 0;
+ for (int i = 0; scram[i]; i++) {
+ eofb = eofb_transition_table[eofb][scram[i]];
+ eorl = eorl_transition_table[eorl][scram[i]];
+ eoud = eoud_transition_table[eoud][scram[i]];
+
+ epose = epose_transition_table[epose][scram[i]];
+ eposs = eposs_transition_table[eposs][scram[i]];
+ eposm = eposm_transition_table[eposm][scram[i]];
+
+ ep = apply_move_ep_int(scram[i], ep);
+
+ coud = coud_transition_table[coud][scram[i]];
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ cp = cp_transition_table[cp][scram[i]];
+
+ emslices = emslices_transition_table[emslices][scram[i]];
+ }
+
+ /* First we check if there are solutions of up to max_small moves. */
+ int max_small = 10;
+ int n = 0;
+ init_small_pruning_tables();
+ for (int i = 0; i <= min(b, max_small); i++) {
+ small_optimal_dfs(eofb, eorl, eoud, ep, coud, cofb, corl, cp,
+ sol, &n, 0, 0, 0, m, i);
+ if (n > 0 && optimal)
+ b = min(b, len(sol[0]));
+ }
+
+
+ if (n >= m || b <= 10)
+ return n;
+
+ /* Then we try a slightly larger optimal solver */
+ /*
+ int max_medium = 11;
+ init_directdr_pruning_tables();
+ for (int i = 0; i <= min(b, max_medium); i++)
+ medium_optimal_dfs(eofb, eorl, eoud, epose, eposs, eposm, ep,
+ coud, cofb, corl, cp, sol, &n, 0, 0, 0, m, i);
+ */
+
+ /* If we found at least a solution, we return */
+ if (n > 0)
+ return n;
+
+ /* Then we try a 2-step solver */
+ int max_step1 = 5000;
+ int db = 14;
+ int step1[max_step1+10][21];
+ int ss[300], step2[2][21];
+ int best = b+1;
+
+ /* TODO maybe: for now, multiple solutions can be found only using the
+ * short solver. */
+
+ int n_step1 = dr_scram_spam(scram, step1, 1, 1, 1, max_step1, min(b, db), 0);
+ for (int i = 0; i < n_step1; i++) {
+ copy_moves(scram, ss);
+ append_moves(step1[i], ss);
+ if (dr_finish_scram_spam(ss, step2, 0, 1, min(best-1,b) - len(step1[i]))) {
+ copy_moves(step1[i], sol[0]);
+ append_moves(step2[0], sol[0]);
+ best = len(sol[0]);
+ }
+ }
+
+ /* If optimal solving was not required, or we have already found an optimal
+ * solution, we return. */
+ if (best <= len(step1[n_step1-1]) || !optimal)
+ return best > b ? 0 : 1;
+
+ /* Otherwise, we go on with the optimal solver. */
+ int searched = len(step1[n_step1-1])-1;
+
+ printf("Searched up to %d moves, no solution found.\n", searched);
+ printf("Using huge pruning tables, if not loaded it might take a while.\n");
+ init_huge_pruning_tables();
+
+ for (int i = searched+1; i <= min(b, best-1); i++) {
+ if (i >= 10)
+ printf("Searching at depth %d.\n", i);
+ if (optimal_dfs(ep, cp, eofb, coud, emslices, sol, 0, 0, 0, i)) {
+ return 1;
+ }
+ }
+ return best > b ? 0 : 1;
+}
diff --git a/src/solver.h b/src/solver.h
@@ -0,0 +1,13 @@
+int eo_scram_spam(int scram[], int eo_list[][21], int fb, int rl, int ud,
+ int m, int b, int niss, int h);
+int dr_scram_spam(int scram[], int dr_list[][21], int fb, int rl, int ud,
+ int m, int b, int h);
+int drfrom_scram_spam(int scram[], int dr_list[][21], int from, int fb,
+ int rl, int ud, int m, int b, int niss, int hide);
+int htr_scram_spam(int scram[], int htr_list[][21], int from,
+ int m, int b, int niss, int hide);
+int dr_corners_scram_spam(int scram[], int sol[][21], int from, int m, int b,
+ int ignore);
+int dr_finish_scram_spam(int scram[], int sol[][21], int from, int m, int b);
+int htr_finish_scram_spam(int scram[], int sol[][21], int m, int b);
+int solve_scram(int scram[], int sol[][21], int m, int b, int optimal);
diff --git a/src/utils.c b/src/utils.c
@@ -0,0 +1,115 @@
+#include "utils.h"
+
+/* Hardcoded factorial of small numbers (n<=12). */
+int factorial[13] = {
+ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
+};
+
+/* swaps two integers */
+void swap(int *a, int *b) {
+ int aux = *a;
+ *a = *b;
+ *b = aux;
+}
+
+/* Converts the integer a to its representation in base b (first n digits
+ * only) and saves the result in r. */
+void int_to_digit_array(int a, int b, int n, int *r) {
+ for (int i = 0; i < n; i++) {
+ r[i] = a % b;
+ a /= b;
+ }
+}
+
+/* Converts the array of n digits a to a integer using base b. */
+int digit_array_to_int(int *a, int n, int b) {
+ int ret = 0, p = 1;
+ for (int i = 0; i < n; i++) {
+ ret += a[i] * p;
+ p *= b;
+ }
+ return ret;
+}
+
+/* Converts a permutation on [0..(n-1)] into the integer i which is the index
+ * of the permutation in the sorted list of all n! such permutations.
+ * Only works for n<=12. */
+int perm_to_index(int *a, int n) {
+ int ret = 0;
+ for (int i = 0; i < n; i++) {
+ int c = 0;
+ for (int j = i+1; j < n; j++)
+ if (a[i] > a[j])
+ c++;
+ ret += factorial[n-i-1] * c;
+ }
+ return ret;
+}
+
+/* Converts a permutation index to the actual permutation as an array
+ * (see perm_to_index) and saves the result to r. */
+void index_to_perm(int p, int n, int *r) {
+ int a[n];
+ for (int j = 0; j < n; j++)
+ a[j] = 0; /* picked elements */
+ for (int i = 0; i < n; i++) {
+ int c = 0, j = 0;
+ while (c <= p / factorial[n-i-1]) {
+ if (!a[j])
+ c++;
+ j++;
+ }
+ r[i] = j-1;
+ a[j-1] = 1;
+ p %= factorial[n-i-1];
+ }
+}
+
+/* Converts a k-element subset of a set with an element from an array of n
+ * elements, of which k are 1 (or just non-zero) and n-k are 0, to its index
+ * in the sorted list of all such subsets.
+ * Works only for n <= 12. */
+int subset_to_index(int *a, int n, int k) {
+ int ret = 0;
+ for (int i = 0; i < n; i++) {
+ if (k == n-i)
+ return ret;
+ if (a[i]) {
+ ret += factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]);
+ k--;
+ }
+ }
+ return ret;
+}
+
+/* Inverse of the above */
+void index_to_subset(int s, int n, int k, int *r) {
+ for (int i = 0; i < n; i++) {
+ if (k == n-i) {
+ for (int j = i; j < n; j++)
+ r[j] = 1;
+ return;
+ }
+ int v = factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]);
+ if (s >= v) {
+ r[i] = 1;
+ k--;
+ s -= v;
+ } else {
+ r[i] = 0;
+ }
+ }
+}
+
+/* Converts the first n-1 digits of a number to an array a of digits in base b;
+ * then adds one element to the array, so that the sum of the elements of a is
+ * zero modulo b.
+ * This is used for determing the edge orientation from an 11-bits integer or
+ * the corner orientation from a 7-trits integer. */
+void int_to_sum_zero_array(int x, int b, int n, int *a) {
+ int_to_digit_array(x, b, n-1, a);
+ int s = 0;
+ for (int i = 0; i < n - 1; i++) s = (s + a[i]) % b;
+ a[n-1] = (b - s) % b;
+}
+
diff --git a/src/utils.h b/src/utils.h
@@ -0,0 +1,54 @@
+#define min(a,b) (((a) < (b)) ? (a) : (b))
+#define max(a,b) (((a) > (b)) ? (a) : (b))
+#define abs(a) (((a) > 0) ? (a) : (-(a)))
+
+/* Some useful constants */
+#define pow2to11 2048
+#define pow2to12 4096
+#define pow3to7 2187
+#define pow3to8 6561
+#define pow12to4 20736
+#define factorial4 24
+#define factorial6 720
+#define factorial8 40320
+#define factorial12 479001600
+#define binom12on4 495
+#define binom8on4 70
+
+void swap(int *a, int *b);
+
+/* Hardcoded factorial of small numbers (n<=12). */
+extern int factorial[13];
+
+/* Converts the integer a to its representation in base b (first n digits
+ * only) and saves the result in r. */
+void int_to_digit_array(int a, int b, int n, int *r);
+
+/* Converts the array of n digits a to a integer using base b. */
+int digit_array_to_int(int *a, int n, int b);
+
+/* Converts a permutation on [0..(n-1)] into the integer i which is the index
+ * of the permutation in the sorted list of all n! such permutations.
+ * Only works for n<=12. */
+int perm_to_index(int *a, int n);
+
+/* Converts a permutation index to the actual permutation as an array
+ * (see perm_to_index) and saves the result to r. */
+void index_to_perm(int p, int n, int *r);
+
+/* Converts a k-element subset of a set with an element from an array of n
+ * elements, of which k are 1 and n-k are 0, to its index in the sorted list
+ * of all such subsets.
+ * Works only for n <= 12. */
+int subset_to_index(int *a, int n, int k);
+
+/* Inverse of the above */
+void index_to_subset(int s, int n, int k, int *r);
+
+/* Converts the first n-1 digits of a number to an array a of digits in base b;
+ * then adds one element to the array, so that the sum of the elements of a is
+ * zero modulo b.
+ * This is used for determing the edge orientation from an 11-bits integer or
+ * the corner orientation from a 7-trits integer. */
+void int_to_sum_zero_array(int x, int b, int n, int *a);
+
