1. Evan Gates
  2. cubeutils

Commits

Evan Gates  committed f0661e3

cleanup and restart refactoring, now that I have a better idea of what I want to do

  • Participants
  • Parent commits 52c42f0
  • Branches default

Comments (0)

Files changed (3)

File cubeutils.c

View file
 static char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
                          "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
 
-static char c_cycles[6][4] = {
-	{ 0, 1, 2, 3 }, // U
-	{ 4, 5, 6, 7 }, // D
-	{ 0, 3, 5, 4 }, // F
-	{ 1, 7, 6, 2 }, // B
-	{ 0, 4, 7, 1 }, // R
-	{ 2, 6, 5, 3 }, // L
+static uint8_t c_cycles[6][4] = {
+	{ 0, 1, 2, 3 }, /* U */
+	{ 4, 5, 6, 7 }, /* D */
+	{ 0, 3, 5, 4 }, /* F */
+	{ 1, 7, 6, 2 }, /* B */
+	{ 0, 4, 7, 1 }, /* R */
+	{ 2, 6, 5, 3 }, /* L */
 };
-static char e_cycles[6][4] = {
-	{ 0,  1, 2,  3 }, // U
-	{ 4,  7, 6,  5 }, // D
-	{ 0,  9, 4,  8 }, // F
-	{ 2, 10, 6, 11 }, // B
-	{ 1,  8, 5, 10 }, // R
-	{ 3, 11, 7,  9 }, // L
+static uint8_t e_cycles[6][4] = {
+	{ 0,  1, 2,  3 }, /* U */
+	{ 4,  7, 6,  5 }, /* D */
+	{ 0,  9, 4,  8 }, /* F */
+	{ 2, 10, 6, 11 }, /* B */
+	{ 1,  8, 5, 10 }, /* R */
+	{ 3, 11, 7,  9 }, /* L */
 };
-static char c_twists[6][4] = {
-	{ 0, 0, 0, 0 }, // U
-	{ 0, 0, 0, 0 }, // D
-	{ 2, 1, 2, 1 }, // F
-	{ 1, 2, 1, 2 }, // B
-	{ 1, 2, 1, 2 }, // R
-	{ 1, 2, 1, 2 }, // L
+static uint8_t c_twists[6][4] = {
+	{ 0, 0, 0, 0 }, /* U */
+	{ 0, 0, 0, 0 }, /* D */
+	{ 2, 1, 2, 1 }, /* F */
+	{ 1, 2, 1, 2 }, /* B */
+	{ 1, 2, 1, 2 }, /* R */
+	{ 1, 2, 1, 2 }, /* L */
 };
-static char e_twists[6][4] = {
-	{ 0, 0, 0, 0 }, // U
-	{ 0, 0, 0, 0 }, // D
-	{ 1, 1, 1, 1 }, // F
-	{ 1, 1, 1, 1 }, // B
-	{ 0, 0, 0, 0 }, // R
-	{ 0, 0, 0, 0 }, // L
+static uint8_t e_twists[6][4] = {
+	{ 0, 0, 0, 0 }, /* U */
+	{ 0, 0, 0, 0 }, /* D */
+	{ 1, 1, 1, 1 }, /* F */
+	{ 1, 1, 1, 1 }, /* B */
+	{ 0, 0, 0, 0 }, /* R */
+	{ 0, 0, 0, 0 }, /* L */
 };
 
 
 	return buf;
 }
 
+void print_move(int mv)
+{
+	char *faces = "UDFBRL", *num = " 2'";
+
+	printf("%c%c ", faces[mv / 3], num[mv % 3]);
+}
+
 /*
  * check even or odd parity of permutations
  */
 	return o;
 }
 
-// math functions
-static int fact [12] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
-static int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }
+/* math functions */
+/*
+int fact  (int n)        { int f; for (f = 1; n; f *= n--); return f; }
+int choose(int n, int k) { return fact(n)/(fact(k) * fact(n - k)); }
+*/
+int fact[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
+int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }
+
+/*
+ * coordinate functions
+ *
+ * the ud1 and ud2 coordinates are based on descriptions at http://kociemba.org/math/twophase.htm
+ * the oriention and permuation functions are based on descirptions at http://www.jaapsch.net/puzzles/compindx.htm
+ *
+ * the get functions return the coordinate for the current state of the array cube
+ * the set functions set the corresponding pieces of the array cube to the given coordinate
+ */
 
 /*
  * ud1 coordinate
  */
-void set_ud1_coord(int coord)
+void set_ud1_coord(uint16_t coord)
 {
 	int i, j;
 
 	memset(ep, 0, 12);
-	for (i = 11, j = 4; i >= 0 && j; i--) {
+	for (i = 11, j = 4; i >= 0 && j > 0; i--) {
 		if (coord >= choose(i, j - 1)) {
 			coord -= choose(i, j - 1);
 		} else {
 	}
 }
 
-int get_ud1_coord(void)
+uint16_t get_ud1_coord(void)
 {
 	int i, j = 0, coord = 0;
 
 /*
  * generic orientation coordinate
  */
-static void set_o_coord(char *orie, int len, int coord, int mod)
+static void set_o_coord(uint8_t *orie, int len, uint16_t coord, int mod)
 {
 	int i, s = 0;
 
 	for (i = len - 2; i >= 0; i--) {
 		orie[i] = coord % mod;
+		coord /= mod;
 		s = (s - orie[i] + mod) % mod;
-		coord /= mod;
 	}
 	orie[len - 1] = s;
 }
 
-static int get_o_coord(char *orie, int len, int mod)
+static uint16_t get_o_coord(uint8_t *orie, int len, int mod)
 {
 	int i, coord = 0;
 
 /*
  * specific orientation coordinates
  */
-void set_eo_coord(int coord) { set_o_coord(eo, 12, coord, 2); }
-void set_co_coord(int coord) { set_o_coord(co,  8, coord, 3); }
+void set_eo_coord(uint16_t coord) { set_o_coord(eo, 12, coord, 2); }
+void set_co_coord(uint16_t coord) { set_o_coord(co,  8, coord, 3); }
 
-int get_eo_coord(void) { return get_o_coord(eo, 12, 2); }
-int get_co_coord(void) { return get_o_coord(co,  8, 3); }
+uint16_t get_eo_coord(void) { return get_o_coord(eo, 12, 2); }
+uint16_t get_co_coord(void) { return get_o_coord(co,  8, 3); }
 
 /*
  * generic permutation coordinate
  */
-static void set_p_coord(char *perm, int len, int coord)
+static void set_p_coord(uint8_t *perm, int len, uint16_t coord)
 {
 	int i, j;
 
 	}
 }
 
-static int get_p_coord(char *perm, int len)
+static uint16_t get_p_coord(uint8_t *perm, int len)
 {
 	int i, j, coord = 0;
 
 /*
  * specific permutation coordinates
  */
-void set_cp_coord (int coord) { set_p_coord(cp,     8, coord); }
-void set_ep_coord (int coord) { set_p_coord(ep,     8, coord); }
-void set_ud2_coord(int coord) { set_p_coord(ep + 8, 4, coord); }
+void set_cp_coord     (uint16_t coord) { set_p_coord(cp,     8, coord); }
+void set_ep_coord     (uint16_t coord) { set_p_coord(ep,     8, coord); }
+void set_ud2_coord    (uint16_t coord) { set_p_coord(ep + 8, 4, coord); }
+void set_ep_coord_full(uint16_t coord) { set_p_coord(ep,    12, coord); }
 
-int get_cp_coord (void) { return get_p_coord(cp,     8); }
-int get_ep_coord (void) { return get_p_coord(ep,     8); }
-int get_ud2_coord(void) { return get_p_coord(ep + 8, 4); }
+uint16_t get_cp_coord     (void) { return get_p_coord(cp,     8); }
+uint16_t get_ep_coord     (void) { return get_p_coord(ep,     8); }
+uint16_t get_ud2_coord    (void) { return get_p_coord(ep + 8, 4); }
+uint16_t get_ep_coord_full(void) { return get_p_coord(ep,    12); }
 
-void set_ep_coord_full(int coord) {set_p_coord(ep, 12, coord); }
-int  get_ep_coord_full(void) { return get_p_coord(ep, 12); }
-
-/*
- * generic pruning table initialization
- */
-// TODO: update based on quarter turn only trans tables
-void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last)
-{
-	int i, mv, old = coord;
-
-	if (depth == mdepth || prune_table[coord] <= depth)
-		return;
-
-	prune_table[coord] = depth;
-
-	for (mv = 0; mv < 18; mv += 3, coord = old) {
-		if (mv / 3 == last / 3)
-			continue;
-		for (i = 0; i < 3; i++) {
-			if (group && mv >= 6 && i) // only want double turns on F, B, R, L in G1
-				break;
-			coord = trans_table[coord][mv / 3];
-			init_prune(group, coord, prune_table, trans_table, mdepth, depth + 1, mv);
-		}
-	}
-}
-
-/*
- * generic transition table initialization
- */
-// TODO: all 6 based on quarter turns no matter what
-void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void))
-{
-	int i, mv;
-
-	for (i = 0; i < len; i++) {
-		for (mv = 0; mv < 18; mv += 3) {
-			set_coord(i);
-			do_move(mv);
-			if (group && mv >= 6) // only want double turns on F, B, R, L in G1
-				do_move(mv);
-			tran_table[i][mv / 3] = get_coord();
-		}
-	}
-}
-
-int num_trys[] = { 0, 3, 1 }; // try to calculate when brain is working instead of lookup
-/*
- * generic solve
- */
-#define MAX_MOVES 32
-int num_moves = 0;
-int solution[MAX_MOVES];
-int solve(int group[6], int *coords, int num_coords, char *prune_tables[], int *trans_tables[][6], int depth, int last)
-{
-	int i, j, k, face, tmp[num_coords];
-
-	for (i = j = 0; i < num_coords && !j; j |= coords[i++]) // check if all coords are 0
-		;
-	if (i == num_coords) return 1; // success
-
-	if (depth == 0) return 0;
-
-	for (i = 0; i < num_coords; i++) // check against pruning tables
-		if (prune_tables[i][coords[i]] > depth)
-			return 0;
-
-	for (face = 0; face < 6; face++) {
-		// no two moves in a row on same face, no move on same axis after U, F, R
-		if (face == last || ((last & 1) == 0 && face == last + 1))
-			continue;
-
-		memcpy(tmp, coords, num_coords);
-
-		for (i = 0; i < num_trys[group[face]]; i++) { // recurse on solve number of times based on group[face], 0 if 0, 3 if 1 (3 quarter turns), 1 if 2 (1 half turn)
-			for (j = 0; j < num_coords; j++)          // loop through coordinates to perform moves
-				for (k = 0; k < group[j]; k++)        // perform transition once for quarter turn (group[j] == 1), twice for half turn (group[j] == 2)
-					tmp[j] = trans_tables[j][tmp[j]][face];
-
-			if (solve(group, tmp, num_coords, prune_tables, trans_tables, depth - 1, face)) {
-				solution[num_moves++] = face * 3 + ((group[face] == 1) ? i : 1); // face * 3 for base move, add i (0, 1, or 2) if quarter turns, add 1 if half turns
-				return 1;
-			}
-		}
-	}
-	return 0;
-}

File cubeutils.h

View file
 #ifndef _CUBEUTILS_H_
 #define _CUBEUTILS_H_
 
+#include <stdint.h>
+
 #define SOLVED_CUBE "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR "
 
 /*
  * corners: UFR URB UBL ULF DRF DFL DLB DBR
  * edges  : UF  UR  UB  UL  DF  DR  DB  DL  FR  FL  BR  BL
  */
-char co[8], eo[12], cp[8], ep[12];
+uint8_t co[8], eo[12], cp[8], ep[12];
 
 /*
  * moves are:
  * U1 U2 U3 D1 D2 D3 F1 F2 F3 B1 B2 B3 R1 R2 R3 L1 L2 L3
  * 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17
  */
-enum { U1, U2, U3, D1, D2, D3, F1, F2, F3, B1, B2, B3, R1, R2, R3, L1, L2, L3 };
-
-/*
- * TODO: add more common/useful groups (eg: Thistlethwaite)
- *       perhaps automate group group dependency in transition/pruning tables and solve
- * groups are:
- * 0 = G0 = <U, D, F , B , R , L >
- * 1 = G1 = <U, D, F2, B2, R2, L2>
- */
-//            U, D, F, B, R, L
-#define G0 (int[]){ 1, 1, 1, 1, 1, 1 }
-#define G1 (int[]){ 1, 1, 2, 2, 2, 1 }
 
 /*
  * perform the given move on the array cube
 char *get_cube(char *buf, int len);
 
 /*
+ * print move (...duh)
+ */
+void print_move(int mv);
+
+/*
  * check even or odd parity of a permutation
  */
 int parity(char *perm, int len);
  */
 int orient(char *orie, int len, int mod);
 
-void set_ud1_coord(int coord);
-int get_ud1_coord(void);
+/*
+ * get and set coordinates
+ */
+void set_ud1_coord(uint16_t coord);
 
-void set_eo_coord(int coord);
-void set_co_coord(int coord);
+uint16_t get_ud1_coord(void);
 
-int get_eo_coord(void);
-int get_co_coord(void);
+void set_eo_coord(uint16_t coord);
+void set_co_coord(uint16_t coord);
 
-void set_cp_coord (int coord);
-void set_ep_coord (int coord);
-void set_ud2_coord(int coord);
+uint16_t get_eo_coord(void);
+uint16_t get_co_coord(void);
 
-int get_cp_coord (void);
-int get_ep_coord (void);
-int get_ud2_coord(void);
+void set_cp_coord     (uint16_t coord);
+void set_ep_coord     (uint16_t coord);
+void set_ud2_coord    (uint16_t coord);
+void set_ep_coord_full(uint16_t coord);
 
-void set_ep_coord_full(int coord);
-int  get_ep_coord_full(void);
-
-/*
- * initialize pruning table
- */
-void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last);
-
-/*
- * initialize transition table
- */
-void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void));
-
-/*
- * TODO: generic solve given a group, list of coordinates, list of tables
- */
-int solve(int group[6], int *coords, int num_coords, char **prune_tables, int *(trans_tables[][6]), int depth, int last);
+uint16_t get_cp_coord     (void);
+uint16_t get_ep_coord     (void);
+uint16_t get_ud2_coord    (void);
+uint16_t get_ep_coord_full(void);
 
 #endif

