SHARE
TWEET

36 cube iterative solution FULL

a guest Jan 18th, 2011 289 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),
  18.         array(0,1,3,2,5,4),
  19.         array(5,4,0,3,0,2),
  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. $solutions = array( );
  26.  
  27. function test_color($pos, $solution, $used_towers, $color, $size) {
  28.         if (36 <= $pos) {
  29.                 return false;
  30.         }
  31.  
  32.         // check if piece exists in solution at this location
  33.         if (false !== $solution[floor($pos / 6)][$pos % 6]) {
  34.                 return false;
  35.         }
  36.  
  37.         // check if tower of this size and color has already been used
  38.         if ($color & $used_towers[$size]) {
  39.                 return false;
  40.         }
  41.  
  42.         // check if tower has already been used in row or column:
  43.         for ($i = 0; $i < 6; ++$i) {
  44.                 if ($color == $solution[floor($pos / 6)][$i]) {
  45.                         return false;
  46.                 }
  47.  
  48.                 if ($color == $solution[$i][$pos % 6]) {
  49.                         return false;
  50.                 }
  51.         }
  52.  
  53.         // special conditions for the two special towers
  54.         if (array(1, 2) == (array(floor($pos / 6), $pos % 6)) && (4 != $color)) {
  55.                 return false;
  56.         }
  57.  
  58.         if (array(3, 2) == (array(floor($pos / 6), $pos % 6)) && (2 != $color)) {
  59.                 return false;
  60.         }
  61.  
  62.         return true;
  63. }
  64.  
  65.  
  66. function filter_color($used, $color) {
  67.         foreach ($used as & $row) {
  68.                 $row = (bool) ($color & $row);
  69.         }
  70.         unset($row);
  71.  
  72.         return array_filter($used);
  73. }
  74.  
  75.  
  76. function solve_color_by_pieces($color, $solution, $used_towers, $continue_colors = false) {
  77.         global $colors, $cube, $MASTER;
  78.  
  79.         $orig = $solution;
  80.  
  81.         if (32 < $color) {
  82.                 // convert all numbers to letters based on position and flatten
  83.                 list($converted, $key) = convert_solution($solution);
  84.                 if ( ! in_array($converted, $MASTER['solution'])) {
  85.                         $MASTER['solution'][] = $converted;
  86.                         $MASTER['key'][] = $key;
  87.                 }
  88.  
  89.                 return $solution;
  90.         }
  91.  
  92.         if (6 <= count(filter_color($used_towers, $color))) {
  93.                 return solve_color_by_pieces($color << 1, $solution, $used_towers, $continue_colors);;
  94.         }
  95.  
  96.         $sols = array( );
  97.         $size = 0;
  98.  
  99.         while (5 >= $size) {
  100.                 if ($color & $used_towers[$size]) {
  101.                         $size++;
  102.                         continue;
  103.                 }
  104.  
  105.                 // find ALL possible solutions for this size
  106.                 for ($pos = 0; $pos < 36; ++$pos) {
  107.                         if ($size != $cube[floor($pos / 6)][$pos % 6]) {
  108.                                 continue;
  109.                         }
  110.  
  111.                         if ( ! test_color($pos, $solution, $used_towers, $color, $size)) {
  112.                                 continue;
  113.                         }
  114.  
  115.                         // add to this solution path and continue...
  116.                         $solution[floor($pos / 6)][$pos % 6] = $color;
  117.                         $used_towers[$size] |= $color;
  118.  
  119.                         // if we're not done with this color
  120.                         if (6 > count(filter_color($used_towers, $color))) {
  121.                                 $return = solve_color_by_pieces($color, $solution, $used_towers, $continue_colors);
  122.                         }
  123.                         elseif ($continue_colors) {
  124.                                 $return = solve_color_by_pieces($color << 1, $solution, $used_towers, $continue_colors);
  125.                         }
  126.                         else {
  127.                                 $return = $solution;
  128.                         }
  129.  
  130.                         if ($return) {
  131.                                 $sols[] = $return;
  132.                         }
  133.  
  134.                         // remove this solution and continue searching this level
  135.                         $solution[floor($pos / 6)][$pos % 6] = false;
  136.                         $used_towers[$size] ^= $color;
  137.                 }
  138.  
  139.                 break;
  140.         }
  141.  
  142.         return $sols;
  143. }
  144.  
  145.  
  146. function convert_solution($sol) {
  147.         global $colors;
  148.  
  149.         $letters = array('A','B','C','D','E','F');
  150.  
  151.         $output = '';
  152.         foreach ($sol as $i => & $row) {
  153.                 foreach ($row as $j => & $piece) {
  154.                         if ( ! $i) {
  155.                                 $conv[$piece] = $letters[$j];
  156.                         }
  157.                         $output .= $conv[$piece];
  158.                 }
  159.         }
  160.  
  161.         $key = array( );
  162.         foreach ($conv as $color => $letter) {
  163.                 $key[$letter] = $colors[$color];
  164.         }
  165.  
  166.         return array($output, $key);
  167. }
  168.  
  169. // solve for red
  170. $solution[1][2] = 4; // yellow
  171. $size = $cube[1][2];
  172. $used_towers[$size] |= 4;
  173.  
  174. $solution[3][2] = 2; // orange
  175. $size = $cube[3][2];
  176. $used_towers[$size] |= 2;
  177. $color = 1;
  178.  
  179. $MASTER = array('solution' => array( ), 'key' => array( ));
  180.  
  181. solve_color_by_pieces($color, $solution, $used_towers, true);
  182. debug($MASTER);
  183.  
  184.  
  185.  
  186. /** function call [dump] [debug]
  187.  *              This function is for debugging only
  188.  *              Outputs given var to screen
  189.  *              or, if no var given, outputs stars to note position
  190.  *
  191.  * @param mixed optional var to output
  192.  * @param bool optional bypass debug value and output anyway
  193.  * @action outputs var to screen
  194.  * @return void
  195.  */
  196. function call($var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*$axe', $bypass = false, $show_from = true, $new_window = false, $error = false)
  197. {
  198.         if ((( ! defined('DEBUG') || ! DEBUG) || ! empty($GLOBALS['NODEBUG'])) && ! (bool) $bypass) {
  199.                 return false;
  200.         }
  201.  
  202.         if ('Th&F=xUFucreSp2*ezAhe=ApuPR*$axe' === $var) {
  203.                 $contents = '<span style="font-size:larger;font-weight:bold;color:red;">--==((OO88OO))==--</span>';
  204.         }
  205.         else {
  206.                 // begin output buffering so we can escape any html
  207.                 // and print_r is better at catching recursion than var_export
  208.                 ob_start( );
  209.  
  210.                 if ((is_string($var) && ! preg_match('/^\\s*$/', $var))) { // non-whitespace strings
  211.                         print_r($var);
  212.                 }
  213.                 else {
  214.                         if ( ! function_exists('xdebug_disable')) {
  215.                                 if (is_array($var) || is_object($var)) {
  216.                                         print_r($var);
  217.                                 }
  218.                                 else {
  219.                                         var_dump($var);
  220.                                 }
  221.                         }
  222.                         else {
  223.                                 var_dump($var);
  224.                         }
  225.                 }
  226.  
  227.                 // end output buffering and output the result
  228.                 if ( ! function_exists('xdebug_disable')) {
  229.                         $contents = htmlentities(ob_get_contents( ));
  230.                 }
  231.                 else {
  232.                         $contents = ob_get_contents( );
  233.                 }
  234.  
  235.                 ob_end_clean( );
  236.         }
  237.  
  238.         $j = 0;
  239.         $html = '';
  240.         $debug_funcs = array('dump', 'debug');
  241.         if ((bool) $show_from) {
  242.                 $called_from = debug_backtrace( );
  243.  
  244.                 if (isset($called_from[$j + 1]) && in_array($called_from[$j + 1]['function'], $debug_funcs)) {
  245.                         ++$j;
  246.                 }
  247.  
  248.                 $file0 = substr($called_from[$j]['file'], strlen($_SERVER['DOCUMENT_ROOT']));
  249.                 $line0 = $called_from[$j]['line'];
  250.  
  251.                 $called = '';
  252.                 if (isset($called_from[$j + 1]['file'])) {
  253.                         $file1 = substr($called_from[$j + 1]['file'], strlen($_SERVER['DOCUMENT_ROOT']));
  254.                         $line1 = $called_from[$j + 1]['line'];
  255.                         $called = "{$file1} : {$line1} called ";
  256.                 }
  257.                 elseif (isset($called_from[$j + 1]['class'])) {
  258.                         $called = $called_from[$j + 1]['class'].$called_from[$j + 1]['type'].$called_from[$j + 1]['function'].' called ';
  259.                 }
  260.  
  261.                 $html = "<strong>{$called}{$file0} : {$line0}</strong>\n";
  262.         }
  263.  
  264.         if ( ! $new_window) {
  265.                 $color = '#000';
  266.                 if ($error) {
  267.                         $color = '#F00';
  268.                 }
  269.  
  270.                 echo "\n\n<pre style=\"background:#FFF;color:{$color};font-size:larger;\">{$html}{$contents}\n<hr /></pre>\n\n";
  271.         }
  272.         else { ?>
  273.                 <script language="javascript">
  274.                         myRef = window.open('','debugWindow');
  275.                         myRef.document.write('\n\n<pre style="background:#FFF;color:#000;font-size:larger;">');
  276.                         myRef.document.write('<?php echo str_replace("'", "\'", str_replace("\n", "<br />", "{$html}{$contents}")); ?>');
  277.                         myRef.document.write('\n<hr /></pre>\n\n');
  278.                 </script>
  279.         <?php }
  280. }
  281. function dump($var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*$axe', $bypass = false, $show_from = true, $new_window = false, $error = false) { call($var, $bypass, $show_from, $new_window, $error); }
  282. function debug($var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*$axe', $bypass = true, $show_from = true, $new_window = false, $error = false) { call($var, $bypass, $show_from, $new_window, $error); }
RAW Paste Data
Want to get better at PHP?
Learn to code PHP in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top