Guest User

36 cube iterative solution

a guest
Jan 7th, 2011
266
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