File solve.c

View file
 #include <stdio.h>
 #include <string.h>
+
 #include "cubeutils.h"
 
-char co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
-int  co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
+/*
+ * index  : 0   1   2   3   4   5   6   7   8    9  10  11
+ * value  : 1   2   3   4   5   6   7   8   9   10  11  12
+ * corners: UFR URB UBL ULF DRF DFL DLB DBR
+ * edges  : UF  UR  UB  UL  DF  DR  DB  DL  FR  FL  BR  BL
+ *
+ * NOTE: values are 1 based due to current set_p_coord()
+ */
+uint8_t  co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
+uint16_t co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
 
 /*
+ * phases are:
+ * 0 = G0 = <U, D, F , B , R , L >
+ * 1 = G1 = <U, D, F2, B2, R2, L2>
+ *
  * moves are:
  * U U2 U' D D2 D' F F2 F' B B2 B' R  R2 R' L  L2 L'
  * 0 1  2  3 4  5  6 7  8  9 10 11 12 13 14 15 16 17
+ *
+ * faces are: move / 3
+ * U D F B R L
+ * 0 1 2 3 4 5
  */
 int sol[30];
 
 /*
+ * generic transition table initialization
+ */
+void init_trans(int phase, uint16_t trans_table[][6], int len, void (*set_coord)(uint16_t), uint16_t (*get_coord)(void))
+{
+	int i, face;
+
+	for (i = 0; i < len; i++) {
+		for (face = 0; face < 6; face++) {
+			set_coord(i);
+			do_move(face * 3);
+			if (phase && face > 1) /* only want double turns on F, B, R, L in G1 */
+				do_move(face * 3);
+			trans_table[i][face] = get_coord();
+		}
+	}
+}
+
+/*
+ * specific transition table initializations
+ */
+void init_trans_tables(void)
+{
+	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
+	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );
+	init_trans(0, ud1_trans,  495,  set_ud1_coord, get_ud1_coord);
+
+	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );
+	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );
+	init_trans(1, ud2_trans,    24, set_ud2_coord, get_ud2_coord);
+}
+
+/*
+ * generic pruning table initialization
+ */
+void init_prune(int phase, int coord, uint8_t prune_table[], uint16_t trans_table[][6], int mdepth, int depth, int last)
+{
+	int i, face, old = coord;
+
+	if (depth == mdepth || prune_table[coord] <= depth)
+		return;
+
+	prune_table[coord] = depth;
+
+	for (face = 0; face < 6; face++, coord = old) {
+		if (face == last) /* don't include turns on the same face as last time */
+			continue;
+		for (i = 0; i < 3; i++) {
+			coord = trans_table[coord][face];
+			init_prune(phase, coord, prune_table, trans_table, mdepth, depth + 1, face);
+			if (phase && face > 1) /* only want double turns on F, B, R, L in G1 */
+				break;
+		}
+	}
+}
+
+/*
  * specific pruning table initializations
  */
 void init_prune_tables(void)
 {
-	memset(eo_prune,  127, sizeof(eo_prune ));
-	memset(co_prune,  127, sizeof(co_prune ));
-	memset(ep_prune,  127, sizeof(ep_prune ));
-	memset(cp_prune,  127, sizeof(cp_prune ));
-	memset(ud1_prune, 127, sizeof(ud1_prune));
-	memset(ud2_prune, 127, sizeof(ud2_prune));
+	memset(eo_prune,  0xff, sizeof(eo_prune ));
+	memset(co_prune,  0xff, sizeof(co_prune ));
+	memset(ep_prune,  0xff, sizeof(ep_prune ));
+	memset(cp_prune,  0xff, sizeof(cp_prune ));
+	memset(ud1_prune, 0xff, sizeof(ud1_prune));
+	memset(ud2_prune, 0xff, sizeof(ud2_prune));
 
 	init_prune(0, 0, eo_prune,  eo_trans,  8, 0, -1);
 	init_prune(0, 0, co_prune,  co_trans,  7, 0, -1);
 }
 
 /*
- * specific transition table initializations
+ * phase solver
  */
