001      /*    Author Malte Pagel    */
002      
003          error_reporting(E_STRICT | E_ALL);
004      
005          if ( !isset($_GET['puzzle']) || !$_GET['puzzle'] || !isset($_GET['speed']) || !$_GET['speed'] || !isset($_GET['offset']) )
006              die( "personal_debug( 'No vaild puzzle data' );" );
007      
008          /**
009           * Human-readable vardump
010           * An invention of O. Schwarten, osdata.org
011           */
012          function v ($x) {
013              echo "<pre>";
014              print_r($x);
015              echo "</pre>";
016          }
017          
018          $sent_puzzle = $_GET['puzzle'];
019          $piece_line = explode(";", $sent_puzzle);
020          for ( $i = 0; $i < count($piece_line); $i++ ) {
021              if ( !$piece_line[$i] ) {
022                  $black_index = $i;
023                  break;
024              }
025          }
026          
027          define("COLS", sqrt(count($piece_line)));
028          define("SPEED", $_GET['speed']);                                            // Does not really seem to be used
029          define("OFFSET", $_GET['offset']);
030          
031          
032          function answer_no_success () {
033              if ( defined("ANSWERED") )
034                  return;
035              
036              define("ANSWERED", 1);
037              echo "next_try( " . OFFSET . " );";
038          }
039          function answer_success ($moves) {
040              if ( defined("ANSWERED") )
041                  return;
042              
043              define("ANSWERED", 1);
044              echo "solution_is_found( [" . implode(", ", $moves) . "], " . OFFSET . " );";
045          }
046          
047          function would_be_closer ($actual, $eventual, $wanted) {
048              
049              $actual_horizontal = abs(($actual % COLS) - ($wanted % COLS));
050              $actual_vertical = abs( (int) ($actual / COLS) - (int) ($wanted / COLS) );
051              $actual_distance = $actual_horizontal + $actual_vertical;
052              
053              $eventual_horizontal = abs(($eventual % COLS) - ($wanted % COLS));
054              $eventual_vertical = abs( (int) ($eventual / COLS) - (int) ($wanted / COLS) );
055              $eventual_distance = $eventual_horizontal + $eventual_vertical;
056              
057              return ($eventual_distance < $actual_distance) ? 1 : 0;
058          }
059          
060          function eventually_continue_search ($moves_made, $situation, $moving_piece_position, $black_position, $allowed_faults) {
061              if ( empty($moves_made) || $situation[$moving_piece_position] != $moves_made[count($moves_made) - 1] ) {
062                  $better = would_be_closer($moving_piece_position, $black_position, ($situation[$moving_piece_position] - 1));
063                  if ( $better || $allowed_faults > 0 ) {
064                      
065                      $tmp_moves_made = $moves_made;
066                      $tmp_moves_made[] = $situation[$moving_piece_position];
067                      
068                      $tmp_situation = $situation;
069                      $tmp_situation[$black_position] = $situation[$moving_piece_position];
070                      $tmp_situation[$moving_piece_position] = $situation[$black_position];
071                      
072                      if ( $better ) {
073                          stack_search($tmp_situation, $moving_piece_position, $tmp_moves_made, $allowed_faults);
074                          return 1;
075                      }
076                      else
077                          stack_search($tmp_situation, $moving_piece_position, $tmp_moves_made, --$allowed_faults);
078                  }
079              }
080              return 0;
081          }
082          
083          function test_if_solved ($situation) {
084              for ( $i = 0; $i < count($situation); $i++ )
085                  if ( $situation[$i] && ($situation[$i] - 1) != $i )
086                      return;
087              
088              define("SOLUTION_FOUND", 1);
089          }
090          
091          function stack_search ($situation, $black_position, $moves_made, $allowed_faults) {
092              
093              if ( defined("SOLUTION_FOUND") || defined("ANSWERED") )
094                  return;
095              
096              $found_something_good = 0;
097              
098              // move black piece up, other piece down
099              if ( ($black_position - COLS) >= 0 ) {
100                  $moving_piece_position = $black_position - COLS;
101                  
102                  if ( eventually_continue_search($moves_made, $situation, $moving_piece_position, $black_position, $allowed_faults) )
103                      $found_something_good = 1;
104              }
105              
106              // move black piece to right, other piece to left
107              if ( ($black_position % COLS) != (COLS - 1) ) {
108                  $moving_piece_position = $black_position + 1;
109                  
110                  if ( eventually_continue_search($moves_made, $situation, $moving_piece_position, $black_position, $allowed_faults) )
111                      $found_something_good = 1;
112              }
113              
114              // move black piece down, other piece up
115              if ( ($black_position + COLS) < (COLS * COLS) ) {
116                  $moving_piece_position = $black_position + COLS;
117                  
118                  if ( eventually_continue_search($moves_made, $situation, $moving_piece_position, $black_position, $allowed_faults) )
119                      $found_something_good = 1;
120              }
121              
122              // move black piece to left, other piece to right
123              if ( ($black_position % COLS) != 0 ) {
124                  $moving_piece_position = $black_position - 1;
125                  
126                  if ( eventually_continue_search($moves_made, $situation, $moving_piece_position, $black_position, $allowed_faults) )
127                      $found_something_good = 1;
128              }
129              
130              if ( !$found_something_good )
131                  test_if_solved($situation);
132              
133              if ( defined("SOLUTION_FOUND") ) {
134                  answer_success($moves_made);
135                  return;
136              }
137          }
138          
139          
140          /*  */
141          
142      
143          $moves_made = Array();
144          stack_search($piece_line, $black_index, $moves_made, OFFSET);
145          
146          if ( !defined("SOLUTION_FOUND") )
147              answer_no_success();
148      
149