SHARE
TWEET

36 cube iterative solution

a guest Jan 7th, 2011 150 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  
  3. $colors = array(
  4.          1 => 'R',
  5.          2 => 'O',
  6.          4 => 'Y',
  7.          8 => 'G',
  8.         16 => 'B',
  9.         32 => 'P',
  10.         false => 'X',
  11. );
  12.  
  13. $used_towers = array_fill(0, 6, 0);
  14.  
  15. $cube = array(
  16.         array(1,3,4,5,2,0),
  17.         array(2,5,1,4,1,3), // note 'special' base at (2, 1) here
  18.         array(0,1,3,2,5,4),
  19.         array(5,4,0,3,0,2), // note 'special' base at (2, 3) here
  20.         array(4,2,5,0,3,1),
  21.         array(3,0,2,1,4,5),
  22. );
  23.  
  24. $solution = array_fill(0, 6, array_fill(0, 6, false));
  25.  
  26.  
  27. function solve_color($color) {
  28.         global $solution, $used_towers, $colors, $cube;
  29.  
  30.         $orig = $solution;
  31.         $failed = array( );
  32.  
  33.         $i = 0;
  34.         $j = -1;
  35.         while ($i <= 5) {
  36.                 // if we already have a piece in this space (via pre-reqs)
  37.                 // just skip it
  38.                 if (in_array($color, $orig[$i])) {
  39.                         $i++;
  40.                         $j = -1;
  41.                         continue;
  42.                 }
  43.  
  44.                 if ( ! isset($failed[$i])) {
  45.                         $failed[$i] = array( );
  46.                 }
  47.  
  48.                 do {
  49.                         $j++;
  50.                         $size = $cube[$i][$j];
  51.                         // we've already tried this one, try the next space
  52.                 } while (in_array($size, $failed[$i]) && (5 > $j));
  53.  
  54.                 // try putting a piece in the ith row in the last + 1 col
  55.                 if (test_color(($i * 6) + $j, $solution, $used_towers, $color, $size) && ! in_array($size, $failed[$i])) {
  56.                         $solution[$i][$j] = $color;
  57.                         $used_towers[$size] |= $color;
  58.                         $i++;
  59.                         $j = -1;
  60.                         continue;
  61.                 }
  62.  
  63.                 // something failed, go back a row and try a new piece
  64.                 if (5 <= $j) {
  65.                         // backtrack until we find a row that didn't already have a piece in it
  66.                         do {
  67.                                 $i--;
  68.                         } while (in_array($color, $orig[$i]));
  69.  
  70.                         // find out what piece was used here
  71.                         foreach ($solution[$i] as $j => $col) {
  72.                                 if ($color == $col) {
  73.                                         $size = $cube[$i][$j];
  74.                                         $failed[$i][] = $size;
  75.                                         $used_towers[$size] ^= $color;
  76.                                 }
  77.                         }
  78.  
  79.                         $solution[$i] = $orig[$i];
  80.                         $j = -1;
  81.                         continue;
  82.                 }
  83.         }
  84.  
  85.         return $solution;
  86. }
  87.  
  88.  
  89. function solve_color_by_pieces($color, $solution, $used_towers, $continue_colors = false, $top = false) {
  90.         global $colors, $cube;
  91.  
  92.         $orig = $solution;
  93.  
  94.         $sols = array( );
  95.         while (32 >= $color) {
  96.                 $size = 0;
  97.  
  98.                 while (6 >= count(filter_color($used_towers, $color)) && (5 >= $size)) {
  99.                         if ($color & $used_towers[$size]) {
  100.                                 $size++;
  101.                                 continue;
  102.                         }
  103.  
  104.                         // find ALL possible solutions for this size
  105.                         for ($pos = 0; $pos < 36; ++$pos) {
  106.                                 if ($size != $cube[floor($pos / 6)][$pos % 6]) {
  107.                                         continue;
  108.                                 }
  109.  
  110.                                 if ( ! test_color($pos, $solution, $used_towers, $color, $size)) {
  111.                                         continue;
  112.                                 }
  113.  
  114.                                 // add to this solution path and continue...
  115.                                 $solution[floor($pos / 6)][$pos % 6] = $color;
  116.                                 $used_towers[$size] |= $color;
  117.                                 $return = ((6 > count(filter_color($used_towers, $color))) ? solve_color_by_pieces($color, $solution, $used_towers, $continue_colors) : array('SOLUTION' => $solution));
  118.                                 if ($return) {
  119.                                         $sols[] = $return;
  120.                                 }
  121.  
  122.                                 // remove this solution and continue searching this level
  123.                                 $solution[floor($pos / 6)][$pos % 6] = false;
  124.                                 $used_towers[$size] ^= $color;
  125.                         }
  126.  
  127.                         break;
  128.                 }
  129.  
  130.                 if ($top) {
  131.                         unset($sols);
  132.                         $sols = array( );
  133.                 }
  134.  
  135.                 if ($continue_colors) {
  136.                         $color << 1;
  137.                 }
  138.                 else {
  139.                         break;
  140.                 }
  141.         }
  142.  
  143.         return $sols;
  144. }
  145.  
  146.  
  147.  
  148.  
  149. // solve for yellow given the initial piece constraint
  150. $color = 4;
  151. $solution[1][2] = $color;
  152. $size = $cube[1][2];
  153. $used_towers[$size] |= $color;
  154. echo solve_color_by_pieces($color, $solution, $used_towers);
  155.  
  156.  
  157.  
  158. // helper functions
  159.  
  160. function test_color($pos, $solution, $used_towers, $color, $size) {
  161.         if (36 <= $pos) {
  162.                 return false;
  163.         }
  164.  
  165.         // check if piece exists in solution at this location
  166.         if (false !== $solution[floor($pos / 6)][$pos % 6]) {
  167.                 return false;
  168.         }
  169.  
  170.         // check if tower of this size and color has already been used
  171.         if ($color & $used_towers[$size]) {
  172.                 return false;
  173.         }
  174.  
  175.         // check if tower has already been used in row or column:
  176.         for ($i = 0; $i < 6; ++$i) {
  177.                 if ($color == $solution[floor($pos / 6)][$i]) {
  178.                         return false;
  179.                 }
  180.  
  181.                 if ($color == $solution[$i][$pos % 6]) {
  182.                         return false;
  183.                 }
  184.         }
  185.  
  186.         // special conditions for the two special towers
  187.         if (array(1, 2) == (array(floor($pos / 6), $pos % 6)) && (4 != $color)) {
  188.                 return false;
  189.         }
  190.  
  191.         if (array(3, 2) == (array(floor($pos / 6), $pos % 6)) && (2 != $color)) {
  192.                 return false;
  193.         }
  194.  
  195.         return true;
  196. }
  197.  
  198.  
  199. function filter_color($used, $color) {
  200.         foreach ($used as & $row) {
  201.                 $row = (bool) ($color & $row);
  202.         }
  203.         unset($row);
  204.  
  205.         return array_filter($used);
  206. }
  207.  
  208.  
  209. function find_sols($sols, $color) {
  210.         foreach ($sols as $key => $sol) {
  211.                 if ('SOLUTION' === $key) {
  212.                         foreach ($sol as $i => $row) {
  213.                                 foreach ($row as $j => $piece) {
  214.                                         if ($color == $piece) {
  215.                                                 echo '$solution['.$i.']['.$j.'] = ';
  216.                                         }
  217.                                 }
  218.                         }
  219.                         echo "<br>\n";
  220.                 }
  221.                 elseif (is_array($sol)) {
  222.                         find_sols($sol, $color);
  223.                 }
  224.         }
  225. }
RAW Paste Data
Top