-void init_trans_tables(void)
+int solve(int phase, int e_coord, int c_coord, int ud_coord, int depth, int last)
 {
-	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
-	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );
-	init_trans(0, ud1_trans, 495,   set_ud1_coord, get_ud1_coord);
+	int i, e_tmp, c_tmp, ud_tmp, face;
 
-	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );
-	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );
-	init_trans(1, ud2_trans, 24,    set_ud2_coord, get_ud2_coord);
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) return 1; /* success! */
+	if (!phase && (depth == 0 || eo_prune[e_coord] > depth || co_prune[c_coord] > depth || ud1_prune[ud_coord] > depth)) return 0; /* test for phase G0 */
+	if ( phase && (depth == 0 || ep_prune[e_coord] > depth || cp_prune[c_coord] > depth || ud2_prune[ud_coord] > depth)) return 0; /* test for phase G1 */
+
+	for (face = 0; face < 6; face++) {
+		/* no two moves in a row on same face, no move on same axis after U, F, R */
+		if (face == last || ((last & 1) == 0 && face == last + 1))
+			continue;
+
+		e_tmp  = e_coord;
+		c_tmp  = c_coord;
+		ud_tmp = ud_coord;
+
+		for (i = 0; i < 3; i++) {
+			e_tmp  = phase ? ep_trans [e_tmp ][face] : eo_trans [e_tmp ][face];
+			c_tmp  = phase ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];
+			ud_tmp = phase ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];
+
+			if (solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face)) {
+				sol[(phase ? 30 : 12) - depth] = face * 3 + ((phase && face > 1) ? 1 : i);
+				return 1;
+			}
+			if (phase && face > 1)
+				break;
+		}
+	}
+	return 0;
 }
 
