HOG2
RubiksCubeCorners.cpp
Go to the documentation of this file.
1 //
2 // RubiksCorner.cpp
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 1/11/13.
6 // Copyright (c) 2013 University of Denver. All rights reserved.
7 //
8 
9 #include "RubiksCubeCorners.h"
10 #include "GLUtil.h"
11 #include <assert.h>
12 
13 #define LINEAR_RANK 1
14 #define POLYNOMIAL_RANK 0
15 
105 inline int get(uint64_t state, int whichLoc)
106 {
107  //return (state>>(4*whichLoc))&0xF;
108  return (state>>((whichLoc<<2)))&0xF;
109 }
110 
111 inline void set(uint64_t &state, int whichLoc, int cube)
112 {
113  const uint64_t blank = 0xF;
114  uint64_t value = cube;//&0xF;
115  state = state&(~(blank<<((whichLoc<<2))));
116  state |= (value<<((whichLoc<<2)));
117 }
118 
119 inline void swap(uint64_t &state, int loc1, int loc2)
120 {
121  loc1<<=2;
122  loc2<<=2;
123  uint64_t val1 = (state>>(loc1));
124  uint64_t val2 = (state>>(loc2));
125 
126  // more efficient here
127  uint64_t xord = (val1 ^ val2)&0xF;
128  xord = (xord << loc1) | (xord << loc2);
129  state = state^xord;
130 
131 // const uint64_t blank = 0xF;
132 // uint64_t mask = (blank<<(loc1))|(blank<<(loc2));
133 // state = state&(~mask);
134 // state = state|(val1<<(loc2))|(val2<<(loc1));
135 }
136 
137 RubiksCornerStateBits::RubiksCornerStateBits()
138 {
139  Reset();
140 }
141 void RubiksCornerStateBits::Reset()
142 {
143  state = 0;
144  for (int x = 0; x < 8; x++)
145  {
146  SetCubeInLoc(x, x);
147  }
148 }
149 
150 int RubiksCornerStateBits::GetCubeInLoc(unsigned int whichLoc) const
151 {
152  assert(whichLoc < 8);
153  return (state>>(16+4*whichLoc))&0xF;
154 }
155 void RubiksCornerStateBits::SetCubeInLoc(unsigned int whichLoc, int cube)
156 {
157  assert(whichLoc < 8);
158  uint64_t blank = 0xF;
159  uint64_t value = cube&0xF;
160  state = state&(~(blank<<(16+4*whichLoc)));
161  state |= (value<<(16+4*whichLoc));
162 }
163 uint64_t RubiksCornerStateBits::GetCubeOrientation(unsigned int whichLoc) const
164 {
165 // assert(whichLoc < 8);
166  if (whichLoc > 8)
167  { return 0x3;}
168  return (state>>(2*whichLoc))&0x3;
169 }
170 void RubiksCornerStateBits::SetCubeOrientation(unsigned int whichLoc, int orient) // orientation is the offset of the 0(low) side
171 {
172  if (whichLoc > 8)
173  return;
174  //assert(whichLoc < 8);
175  uint64_t blank = 0x3;
176  uint64_t value = orient&0x3;
177  state = state&(~(blank<<(2*whichLoc)));
178  state |= (value<<(2*whichLoc));
179 }
180 int RubiksCornerStateBits::GetFaceInLoc(unsigned int whichLoc) const // loc 0...24
181 {
182  assert(whichLoc < 8);
183  int cube = GetCubeInLoc(whichLoc/3);
184  int rot = (int)GetCubeOrientation(cube);
185  return cube*3+(3+(whichLoc%3)-rot)%3;
186 }
187 
188 
189 void RubiksCornerStateBits::Rotate(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
190 {
191  a = (a<<2) + 16; // multiply by 4 for shifting purposes; add 16 for rotations
192  b = (b<<2) + 16;
193  c = (c<<2) + 16;
194  d = (d<<2) + 16;
195 
196  const uint64_t blank = 0xF;
197 
198  uint64_t mask;
199  uint64_t bits;
200  bits =
201  (((state>>a)&blank)<<b)|(((state>>b)&blank)<<c)|
202  (((state>>c)&blank)<<d)|(((state>>d)&blank)<<a);
203  mask = (blank<<(a))|(blank<<(b))|(blank<<(c))|(blank<<(d));
204  state = (state&(~mask))|bits;
205 }
206 
207 void RubiksCornerStateBits::Swap(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
208 {
209  a = (a<<2) + 16; // multiply by 4 for shifting purposes; add 16 for rotations
210  b = (b<<2) + 16;
211  c = (c<<2) + 16;
212  d = (d<<2) + 16;
213 
214  const uint64_t blank = 0xF;
215 
216  uint64_t mask;
217  uint64_t bits;
218  bits =
219  (((state>>a)&blank)<<b)|(((state>>b)&blank)<<a)|
220  (((state>>c)&blank)<<d)|(((state>>d)&blank)<<c);
221  mask = (blank<<(a))|(blank<<(b))|(blank<<(c))|(blank<<(d));
222  state = (state&(~mask))|bits;
223 }
224 
225 RubiksCornerStateArray::RubiksCornerStateArray()
226 {
227  Reset();
228 }
229 void RubiksCornerStateArray::Reset()
230 {
231  for (int x = 8; x < 16; x++)
232  state[x] = 0;
233  for (int x = 0; x < 8; x++)
234  {
235  SetCubeInLoc(x, x);
236  }
237 }
238 int RubiksCornerStateArray::GetCubeInLoc(unsigned int whichLoc) const
239 {
240  assert(whichLoc < 8);
241  return state[whichLoc];
242 }
243 void RubiksCornerStateArray::SetCubeInLoc(unsigned int whichLoc, int cube)
244 {
245  assert(whichLoc < 8);
246  state[whichLoc] = cube;
247 }
248 uint64_t RubiksCornerStateArray::GetCubeOrientation(unsigned int whichLoc) const
249 {
250  if (whichLoc > 8)
251  { return 0x3;}
252  return state[whichLoc+8];
253 }
254 void RubiksCornerStateArray::SetCubeOrientation(unsigned int whichLoc, int orient) // orientation is the offset of the 0(low) side
255 {
256  if (whichLoc > 8)
257  return;
258  state[whichLoc+8] = orient;
259 }
260 int RubiksCornerStateArray::GetFaceInLoc(unsigned int whichLoc) const // loc 0...24
261 {
262  int cube = GetCubeInLoc(whichLoc/3);
263  int rot = (int)GetCubeOrientation(cube);
264  return cube*3+(3+(whichLoc%3)-rot)%3;
265 }
266 void RubiksCornerStateArray::Rotate(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
267 {
268  uint8_t tmp = state[d];
269  state[d] = state[c];
270  state[c] = state[b];
271  state[b] = state[a];
272  state[a] = tmp;
273 }
274 
275 void RubiksCornerStateArray::Swap(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
276 {
277  uint8_t tmp = state[a];
278  state[a] = state[b];
279  state[b] = tmp;
280 
281  tmp = state[c];
282  state[c] = state[d];
283  state[d] = tmp;
284 }
285 
286 
287 
288 
289 void RubiksCorner::GetSuccessors(const RubiksCornerState &nodeID, std::vector<RubiksCornerState> &neighbors) const
290 {
291  RubiksCornerState s;
292  for (int x = 0; x < 18; x++)
293  {
294  GetNextState(nodeID, x, s);
295  neighbors.push_back(s);
296  }
297 }
298 
299 void RubiksCorner::GetActions(const RubiksCornerState &nodeID, std::vector<RubiksCornersAction> &actions) const
300 {
301  actions.resize(0);
302  for (int x = 0; x < 18; x++)
303  {
304  actions.push_back(x);
305  }
306 }
307 
308 RubiksCornersAction RubiksCorner::GetAction(const RubiksCornerState &s1, const RubiksCornerState &s2) const
309 {
310  assert(false);
311  RubiksCornersAction a;
312  return a;
313 }
314 
315 void RubiksCorner::ApplyAction(RubiksCornerState &s, RubiksCornersAction a) const
316 {
317  switch (a)
318  {
319  case 0: // face 0
320  {
321  s.Rotate(0, 1, 2, 3);
322  }
323  break;
324  case 1:
325  {
326  s.Rotate(3, 2, 1, 0);
327  }
328  break;
329  case 2:
330  {
331  s.Swap(0, 2, 1, 3);
332  }
333  break;
334  case 3: // face 5
335  {
336  s.Rotate(4, 5, 6, 7);
337  }
338  break;
339  case 4:
340  {
341  s.Rotate(7, 6, 5, 4);
342  }
343  break;
344  case 5:
345  {
346  s.Swap(4, 6, 5, 7);
347  }
348  break;
349 
350  case 6: // face 2
351  {
352  s.Rotate(0, 1, 5, 4);
353  s.SetCubeOrientation(s.GetCubeInLoc(1), (s.GetCubeOrientation(s.GetCubeInLoc(1))+2)%3);
354  s.SetCubeOrientation(s.GetCubeInLoc(5), (s.GetCubeOrientation(s.GetCubeInLoc(5))+1)%3);
355  s.SetCubeOrientation(s.GetCubeInLoc(4), (s.GetCubeOrientation(s.GetCubeInLoc(4))+2)%3);
356  s.SetCubeOrientation(s.GetCubeInLoc(0), (s.GetCubeOrientation(s.GetCubeInLoc(0))+1)%3);
357  }
358  break;
359  case 7:
360  {
361  s.Rotate(4, 5, 1, 0);
362  s.SetCubeOrientation(s.GetCubeInLoc(1), (s.GetCubeOrientation(s.GetCubeInLoc(1))+2)%3);
363  s.SetCubeOrientation(s.GetCubeInLoc(5), (s.GetCubeOrientation(s.GetCubeInLoc(5))+1)%3);
364  s.SetCubeOrientation(s.GetCubeInLoc(4), (s.GetCubeOrientation(s.GetCubeInLoc(4))+2)%3);
365  s.SetCubeOrientation(s.GetCubeInLoc(0), (s.GetCubeOrientation(s.GetCubeInLoc(0))+1)%3);
366  }
367  break;
368  case 8:
369  {
370  s.Swap(0, 5, 1, 4);
371  }
372  break;
373 
374  case 9: // face 4
375  {
376  s.Rotate(2, 3, 7, 6);
377  //std::cout << "^" << s << "\n";
378  s.SetCubeOrientation(s.GetCubeInLoc(3), (s.GetCubeOrientation(s.GetCubeInLoc(3))+2)%3);
379  //std::cout << "^" << s << "\n";
380  s.SetCubeOrientation(s.GetCubeInLoc(2), (s.GetCubeOrientation(s.GetCubeInLoc(2))+1)%3);
381  //std::cout << "^" << s << "\n";
382  s.SetCubeOrientation(s.GetCubeInLoc(6), (s.GetCubeOrientation(s.GetCubeInLoc(6))+2)%3);
383  //std::cout << "^" << s << "\n";
384  s.SetCubeOrientation(s.GetCubeInLoc(7), (s.GetCubeOrientation(s.GetCubeInLoc(7))+1)%3);
385  //std::cout << "^" << s << "\n";
386  }
387  break;
388  case 10:
389  {
390  s.Rotate(6, 7, 3, 2);
391  //std::cout << "*" << s << "\n";
392  s.SetCubeOrientation(s.GetCubeInLoc(3), (s.GetCubeOrientation(s.GetCubeInLoc(3))+2)%3);
393  //std::cout << "*" << s << "\n";
394  s.SetCubeOrientation(s.GetCubeInLoc(2), (s.GetCubeOrientation(s.GetCubeInLoc(2))+1)%3);
395  //std::cout << "*" << s << "\n";
396  s.SetCubeOrientation(s.GetCubeInLoc(6), (s.GetCubeOrientation(s.GetCubeInLoc(6))+2)%3);
397  //std::cout << "*" << s << "\n";
398  s.SetCubeOrientation(s.GetCubeInLoc(7), (s.GetCubeOrientation(s.GetCubeInLoc(7))+1)%3);
399  //std::cout << "*" << s << "\n";
400  }
401  break;
402  case 11:
403  {
404  s.Swap(6, 3, 2, 7);
405  }
406  break;
407 
408  case 12: // face 1
409  {
410  s.Rotate(0, 4, 7, 3);
411  s.SetCubeOrientation(s.GetCubeInLoc(0), (s.GetCubeOrientation(s.GetCubeInLoc(0))+2)%3);
412  s.SetCubeOrientation(s.GetCubeInLoc(4), (s.GetCubeOrientation(s.GetCubeInLoc(4))+1)%3);
413  s.SetCubeOrientation(s.GetCubeInLoc(7), (s.GetCubeOrientation(s.GetCubeInLoc(7))+2)%3);
414  s.SetCubeOrientation(s.GetCubeInLoc(3), (s.GetCubeOrientation(s.GetCubeInLoc(3))+1)%3);
415  }
416  break;
417  case 13:
418  {
419  s.Rotate(3, 7, 4, 0);
420  s.SetCubeOrientation(s.GetCubeInLoc(0), (s.GetCubeOrientation(s.GetCubeInLoc(0))+2)%3);
421  s.SetCubeOrientation(s.GetCubeInLoc(4), (s.GetCubeOrientation(s.GetCubeInLoc(4))+1)%3);
422  s.SetCubeOrientation(s.GetCubeInLoc(7), (s.GetCubeOrientation(s.GetCubeInLoc(7))+2)%3);
423  s.SetCubeOrientation(s.GetCubeInLoc(3), (s.GetCubeOrientation(s.GetCubeInLoc(3))+1)%3);
424  }
425  break;
426  case 14:
427  {
428  s.Swap(0, 7, 4, 3);
429  }
430  break;
431  case 15: // face 3
432  {
433  s.Rotate(1, 2, 6, 5);
434  s.SetCubeOrientation(s.GetCubeInLoc(2), (s.GetCubeOrientation(s.GetCubeInLoc(2))+2)%3);
435  s.SetCubeOrientation(s.GetCubeInLoc(6), (s.GetCubeOrientation(s.GetCubeInLoc(6))+1)%3);
436  s.SetCubeOrientation(s.GetCubeInLoc(5), (s.GetCubeOrientation(s.GetCubeInLoc(5))+2)%3);
437  s.SetCubeOrientation(s.GetCubeInLoc(1), (s.GetCubeOrientation(s.GetCubeInLoc(1))+1)%3);
438  }
439  break;
440  case 16:
441  {
442  s.Rotate(5, 6, 2, 1);
443  s.SetCubeOrientation(s.GetCubeInLoc(2), (s.GetCubeOrientation(s.GetCubeInLoc(2))+2)%3);
444  s.SetCubeOrientation(s.GetCubeInLoc(6), (s.GetCubeOrientation(s.GetCubeInLoc(6))+1)%3);
445  s.SetCubeOrientation(s.GetCubeInLoc(5), (s.GetCubeOrientation(s.GetCubeInLoc(5))+2)%3);
446  s.SetCubeOrientation(s.GetCubeInLoc(1), (s.GetCubeOrientation(s.GetCubeInLoc(1))+1)%3);
447  }
448  break;
449  case 17:
450  {
451  s.Swap(1, 6, 2, 5);
452  }
453  break;
454  default:
455  break;
456  }
457 
458 }
459 
460 void RubiksCorner::GetNextState(const RubiksCornerState &s0, RubiksCornersAction a, RubiksCornerState &s1) const
461 {
462  s1 = s0;
463  ApplyAction(s1, a);
464 }
465 
466 
467 bool RubiksCorner::InvertAction(RubiksCornersAction &a) const
468 {
469  if (2 == a%3)
470  return true;
471  if (1 == a%3)
472  {
473  a -= 1;
474  return true;
475  }
476  a += 1;
477  return true;
478 }
479 
481 bool RubiksCorner::GoalTest(const RubiksCornerStateBits &node) const
482 {
483  return node.state == 0;
484 }
485 
486 bool RubiksCorner::GoalTest(const RubiksCornerStateArray &node) const
487 {
488  for (int x = 0; x < 16; x++)
489  if (node.state[x] != 0)
490  return false;
491  return true;
492 }
493 
494 void RubiksCorner::ApplyMove(RubiksCornerState &s, RubikCornerMove *a)
495 {
496  ApplyAction(s, a->act);
497 }
498 void RubiksCorner::UndoMove(RubiksCornerState &s, RubikCornerMove *a)
499 {
500  RubiksCornersAction todo = a->act;
501  if (0 == todo%3)
502  {
503  todo += 1;
504  }
505  else if (1 == todo%3)
506  {
507  todo -= 1;
508  }
509  ApplyAction(s, todo);
510 }
511 
512 int64_t RubiksCorner::getMaxSinglePlayerRank()
513 {
514  // static uint64_t Factorial[21] =
515  // { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
516  // 6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
517  // 6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
518  //
519  // return Factorial[8]*(2187); // 3^7
520  return 88179840;
521 }
522 int64_t RubiksCorner::getMaxSinglePlayerRank2()
523 {
524  return 9;
525 }
526 int64_t RubiksCorner::getMaxSinglePlayerRank2(int64_t firstIndex)
527 {
528  return 9797760;
529 }
530 
531 void RubiksCorner::rankPlayerFirstTwo(const RubiksCornerState &s, int who, int64_t &rank)
532 {
533  rank = s.GetCubeOrientation(0)*3+s.GetCubeOrientation(1);
534 }
535 
536 void RubiksCorner::rankPlayerRemaining(const RubiksCornerState &node, int who, int64_t &rank)
537 {
538  static uint64_t Factorial[21] =
539  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
540  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
541  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
542 #if POLYNOMIAL_RANK == 1
543 
544  int puzzle[12];
545  for (int x = 0; x < 8; x++)
546  puzzle[x] = node.GetCubeInLoc(x);
547 
548  uint64_t hashVal = 0;
549  uint64_t part2 = 0;
550  int numEntriesLeft = 8;
551  for (unsigned int x = 0; x < 8; x++)
552  {
553  hashVal += puzzle[x]*Factorial[numEntriesLeft-1];
554  numEntriesLeft--;
555  for (unsigned y = x; y < 8; y++)
556  {
557  if (puzzle[y] > puzzle[x])
558  puzzle[y]--;
559  }
560  }
561  for (int x = 2; x < 7; x++)
562  {
563  part2 = part2*3+node.GetCubeOrientation(x);
564  }
565  rank = part2*Factorial[8]+hashVal;
566 #endif
567 #if LINEAR_RANK == 1
568  uint64_t perm = 0, dual = 0;
569  for (int x = 0; x < 8; x++)
570  {
571  set(perm, x, node.GetCubeInLoc(x));
572  set(dual, node.GetCubeInLoc(x), x);
573  }
574 
575  uint64_t hashVal = 0;
576  for (int x = 2; x < 7; x++)
577  {
578  hashVal = hashVal*3+node.GetCubeOrientation(x);
579  }
580  hashVal = hashVal*Factorial[8]+MRRank(8, perm, dual);
581  rank = hashVal;
582 #endif
583 }
584 
585 
586 uint64_t RubiksCorner::GetStateHash(const RubiksCornerState &node) const
587 {
588  static uint64_t Factorial[21] =
589  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
590  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
591  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
592 
593 #if POLYNOMIAL_RANK == 1
594  int puzzle[12];
595  for (int x = 0; x < 8; x++)
596  puzzle[x] = node.GetCubeInLoc(x);
597 
598  uint64_t hashVal = 0;
599  uint64_t part2 = 0;
600  int numEntriesLeft = 8;
601  for (unsigned int x = 0; x < 8; x++)
602  {
603  hashVal += puzzle[x]*Factorial[numEntriesLeft-1];
604  numEntriesLeft--;
605  for (unsigned y = x; y < 8; y++)
606  {
607  if (puzzle[y] > puzzle[x])
608  puzzle[y]--;
609  }
610  }
611  for (int x = 0; x < 7; x++)
612  {
613  part2 = part2*3+node.GetCubeOrientation(x);
614  }
615  return part2*Factorial[8]+hashVal;
616  // return hashVal;
617 #endif
618 #if LINEAR_RANK == 1
619  uint64_t perm = 0, dual = 0;
620  for (int x = 0; x < 8; x++)
621  {
622  int val = node.GetCubeInLoc(x);
623  set(perm, x, val);
624  set(dual, val, x);
625  }
626 
627  uint64_t hashVal = 0;
628  for (int x = 0; x < 7; x++)
629  {
630  hashVal = hashVal*3+node.GetCubeOrientation(x);
631  }
632  // return (MRRank(12, perm, dual)<<11)|hashVal;
633  hashVal = hashVal*Factorial[8]+MRRank(8, perm, dual);
634  return hashVal;
635 #endif
636 }
637 
639 
640 uint64_t RubiksCorner::MRRank(int n, uint64_t perm, uint64_t dual)
641 {
642  int ss[12];
643  int ssLoc = 0;
644 
645  int s;
646  for (int i = n; i > 1; i--)
647  {
648  s = get(perm, i-1);
649  ss[ssLoc] = s;
650  ssLoc++;
651 
652  swap(perm, i-1, get(dual, i-1));
653  swap(dual, s, i-1);
654  }
655  uint64_t result = 0;
656  int cnt = 2;
657  for (int i = (int)ssLoc-1; i >= 0; i--)
658  {
659  result *= cnt;
660  result += ss[i];
661  cnt++;
662  }
663  return result;
664 }
665 
666 
668 
669 
670 void RubiksCorner::GetStateFromHash(uint64_t hash, RubiksCornerState &node) const
671 {
672  static uint64_t Factorial[21] =
673  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
674  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
675  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
676 #if POLYNOMIAL_RANK == 1
677 
678  int puzzle[12];
679  uint64_t hashVal = hash;
680  hash /= Factorial[8]; // for rotations
681  hashVal = hashVal%Factorial[8]; // for pieces
682 
683  int cnt = 0;
684  for (int x = 6; x >= 0; x--)
685  {
686  node.SetCubeOrientation(x, hash%3);
687  cnt += hash%3;
688  hash/=3;
689  }
690  node.SetCubeOrientation(7, (3-(cnt%3))%3);
691 
692  int numEntriesLeft = 1;
693  for (int x = 8-1; x >= 0; x--)
694  {
695  puzzle[x] = hashVal%numEntriesLeft;
696  hashVal /= numEntriesLeft;
697  numEntriesLeft++;
698  for (int y = x+1; y < 8; y++)
699  {
700  if (puzzle[y] >= puzzle[x])
701  puzzle[y]++;
702  }
703  }
704  for (int x = 0; x < 8; x++)
705  node.SetCubeInLoc(x, puzzle[x]);
706 #endif
707 #if LINEAR_RANK == 1
708  uint64_t bits = hash/Factorial[8];
709  uint64_t hVal = hash%Factorial[8];
710 
711  int cnt = 0;
712  for (int x = 6; x >= 0; x--)
713  {
714  node.SetCubeOrientation(x, bits%3);
715  cnt += bits%3;
716  bits/=3;
717  }
718  node.SetCubeOrientation(7, (3-(cnt%3))%3);
719 
720  uint64_t val = 0;
721  for (int x = 0; x < 8; x++)
722  set(val, x, x);
723  MRUnrank2(8, hVal, val);
724  for (int x = 0; x < 8; x++)
725  {
726  node.SetCubeInLoc(x, get(val, x));
727  }
728 #endif
729 }
730 
731 void RubiksCorner::MRUnrank2(int n, uint64_t r, uint64_t &perm)
732 {
733  for (int i = n; i > 0; i--)
734  {
735  swap(perm, i-1, r%i);
736  r = r/i;
737  }
738 }
739 
740 
741 void RubiksCorner::OpenGLDraw() const
742 {
743 
744 }
745 
746 void RubiksCorner::OpenGLDraw(const RubiksCornerState&s) const
747 {
748 // glPushMatrix();
749 // glRotatef(45, 0.0, 1.0, 0.0);
750  glBegin(GL_QUADS);
751  OpenGLDrawCube(s, 0);
752  OpenGLDrawCube(s, 2);
753  OpenGLDrawCube(s, 6);
754  OpenGLDrawCube(s, 8);
755 // glEnd();
756 // glPopMatrix();
757 //
758 // glBegin(GL_QUADS);
759  OpenGLDrawCube(s, 18);
760  OpenGLDrawCube(s, 20);
761  OpenGLDrawCube(s, 24);
762  OpenGLDrawCube(s, 26);
763  glEnd();
764 }
765 
766 void RubiksCorner::OpenGLDrawCube(const RubiksCornerState &s, int cube) const
767 {
768  const float scale = 0.3;
769  const float offset = 0.95*2.0*scale/3.0;
770  const float offset2 = 2.0*scale/3.0;
771  const float epsilon = 0.002;
772  switch(cube)
773  {
774  case 0:
775  {
776  // Face 0 - cube 0
777  SetFaceColor(0, s);
778  glVertex3f(-scale, -scale, -scale+offset);
779  glVertex3f(-scale, -scale, -scale);
780  glVertex3f(-scale+offset, -scale, -scale);
781  glVertex3f(-scale+offset, -scale, -scale+offset);
782 
783  SetFaceColor(-1, s);
784  glVertex3f(-scale, -scale+epsilon, -scale+offset2);
785  glVertex3f(-scale, -scale+epsilon, -scale);
786  glVertex3f(-scale+offset2, -scale+epsilon, -scale);
787  glVertex3f(-scale+offset2, -scale+epsilon, -scale+offset2);
788 
789  // Face 1 - cube 0
790  SetFaceColor(1, s);
791  glVertex3f(-scale, -scale+offset, -scale);
792  glVertex3f(-scale, -scale+offset, -scale+offset);
793  glVertex3f(-scale, -scale, -scale+offset);
794  glVertex3f(-scale, -scale, -scale);
795 
796  SetFaceColor(-1, s);
797  glVertex3f(-scale+epsilon, -scale+offset2, -scale);
798  glVertex3f(-scale+epsilon, -scale+offset2, -scale+offset2);
799  glVertex3f(-scale+epsilon, -scale, -scale+offset2);
800  glVertex3f(-scale+epsilon, -scale, -scale);
801 
802  // Face 2 - cube 0
803  SetFaceColor(2, s);
804  glVertex3f(-scale, -scale+offset, -scale);
805  glVertex3f(-scale+offset, -scale+offset, -scale);
806  glVertex3f(-scale+offset, -scale, -scale);
807  glVertex3f(-scale, -scale, -scale);
808 
809  SetFaceColor(-1, s);
810  glVertex3f(-scale, -scale+offset2, -scale+epsilon);
811  glVertex3f(-scale+offset2, -scale+offset2, -scale+epsilon);
812  glVertex3f(-scale+offset2, -scale, -scale+epsilon);
813  glVertex3f(-scale, -scale, -scale+epsilon);
814 
815  } break;
816  case 2:
817  {
818  // Face 0 - cube 2
819  SetFaceColor(3, s);
820  glVertex3f(scale-offset, -scale, -scale+offset);
821  glVertex3f(scale-offset, -scale, -scale);
822  glVertex3f(scale, -scale, -scale);
823  glVertex3f(scale, -scale, -scale+offset);
824 
825  SetFaceColor(-1, s);
826  glVertex3f(scale-offset2, -scale+epsilon, -scale+offset2);
827  glVertex3f(scale-offset2, -scale+epsilon, -scale);
828  glVertex3f(scale, -scale+epsilon, -scale);
829  glVertex3f(scale, -scale+epsilon, -scale+offset2);
830 
831  // Face 2 - cube 2
832  SetFaceColor(4, s);
833  glVertex3f(scale, -scale+offset, -scale);
834  glVertex3f(scale-offset, -scale+offset, -scale);
835  glVertex3f(scale-offset, -scale, -scale);
836  glVertex3f(scale, -scale, -scale);
837 
838  SetFaceColor(-1, s);
839  glVertex3f(scale, -scale+offset2, -scale+epsilon);
840  glVertex3f(scale-offset2, -scale+offset2, -scale+epsilon);
841  glVertex3f(scale-offset2, -scale, -scale+epsilon);
842  glVertex3f(scale, -scale, -scale+epsilon);
843 
844  // Face 3 - cube 2
845  SetFaceColor(5, s);
846  glVertex3f(scale, -scale+offset, -scale);
847  glVertex3f(scale, -scale+offset, -scale+offset);
848  glVertex3f(scale, -scale, -scale+offset);
849  glVertex3f(scale, -scale, -scale);
850 
851  SetFaceColor(-1, s);
852  glVertex3f(scale-epsilon, -scale+offset2, -scale);
853  glVertex3f(scale-epsilon, -scale+offset2, -scale+offset2);
854  glVertex3f(scale-epsilon, -scale, -scale+offset2);
855  glVertex3f(scale-epsilon, -scale, -scale);
856  } break;
857  case 6:
858  {
859  // Face 0 - cube 6
860  SetFaceColor(9, s);
861  glVertex3f(-scale, -scale, scale);
862  glVertex3f(-scale, -scale, scale-offset);
863  glVertex3f(-scale+offset, -scale, scale-offset);
864  glVertex3f(-scale+offset, -scale, scale);
865 
866  SetFaceColor(-1, s);
867  glVertex3f(-scale, -scale+epsilon, scale);
868  glVertex3f(-scale, -scale+epsilon, scale-offset2);
869  glVertex3f(-scale+offset2, -scale+epsilon, scale-offset2);
870  glVertex3f(-scale+offset2, -scale+epsilon, scale);
871 
872 
873  // Face 1 - cube 6
874  SetFaceColor(11, s);
875  glVertex3f(-scale, -scale+offset, scale);
876  glVertex3f(-scale, -scale+offset, scale-offset);
877  glVertex3f(-scale, -scale, scale-offset);
878  glVertex3f(-scale, -scale, scale);
879 
880  SetFaceColor(-1, s);
881  glVertex3f(-scale+epsilon, -scale+offset2, scale);
882  glVertex3f(-scale+epsilon, -scale+offset2, scale-offset2);
883  glVertex3f(-scale+epsilon, -scale, scale-offset2);
884  glVertex3f(-scale+epsilon, -scale, scale);
885 
886  // Face 4 - cube 6
887  SetFaceColor(10, s);
888  glVertex3f(-scale, -scale+offset, scale);
889  glVertex3f(-scale+offset, -scale+offset, scale);
890  glVertex3f(-scale+offset, -scale, scale);
891  glVertex3f(-scale, -scale, scale);
892 
893  SetFaceColor(-1, s);
894  glVertex3f(-scale, -scale+offset2, scale-epsilon);
895  glVertex3f(-scale+offset2, -scale+offset2, scale-epsilon);
896  glVertex3f(-scale+offset2, -scale, scale-epsilon);
897  glVertex3f(-scale, -scale, scale-epsilon);
898 
899  } break;
900  case 8:
901  {
902  // Face 0 - cube 8
903  SetFaceColor(6, s);
904  glVertex3f(scale-offset, -scale, scale);
905  glVertex3f(scale-offset, -scale, scale-offset);
906  glVertex3f(scale, -scale, scale-offset);
907  glVertex3f(scale, -scale, scale);
908 
909  SetFaceColor(-1, s);
910  glVertex3f(scale-offset2, -scale+epsilon, scale);
911  glVertex3f(scale-offset2, -scale+epsilon, scale-offset2);
912  glVertex3f(scale, -scale+epsilon, scale-offset2);
913  glVertex3f(scale, -scale+epsilon, scale);
914 
915  // Face 3 - cube 8
916  SetFaceColor(7, s);
917  glVertex3f(scale, -scale+offset, scale);
918  glVertex3f(scale, -scale+offset, scale-offset);
919  glVertex3f(scale, -scale, scale-offset);
920  glVertex3f(scale, -scale, scale);
921 
922  SetFaceColor(-1, s);
923  glVertex3f(scale-epsilon, -scale+offset2, scale);
924  glVertex3f(scale-epsilon, -scale+offset2, scale-offset2);
925  glVertex3f(scale-epsilon, -scale, scale-offset2);
926  glVertex3f(scale-epsilon, -scale, scale);
927 
928 
929  // Face 4 - cube 8
930  SetFaceColor(8, s);
931  glVertex3f(scale, -scale+offset, scale);
932  glVertex3f(scale-offset, -scale+offset, scale);
933  glVertex3f(scale-offset, -scale, scale);
934  glVertex3f(scale, -scale, scale);
935 
936  SetFaceColor(-1, s);
937  glVertex3f(scale, -scale+offset2, scale-epsilon);
938  glVertex3f(scale-offset2, -scale+offset2, scale-epsilon);
939  glVertex3f(scale-offset2, -scale, scale-epsilon);
940  glVertex3f(scale, -scale, scale-epsilon);
941 
942  } break;
943  case 18:
944  {
945  // Face 1 - cube 18
946  SetFaceColor(14, s);
947  glVertex3f(-scale, scale-offset, -scale);
948  glVertex3f(-scale, scale-offset, -scale+offset);
949  glVertex3f(-scale, scale, -scale+offset);
950  glVertex3f(-scale, scale, -scale);
951 
952  SetFaceColor(-1, s);
953  glVertex3f(-scale+epsilon, scale-offset2, -scale);
954  glVertex3f(-scale+epsilon, scale-offset2, -scale+offset2);
955  glVertex3f(-scale+epsilon, scale, -scale+offset2);
956  glVertex3f(-scale+epsilon, scale, -scale);
957 
958 
959  // Face 2 - cube 18
960  SetFaceColor(13, s);
961  glVertex3f(-scale, scale-offset, -scale);
962  glVertex3f(-scale+offset, scale-offset, -scale);
963  glVertex3f(-scale+offset, scale, -scale);
964  glVertex3f(-scale, scale, -scale);
965 
966  SetFaceColor(-1, s);
967  glVertex3f(-scale, scale-offset2, -scale+epsilon);
968  glVertex3f(-scale+offset2, scale-offset2, -scale+epsilon);
969  glVertex3f(-scale+offset2, scale, -scale+epsilon);
970  glVertex3f(-scale, scale, -scale+epsilon);
971 
972 
973  // Face 5 - cube 18
974  SetFaceColor(12, s);
975  glVertex3f(-scale, scale, -scale+offset);
976  glVertex3f(-scale, scale, -scale);
977  glVertex3f(-scale+offset, scale, -scale);
978  glVertex3f(-scale+offset, scale, -scale+offset);
979 
980  SetFaceColor(-1, s);
981  glVertex3f(-scale, scale-epsilon, -scale+offset2);
982  glVertex3f(-scale, scale-epsilon, -scale);
983  glVertex3f(-scale+offset2, scale-epsilon, -scale);
984  glVertex3f(-scale+offset2, scale-epsilon, -scale+offset2);
985 
986  } break;
987  case 20:
988  {
989  // Face 2 - cube 20
990  SetFaceColor(17, s);
991  glVertex3f(scale, scale-offset, -scale);
992  glVertex3f(scale-offset, scale-offset, -scale);
993  glVertex3f(scale-offset, scale, -scale);
994  glVertex3f(scale, scale, -scale);
995 
996  SetFaceColor(-1, s);
997  glVertex3f(scale, scale-offset2, -scale+epsilon);
998  glVertex3f(scale-offset2, scale-offset2, -scale+epsilon);
999  glVertex3f(scale-offset2, scale, -scale+epsilon);
1000  glVertex3f(scale, scale, -scale+epsilon);
1001 
1002  // Face 3 - cube 20
1003  SetFaceColor(16, s);
1004  glVertex3f(scale, scale-offset, -scale);
1005  glVertex3f(scale, scale-offset, -scale+offset);
1006  glVertex3f(scale, scale, -scale+offset);
1007  glVertex3f(scale, scale, -scale);
1008 
1009  SetFaceColor(-1, s);
1010  glVertex3f(scale-epsilon, scale-offset2, -scale);
1011  glVertex3f(scale-epsilon, scale-offset2, -scale+offset2);
1012  glVertex3f(scale-epsilon, scale, -scale+offset2);
1013  glVertex3f(scale-epsilon, scale, -scale);
1014 
1015  // Face 5 - cube 20
1016  SetFaceColor(15, s);
1017  glVertex3f(scale-offset, scale, -scale+offset);
1018  glVertex3f(scale-offset, scale, -scale);
1019  glVertex3f(scale, scale, -scale);
1020  glVertex3f(scale, scale, -scale+offset);
1021 
1022  SetFaceColor(-1, s);
1023  glVertex3f(scale-offset2, scale-epsilon, -scale+offset2);
1024  glVertex3f(scale-offset2, scale-epsilon, -scale);
1025  glVertex3f(scale, scale-epsilon, -scale);
1026  glVertex3f(scale, scale-epsilon, -scale+offset2);
1027  } break;
1028  case 24:
1029  {
1030  // Face 1 - cube 24
1031  SetFaceColor(22, s);
1032  glVertex3f(-scale, scale-offset, scale);
1033  glVertex3f(-scale, scale-offset, scale-offset);
1034  glVertex3f(-scale, scale, scale-offset);
1035  glVertex3f(-scale, scale, scale);
1036 
1037  SetFaceColor(-1, s);
1038  glVertex3f(-scale+epsilon, scale-offset2, scale);
1039  glVertex3f(-scale+epsilon, scale-offset2, scale-offset2);
1040  glVertex3f(-scale+epsilon, scale, scale-offset2);
1041  glVertex3f(-scale+epsilon, scale, scale);
1042 
1043 
1044  // Face 4 - cube 24
1045  SetFaceColor(23, s);
1046  glVertex3f(-scale, scale-offset, scale);
1047  glVertex3f(-scale+offset, scale-offset, scale);
1048  glVertex3f(-scale+offset, scale, scale);
1049  glVertex3f(-scale, scale, scale);
1050 
1051  SetFaceColor(-1, s);
1052  glVertex3f(-scale, scale-offset2, scale-epsilon);
1053  glVertex3f(-scale+offset2, scale-offset2, scale-epsilon);
1054  glVertex3f(-scale+offset2, scale, scale-epsilon);
1055  glVertex3f(-scale, scale, scale-epsilon);
1056 
1057 
1058  // Face 5 - cube 24
1059  SetFaceColor(21, s);
1060  glVertex3f(-scale, scale, scale);
1061  glVertex3f(-scale, scale, scale-offset);
1062  glVertex3f(-scale+offset, scale, scale-offset);
1063  glVertex3f(-scale+offset, scale, scale);
1064 
1065  SetFaceColor(-1, s);
1066  glVertex3f(-scale, scale-epsilon, scale);
1067  glVertex3f(-scale, scale-epsilon, scale-offset2);
1068  glVertex3f(-scale+offset2, scale-epsilon, scale-offset2);
1069  glVertex3f(-scale+offset2, scale-epsilon, scale);
1070  } break;
1071  case 26:
1072  {
1073  // Face 3 - cube 26
1074  SetFaceColor(20, s);
1075  glVertex3f(scale, scale-offset, scale);
1076  glVertex3f(scale, scale-offset, scale-offset);
1077  glVertex3f(scale, scale, scale-offset);
1078  glVertex3f(scale, scale, scale);
1079 
1080  SetFaceColor(-1, s);
1081  glVertex3f(scale-epsilon, scale-offset2, scale);
1082  glVertex3f(scale-epsilon, scale-offset2, scale-offset2);
1083  glVertex3f(scale-epsilon, scale, scale-offset2);
1084  glVertex3f(scale-epsilon, scale, scale);
1085 
1086 
1087  // Face 4 - cube 26
1088  SetFaceColor(19, s);
1089  glVertex3f(scale, scale-offset, scale);
1090  glVertex3f(scale-offset, scale-offset, scale);
1091  glVertex3f(scale-offset, scale, scale);
1092  glVertex3f(scale, scale, scale);
1093 
1094  SetFaceColor(-1, s);
1095  glVertex3f(scale, scale-offset2, scale-epsilon);
1096  glVertex3f(scale-offset2, scale-offset2, scale-epsilon);
1097  glVertex3f(scale-offset2, scale, scale-epsilon);
1098  glVertex3f(scale, scale, scale-epsilon);
1099 
1100 
1101  // Face 5 - cube 26
1102  SetFaceColor(18, s);
1103  glVertex3f(scale-offset, scale, scale);
1104  glVertex3f(scale-offset, scale, scale-offset);
1105  glVertex3f(scale, scale, scale-offset);
1106  glVertex3f(scale, scale, scale);
1107 
1108  SetFaceColor(-1, s);
1109  glVertex3f(scale-offset2, scale-epsilon, scale);
1110  glVertex3f(scale-offset2, scale-epsilon, scale-offset2);
1111  glVertex3f(scale, scale-epsilon, scale-offset2);
1112  glVertex3f(scale, scale-epsilon, scale);
1113 
1114  } break;
1115  }
1116 }
1117 
1120 void RubiksCorner::OpenGLDraw(const RubiksCornerState&, const RubiksCornerState&, float) const
1121 {
1122 
1123 }
1124 
1125 void RubiksCorner::OpenGLDraw(const RubiksCornerState&, const RubiksCornersAction&) const
1126 {
1127 
1128 }
1129 
1130 void RubiksCorner::SetFaceColor(int face, const RubiksCornerState &s) const
1131 {
1132  int theColor = -1;
1133  if (face == -1)
1134  {
1135  glColor3f(0.0, 0.0, 0.0);
1136  return;
1137  }
1138 
1139  int cube = s.GetFaceInLoc(face);
1140  switch (cube)
1141  {
1142  case 0: theColor = 0; break;
1143  case 1: theColor = 1; break;
1144  case 2: theColor = 2; break;
1145  case 3: theColor = 0; break;
1146  case 4: theColor = 2; break;
1147  case 5: theColor = 3; break;
1148  case 6: theColor = 0; break;
1149  case 7: theColor = 3; break;
1150  case 8: theColor = 4; break;
1151  case 9: theColor = 0; break;
1152  case 10: theColor = 4; break;
1153  case 11: theColor = 1; break;
1154  case 12: theColor = 5; break;
1155  case 13: theColor = 2; break;
1156  case 14: theColor = 1; break;
1157  case 15: theColor = 5; break;
1158  case 16: theColor = 3; break;
1159  case 17: theColor = 2; break;
1160  case 18: theColor = 5; break;
1161  case 19: theColor = 4; break;
1162  case 20: theColor = 3; break;
1163  case 21: theColor = 5; break;
1164  case 22: theColor = 1; break;
1165  case 23: theColor = 4; break;
1166  default: theColor = -1; break;
1167  }
1168 
1169  switch (theColor)
1170  {
1171  case 0: glColor3f(1.0, 0.0, 0.0); break;
1172  case 1: glColor3f(0.0, 1.0, 0.0); break;
1173  case 2: glColor3f(0.0, 0.0, 1.0); break;
1174  case 3: glColor3f(1.0, 1.0, 0.0); break;
1175  case 4: glColor3f(1.0, 0.75, 0.0); break;
1176  case 5: glColor3f(1.0, 1.0, 1.0); break;
1177  default: glColor3f(0.0, 0.0, 0.0); break;
1178  }
1179 }
1180 
1181 
1182 
1183 RubikCornerPDB::RubikCornerPDB(RubiksCorner *e, const RubiksCornerState &s, std::vector<int> &distinctCorners)
1184 :PDBHeuristic(e), corners(distinctCorners)
1185 {
1186  SetGoal(s);
1187 }
1188 
1189 uint64_t RubikCornerPDB::GetStateSpaceSize()
1190 {
1191 #pragma message("This code belongs in the RubikCorner, not in the PDB.")
1192  return 40320ll*2187ll;
1193 }
1194 
1195 uint64_t RubikCornerPDB::GetStateHash(const RubiksCornerState &s)
1196 {
1197  RubiksCorner rc;
1198  return rc.GetStateHash(s);
1199 }
1200 
1201 void RubikCornerPDB::GetStateFromHash(RubiksCornerState &s, uint64_t hash)
1202 {
1203  RubiksCorner rc;
1204  rc.GetStateFromHash(hash, s);
1205 }
1206 
1207 uint64_t RubikCornerPDB::GetPDBSize() const
1208 {
1209 // uint64_t power3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 2187}; // last tile is symmetric
1210 // int elts = (int)corners.size();
1211 // return FactorialUpperK(8, 8-elts)*power3[elts];
1212  uint64_t answer[] = {1, 24, 504, 9072, 136080, 1632960, 14696640, 88179840, 88179840};
1213  return answer[corners.size()];
1214 }
1215 
1216 #define MR
1217 
1218 uint64_t RubikCornerPDB::GetPDBHash(const RubiksCornerState &s, int threadID) const
1219 {
1220 #ifdef MR
1221  // TODO: handle fewer according to pattern
1222  int puzzle[8] = {-1, -1, -1, -1, -1, -1, -1, -1};
1223  int dual[16]; // seamlessly handle 0xF entries (no cube)
1224  int newdual[16]; // seamlessly handle 0xF entries (no cube)
1225  int cornerSize = corners.size();
1226  int lastPiece = 8-(int)cornerSize;
1227  for (int x = 0; x < 8; x++)
1228  dual[s.GetCubeInLoc(x)] = x;
1229  for (int x = 0; x < cornerSize; x++)
1230  {
1231  newdual[x] = dual[corners[x]];
1232  puzzle[dual[corners[x]]] = x;
1233  }
1234  uint64_t hashVal = 0;
1235  uint64_t part2 = 0;
1236  hashVal = mr1.Rank(puzzle, newdual, cornerSize, 8);//mr1.GetRank(puzzle, threadID);
1237 
1238  int limit = std::min((int)cornerSize, 7);
1239  for (int x = 0; x < limit; x++)
1240  {
1241  part2 = part2*3+s.GetCubeOrientation(corners[x]);
1242  //part2 = part2*3+s.GetCubeOrientation(dual[corners[x]]);
1243  }
1244  return part2*FactorialUpperK(8, lastPiece)+hashVal;
1245 
1246 #else
1247 
1248  // TODO: handle fewer according to pattern
1249  int puzzle[8];
1250  int dual[16]; // seamlessly handle 0xF entries (no cube)
1251  int cornerSize = corners.size();
1252  int lastPiece = 8-(int)corners.size();
1253  for (int x = 0; x < 8; x++)
1254  dual[s.GetCubeInLoc(x)] = x;
1255  for (int x = 0; x < cornerSize; x++)
1256  puzzle[x] = dual[corners[x]];
1257 
1258  uint64_t hashVal = 0;
1259  uint64_t part2 = 0;
1260  int numEntriesLeft = 8;
1261  for (unsigned int x = 0; x < cornerSize; x++)
1262  {
1263  hashVal += puzzle[x]*FactorialUpperK(numEntriesLeft-1, lastPiece);
1264 
1265  numEntriesLeft--;
1266  for (unsigned y = x; y < cornerSize; y++)
1267  {
1268  if (puzzle[y] > puzzle[x])
1269  puzzle[y]--;
1270  }
1271  }
1272  int limit = std::min((int)cornerSize, 7);
1273  for (int x = 0; x < limit; x++)
1274  {
1275  part2 = part2*3+s.GetCubeOrientation(corners[x]);
1276  //part2 = part2*3+s.GetCubeOrientation(dual[corners[x]]);
1277  }
1278  return part2*FactorialUpperK(8, lastPiece)+hashVal;
1279 #endif
1280 
1281 }
1282 
1283 void RubikCornerPDB::GetStateFromPDBHash(uint64_t hash, RubiksCornerState &s, int threadID) const
1284 {
1285 #ifdef MR
1286  int lastPiece = 8-(int)corners.size();
1287  int puzzle[8] = {-1, -1, -1, -1, -1, -1, -1};
1288  int dual[16] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
1289  uint64_t hashVal = hash;
1290  int cornerSize = corners.size();
1291  hash /= FactorialUpperK(8, lastPiece); // for rotations
1292  hashVal = hashVal%FactorialUpperK(8, lastPiece); // for pieces)
1293  mr1.Unrank(hashVal, puzzle, dual, cornerSize, 8);
1294 
1295  for (int x = 0; x < 8; x++)
1296  {
1297  s.SetCubeInLoc(x, 0xF);
1298  s.SetCubeOrientation(x, 0);
1299  }
1300 
1301  for (int x = 0; x < cornerSize; x++)
1302  {
1303  s.SetCubeInLoc(dual[x], corners[x]);
1304  }
1305 
1306  int cnt = 0;
1307  int limit = std::min((int)cornerSize, 7);
1308  for (int x = limit-1; x >= 0; x--)
1309  {
1310  s.SetCubeOrientation(corners[x], hash%3);
1311  cnt += hash%3;
1312  hash/=3;
1313  }
1314  if (cornerSize == 8)
1315  s.SetCubeOrientation(corners[7], (3-(cnt%3))%3); // 0->0 2->1 1->2
1316 #else
1317 
1318  int lastPiece = 8-(int)corners.size();
1319  int cornerSize = corners.size();
1320  int puzzle[12];
1321  int dual[16];
1322  uint64_t hashVal = hash;
1323  hash /= FactorialUpperK(8, lastPiece); // for rotations
1324  hashVal = hashVal%FactorialUpperK(8, lastPiece); // for pieces
1325 
1326  int numEntriesLeft = lastPiece+1;
1327  for (int x = corners.size()-1; x >= 0; x--)
1328  {
1329  puzzle[x] = hashVal%numEntriesLeft;
1330  hashVal /= numEntriesLeft;
1331  numEntriesLeft++;
1332  for (int y = x+1; y < cornerSize; y++)
1333  {
1334  if (puzzle[y] >= puzzle[x])
1335  puzzle[y]++;
1336  }
1337  }
1338  for (int x = 0; x < 8; x++)
1339  {
1340  s.SetCubeInLoc(x, 0xF);
1341  s.SetCubeOrientation(x, 0);
1342  }
1343 
1344  for (int x = 0; x < cornerSize; x++)
1345  {
1346  s.SetCubeInLoc(puzzle[x], corners[x]);
1347  dual[corners[x]] = puzzle[x];
1348  }
1349 
1350  int cnt = 0;
1351  int limit = std::min((int)corners.size(), 7);
1352  for (int x = limit-1; x >= 0; x--)
1353  {
1354  s.SetCubeOrientation(corners[x], hash%3);
1355  cnt += hash%3;
1356  hash/=3;
1357  }
1358  if (corners.size() == 8)
1359  s.SetCubeOrientation(corners[7], (3-(cnt%3))%3); // 0->0 2->1 1->2
1360 
1361 #endif
1362 }
1363 
1364 
1365 bool RubikCornerPDB::Load(const char *prefix)
1366 {
1367  FILE *f = fopen(GetFileName(prefix).c_str(), "rb");
1368  if (f == 0)
1369  {
1370  perror("Opening RubiksCornerPDB file");
1371  return false;
1372  }
1373  Save(f);
1374  fclose(f);
1375  return true;
1376 }
1377 
1378 void RubikCornerPDB::Save(const char *prefix)
1379 {
1380  FILE *f = fopen(GetFileName(prefix).c_str(), "w+");
1381  if (f == 0)
1382  {
1383  perror("Opening RubiksCornerPDB file");
1384  return;
1385  }
1386  Save(f);
1387  fclose(f);
1388 }
1389 
1390 bool RubikCornerPDB::Load(FILE *f)
1391 {
1392  if (PDBHeuristic<RubiksCornerState, RubiksCornersAction, RubiksCorner, RubiksCornerState, 4>::Load(f) == false)
1393  return false;
1394  if (fread(&puzzleSize, sizeof(puzzleSize), 1, f) != 1)
1395  return false;
1396  if (fread(&pdbSize, sizeof(pdbSize), 1, f) != 1)
1397  return false;
1398  size_t edgeSize = corners.size();
1399  if (fread(&edgeSize, sizeof(edgeSize), 1, f) != 1)
1400  return false;
1401  corners.resize(edgeSize);
1402  if (fread(&corners[0], sizeof(corners[0]), corners.size(), f) != edgeSize)
1403  return false;
1404  return true;
1405 }
1406 
1407 void RubikCornerPDB::Save(FILE *f)
1408 {
1409  PDBHeuristic<RubiksCornerState, RubiksCornersAction, RubiksCorner, RubiksCornerState, 4>::Save(f);
1410  fwrite(&puzzleSize, sizeof(puzzleSize), 1, f);
1411  fwrite(&pdbSize, sizeof(pdbSize), 1, f);
1412  size_t edgeSize = corners.size();
1413  fwrite(&edgeSize, sizeof(edgeSize), 1, f);
1414  fwrite(&corners[0], sizeof(corners[0]), corners.size(), f);
1415 }
1416 
1417 std::string RubikCornerPDB::GetFileName(const char *prefix)
1418 {
1419  std::string fileName;
1420  fileName += "RC-C-";
1421  // origin state
1422  for (int x = 0; x < 8; x++)
1423  {
1424  fileName += std::to_string(goalState[0].GetCubeInLoc(x));
1425  fileName += ".";
1426  fileName += std::to_string(goalState[0].GetCubeOrientation(goalState[0].GetCubeInLoc(x)));
1427  fileName += ";";
1428  }
1429  fileName.pop_back();
1430  fileName += "-";
1431  // pattern
1432  for (size_t x = 0; x < corners.size(); x++)
1433  {
1434  fileName += std::to_string(corners[x]);
1435  fileName += ";";
1436  }
1437  fileName.pop_back(); // remove colon
1438 #ifdef MR
1439  fileName += "-MR";
1440 #endif
1441  if (std::is_same<RubiksCornerStateArray,RubiksCornerState>::value)
1442  {
1443  fileName += "-AR";
1444  }
1445  fileName += ".pdb";
1446 
1447  return fileName;
1448 }
1449 
1450 uint64_t RubikCornerPDB::Factorial(int val) const
1451 {
1452  static uint64_t table[21] =
1453  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
1454  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
1455  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
1456  if (val > 20)
1457  return (uint64_t)-1;
1458  return table[val];
1459 }
1460 
1461 uint64_t RubikCornerPDB::FactorialUpperK(int n, int k) const
1462 {
1463  const uint64_t result[9][9] = {
1464  {1}, // n = 0
1465  {1, 1}, // n = 1
1466  {2, 2, 1}, // n = 2
1467  {6, 6, 3, 1}, // n = 3
1468  {24, 24, 12, 4, 1}, // n = 4
1469  {120, 120, 60, 20, 5, 1}, // n = 5
1470  {720, 720, 360, 120, 30, 6, 1}, // n = 6
1471  {5040, 5040, 2520, 840, 210, 42, 7, 1}, // n = 7
1472  {40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1}, // n = 8
1473  };
1474  return result[n][k];
1475 // uint64_t value = 1;
1476 // assert(n >= 0 && k >= 0);
1477 //
1478 // for (int i = n; i > k; i--)
1479 // {
1480 // value *= i;
1481 // }
1482 //
1483 // return value;
1484 }
RubiksCornerStateArray
Definition: RubiksCubeCorners.h:38
RubikCornerPDB::GetPDBHash
uint64_t GetPDBHash(const RubiksCornerState &s, int threadID=0) const
Definition: RubiksCubeCorners.cpp:1218
RubiksCornerStateBits::state
uint64_t state
Definition: RubiksCubeCorners.h:35
RubiksCornersAction
int RubiksCornersAction
Definition: RubiksCubeCorners.h:105
min
double min(double a, double b)
Definition: FPUtil.h:35
RubiksCornerStateArray::GetCubeOrientation
uint64_t GetCubeOrientation(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:248
RubiksCorner::MRUnrank2
static void MRUnrank2(int n, uint64_t r, uint64_t &perm)
Definition: RubiksCubeCorners.cpp:731
RubiksCorner::OpenGLDrawCube
void OpenGLDrawCube(const RubiksCornerState &s, int cube) const
Definition: RubiksCubeCorners.cpp:766
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
RubikCornerPDB::GetStateFromPDBHash
void GetStateFromPDBHash(uint64_t hash, RubiksCornerState &s, int threadID=0) const
Definition: RubiksCubeCorners.cpp:1283
Factorial
uint64_t Factorial(int n)
Definition: RubiksCube7Edges.cpp:335
get
int get(uint64_t state, int whichLoc)
Implementation details:
Definition: RubiksCubeCorners.cpp:105
RubikCornerPDB::Factorial
uint64_t Factorial(int val) const
Definition: RubiksCubeCorners.cpp:1450
RubiksCornerStateBits::GetFaceInLoc
int GetFaceInLoc(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:180
RubiksCornerStateBits::Rotate
void Rotate(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
Definition: RubiksCubeCorners.cpp:189
RubiksCorner::InvertAction
virtual bool InvertAction(RubiksCornersAction &a) const
Definition: RubiksCubeCorners.cpp:467
RubikCornerPDB::pdbSize
uint64_t pdbSize
Definition: RubiksCubeCorners.h:216
RubiksCorner::rankPlayerRemaining
void rankPlayerRemaining(const RubiksCornerState &s, int who, int64_t &rank)
Definition: RubiksCubeCorners.cpp:536
RubiksCornerStateBits::GetCubeOrientation
uint64_t GetCubeOrientation(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:163
RubikCornerPDB::puzzleSize
size_t puzzleSize
Definition: RubiksCubeCorners.h:215
RubikCornerPDB::GetFileName
virtual std::string GetFileName(const char *prefix)
Definition: RubiksCubeCorners.cpp:1417
RubiksCornerStateArray::state
uint8_t state[16]
Definition: RubiksCubeCorners.h:54
RubiksCorner::UndoMove
void UndoMove(RubiksCornerState &s, RubikCornerMove *a)
Definition: RubiksCubeCorners.cpp:498
PDBHeuristic< RubiksCornerState, RubiksCornersAction, RubiksCorner, RubiksCornerState, 4 >::goalState
std::vector< RubiksCornerState > goalState
Definition: PDBHeuristic.h:129
RubiksCorner::GetStateHash
uint64_t GetStateHash(const RubiksCornerState &node) const
Definition: RubiksCubeCorners.cpp:586
RubiksCornerStateBits::SetCubeOrientation
void SetCubeOrientation(unsigned int whichLoc, int orient)
Definition: RubiksCubeCorners.cpp:170
RubiksCornerStateArray::Rotate
void Rotate(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
Definition: RubiksCubeCorners.cpp:266
RubikCornerMove::act
RubiksCornersAction act
Definition: RubiksCubeCorners.h:109
RubiksCornerStateBits::SetCubeInLoc
void SetCubeInLoc(unsigned int whichLoc, int cube)
Definition: RubiksCubeCorners.cpp:155
RubiksCorner::GetSuccessors
virtual void GetSuccessors(const RubiksCornerState &nodeID, std::vector< RubiksCornerState > &neighbors) const
Definition: RubiksCubeCorners.cpp:289
RubiksCornerStateBits::Swap
void Swap(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
Definition: RubiksCubeCorners.cpp:207
RubiksCornerStateArray::SetCubeInLoc
void SetCubeInLoc(unsigned int whichLoc, int cube)
Definition: RubiksCubeCorners.cpp:243
RubikCornerPDB::GetStateSpaceSize
static uint64_t GetStateSpaceSize()
Definition: RubiksCubeCorners.cpp:1189
RubiksCornerStateArray::RubiksCornerStateArray
RubiksCornerStateArray()
Definition: RubiksCubeCorners.cpp:225
RubikCornerPDB::Load
virtual bool Load(const char *prefix)
Definition: RubiksCubeCorners.cpp:1365
RubiksCorner::ApplyAction
virtual void ApplyAction(RubiksCornerState &s, RubiksCornersAction a) const
Definition: RubiksCubeCorners.cpp:315
RubikCornerMove
Definition: RubiksCubeCorners.h:107
PDBHeuristic
Definition: PDBHeuristic.h:39
RubikCornerPDB::Save
virtual void Save(const char *prefix)
Definition: RubiksCubeCorners.cpp:1378
RubiksCornerStateArray::GetFaceInLoc
int GetFaceInLoc(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:260
RubiksCornerStateArray::Swap
void Swap(uint64_t a, uint64_t b, uint64_t c, uint64_t d)
Definition: RubiksCubeCorners.cpp:275
set
void set(uint64_t &state, int whichLoc, int cube)
Definition: RubiksCubeCorners.cpp:111
PDBHeuristic::Save
virtual void Save(const char *prefix)=0
RubikCornerPDB::GetPDBSize
uint64_t GetPDBSize() const
Definition: RubiksCubeCorners.cpp:1207
RubikCornerPDB::mr1
MR1KPermutation mr1
Definition: RubiksCubeCorners.h:217
RubiksCorner::OpenGLDraw
virtual void OpenGLDraw() const
Definition: RubiksCubeCorners.cpp:741
RubiksCornerStateArray::GetCubeInLoc
int GetCubeInLoc(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:238
GLUtil.h
PDBHeuristic< RubiksCornerState, RubiksCornersAction, RubiksCorner, RubiksCornerState, 4 >::SetGoal
void SetGoal(const RubiksCornerState &goal)
Definition: PDBHeuristic.h:45
RubiksCornerStateBits::RubiksCornerStateBits
RubiksCornerStateBits()
Definition: RubiksCubeCorners.cpp:137
RubikCornerPDB::GetStateHash
static uint64_t GetStateHash(const RubiksCornerState &s)
Definition: RubiksCubeCorners.cpp:1195
RubiksCorner::SetFaceColor
void SetFaceColor(int face, const RubiksCornerState &) const
Definition: RubiksCubeCorners.cpp:1130
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
RubiksCorner::rankPlayerFirstTwo
void rankPlayerFirstTwo(const RubiksCornerState &s, int who, int64_t &rank)
Definition: RubiksCubeCorners.cpp:531
RubiksCornerStateArray::SetCubeOrientation
void SetCubeOrientation(unsigned int whichLoc, int orient)
Definition: RubiksCubeCorners.cpp:254
RubiksCornerStateBits
Definition: RubiksCubeCorners.h:19
RubiksCornerStateArray::Reset
void Reset()
Definition: RubiksCubeCorners.cpp:229
RubiksCorner::getMaxSinglePlayerRank2
int64_t getMaxSinglePlayerRank2()
Definition: RubiksCubeCorners.cpp:522
RubiksCubeCorners.h
RubikCornerPDB::GetStateFromHash
static void GetStateFromHash(RubiksCornerState &s, uint64_t hash)
Definition: RubiksCubeCorners.cpp:1201
RubikCornerPDB::corners
std::vector< int > corners
Definition: RubiksCubeCorners.h:214
RubiksCorner::GetActions
virtual void GetActions(const RubiksCornerState &nodeID, std::vector< RubiksCornersAction > &actions) const
Definition: RubiksCubeCorners.cpp:299
RubiksCorner::MRRank
static uint64_t MRRank(int n, uint64_t perm, uint64_t dual)
Definition: RubiksCubeCorners.cpp:640
RubiksCornerStateBits::GetCubeInLoc
int GetCubeInLoc(unsigned int whichLoc) const
Definition: RubiksCubeCorners.cpp:150
RubiksCorner::ApplyMove
void ApplyMove(RubiksCornerState &s, RubikCornerMove *a)
Definition: RubiksCubeCorners.cpp:494
MR1KPermutation::Rank
uint64_t Rank(int *items, int *dual, int k, int N) const
Definition: MR1Permutation.cpp:21
RubiksCorner::GetStateFromHash
void GetStateFromHash(uint64_t hash, RubiksCornerState &node) const
Definition: RubiksCubeCorners.cpp:670
RubiksCorner::GetAction
virtual RubiksCornersAction GetAction(const RubiksCornerState &s1, const RubiksCornerState &s2) const
Definition: RubiksCubeCorners.cpp:308
RubiksCorner::GoalTest
virtual bool GoalTest(const RubiksCornerState &node, const RubiksCornerState &goal) const
Definition: RubiksCubeCorners.h:169
swap
void swap(uint64_t &state, int loc1, int loc2)
Definition: RubiksCubeCorners.cpp:119
RubiksCornerStateBits::Reset
void Reset()
Definition: RubiksCubeCorners.cpp:141
RubiksCorner::getMaxSinglePlayerRank
int64_t getMaxSinglePlayerRank()
Definition: RubiksCubeCorners.cpp:512
RubiksCorner::GetNextState
virtual void GetNextState(const RubiksCornerState &, RubiksCornersAction, RubiksCornerState &) const
Definition: RubiksCubeCorners.cpp:460
RubiksCorner
Definition: RubiksCubeCorners.h:114
RubikCornerPDB::RubikCornerPDB
RubikCornerPDB(RubiksCorner *e, const RubiksCornerState &s, std::vector< int > &distinctCorners)
Definition: RubiksCubeCorners.cpp:1183
RubikCornerPDB::FactorialUpperK
uint64_t FactorialUpperK(int n, int k) const
Definition: RubiksCubeCorners.cpp:1461
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
Generated by   doxygen 1.8.17