HOG2
RubiksCubeEdges.cpp
Go to the documentation of this file.
1 //
2 // RubikEdge.cpp
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 1/4/13.
6 // Copyright (c) 2013 University of Denver. All rights reserved.
7 //
8 
9 #include "RubiksCubeEdges.h"
10 #include "GLUtil.h"
11 #include <cassert>
12 #include <string>
13 #include <thread>
14 
43 RubikEdgeState RotateRubikEdgeClockwise(const RubikEdgeState &in, int step)
44 {
45  RubikEdgeState e = in;
46  int rotations[] = {8, 9, 1, 2, 0, 6, 7, 11, 10, 3, 4, 5};
47  for (int x = 0; x < 12; x++)
48  {
49  e.SetCubeInLoc(x, in.GetCubeInLoc(rotations[x]));
50  e.SetCubeOrientation(in.GetCubeInLoc(rotations[x]), in.GetCubeOrientation(in.GetCubeInLoc(rotations[x])));
51  }
52  e.FlipCubeOrientation(e.GetCubeInLoc(1));
53  e.FlipCubeOrientation(e.GetCubeInLoc(3));
54  e.FlipCubeOrientation(e.GetCubeInLoc(4));
55  e.FlipCubeOrientation(e.GetCubeInLoc(8));
56  e.FlipCubeOrientation(e.GetCubeInLoc(7));
57  e.FlipCubeOrientation(e.GetCubeInLoc(11));
58  return e;
59 }
60 
61 
62 RubikEdgeStateBits::RubikEdgeStateBits()
63 {
64  Reset();
65 }
66 void RubikEdgeStateBits::Reset()
67 {
68  state = 0;
69  for (int x = 0; x < 12; x++)
70  SetCubeInLoc(x, x);
71 }
72 void RubikEdgeStateBits::Clear()
73 {
74  state = 0;
75 }
76 int RubikEdgeStateBits::GetCubeInLoc(int whichLoc) const
77 {
78  return (state>>(12+4*whichLoc))&0xF;
79 }
80 void RubikEdgeStateBits::SetCubeInLoc(int whichLoc, int cube)
81 {
82  if (whichLoc >= 12)
83  return;
84  uint64_t blank = 0xF;
85  uint64_t value = cube&0xF;
86  state = state&(~(blank<<(12+4*whichLoc)));
87  state |= (value<<(12+4*whichLoc));
88 }
89 bool RubikEdgeStateBits::GetCubeOrientation(int whichCube) const
90 {
91  return state&(0x1<<whichCube);
92 }
93 void RubikEdgeStateBits::SetCubeOrientation(int whichCube, bool flip)
94 {
95  if (whichCube >= 12)
96  return;
97  uint64_t blank = 0x1;
98  if (flip)
99  state |= (0x1<<whichCube);
100  else
101  state = state&(~(blank<<whichCube));
102 }
103 void RubikEdgeStateBits::FlipCubeOrientation(int whichCube)
104 {
105  if (whichCube >= 12)
106  return;
107  state = state^(0x1<<whichCube);
108 }
109 
110 void RubikEdgeStateBits::GetDual(RubikEdgeStateBits &s) const
111 {
112  for (int x = 0; x < 12; x++)
113  {
114  s.SetCubeInLoc(GetCubeInLoc(x), x);
115  s.SetCubeOrientation(x, GetCubeOrientation(GetCubeInLoc(x)));
116  }
117 }
118 
119 
120 RubikEdgeStateArray::RubikEdgeStateArray()
121 {
122  Reset();
123 }
124 void RubikEdgeStateArray::Reset()
125 {
126  for (int x = 0; x < 12; x++)
127  {
128  state[x] = 0;
129  SetCubeInLoc(x, x);
130  }
131 }
132 void RubikEdgeStateArray::Clear()
133 {
134  Reset();
135 }
136 int RubikEdgeStateArray::GetCubeInLoc(int whichLoc) const
137 {
138  return state[12+whichLoc];
139  //return (state>>(12+4*whichLoc))&0xF;
140 }
141 void RubikEdgeStateArray::SetCubeInLoc(int whichLoc, int cube)
142 {
143  if (whichLoc >= 12)
144  return;
145  state[whichLoc+12] = cube;
146 // uint64_t blank = 0xF;
147 // uint64_t value = cube&0xF;
148 // state = state&(~(blank<<(12+4*whichLoc)));
149 // state |= (value<<(12+4*whichLoc));
150 }
151 bool RubikEdgeStateArray::GetCubeOrientation(int whichCube) const
152 {
153  return state[whichCube];
154  //return state&(0x1<<whichLoc);
155 }
156 void RubikEdgeStateArray::SetCubeOrientation(int whichCube, bool flip)
157 {
158  if (whichCube >= 12)
159  return;
160  state[whichCube] = flip;
161 // uint64_t blank = 0x1;
162 // if (flip)
163 // state |= (0x1<<whichLoc);
164 // else
165 // state = state&(~(blank<<whichLoc));
166 }
167 void RubikEdgeStateArray::FlipCubeOrientation(int whichCube)
168 {
169  if (whichCube >= 12)
170  return;
171  state[whichCube] = !state[whichCube];
172  //state = state^(0x1<<whichLoc);
173 }
174 
175 void RubikEdgeStateArray::GetDual(RubikEdgeStateArray &s) const
176 {
177  for (int x = 0; x < 12; x++)
178  {
179  s.SetCubeInLoc(GetCubeInLoc(x), x);
180  s.SetCubeOrientation(x, GetCubeOrientation(GetCubeInLoc(x)));
181  }
182 }
183 
184 
185 void RubikEdge::GetSuccessors(const RubikEdgeState &nodeID, std::vector<RubikEdgeState> &neighbors) const
186 {
187  RubikEdgeState s;
188  for (int x = 0; x < 18; x++)
189  {
190  GetNextState(nodeID, x, s);
191  neighbors.push_back(s);
192  }
193 }
194 
195 void RubikEdge::GetActions(const RubikEdgeState &nodeID, std::vector<RubikEdgeAction> &actions) const
196 {
197  actions.resize(0);
198  for (int x = 0; x < 18; x++)
199  {
200  actions.push_back(x);
201  }
202 }
203 
204 RubikEdgeAction RubikEdge::GetAction(const RubikEdgeState &s1, const RubikEdgeState &s2) const
205 {
206  assert(false);
207  RubikEdgeAction a;
208  return a;
209 }
210 
211 void RubikEdge::ApplyMove(RubikEdgeState &s, RubikEdgeMove *a)
212 {
213  ApplyAction(s, a->act);
214 }
215 
216 void RubikEdge::UndoMove(RubikEdgeState &s, RubikEdgeMove *a)
217 {
218  RubikEdgeAction todo = a->act;
219  if (0 == todo%3)
220  {
221  todo += 1;
222  }
223  else if (1 == todo%3)
224  {
225  todo -= 1;
226  }
227  ApplyAction(s, todo);
228 }
229 
230 void RubikEdge::UndoAction(RubikEdgeStateBits &s, RubikEdgeAction a) const
231 {
232  RubikEdgeAction todo = a;
233  if (0 == todo%3)
234  {
235  todo += 1;
236  }
237  else if (1 == todo%3)
238  {
239  todo -= 1;
240  }
241  ApplyAction(s, todo);
242 }
243 
244 void RubikEdge::UndoAction(RubikEdgeStateArray &s, RubikEdgeAction a) const
245 {
246  RubikEdgeAction todo = a;
247  if (0 == todo%3)
248  {
249  todo += 1;
250  }
251  else if (1 == todo%3)
252  {
253  todo -= 1;
254  }
255  ApplyAction(s, todo);
256 }
257 
258 template <typename t>
259 void LocalApplyAction(t &s, RubikEdgeAction a)
260 {
261  switch (a)
262  {
263  case 0: // face 0
264  {
265  int a = s.GetCubeInLoc(1-1);
266  int b = s.GetCubeInLoc(3-1);
267  int c = s.GetCubeInLoc(5-1);
268  int d = s.GetCubeInLoc(7-1);
269  s.SetCubeInLoc(1-1, d);
270  s.SetCubeInLoc(3-1, a);
271  s.SetCubeInLoc(5-1, b);
272  s.SetCubeInLoc(7-1, c);
273  }
274  break;
275  case 1:
276  {
277  int a = s.GetCubeInLoc(1-1);
278  int b = s.GetCubeInLoc(3-1);
279  int c = s.GetCubeInLoc(5-1);
280  int d = s.GetCubeInLoc(7-1);
281  s.SetCubeInLoc(1-1, b);
282  s.SetCubeInLoc(3-1, c);
283  s.SetCubeInLoc(5-1, d);
284  s.SetCubeInLoc(7-1, a);
285  }
286  break;
287  case 2:
288  {
289  int a = s.GetCubeInLoc(1-1);
290  int b = s.GetCubeInLoc(3-1);
291  int c = s.GetCubeInLoc(5-1);
292  int d = s.GetCubeInLoc(7-1);
293  s.SetCubeInLoc(1-1, c);
294  s.SetCubeInLoc(3-1, d);
295  s.SetCubeInLoc(5-1, a);
296  s.SetCubeInLoc(7-1, b);
297  }
298  break;
299  case 3: // face 5
300  {
301  int a = s.GetCubeInLoc(9-1);
302  int b = s.GetCubeInLoc(10-1);
303  int c = s.GetCubeInLoc(11-1);
304  int d = s.GetCubeInLoc(12-1);
305  s.SetCubeInLoc(9-1, d);
306  s.SetCubeInLoc(10-1, a);
307  s.SetCubeInLoc(11-1, b);
308  s.SetCubeInLoc(12-1, c);
309  }
310  break;
311  case 4:
312  {
313  int a = s.GetCubeInLoc(9-1);
314  int b = s.GetCubeInLoc(10-1);
315  int c = s.GetCubeInLoc(11-1);
316  int d = s.GetCubeInLoc(12-1);
317  s.SetCubeInLoc(9-1, b);
318  s.SetCubeInLoc(10-1, c);
319  s.SetCubeInLoc(11-1, d);
320  s.SetCubeInLoc(12-1, a);
321  }
322  break;
323  case 5:
324  {
325  int a = s.GetCubeInLoc(9-1);
326  int b = s.GetCubeInLoc(10-1);
327  int c = s.GetCubeInLoc(11-1);
328  int d = s.GetCubeInLoc(12-1);
329  s.SetCubeInLoc(9-1, c);
330  s.SetCubeInLoc(10-1, d);
331  s.SetCubeInLoc(11-1, a);
332  s.SetCubeInLoc(12-1, b);
333  }
334  break;
335 
336  case 6: // face 2
337  {
338  int a = s.GetCubeInLoc(2-1);
339  int b = s.GetCubeInLoc(3-1);
340  int c = s.GetCubeInLoc(4-1);
341  int d = s.GetCubeInLoc(10-1);
342  s.SetCubeInLoc(2-1, d);
343  s.SetCubeInLoc(3-1, a);
344  s.SetCubeInLoc(4-1, b);
345  s.SetCubeInLoc(10-1, c);
346  s.FlipCubeOrientation(b);
347  s.FlipCubeOrientation(d);
348  }
349  break;
350  case 7:
351  {
352  int a = s.GetCubeInLoc(2-1);
353  int b = s.GetCubeInLoc(3-1);
354  int c = s.GetCubeInLoc(4-1);
355  int d = s.GetCubeInLoc(10-1);
356  s.SetCubeInLoc(2-1, b);
357  s.SetCubeInLoc(3-1, c);
358  s.SetCubeInLoc(4-1, d);
359  s.SetCubeInLoc(10-1, a);
360  s.FlipCubeOrientation(a);
361  s.FlipCubeOrientation(c);
362  }
363  break;
364  case 8:
365  {
366  int a = s.GetCubeInLoc(2-1);
367  int b = s.GetCubeInLoc(3-1);
368  int c = s.GetCubeInLoc(4-1);
369  int d = s.GetCubeInLoc(10-1);
370  s.SetCubeInLoc(2-1, c);
371  s.SetCubeInLoc(3-1, d);
372  s.SetCubeInLoc(4-1, a);
373  s.SetCubeInLoc(10-1, b);
374  s.FlipCubeOrientation(a);
375  s.FlipCubeOrientation(b);
376  s.FlipCubeOrientation(c);
377  s.FlipCubeOrientation(d);
378  }
379  break;
380 
381  case 9: // face 4
382  {
383  int a = s.GetCubeInLoc(6-1);
384  int b = s.GetCubeInLoc(7-1);
385  int c = s.GetCubeInLoc(8-1);
386  int d = s.GetCubeInLoc(12-1);
387  s.SetCubeInLoc(6-1, d);
388  s.SetCubeInLoc(7-1, a);
389  s.SetCubeInLoc(8-1, b);
390  s.SetCubeInLoc(12-1, c);
391  s.FlipCubeOrientation(c);
392  s.FlipCubeOrientation(d);
393  }
394  break;
395  case 10:
396  {
397  int a = s.GetCubeInLoc(6-1);
398  int b = s.GetCubeInLoc(7-1);
399  int c = s.GetCubeInLoc(8-1);
400  int d = s.GetCubeInLoc(12-1);
401  s.SetCubeInLoc(6-1, b);
402  s.SetCubeInLoc(7-1, c);
403  s.SetCubeInLoc(8-1, d);
404  s.SetCubeInLoc(12-1, a);
405  s.FlipCubeOrientation(a);
406  s.FlipCubeOrientation(d);
407  }
408  break;
409  case 11:
410  {
411  int a = s.GetCubeInLoc(6-1);
412  int b = s.GetCubeInLoc(7-1);
413  int c = s.GetCubeInLoc(8-1);
414  int d = s.GetCubeInLoc(12-1);
415  s.SetCubeInLoc(6-1, c);
416  s.SetCubeInLoc(7-1, d);
417  s.SetCubeInLoc(8-1, a);
418  s.SetCubeInLoc(12-1, b);
419  s.FlipCubeOrientation(b);
420  s.FlipCubeOrientation(d);
421  }
422  break;
423 
424  case 12: // face 1
425  {
426  int a = s.GetCubeInLoc(1-1);
427  int b = s.GetCubeInLoc(2-1);
428  int c = s.GetCubeInLoc(9-1);
429  int d = s.GetCubeInLoc(8-1);
430  s.SetCubeInLoc(1-1, d);
431  s.SetCubeInLoc(2-1, a);
432  s.SetCubeInLoc(9-1, b);
433  s.SetCubeInLoc(8-1, c);
434  s.FlipCubeOrientation(a);
435  s.FlipCubeOrientation(d);
436  }
437  break;
438  case 13:
439  {
440  int a = s.GetCubeInLoc(1-1);
441  int b = s.GetCubeInLoc(2-1);
442  int c = s.GetCubeInLoc(9-1);
443  int d = s.GetCubeInLoc(8-1);
444  s.SetCubeInLoc(1-1, b);
445  s.SetCubeInLoc(2-1, c);
446  s.SetCubeInLoc(9-1, d);
447  s.SetCubeInLoc(8-1, a);
448  s.FlipCubeOrientation(a);
449  s.FlipCubeOrientation(b);
450  }
451  break;
452  case 14:
453  {
454  int a = s.GetCubeInLoc(1-1);
455  int b = s.GetCubeInLoc(2-1);
456  int c = s.GetCubeInLoc(9-1);
457  int d = s.GetCubeInLoc(8-1);
458  s.SetCubeInLoc(1-1, c);
459  s.SetCubeInLoc(2-1, d);
460  s.SetCubeInLoc(9-1, a);
461  s.SetCubeInLoc(8-1, b);
462  s.FlipCubeOrientation(a);
463  s.FlipCubeOrientation(c);
464  }
465  break;
466  case 15: // face 3
467  {
468  int a = s.GetCubeInLoc(4-1);
469  int b = s.GetCubeInLoc(5-1);
470  int c = s.GetCubeInLoc(6-1);
471  int d = s.GetCubeInLoc(11-1);
472  s.SetCubeInLoc(4-1, d);
473  s.SetCubeInLoc(5-1, a);
474  s.SetCubeInLoc(6-1, b);
475  s.SetCubeInLoc(11-1, c);
476  s.FlipCubeOrientation(b);
477  s.FlipCubeOrientation(d);
478  }
479  break;
480  case 16:
481  {
482  int a = s.GetCubeInLoc(4-1);
483  int b = s.GetCubeInLoc(5-1);
484  int c = s.GetCubeInLoc(6-1);
485  int d = s.GetCubeInLoc(11-1);
486  s.SetCubeInLoc(4-1, b);
487  s.SetCubeInLoc(5-1, c);
488  s.SetCubeInLoc(6-1, d);
489  s.SetCubeInLoc(11-1, a);
490  s.FlipCubeOrientation(a);
491  s.FlipCubeOrientation(c);
492  }
493  break;
494  case 17:
495  {
496  int a = s.GetCubeInLoc(4-1);
497  int b = s.GetCubeInLoc(5-1);
498  int c = s.GetCubeInLoc(6-1);
499  int d = s.GetCubeInLoc(11-1);
500  s.SetCubeInLoc(4-1, c);
501  s.SetCubeInLoc(5-1, d);
502  s.SetCubeInLoc(6-1, a);
503  s.SetCubeInLoc(11-1, b);
504  s.FlipCubeOrientation(a);
505  s.FlipCubeOrientation(b);
506  s.FlipCubeOrientation(c);
507  s.FlipCubeOrientation(d);
508  }
509  break;
510  default:
511  break;
512  }
513 
514 }
515 
516 void RubikEdge::ApplyAction(RubikEdgeStateArray &s, RubikEdgeAction a) const
517 {
518  LocalApplyAction<RubikEdgeStateArray>(s, a);
519 }
520 
521 void RubikEdge::ApplyAction(RubikEdgeStateBits &s, RubikEdgeAction a) const
522 {
523  LocalApplyAction<RubikEdgeStateBits>(s, a);
524 }
525 
526 
527 void RubikEdge::GetNextState(const RubikEdgeState &s0, RubikEdgeAction a, RubikEdgeState &s1) const
528 {
529  s1 = s0;
530  ApplyAction(s1, a);
531 }
532 
533 bool RubikEdge::InvertAction(RubikEdgeAction &a) const
534 {
535  if (2 == a%3)
536  return true;
537  if (1 == a%3)
538  {
539  a -= 1;
540  return true;
541  }
542  a += 1;
543  return true;
544 
545 }
546 
547 bool RubikEdge::GoalTest(const RubikEdgeStateBits &b) const
548 {
549  assert(!"Code not called");
550  return b.state == 0;
551 }
552 
553 bool RubikEdge::GoalTest(const RubikEdgeStateArray &a) const
554 {
555  assert(!"Code not called");
556 }
557 
558 
559 inline uint64_t Factorial(int n)
560 {
561  static uint64_t Factorial[21] =
562  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
563  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
564  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
565 
566  return Factorial[n];
567 }
568 
569 inline int get(uint64_t state, int whichLoc)
570 {
571  return (state>>((whichLoc<<2)))&0xF;
572 }
573 
574 inline void set(uint64_t &state, int whichLoc, int cube)
575 {
576  const uint64_t blank = 0xF;
577  uint64_t value = cube;//&0xF;
578  state = state&(~(blank<<((whichLoc<<2))));
579  state |= (value<<((whichLoc<<2)));
580 }
581 
582 inline void swap(uint64_t &state, int loc1, int loc2)
583 {
584  loc1<<=2;
585  loc2<<=2;
586  uint64_t val1 = (state>>(loc1));
587  uint64_t val2 = (state>>(loc2));
588 
589  uint64_t xord = (val1 ^ val2)&0xF;
590  xord = (xord << loc1) | (xord << loc2);
591  state = state^xord;
592 // const uint64_t blank = 0xF;
593 // uint64_t mask = (blank<<(loc1))|(blank<<(loc2));
594 // state = state&(~mask);
595 // state = state|(val1<<(loc2))|(val2<<(loc1));
596 }
597 
598 int64_t RubikEdge::getMaxSinglePlayerRank() const
599 {
600  static uint64_t Factorial[21] =
601  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
602  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
603  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
604 
605  return Factorial[12]*(0x1<<11);
606  // return 980995276800ll;
607 }
608 
609 int64_t RubikEdge::getMaxSinglePlayerRank2()
610 {
611  return 128;
612 }
613 
614 int64_t RubikEdge::getMaxSinglePlayerRank2(int64_t firstIndex)
615 {
616  return (Factorial(12)*(0x1<<4));
617 }
618 
619 void RubikEdge::rankPlayerFirstTwo(const RubikEdgeState &s, int, int64_t &rank)
620 {
621  rank = (s.GetCubeOrientation(11)<<6)|(s.GetCubeOrientation(10)<<5)|
622  (s.GetCubeOrientation(9)<<4)|(s.GetCubeOrientation(8)<<3)|
623  (s.GetCubeOrientation(7)<<2)|(s.GetCubeOrientation(6)<<1)|
624  s.GetCubeOrientation(5);
625  // rank = s.GetCubeInLoc(0);
626 }
627 
628 void RubikEdge::rankPlayerRemaining(const RubikEdgeState &node, int, int64_t &rank)
629 {
630  uint64_t perm = 0, dual = 0;
631  for (int x = 0; x < 12; x++)
632  {
633  set(perm, x, node.GetCubeInLoc(x));
634  set(dual, node.GetCubeInLoc(x), x);
635  }
636 
637  uint64_t hashVal = 0;
638  for (int x = 7; x < 11; x++)
639  {
640  hashVal = (hashVal<<1)+node.GetCubeOrientation(11-x);
641  }
642  hashVal = hashVal*Factorial(12)+MRRank(12, perm, dual);
643  rank = hashVal;
644 }
645 
646 
647 uint64_t RubikEdge::GetStateHash(const RubikEdgeState &node) const
648 {
649  uint64_t perm = 0, dual = 0;
650  for (int x = 0; x < 12; x++)
651  {
652  int val = node.GetCubeInLoc(x);
653  set(perm, x, val);
654  set(dual, val, x);
655  }
656 
657  uint64_t hashVal = 0;
658  for (int x = 0; x < 11; x++)
659  {
660  hashVal = (hashVal<<1)+node.GetCubeOrientation(11-x);
661  }
662  // return (MRRank(12, perm, dual)<<11)|hashVal;
663  hashVal = hashVal*Factorial(12)+MRRank(12, perm, dual);
664  return hashVal;
665 }
666 
667 // 38.522
668 uint64_t RubikEdge::MRRank(int n, uint64_t perm, uint64_t dual)
669 {
670  int ss[12];
671  int ssLoc = 0;
672  // static std::vector<int> ss;
673  // ss.resize(0);
674  int s;
675  for (int i = n; i > 1; i--)
676  {
677  s = get(perm, i-1);
678  ss[ssLoc] = s;
679  ssLoc++;
680  // ss.push_back(s);
681  swap(perm, i-1, get(dual, i-1));
682  swap(dual, s, i-1);
683  }
684  uint64_t result = 0;
685  int cnt = 2;
686  // printf("0");
687  for (int i = (int)ssLoc-1; i >= 0; i--)
688  {
689  // printf(")*%d + %d ", cnt, ss[i]);
690  result *= cnt;
691  result += ss[i];
692  cnt++;
693  }
694  // printf("\n");
695  return result;
696  // if (n == 1)
697  // return 0;
698  // int s = get(perm, n-1);
699  // swap(perm, n-1, get(dual, n-1));
700  // swap(dual, s, n-1);
701  // return s+n*MRRank(n-1, perm, dual);
702 }
703 
704 // 53.5% time
705 uint64_t RubikEdge::MRRank2(int n, uint64_t perm, uint64_t dual)
706 {
707  if (n == 1)
708  return 0;
709  int s = get(perm, n-1);
710  swap(perm, n-1, get(dual, n-1));
711  swap(dual, s, n-1);
712  return s+n*MRRank2(n-1, perm, dual);
713 }
714 
715 void RubikEdge::GetStateFromHash(uint64_t hash, RubikEdgeState &node) const
716 {
717  int cnt = 0;
718  uint64_t bits = hash/Factorial(12);
719  uint64_t hVal = hash%Factorial(12);
720  for (int x = 10; x >= 0; x--)
721  {
722  node.SetCubeOrientation(11-x, bits&0x1);
723  cnt += bits & 0x1;
724  bits >>= 1;
725  }
726  if (1 == cnt%2)
727  {
728  node.SetCubeOrientation(11-11, true);
729  }
730  else {
731  node.SetCubeOrientation(11-11, false);
732  }
733 
734  uint64_t val = 0;
735  for (int x = 0; x < 12; x++)
736  set(val, x, x);
737  MRUnrank2(12, hVal, val);
738  for (int x = 0; x < 12; x++)
739  {
740  node.SetCubeInLoc(x, get(val, x));
741  }
742 }
743 
744 // 38.982 sec elapsed
745 // 3.5 % of time in function
746 // Overall locality: 936842 / 1800000 = 0.520468
747 void RubikEdge::MRUnrank(int n, uint64_t r, uint64_t &perm)
748 {
749  if (n > 0)
750  {
751  // printf("Swap %d %" PRId64 "\n", n-1, r%n);
752  swap(perm, n-1, r%n);
753  MRUnrank(n-1, r/n, perm);
754  }
755 }
756 
757 //38.152 sec elapsed
758 void RubikEdge::MRUnrank2(int n, uint64_t r, uint64_t &perm)
759 {
760  for (int i = n; i > 0; i--)
761  {
762  // printf("Swap %d %" PRId64 "\n", i-1, r%i);
763  swap(perm, i-1, r%i);
764  r = r/i;
765  }
766 }
767 
768 
769 // 50.970 sec elapsed
770 // 73.9% of time inside this function
771 // Overall locality: 1044342 / 1800000 = 0.580190
772 //uint64_t RubikEdge::GetStateHash(const RubikEdgeState &node) const
773 //{
774 // static uint64_t Factorial[21] =
775 // { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
776 // 6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
777 // 6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
778 //
779 // int puzzle[12];
780 // for (int x = 0; x < 12; x++)
781 // puzzle[x] = node.GetCubeInLoc(x);
782 //
783 // uint64_t hashVal = 0;
784 // int numEntriesLeft = 12;
785 // for (unsigned int x = 0; x < 12; x++)
786 // {
787 // hashVal += puzzle[x]*Factorial[numEntriesLeft-1];
788 // numEntriesLeft--;
789 // for (unsigned y = x; y < 12; y++)
790 // {
791 // if (puzzle[y] > puzzle[x])
792 // puzzle[y]--;
793 // }
794 // }
795 // for (int x = 0; x < 11; x++)
796 // {
797 // hashVal = (hashVal<<1)+node.GetCubeOrientation(x);
798 // }
799 // return hashVal;
800 //}
801 //
802 //void RubikEdge::GetStateFromHash(uint64_t hash, RubikEdgeState &node) const
803 //{
804 // int puzzle[12];
805 // uint64_t hashVal = hash;
806 //
807 // int cnt = 0;
808 // for (int x = 10; x >= 0; x--)
809 // {
810 // node.SetCubeOrientation(x, hashVal&0x1);
811 // cnt += hashVal & 0x1;
812 // hashVal >>= 1;
813 // }
814 // if (1 == cnt%2)
815 // {
816 // node.SetCubeOrientation(11, true);
817 // }
818 // int numEntriesLeft = 1;
819 // for (int x = 12-1; x >= 0; x--)
820 // {
821 // puzzle[x] = hashVal%numEntriesLeft;
822 // hashVal /= numEntriesLeft;
823 // numEntriesLeft++;
824 // for (int y = x+1; y < 12; y++)
825 // {
826 // if (puzzle[y] >= puzzle[x])
827 // puzzle[y]++;
828 // }
829 // }
830 // for (int x = 0; x < 12; x++)
831 // node.SetCubeInLoc(x, puzzle[x]);
832 //}
833 
834 void RubikEdge::OpenGLDraw() const
835 {
836 
837 }
838 
839 void RubikEdge::OpenGLDraw(const RubikEdgeState&s) const
840 {
841 // glPushMatrix();
842 // glRotatef(45, 0, 1, 0);
843  glBegin(GL_QUADS);
844  for (int x = 1; x <= 7; x+=2)
845  OpenGLDrawCube(s, x);
846 // glEnd();
847 // glPopMatrix();
848 //
849 // glBegin(GL_QUADS);
850  for (int x = 9; x <= 25; x+=2)
851  OpenGLDrawCube(s, x);
852  glEnd();
853 }
856 void RubikEdge::OpenGLDraw(const RubikEdgeState&, const RubikEdgeState&, float) const
857 {
858 
859 }
860 
861 void RubikEdge::OpenGLDraw(const RubikEdgeState&, const RubikEdgeAction&) const
862 {
863 
864 }
865 
866 void RubikEdge::OpenGLDrawCube(const RubikEdgeState &s, int cube) const
867 {
868  const float scale = 0.3;
869  const float offset = 0.95*2.0*scale/3.0;
870  const float offset2 = 2.0*scale/3.0;
871  const float epsilon = 0.002;
872  switch(cube)
873  {
874  case 1: // cube 1
875  {
876  // Face 0 - cube 1
877  SetCubeColor(3, false, s);
878  glVertex3f(-offset/2.0, -scale, -scale);
879  glVertex3f(-offset/2.0, -scale, -scale+offset);
880  glVertex3f(offset/2.0, -scale, -scale+offset);
881  glVertex3f(offset/2.0, -scale, -scale);
882 
883  SetCubeColor(-1, false, s);
884  glVertex3f(-offset2/2.0, -scale+epsilon, -scale);
885  glVertex3f(-offset2/2.0, -scale+epsilon, -scale+offset2);
886  glVertex3f(offset2/2.0, -scale+epsilon, -scale+offset2);
887  glVertex3f(offset2/2.0, -scale+epsilon, -scale);
888 
889 
890  // Face 2 - cube 1
891  SetCubeColor(3, true, s);
892  glVertex3f(-offset/2.0, -scale+offset, -scale);
893  glVertex3f(offset/2.0, -scale+offset, -scale);
894  glVertex3f(offset/2.0, -scale, -scale);
895  glVertex3f(-offset/2.0, -scale, -scale);
896 
897  SetCubeColor(-1, true, s);
898  glVertex3f(-offset2/2.0, -scale+offset2, -scale+epsilon);
899  glVertex3f(offset2/2.0, -scale+offset2, -scale+epsilon);
900  glVertex3f(offset2/2.0, -scale, -scale+epsilon);
901  glVertex3f(-offset2/2.0, -scale, -scale+epsilon);
902 
903  } break;
904  case 3: // cube 3
905  {
906  // Face 0 - cube 3
907  SetCubeColor(1, false, s);
908  glVertex3f(-scale, -scale, offset/2.0);
909  glVertex3f(-scale, -scale, -offset/2.0);
910  glVertex3f(-scale+offset, -scale, -offset/2.0);
911  glVertex3f(-scale+offset, -scale, offset/2.0);
912 
913  SetCubeColor(-1, false, s);
914  glVertex3f(-scale, -scale+epsilon, offset2/2.0);
915  glVertex3f(-scale, -scale+epsilon, -offset2/2.0);
916  glVertex3f(-scale+offset2, -scale+epsilon, -offset2/2.0);
917  glVertex3f(-scale+offset2, -scale+epsilon, offset2/2.0);
918 
919  // Face 1 - cube 3
920  SetCubeColor(1, true, s);
921  glVertex3f(-scale, -scale+offset, -offset/2.0);
922  glVertex3f(-scale, -scale+offset, offset/2.0);
923  glVertex3f(-scale, -scale, offset/2.0);
924  glVertex3f(-scale, -scale, -offset/2.0);
925 
926  SetCubeColor(-1, true, s);
927  glVertex3f(-scale+epsilon, -scale+offset2, -offset2/2.0);
928  glVertex3f(-scale+epsilon, -scale+offset2, offset2/2.0);
929  glVertex3f(-scale+epsilon, -scale, offset2/2.0);
930  glVertex3f(-scale+epsilon, -scale, -offset2/2.0);
931 
932  } break;
933  case 5: // cube 5
934  {
935  // Face 0 - cube 5
936  SetCubeColor(5, false, s);
937  glVertex3f(scale, -scale, offset/2.0);
938  glVertex3f(scale, -scale, -offset/2.0);
939  glVertex3f(scale-offset, -scale, -offset/2.0);
940  glVertex3f(scale-offset, -scale, offset/2.0);
941 
942  SetCubeColor(-1, false, s);
943  glVertex3f(scale, -scale+epsilon, offset2/2.0);
944  glVertex3f(scale, -scale+epsilon, -offset2/2.0);
945  glVertex3f(scale-offset2, -scale+epsilon, -offset2/2.0);
946  glVertex3f(scale-offset2, -scale+epsilon, offset2/2.0);
947 
948  // Face 3 - cube 5
949  SetCubeColor(5, true, s);
950  glVertex3f(scale, -scale+offset, -offset/2.0);
951  glVertex3f(scale, -scale+offset, offset/2.0);
952  glVertex3f(scale, -scale, offset/2.0);
953  glVertex3f(scale, -scale, -offset/2.0);
954 
955  SetCubeColor(-1, true, s);
956  glVertex3f(scale-epsilon, -scale+offset2, -offset2/2.0);
957  glVertex3f(scale-epsilon, -scale+offset2, offset2/2.0);
958  glVertex3f(scale-epsilon, -scale, offset2/2.0);
959  glVertex3f(scale-epsilon, -scale, -offset2/2.0);
960  } break;
961  case 7: // cube 7
962  {
963  // Face 0 - cube 7
964  SetCubeColor(7, false, s);
965  glVertex3f(-offset/2.0, -scale, scale);
966  glVertex3f(-offset/2.0, -scale, scale-offset);
967  glVertex3f(offset/2.0, -scale, scale-offset);
968  glVertex3f(offset/2.0, -scale, scale);
969 
970  SetCubeColor(-1, false, s);
971  glVertex3f(-offset2/2.0, -scale+epsilon, scale);
972  glVertex3f(-offset2/2.0, -scale+epsilon, scale-offset2);
973  glVertex3f(offset2/2.0, -scale+epsilon, scale-offset2);
974  glVertex3f(offset2/2.0, -scale+epsilon, scale);
975 
976  // Face 4 - cube 7
977  SetCubeColor(7, true, s);
978  glVertex3f(-offset/2.0, -scale+offset, scale);
979  glVertex3f(offset/2.0, -scale+offset, scale);
980  glVertex3f(offset/2.0, -scale, scale);
981  glVertex3f(-offset/2.0, -scale, scale);
982 
983  SetCubeColor(-1, true, s);
984  glVertex3f(-offset2/2.0, -scale+offset2, scale-epsilon);
985  glVertex3f(offset2/2.0, -scale+offset2, scale-epsilon);
986  glVertex3f(offset2/2.0, -scale, scale-epsilon);
987  glVertex3f(-offset2/2.0, -scale, scale-epsilon);
988 
989  } break;
990  case 9: // cube 9
991  {
992  // Face 1 - cube 9
993  SetCubeColor(2, false, s);
994  glVertex3f(-scale, -offset/2.0, -scale+offset);
995  glVertex3f(-scale, offset/2.0, -scale+offset);
996  glVertex3f(-scale, offset/2.0, -scale);
997  glVertex3f(-scale, -offset/2.0, -scale);
998 
999  SetCubeColor(-1, false, s);
1000  glVertex3f(-scale+epsilon, -offset2/2.0, -scale+offset2);
1001  glVertex3f(-scale+epsilon, offset2/2.0, -scale+offset2);
1002  glVertex3f(-scale+epsilon, offset2/2.0, -scale);
1003  glVertex3f(-scale+epsilon, -offset2/2.0, -scale);
1004 
1005 
1006  // Face 2 - cube 9
1007  SetCubeColor(2, true, s);
1008  glVertex3f(-scale+offset, -offset/2.0, -scale);
1009  glVertex3f(-scale+offset, offset/2.0, -scale);
1010  glVertex3f(-scale, offset/2.0, -scale);
1011  glVertex3f(-scale, -offset/2.0, -scale);
1012 
1013  SetCubeColor(-1, true, s);
1014  glVertex3f(-scale+offset2, -offset2/2.0, -scale+epsilon);
1015  glVertex3f(-scale+offset2, offset2/2.0, -scale+epsilon);
1016  glVertex3f(-scale, offset2/2.0, -scale+epsilon);
1017  glVertex3f(-scale, -offset2/2.0, -scale+epsilon);
1018  } break;
1019  case 11: // cube 11
1020  {
1021  // Face 2 - cube 11
1022  SetCubeColor(4, false, s);
1023  glVertex3f(scale-offset, -offset/2.0, -scale);
1024  glVertex3f(scale-offset, offset/2.0, -scale);
1025  glVertex3f(scale, offset/2.0, -scale);
1026  glVertex3f(scale, -offset/2.0, -scale);
1027 
1028  SetCubeColor(-1, false, s);
1029  glVertex3f(scale-offset2, -offset2/2.0, -scale+epsilon);
1030  glVertex3f(scale-offset2, offset2/2.0, -scale+epsilon);
1031  glVertex3f(scale, offset2/2.0, -scale+epsilon);
1032  glVertex3f(scale, -offset2/2.0, -scale+epsilon);
1033 
1034 
1035  // Face 3 - cube 11
1036  SetCubeColor(4, true, s);
1037  glVertex3f(scale, -offset/2.0, -scale+offset);
1038  glVertex3f(scale, offset/2.0, -scale+offset);
1039  glVertex3f(scale, offset/2.0, -scale);
1040  glVertex3f(scale, -offset/2.0, -scale);
1041 
1042  SetCubeColor(-1, true, s);
1043  glVertex3f(scale-epsilon, -offset2/2.0, -scale+offset2);
1044  glVertex3f(scale-epsilon, offset2/2.0, -scale+offset2);
1045  glVertex3f(scale-epsilon, offset2/2.0, -scale);
1046  glVertex3f(scale-epsilon, -offset2/2.0, -scale);
1047 
1048  } break;
1049  case 15: // cube 15
1050  {
1051  // Face 1 - cube 15
1052  SetCubeColor(8, false, s);
1053  glVertex3f(-scale, -offset/2.0, scale-offset);
1054  glVertex3f(-scale, offset/2.0, scale-offset);
1055  glVertex3f(-scale, offset/2.0, scale);
1056  glVertex3f(-scale, -offset/2.0, scale);
1057 
1058  SetCubeColor(-1, false, s);
1059  glVertex3f(-scale+epsilon, -offset2/2.0, scale-offset2);
1060  glVertex3f(-scale+epsilon, offset2/2.0, scale-offset2);
1061  glVertex3f(-scale+epsilon, offset2/2.0, scale);
1062  glVertex3f(-scale+epsilon, -offset2/2.0, scale);
1063 
1064  // Face 4 - cube 17
1065  SetCubeColor(8, true, s);
1066  glVertex3f(-scale+offset, -offset/2.0, scale);
1067  glVertex3f(-scale+offset, offset/2.0, scale);
1068  glVertex3f(-scale, offset/2.0, scale);
1069  glVertex3f(-scale, -offset/2.0, scale);
1070 
1071  SetCubeColor(-1, true, s);
1072  glVertex3f(-scale+offset2, -offset2/2.0, scale-epsilon);
1073  glVertex3f(-scale+offset2, offset2/2.0, scale-epsilon);
1074  glVertex3f(-scale, offset2/2.0, scale-epsilon);
1075  glVertex3f(-scale, -offset2/2.0, scale-epsilon);
1076 
1077  } break;
1078  case 17: // cube 17
1079  {
1080  // Face 3 - cube 17
1081  SetCubeColor(6, false, s);
1082  glVertex3f(scale, -offset/2.0, scale-offset);
1083  glVertex3f(scale, offset/2.0, scale-offset);
1084  glVertex3f(scale, offset/2.0, scale);
1085  glVertex3f(scale, -offset/2.0, scale);
1086 
1087  SetCubeColor(-1, false, s);
1088  glVertex3f(scale-epsilon, -offset2/2.0, scale-offset2);
1089  glVertex3f(scale-epsilon, offset2/2.0, scale-offset2);
1090  glVertex3f(scale-epsilon, offset2/2.0, scale);
1091  glVertex3f(scale-epsilon, -offset2/2.0, scale);
1092 
1093  // Face 4 - cube 15
1094  SetCubeColor(6, true, s);
1095  glVertex3f(scale-offset, -offset/2.0, scale);
1096  glVertex3f(scale-offset, offset/2.0, scale);
1097  glVertex3f(scale, offset/2.0, scale);
1098  glVertex3f(scale, -offset/2.0, scale);
1099 
1100  SetCubeColor(-1, true, s);
1101  glVertex3f(scale-offset2, -offset2/2.0, scale-epsilon);
1102  glVertex3f(scale-offset2, offset2/2.0, scale-epsilon);
1103  glVertex3f(scale, offset2/2.0, scale-epsilon);
1104  glVertex3f(scale, -offset2/2.0, scale-epsilon);
1105  } break;
1106  case 19: // cube 19
1107  {
1108  // Face 2 - cube 19
1109  SetCubeColor(10, false, s);
1110  glVertex3f(-offset/2.0, scale-offset, -scale);
1111  glVertex3f(offset/2.0, scale-offset, -scale);
1112  glVertex3f(offset/2.0, scale, -scale);
1113  glVertex3f(-offset/2.0, scale, -scale);
1114 
1115  SetCubeColor(-1, false, s);
1116  glVertex3f(-offset2/2.0, scale-offset2, -scale+epsilon);
1117  glVertex3f(offset2/2.0, scale-offset2, -scale+epsilon);
1118  glVertex3f(offset2/2.0, scale, -scale+epsilon);
1119  glVertex3f(-offset2/2.0, scale, -scale+epsilon);
1120 
1121  // Face 5 - cube 19
1122  SetCubeColor(10, true, s);
1123  glVertex3f(-offset/2.0, scale, -scale);
1124  glVertex3f(-offset/2.0, scale, -scale+offset);
1125  glVertex3f(offset/2.0, scale, -scale+offset);
1126  glVertex3f(offset/2.0, scale, -scale);
1127 
1128  SetCubeColor(-1, true, s);
1129  glVertex3f(-offset2/2.0, scale-epsilon, -scale);
1130  glVertex3f(-offset2/2.0, scale-epsilon, -scale+offset2);
1131  glVertex3f(offset2/2.0, scale-epsilon, -scale+offset2);
1132  glVertex3f(offset2/2.0, scale-epsilon, -scale);
1133 
1134  } break;
1135  case 21: // cube 21
1136  {
1137  // Face 1 - cube 21
1138  SetCubeColor(9, false, s);
1139  glVertex3f(-scale, scale-offset, -offset/2.0);
1140  glVertex3f(-scale, scale-offset, offset/2.0);
1141  glVertex3f(-scale, scale, offset/2.0);
1142  glVertex3f(-scale, scale, -offset/2.0);
1143 
1144  SetCubeColor(-1, false, s);
1145  glVertex3f(-scale+epsilon, scale-offset2, -offset2/2.0);
1146  glVertex3f(-scale+epsilon, scale-offset2, offset2/2.0);
1147  glVertex3f(-scale+epsilon, scale, offset2/2.0);
1148  glVertex3f(-scale+epsilon, scale, -offset2/2.0);
1149 
1150  // Face 5 - cube 21
1151  SetCubeColor(9, true, s);
1152  glVertex3f(-scale, scale, offset/2.0);
1153  glVertex3f(-scale, scale, -offset/2.0);
1154  glVertex3f(-scale+offset, scale, -offset/2.0);
1155  glVertex3f(-scale+offset, scale, offset/2.0);
1156 
1157  SetCubeColor(-1, true, s);
1158  glVertex3f(-scale, scale-epsilon, offset2/2.0);
1159  glVertex3f(-scale, scale-epsilon, -offset2/2.0);
1160  glVertex3f(-scale+offset2, scale-epsilon, -offset2/2.0);
1161  glVertex3f(-scale+offset2, scale-epsilon, offset2/2.0);
1162 
1163  } break;
1164  case 23: // cube 23
1165  {
1166  // Face 3 - cube 23
1167  SetCubeColor(11, false, s);
1168  glVertex3f(scale, scale-offset, -offset/2.0);
1169  glVertex3f(scale, scale-offset, offset/2.0);
1170  glVertex3f(scale, scale, offset/2.0);
1171  glVertex3f(scale, scale, -offset/2.0);
1172 
1173  SetCubeColor(-1, false, s);
1174  glVertex3f(scale-epsilon, scale-offset2, -offset2/2.0);
1175  glVertex3f(scale-epsilon, scale-offset2, offset2/2.0);
1176  glVertex3f(scale-epsilon, scale, offset2/2.0);
1177  glVertex3f(scale-epsilon, scale, -offset2/2.0);
1178 
1179  // Face 5 - cube 23
1180  SetCubeColor(11, true, s);
1181  glVertex3f(scale, scale, offset/2.0);
1182  glVertex3f(scale, scale, -offset/2.0);
1183  glVertex3f(scale-offset, scale, -offset/2.0);
1184  glVertex3f(scale-offset, scale, offset/2.0);
1185 
1186  SetCubeColor(-1, true, s);
1187  glVertex3f(scale, scale-epsilon, offset2/2.0);
1188  glVertex3f(scale, scale-epsilon, -offset2/2.0);
1189  glVertex3f(scale-offset2, scale-epsilon, -offset2/2.0);
1190  glVertex3f(scale-offset2, scale-epsilon, offset2/2.0);
1191 
1192  } break;
1193  case 25: // cube 25
1194  {
1195  // Face 4 - cube 25
1196  SetCubeColor(12, false, s);
1197  glVertex3f(-offset/2.0, scale-offset, scale);
1198  glVertex3f(offset/2.0, scale-offset, scale);
1199  glVertex3f(offset/2.0, scale, scale);
1200  glVertex3f(-offset/2.0, scale, scale);
1201 
1202  SetCubeColor(-1, false, s);
1203  glVertex3f(-offset2/2.0, scale-offset2, scale-epsilon);
1204  glVertex3f(offset2/2.0, scale-offset2, scale-epsilon);
1205  glVertex3f(offset2/2.0, scale, scale-epsilon);
1206  glVertex3f(-offset2/2.0, scale, scale-epsilon);
1207 
1208  // Face 5 - cube 25
1209  SetCubeColor(12, true, s);
1210  glVertex3f(-offset/2.0, scale, scale);
1211  glVertex3f(-offset/2.0, scale, scale-offset);
1212  glVertex3f(offset/2.0, scale, scale-offset);
1213  glVertex3f(offset/2.0, scale, scale);
1214 
1215  SetCubeColor(-1, true, s);
1216  glVertex3f(-offset2/2.0, scale-epsilon, scale);
1217  glVertex3f(-offset2/2.0, scale-epsilon, scale-offset2);
1218  glVertex3f(offset2/2.0, scale-epsilon, scale-offset2);
1219  glVertex3f(offset2/2.0, scale-epsilon, scale);
1220 
1221  } break;
1222  }
1223 }
1224 
1225 void RubikEdge::SetCubeColor(int which, bool face, const RubikEdgeState &s) const
1226 {
1227  int cubes_first[12] = { 0, 1, 0, 2, 0, 3, 0, 1, 1, 2, 3, 4};
1228  int cubes_second[12] = { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5};
1229 
1230  if (which == -1)
1231  {
1232  glColor3f(0.0, 0.0, 0.0);
1233  return;
1234  }
1235 
1236  int theColor = -1;
1237  int cube = s.GetCubeInLoc(which-1);
1238  if (cube == 0xF)
1239  {
1240  glColor3f(0.0, 0.0, 0.0);
1241  return;
1242  }
1243  bool flipped = s.GetCubeOrientation(cube);
1244  if (flipped == face)
1245  theColor = cubes_first[cube];
1246  else
1247  theColor = cubes_second[cube];
1248 
1249  switch (theColor)
1250  {
1251  case 0: glColor3f(1.0, 0.0, 0.0); break;
1252  case 1: glColor3f(0.0, 1.0, 0.0); break;
1253  case 2: glColor3f(0.0, 0.0, 1.0); break;
1254  case 3: glColor3f(1.0, 1.0, 0.0); break;
1255  case 4: glColor3f(1.0, 0.75, 0.0); break;
1256  case 5: glColor3f(1.0, 1.0, 1.0); break;
1257  default: assert(false);
1258  }
1259 }
1260 
1261 
1262 RubikEdgePDB::RubikEdgePDB(RubikEdge *e, const RubikEdgeState &s, std::vector<int> &distinctEdges)
1263 :PDBHeuristic(e), edges(distinctEdges), puzzles(std::thread::hardware_concurrency())
1264 {
1265  for (size_t x = 0; x < puzzles.size(); x++)
1266  puzzles[x].resize(12);
1267  SetGoal(s);
1268 }
1269 
1270 uint64_t RubikEdgePDB::GetStateSpaceSize()
1271 {
1272 #pragma message("This code belongs in the RubikEdge, not in the PDB.")
1273  return 479001600ll*2048ll;
1274 }
1275 
1276 uint64_t RubikEdgePDB::GetStateHash(const RubikEdgeState &s)
1277 {
1278  uint64_t perm = 0, dual = 0;
1279  for (int x = 0; x < 12; x++)
1280  {
1281  int val = s.GetCubeInLoc(x);
1282  set(perm, x, val);
1283  set(dual, val, x);
1284  }
1285 
1286  uint64_t hashVal = 0;
1287  for (int x = 0; x < 11; x++)
1288  {
1289  hashVal = (hashVal<<1)+s.GetCubeOrientation(11-x);
1290  }
1291  hashVal = hashVal*Factorial(12)+RubikEdge::MRRank(12, perm, dual);
1292  return hashVal;
1293 }
1294 
1295 void RubikEdgePDB::GetStateFromHash(RubikEdgeState &s, uint64_t hash)
1296 {
1297  int cnt = 0;
1298  uint64_t bits = hash/Factorial(12);
1299  uint64_t hVal = hash%Factorial(12);
1300  for (int x = 10; x >= 0; x--)
1301  {
1302  s.SetCubeOrientation(11-x, bits&0x1);
1303  cnt += bits & 0x1;
1304  bits >>= 1;
1305  }
1306  if (1 == cnt%2)
1307  {
1308  s.SetCubeOrientation(11-11, true);
1309  }
1310  else {
1311  s.SetCubeOrientation(11-11, false);
1312  }
1313 
1314  uint64_t val = 0;
1315  for (int x = 0; x < 12; x++)
1316  set(val, x, x);
1317  RubikEdge::MRUnrank2(12, hVal, val);
1318  for (int x = 0; x < 12; x++)
1319  {
1320  s.SetCubeInLoc(x, get(val, x));
1321  }
1322 }
1323 
1324 //
1325 
1326 uint64_t RubikEdgePDB::GetPDBSize() const
1327 {
1328  // last tile is symmetric
1329  uint64_t power2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 2048};
1330  int elts = (int)edges.size();
1331  return FactorialUpperK(12, 12-elts)*power2[elts];
1332 // return mr1.GetMaxRank()*power2[elts];
1333 }
1334 
1335 #define MR
1336 
1337 uint64_t RubikEdgePDB::GetPDBHash(const RubikEdgeState &s, int threadID) const
1338 {
1339 #ifdef MR
1340  int puzzle[12] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
1341  int dual[16]; // seamlessly handle 0xF entries (no cube)
1342  int newdual[16]; // seamlessly handle 0xF entries (no cube)
1343  int edgeSize = edges.size();
1344  int lastPiece = 12-(int)edgeSize;
1345  for (int x = 0; x < 12; x++)
1346  dual[s.GetCubeInLoc(x)] = x;
1347  for (int x = 0; x < edgeSize; x++)
1348  {
1349  newdual[x] = dual[edges[x]];
1350  puzzle[dual[edges[x]]] = x;
1351  }
1352  uint64_t hashVal = 0;
1353  uint64_t part2 = 0;
1354  hashVal = mr1.Rank(puzzle, newdual, edgeSize, 12);//mr1.GetRank(puzzle, threadID);
1355 
1356 
1357  int limit = std::min((int)edges.size(), 11);
1358  for (int x = 0; x < limit; x++)
1359  {
1360  part2 = part2*2+(s.GetCubeOrientation(edges[x]));
1361  }
1362  return part2*FactorialUpperK(12, lastPiece)+hashVal;
1363 #else
1364  int puzzle[12];
1365  int dual[16]; // seamlessly handle 0xF entries (no cube)
1366  int lastPiece = 12-(int)edges.size();
1367  //std::cout << "!" << s << "\n";
1368  for (int x = 0; x < 12; x++)
1369  dual[s.GetCubeInLoc(x)] = x;
1370  for (int x = 0; x < edges.size(); x++)
1371  puzzle[x] = dual[edges[x]];
1372 
1373  uint64_t hashVal = 0;
1374  uint64_t part2 = 0;
1375  int numEntriesLeft = 12;
1376  for (unsigned int x = 0; x < edges.size(); x++)
1377  {
1378  hashVal += puzzle[x]*FactorialUpperK(numEntriesLeft-1, lastPiece);
1379 
1380  numEntriesLeft--;
1381  for (unsigned y = x; y < edges.size(); y++)
1382  {
1383  if (puzzle[y] > puzzle[x])
1384  puzzle[y]--;
1385  }
1386  }
1387  int limit = std::min((int)edges.size(), 11);
1388  for (int x = 0; x < limit; x++)
1389  {
1390  part2 = part2*2+(s.GetCubeOrientation(edges[x])?1:0);
1391  //part2 = part2*3+s.GetCubeOrientation(dual[corners[x]]);
1392  }
1393  return part2*FactorialUpperK(12, lastPiece)+hashVal;
1394 #endif
1395 
1396 }
1397 
1398 void RubikEdgePDB::GetStateFromPDBHash(uint64_t hash, RubikEdgeState &s, int threadID) const
1399 {
1400 #ifdef MR
1401 
1402  int lastPiece = 12-(int)edges.size();
1403  int puzzle[12] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
1404  int dual[16] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
1405  uint64_t hashVal = hash;
1406  int edgeSize = edges.size();
1407  hash /= FactorialUpperK(12, lastPiece); // for rotations
1408  hashVal = hashVal%FactorialUpperK(12, lastPiece); // for pieces
1409 
1410  mr1.Unrank(hashVal, puzzle, dual, edgeSize, 12);
1411  for (int x = 0; x < 12; x++)
1412  {
1413  s.SetCubeInLoc(x, 0xF);
1414  s.SetCubeOrientation(x, 0);
1415  }
1416 
1417  for (int x = 0; x < edgeSize; x++)
1418  {
1419  s.SetCubeInLoc(dual[x], edges[x]);
1420  }
1421 
1422  int cnt = 0;
1423  int limit = std::min((int)edgeSize, 11);
1424  for (int x = limit-1; x >= 0; x--)
1425  {
1426  s.SetCubeOrientation(edges[x], hash%2);
1427  cnt += hash%2;
1428  hash/=2;
1429  }
1430  if (edges.size() == 12)
1431  {
1432  assert(!"Be sure to test this code");
1433  s.SetCubeOrientation(edges[11], cnt%2);
1434  }
1435 
1436 #else
1437 
1438  int lastPiece = 12-(int)edges.size();
1439  int puzzle[12];
1440  int dual[16];
1441  uint64_t hashVal = hash;
1442  hash /= FactorialUpperK(12, lastPiece); // for rotations
1443  hashVal = hashVal%FactorialUpperK(12, lastPiece); // for pieces
1444 
1445  int numEntriesLeft = lastPiece+1;
1446  for (int x = edges.size()-1; x >= 0; x--)
1447  {
1448  puzzle[x] = hashVal%numEntriesLeft;
1449  hashVal /= numEntriesLeft;
1450  numEntriesLeft++;
1451  for (int y = x+1; y < edges.size(); y++)
1452  {
1453  if (puzzle[y] >= puzzle[x])
1454  puzzle[y]++;
1455  }
1456  }
1457  for (int x = 0; x < 12; x++)
1458  {
1459  s.SetCubeInLoc(x, 0xF);
1460  s.SetCubeOrientation(x, 0);
1461  }
1462 
1463  for (int x = 0; x < edges.size(); x++)
1464  {
1465  s.SetCubeInLoc(puzzle[x], edges[x]);
1466  dual[edges[x]] = puzzle[x];
1467  }
1468 
1469  int cnt = 0;
1470  int limit = std::min((int)edges.size(), 11);
1471  for (int x = limit-1; x >= 0; x--)
1472  {
1473  s.SetCubeOrientation(edges[x], hash%2);
1474  //s.SetCubeOrientation(dual[corners[x]], hash%3);
1475  cnt += hash%2;
1476  hash/=2;
1477  }
1478  if (edges.size() == 12)
1479  s.SetCubeOrientation(edges[11], cnt%2);
1480 #endif
1481 }
1482 
1483 bool RubikEdgePDB::Load(const char *prefix)
1484 {
1485  FILE *f = fopen(GetFileName(prefix).c_str(), "rb");
1486  if (f == 0)
1487  {
1488  perror("Opening RubiksEdgePDB file");
1489  return false;
1490  }
1491  Save(f);
1492  fclose(f);
1493  return true;
1494 }
1495 
1496 void RubikEdgePDB::Save(const char *prefix)
1497 {
1498  FILE *f = fopen(GetFileName(prefix).c_str(), "w+");
1499  if (f == 0)
1500  {
1501  perror("Opening RubiksEdgePDB file");
1502  return;
1503  }
1504  Save(f);
1505  fclose(f);
1506 }
1507 
1508 bool RubikEdgePDB::Load(FILE *f)
1509 {
1510  if (PDBHeuristic<RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4>::Load(f) != true)
1511  {
1512  return false;
1513  }
1514  if (fread(&puzzleSize, sizeof(puzzleSize), 1, f) != 1)
1515  return false;
1516  if (fread(&pdbSize, sizeof(pdbSize), 1, f) != 1)
1517  return false;
1518  size_t edgeSize = edges.size();
1519  if (fread(&edgeSize, sizeof(edgeSize), 1, f) != 1)
1520  return false;
1521  edges.resize(edgeSize);
1522  if (fread(&edges[0], sizeof(edges[0]), edges.size(), f) != edgeSize)
1523  return false;
1524  return true;
1525 }
1526 
1527 void RubikEdgePDB::Save(FILE *f)
1528 {
1529  PDBHeuristic<RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4>::Save(f);
1530  fwrite(&puzzleSize, sizeof(puzzleSize), 1, f);
1531  fwrite(&pdbSize, sizeof(pdbSize), 1, f);
1532  size_t edgeSize = edges.size();
1533  fwrite(&edgeSize, sizeof(edgeSize), 1, f);
1534  fwrite(&edges[0], sizeof(edges[0]), edges.size(), f);
1535 }
1536 
1537 std::string RubikEdgePDB::GetFileName(const char *prefix)
1538 {
1539  std::string fileName;
1540  fileName += "RC-E-";
1541  // denote the origin state from which the PDB is computed
1542  for (int x = 0; x < 12; x++)
1543  {
1544  fileName += std::to_string(goalState[0].GetCubeInLoc(x));
1545  fileName += ".";
1546  fileName += std::to_string(goalState[0].GetCubeOrientation(goalState[0].GetCubeInLoc(x)));
1547  fileName += ";";
1548  }
1549  fileName.pop_back();
1550  fileName += "-";
1551  // denote the pattern used for the PDB
1552  for (size_t x = 0; x < edges.size(); x++)
1553  {
1554  fileName += std::to_string(edges[x]);
1555  fileName += ";";
1556  }
1557  fileName.pop_back(); // remove colon
1558 #ifdef MR
1559  fileName += "-MR";
1560 #endif
1561  if (std::is_same<RubikEdgeStateArray,RubikEdgeState>::value)
1562  {
1563  fileName += "-AR";
1564  }
1565  fileName += ".pdb";
1566 
1567  return fileName;
1568 }
1569 
1570 uint64_t RubikEdgePDB::Factorial(int val)
1571 {
1572  static uint64_t table[21] =
1573  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
1574  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
1575  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
1576  if (val > 20)
1577  return (uint64_t)-1;
1578  return table[val];
1579 }
1580 
1581 uint64_t RubikEdgePDB::FactorialUpperK(int n, int k)
1582 {
1583  const uint64_t result[13][13] = {
1584  {1}, // n = 0
1585  {1, 1}, // n = 1
1586  {2, 2, 1}, // n = 2
1587  {6, 6, 3, 1}, // n = 3
1588  {24, 24, 12, 4, 1}, // n = 4
1589  {120, 120, 60, 20, 5, 1}, // n = 5
1590  {720, 720, 360, 120, 30, 6, 1}, // n = 6
1591  {5040, 5040, 2520, 840, 210, 42, 7, 1}, // n = 7
1592  {40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1}, // n = 8
1593  {362880, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1}, // n = 9
1594  {3628800, 3628800, 1814400, 604800, 151200, 30240, 5040, 720, 90, 10, 1}, // n = 10
1595  {39916800, 39916800, 19958400, 6652800, 1663200, 332640, 55440, 7920, 990, 110, 11, 1}, // n = 11
1596  {479001600, 479001600, 239500800, 79833600, 19958400, 3991680, 665280, 95040, 11880, 1320, 132, 12, 1} // n = 12
1597  };
1598  return result[n][k];
1599 // uint64_t value = 1;
1600 // assert(n >= 0 && k >= 0);
1601 //
1602 // for (int i = n; i > k; i--)
1603 // {
1604 // value *= i;
1605 // }
1606 //
1607 // return value;
1608 }
1609 
1610 
1611 #pragma mark orientation pdb
1612 
1613 RubikEdgeOrientationPDB::RubikEdgeOrientationPDB(RubikEdge *e, const RubikEdgeState &s)
1614 :PDBHeuristic(e)
1615 {
1616  SetGoal(s);
1617 }
1618 
1619 uint64_t RubikEdgeOrientationPDB::GetStateSpaceSize()
1620 {
1621 #pragma message("This code belongs in the RubikEdge, not in the PDB.")
1622  return 2048ll;
1623 }
1624 
1625 uint64_t RubikEdgeOrientationPDB::GetStateHash(const RubikEdgeState &s)
1626 {
1627  uint64_t hashVal = 0;
1628  for (int x = 0; x < 11; x++)
1629  {
1630  hashVal = (hashVal<<1)+s.GetCubeOrientation(11-x);
1631  }
1632  return hashVal;
1633 }
1634 
1635 void RubikEdgeOrientationPDB::GetStateFromHash(RubikEdgeState &s, uint64_t hash)
1636 {
1637  int cnt = 0;
1638  for (int x = 10; x >= 0; x--)
1639  {
1640  s.SetCubeOrientation(11-x, hash&0x1);
1641  cnt += hash & 0x1;
1642  hash >>= 1;
1643  }
1644  if (1 == cnt%2)
1645  {
1646  s.SetCubeOrientation(0, true);
1647  }
1648  else {
1649  s.SetCubeOrientation(0, false);
1650  }
1651 }
1652 
1653 //
1654 
1655 uint64_t RubikEdgeOrientationPDB::GetPDBSize() const
1656 {
1657  return 1<<11;
1658 }
1659 
1660 uint64_t RubikEdgeOrientationPDB::GetPDBHash(const RubikEdgeState &s, int threadID) const
1661 {
1662  return GetStateHash(s);
1663 }
1664 
1665 void RubikEdgeOrientationPDB::GetStateFromPDBHash(uint64_t hash, RubikEdgeState &s, int threadID) const
1666 {
1667  return GetStateFromHash(s, hash);
1668 }
1669 
1670 bool RubikEdgeOrientationPDB::Load(const char *prefix)
1671 {
1672  FILE *f = fopen(GetFileName(prefix).c_str(), "rb");
1673  if (f == 0)
1674  {
1675  perror("Opening RubiksEdgePDB file");
1676  return false;
1677  }
1678  Save(f);
1679  fclose(f);
1680  return true;
1681 }
1682 
1683 void RubikEdgeOrientationPDB::Save(const char *prefix)
1684 {
1685  FILE *f = fopen(GetFileName(prefix).c_str(), "w+");
1686  if (f == 0)
1687  {
1688  perror("Opening RubiksEdgePDB file");
1689  return;
1690  }
1691  Save(f);
1692  fclose(f);
1693 }
1694 
1695 bool RubikEdgeOrientationPDB::Load(FILE *f)
1696 {
1697  if (PDBHeuristic<RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4>::Load(f) != true)
1698  {
1699  return false;
1700  }
1701  return true;
1702 }
1703 
1704 void RubikEdgeOrientationPDB::Save(FILE *f)
1705 {
1706  PDBHeuristic<RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4>::Save(f);
1707 }
1708 
1709 std::string RubikEdgeOrientationPDB::GetFileName(const char *prefix)
1710 {
1711  std::string fileName;
1712  fileName += "RC-E12-OR.pdb";
1713  return fileName;
1714 }
RubikEdgePDB::GetStateFromPDBHash
void GetStateFromPDBHash(uint64_t hash, RubikEdgeState &s, int threadID=0) const
Definition: RubiksCubeEdges.cpp:1398
RubikEdgeOrientationPDB::GetPDBSize
uint64_t GetPDBSize() const
Definition: RubiksCubeEdges.cpp:1655
RubikEdgePDB::mr1
MR1KPermutation mr1
Definition: RubiksCubeEdges.h:225
RubikEdgeStateBits::GetCubeInLoc
int GetCubeInLoc(int whichLoc) const
Definition: RubiksCubeEdges.cpp:76
RubikEdgeOrientationPDB::GetStateFromHash
static void GetStateFromHash(RubikEdgeState &s, uint64_t hash)
Definition: RubiksCubeEdges.cpp:1635
RubikEdgeAction
int RubikEdgeAction
Definition: RubiksCubeEdges.h:116
LocalApplyAction
void LocalApplyAction(t &s, RubikEdgeAction a)
Definition: RubiksCubeEdges.cpp:259
min
double min(double a, double b)
Definition: FPUtil.h:35
RubikEdgePDB::GetFileName
std::string GetFileName(const char *prefix)
Definition: RubiksCubeEdges.cpp:1537
RubikEdge::InvertAction
virtual bool InvertAction(RubikEdgeAction &a) const
Definition: RubiksCubeEdges.cpp:533
set
void set(uint64_t &state, int whichLoc, int cube)
Definition: RubiksCubeEdges.cpp:574
RubikEdge::UndoAction
virtual void UndoAction(RubikEdgeStateArray &s, RubikEdgeAction a) const
Definition: RubiksCubeEdges.cpp:244
RubikEdgePDB::GetStateHash
static uint64_t GetStateHash(const RubikEdgeState &s)
Definition: RubiksCubeEdges.cpp:1276
RubikEdgeStateArray::state
uint8_t state[24]
Definition: RubiksCubeEdges.h:52
RubikEdgeStateArray::Clear
void Clear()
Definition: RubiksCubeEdges.cpp:132
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
RubikEdgeStateArray::FlipCubeOrientation
void FlipCubeOrientation(int whichLoc)
Definition: RubiksCubeEdges.cpp:167
swap
void swap(uint64_t &state, int loc1, int loc2)
Definition: RubiksCubeEdges.cpp:582
RotateRubikEdgeClockwise
RubikEdgeState RotateRubikEdgeClockwise(const RubikEdgeState &in, int step)
Implementation details:
Definition: RubiksCubeEdges.cpp:43
RubikEdgePDB::Load
bool Load(const char *prefix)
Definition: RubiksCubeEdges.cpp:1483
RubikEdge::OpenGLDraw
virtual void OpenGLDraw() const
Definition: RubiksCubeEdges.cpp:834
RubikEdgeOrientationPDB::GetStateHash
static uint64_t GetStateHash(const RubikEdgeState &s)
Definition: RubiksCubeEdges.cpp:1625
RubikEdgeOrientationPDB::GetStateFromPDBHash
void GetStateFromPDBHash(uint64_t hash, RubikEdgeState &s, int threadID=0) const
Definition: RubiksCubeEdges.cpp:1665
RubikEdgeOrientationPDB::GetFileName
std::string GetFileName(const char *prefix)
Definition: RubiksCubeEdges.cpp:1709
PDBHeuristic< RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4 >::goalState
std::vector< RubikEdgeState > goalState
Definition: PDBHeuristic.h:129
RubikEdgeMove
Definition: RubiksCubeEdges.h:118
RubikEdgeStateBits::RubikEdgeStateBits
RubikEdgeStateBits()
Definition: RubiksCubeEdges.cpp:62
RubikEdgeStateArray::SetCubeInLoc
void SetCubeInLoc(int whichLoc, int cube)
Definition: RubiksCubeEdges.cpp:141
RubikEdge::MRUnrank
static void MRUnrank(int n, uint64_t r, uint64_t &perm)
Definition: RubiksCubeEdges.cpp:747
RubikEdgeStateBits::FlipCubeOrientation
void FlipCubeOrientation(int whichLoc)
Definition: RubiksCubeEdges.cpp:103
RubikEdge::rankPlayerFirstTwo
void rankPlayerFirstTwo(const RubikEdgeState &s, int who, int64_t &rank)
Definition: RubiksCubeEdges.cpp:619
RubikEdge::GetNextState
virtual void GetNextState(const RubikEdgeState &, RubikEdgeAction, RubikEdgeState &) const
Definition: RubiksCubeEdges.cpp:527
RubikEdge::GoalTest
virtual bool GoalTest(const RubikEdgeState &node, const RubikEdgeState &goal) const
Definition: RubiksCubeEdges.h:152
RubikEdge::MRRank
static uint64_t MRRank(int n, uint64_t perm, uint64_t dual)
Definition: RubiksCubeEdges.cpp:668
RubikEdgeStateArray::Reset
void Reset()
Definition: RubiksCubeEdges.cpp:124
RubikEdgePDB::Factorial
static uint64_t Factorial(int val)
Definition: RubiksCubeEdges.cpp:1570
RubikEdgePDB::edges
std::vector< int > edges
Definition: RubiksCubeEdges.h:222
RubikEdge
Definition: RubiksCubeEdges.h:125
RubikEdgePDB::puzzleSize
size_t puzzleSize
Definition: RubiksCubeEdges.h:223
RubikEdgeStateArray::GetCubeInLoc
int GetCubeInLoc(int whichLoc) const
Definition: RubiksCubeEdges.cpp:136
RubikEdgeStateBits::GetDual
void GetDual(RubikEdgeStateBits &s) const
Definition: RubiksCubeEdges.cpp:110
RubikEdgeStateBits::SetCubeInLoc
void SetCubeInLoc(int whichLoc, int cube)
Definition: RubiksCubeEdges.cpp:80
RubikEdge::rankPlayerRemaining
void rankPlayerRemaining(const RubikEdgeState &s, int who, int64_t &rank)
Definition: RubiksCubeEdges.cpp:628
PDBHeuristic
Definition: PDBHeuristic.h:39
RubikEdgeStateBits::SetCubeOrientation
void SetCubeOrientation(int whichLoc, bool flip)
Definition: RubiksCubeEdges.cpp:93
RubikEdgeOrientationPDB::GetPDBHash
uint64_t GetPDBHash(const RubikEdgeState &s, int threadID=0) const
Definition: RubiksCubeEdges.cpp:1660
RubikEdgeStateArray::RubikEdgeStateArray
RubikEdgeStateArray()
Definition: RubiksCubeEdges.cpp:120
RubikEdge::getMaxSinglePlayerRank
int64_t getMaxSinglePlayerRank() const
Definition: RubiksCubeEdges.cpp:598
RubikEdge::OpenGLDrawCube
void OpenGLDrawCube(const RubikEdgeState &s, int cube) const
Definition: RubiksCubeEdges.cpp:866
RubikEdge::ApplyAction
virtual void ApplyAction(RubikEdgeStateArray &s, RubikEdgeAction a) const
Definition: RubiksCubeEdges.cpp:516
PDBHeuristic::Save
virtual void Save(const char *prefix)=0
RubiksCubeEdges.h
RubikEdge::MRUnrank2
static void MRUnrank2(int n, uint64_t r, uint64_t &perm)
Definition: RubiksCubeEdges.cpp:758
RubikEdgeOrientationPDB::GetStateSpaceSize
static uint64_t GetStateSpaceSize()
Definition: RubiksCubeEdges.cpp:1619
RubikEdge::GetSuccessors
virtual void GetSuccessors(const RubikEdgeState &nodeID, std::vector< RubikEdgeState > &neighbors) const
Definition: RubiksCubeEdges.cpp:185
RubikEdge::MRRank2
static uint64_t MRRank2(int n, uint64_t perm, uint64_t dual)
Definition: RubiksCubeEdges.cpp:705
Factorial
uint64_t Factorial(int n)
Definition: RubiksCubeEdges.cpp:559
GLUtil.h
RubikEdgeMove::act
RubikEdgeAction act
Definition: RubiksCubeEdges.h:120
PDBHeuristic< RubikEdgeState, RubikEdgeAction, RubikEdge, RubikEdgeState, 4 >::SetGoal
void SetGoal(const RubikEdgeState &goal)
Definition: PDBHeuristic.h:45
RubikEdgeStateArray
Definition: RubiksCubeEdges.h:37
RubikEdge::GetAction
virtual RubikEdgeAction GetAction(const RubikEdgeState &s1, const RubikEdgeState &s2) const
Definition: RubiksCubeEdges.cpp:204
RubikEdge::SetCubeColor
void SetCubeColor(int which, bool face, const RubikEdgeState &) const
Definition: RubiksCubeEdges.cpp:1225
RubikEdgeStateBits::GetCubeOrientation
bool GetCubeOrientation(int whichLoc) const
Definition: RubiksCubeEdges.cpp:89
RubikEdge::ApplyMove
void ApplyMove(RubikEdgeState &s, RubikEdgeMove *a)
Definition: RubiksCubeEdges.cpp:211
MR1KPermutation::Unrank
void Unrank(uint64_t hash, int *items, int *dual, int k, int N) const
Given the hash returns the state and its dual.
Definition: MR1Permutation.cpp:68
RubikEdgeStateArray::SetCubeOrientation
void SetCubeOrientation(int whichLoc, bool flip)
Definition: RubiksCubeEdges.cpp:156
RubikEdge::getMaxSinglePlayerRank2
int64_t getMaxSinglePlayerRank2()
Definition: RubiksCubeEdges.cpp:609
RubikEdgeStateBits::Reset
void Reset()
Definition: RubiksCubeEdges.cpp:66
RubikEdgePDB::RubikEdgePDB
RubikEdgePDB(RubikEdge *e, const RubikEdgeState &s, std::vector< int > &distinctEdges)
Definition: RubiksCubeEdges.cpp:1262
RubikEdgePDB::puzzles
std::vector< std::vector< int > > puzzles
Definition: RubiksCubeEdges.h:227
RubikEdgePDB::GetStateFromHash
static void GetStateFromHash(RubikEdgeState &s, uint64_t hash)
Definition: RubiksCubeEdges.cpp:1295
RubikEdgeStateBits::Clear
void Clear()
Definition: RubiksCubeEdges.cpp:72
std
Definition: CanonicalGraphEnvironment.h:26
RubikEdgePDB::FactorialUpperK
static uint64_t FactorialUpperK(int n, int k)
Definition: RubiksCubeEdges.cpp:1581
RubikEdgePDB::GetStateSpaceSize
static uint64_t GetStateSpaceSize()
Definition: RubiksCubeEdges.cpp:1270
RubikEdge::GetActions
virtual void GetActions(const RubikEdgeState &nodeID, std::vector< RubikEdgeAction > &actions) const
Definition: RubiksCubeEdges.cpp:195
RubikEdgeStateArray::GetCubeOrientation
bool GetCubeOrientation(int whichLoc) const
Definition: RubiksCubeEdges.cpp:151
RubikEdgePDB::GetPDBSize
uint64_t GetPDBSize() const
Definition: RubiksCubeEdges.cpp:1326
RubikEdgeOrientationPDB::RubikEdgeOrientationPDB
RubikEdgeOrientationPDB(RubikEdge *e, const RubikEdgeState &s)
Definition: RubiksCubeEdges.cpp:1613
RubikEdgeStateBits
Definition: RubiksCubeEdges.h:19
MR1KPermutation::Rank
uint64_t Rank(int *items, int *dual, int k, int N) const
Definition: MR1Permutation.cpp:21
RubikEdge::UndoMove
void UndoMove(RubikEdgeState &s, RubikEdgeMove *a)
Definition: RubiksCubeEdges.cpp:216
RubikEdge::GetStateHash
virtual uint64_t GetStateHash(const RubikEdgeState &node) const
Definition: RubiksCubeEdges.cpp:647
RubikEdgeOrientationPDB::Save
void Save(const char *prefix)
Definition: RubiksCubeEdges.cpp:1683
RubikEdgePDB::GetPDBHash
uint64_t GetPDBHash(const RubikEdgeState &s, int threadID=0) const
Definition: RubiksCubeEdges.cpp:1337
RubikEdgePDB::pdbSize
uint64_t pdbSize
Definition: RubiksCubeEdges.h:224
get
int get(uint64_t state, int whichLoc)
Definition: RubiksCubeEdges.cpp:569
RubikEdgeOrientationPDB::Load
bool Load(const char *prefix)
Definition: RubiksCubeEdges.cpp:1670
RubikEdgeStateBits::state
uint64_t state
Definition: RubiksCubeEdges.h:34
RubikEdgeStateArray::GetDual
void GetDual(RubikEdgeStateArray &s) const
Definition: RubiksCubeEdges.cpp:175
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
bits
constexpr uint64_t bits(uint64_t a, uint64_t b, uint64_t c)
Definition: Hexagon.cpp:16
RubikEdge::GetStateFromHash
virtual void GetStateFromHash(uint64_t hash, RubikEdgeState &node) const
Definition: RubiksCubeEdges.cpp:715
RubikEdgePDB::Save
void Save(const char *prefix)
Definition: RubiksCubeEdges.cpp:1496
Generated by   doxygen 1.8.17