-void print_move(int mv)
+int main(void)
 {
-	char *faces = "UDFBRL", *num = " 2'";
-
-	printf("%c%c ", faces[mv / 3], num[mv % 3]);
-}
-
-int main(int argc, char **argv)
-{
-	char buf[128], i;
+	char buf[128];
+	int i;
 
 	init_trans_tables();
 	init_prune_tables();
 
+	/* Use to read a single cube as 1 or 20 arguments */
+	/*
+	*buf = '\0';
+	for (i = 1; i < argc; i++) {
+		strcat(buf, argv[i]);
+		strcat(buf, " ");
+	}
+	*/
+
+	/* Use to continually read cubes from stdin */
 	while (fgets(buf, sizeof(buf), stdin)) {
 		memset(sol, -1, sizeof(sol));
 		set_cube(buf);
 
-		int (*trans[])[][6] = { &eo_trans, &co_trans, &ud1_trans };
-
-		for (i = 0; solve(G0, (int[]){ get_eo_coord(), get_co_coord(), get_ud1_coord() }, 3, (char*[]){ eo_prune, co_prune, ud1_prune }, trans, i, -1) == 0; i++)
+		for (i = 0; solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), i, -1) == 0; i++)
 			;
 
 		for (i = 12 - i; i < 12; i++)
 			do_move(sol[i]);
 
-		//for (i = 0; solve(G1, (int[]){ get_ep_coord(), get_cp_coord(), get_ud2_coord() }, 3, (char*[]){ ep_prune, cp_prune, ud2_prune }, (int[]){ ep_trans, cp_trans, ud2_trans }, i, -1) == 0; i++)
-			//;
+		for (i = 0; solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), i, -1) == 0; i++)
+			;
 
-		// if the last move from phase 1 and first move from phase 2 are on the same face
-		// it will always be a quarter turn then half turn on FBLR
+		/* if the last move from phase 1 and first move from phase 2 are on the same face
+		   it will always be a quarter turn then half turn on FBLR */
 		if (sol[11] > -1 && sol[30 - i] > -1 && sol[30 - i] / 3 == sol[11] / 3) {
 			sol[30 - i] = -1;
 			sol[11] += (sol[11] % 3) ? -2 : 2;
 				print_move(sol[i]);
 
 		printf("\n");
+		fflush(stdout);
 	}
 	return 0;
 }