Brute-forcing with a recursive function a chess knight puzzle

[AnotherLife]

I want to solve a chess knight puzzle (it is for the testament of sherlok holmes game )

 

I have a 8x8 size chess board and the knight starts at (0,0). I got to find a sequence of moves to cover every spot on the chess board. (I suppose everyone knows the actual knight allowed movement in chess)

 

Here is my code, but I can't find what is wrong with it. Looking at the output, after some moves it sometimes chooses the wrong square to move to ...

<?php

echo "\n  - Knight puzzle brute forcer by VGA - \n";
$currpos = array(0,0);
$occupiedpositions = array();
$validpositions = getvalidmoves($currpos, $occupiedpositions);

print_r ($validpositions);

function getvalidmoves($currpos, $occupiedpositions) {

	$validpositions = array(
		array($currpos[0]+1,$currpos[1]-2),
		array($currpos[0]+2,$currpos[1]-1),
		array($currpos[0]+2,$currpos[1]+1),
		array($currpos[0]+1,$currpos[1]+2),
		array($currpos[0]-1,$currpos[1]+2),
		array($currpos[0]-2,$currpos[1]+1),
		array($currpos[0]-1,$currpos[1]-2),
		array($currpos[0]-2,$currpos[1]-1)
	);
	
	foreach ($validpositions as $key => $pos) {
		if (($pos[0] < 0) || ($pos[0] > 7) || ($pos[1] < 0) || ($pos[1] > 7) || in_array($pos,$occupiedpositions)) {
			unset($validpositions[$key]);
		}
	}
	
	if (sizeof($validpositions) > 0) {
		if (sizeof($occupiedpositions) == 62) {
			echo "SUCCESS !!!!!!!\n";
			print_r ($occupiedpositions);
			exit;
		}
	} else {
		echo "FAILURE after ",sizeof($occupiedpositions)," moves \n";
		return;			
	}
	
	foreach ($validpositions as $key => $pos) {
		array_push($occupiedpositions,$currpos);
		$currpos = $pos;
		getvalidmoves($currpos, $occupiedpositions);
	}
	
	return;
}
?>

[Psycho]

What do you mean by " . . . after some moves it sometimes chooses the wrong square to move to . . . "? Are you saying it chooses a square not on the board or that it chooses a square that has already been used?

 

I ran the code and the results were that there were a large number of "Failures" after x number of moves and then a "Success" at the end. Don't know how you are seeing that some are choosing the wrong positions.

[AnotherLife]

After the success it prints the  sequence of moves. I follow that and sooner or later some moves start being wrong (wrong movement pattern for the knight !) but it never tries to move to a previously visited square at least.

[Psycho]

After the success it prints the  sequence of moves. I follow that and sooner or later some moves start being wrong (wrong movement pattern for the knight !) but it never tries to move to a previously visited square at least.

 

Not sure what you are saying exactly. How do you know the moves are wrong? I can verify that the success result does not duplicate any positions. But, I noticed that you are stopping the process too early! On an 8 x 8 board there are 64 total positions and you are exiting the process after only 62 positions are reached. But, just increasing the number to 63 caused the script to timeout after 60 seconds and over 379,000 different attempts. Increasing it to 64 would take exponentially longer.

Edited September 17, 2013 by Psycho

[AnotherLife]

I see the moves because I print the $occupiedpositions and check the moves one by one. And when I see (2,2) and then (1,1) for example, well, it's wrong.

 

Also, my thinking is that there are 62 occupied squares, 1 current square and 1 valid position remaining at the point I do that check. Still, that's not my main concern.

[Psycho]

Hmm . . . yes, that's odd. I don't see anything that jumps out at me.

[AnotherLife]

It's weird that there is a situation that an invalid move is selected since there are 8 valid moves minus the out of border moves minus the already passed-through squares.

 

Maybe it's some PHP array intricacy. Maybe "unset" doesn't work the way I think it does ? Maybe some variable confusion ?

 

Another indication of an error is that before I put code in to stop execution and print the result at the first success, the program would run seemingly forever. Isn't there a finite combination of possible and valid moves ? I had left it running for 2-3 hours and the program didn't end, so the first function call never returned.

 

This recursive stuff is hard to debug, too 

[Psycho]

I tried adding some debugging and wasn't able to see why that problem was occurring either. It's not so much that it is a recursive function as much as it is exponential. Each execution triggers up 8 separate new executions. So, it increases exponentially.

 

 

Another indication of an error is that before I put code in to stop execution and print the result at the first success, the program would run seemingly forever. Isn't there a finite combination of possible and valid moves ? I had left it running for 2-3 hours and the program didn't end, so the first function call never returned.

 

It's hard to say if that is due to a bug or not because, as I stated, each execution increases exponentially.

 

Although, I do think the function could be improved. For instance, why do you need to pass $currpos to the function. Start with an array with the first position and pass it is as the $occupiedpositions array. You can then determine $currpos by getting last value in the array. I don't know where the problem is, but reducing the number of variables and complexity could only help find the problem.

Edited September 19, 2013 by Psycho

[Psycho]

Aha! Here's the problem

 

    foreach ($validpositions as $key => $pos) {
        array_push($occupiedpositions,$currpos);
        $currpos = $pos;
        getvalidmoves($currpos, $occupiedpositions);
    }

 

In that loop you are appening $currpos to the end of $occupiedpositions. On the first iteration of that loop $currpos is the value that was passed to the function. Then on the subsequent iterations it is appending the previous "valid moves". There are a couple problems with that. One is that the valid moves are only valid if the current last position. Instead, you are adding valid postion2 after valid position1 - which may not be a valid move from position1. Plus, you are never adding the last valid position!

 

So, let's say your occupied positions are A, B, & C. And you pass current position as D to the function. It then calculates that the valid positions from D are E, F, & G. You should end up with three new arrays as:

A, B, C, D, E

A, B, C, D, F

A, B, C, D, G

 

Instead you are getting

A, B, C, D, E

A, B, C, D, E, F

A, B, C, D, E, F, G

 

Instead of adding the values to the same array, you need to create a new array containing $occupiedpositions (as passed to the function) and just the next valid position. To do this, it would be easiest to have the current position already included.

Edited September 19, 2013 by Psycho

[Psycho]

OK, here is a corrected version. I also added a better output of the success value to make it easier to validate the results. It shows each position and the change from the last position: either 1, 2 or 2, 1. Note, the function is still only looking for 62 valid positions - but there are 64 positions on an 8 x 8 board. It took about 20 seconds to run for 62 positions. Increasing to 63 to calculate a success caused a timeout at 60 seconds. So, going to 64 will probably take good while to run.

 

I'll let you verify the results

 

<?php

function getvalidmoves($occupiedPositions)
{
    //Check if max moves have already been reached (should be 64)
    if (count($occupiedPositions) == 62)
    {
        echo "SUCCESS !!!!!!!<br>\n";
        $lastPos = false;
        foreach($occupiedPositions as $idx => $pos)
        {
            echo "{$idx}: Position: $pos[0], $pos[1]";
            if($lastPos)
            {
                echo ", Movement: " . abs($pos[0]-$lastPos[0]) . ", " . abs($pos[1]-$lastPos[1]);
            }
            echo "<br>\n";
            $lastPos = $pos;
        }
        //echo "<pre>" . print_r ($occupiedPositions, 1) . "</pre>";
        exit;
    }

    //Determine the current position
    $curPosition = end($occupiedPositions);

    //Determine 'possible' next positions
    $nextPositions = array(
        array($curPosition[0]+1, $curPosition[1]-2),
        array($curPosition[0]+2, $curPosition[1]-1),
        array($curPosition[0]+2, $curPosition[1]+1),
        array($curPosition[0]+1, $curPosition[1]+2),
        array($curPosition[0]-1, $curPosition[1]+2),
        array($curPosition[0]-2, $curPosition[1]+1),
        array($curPosition[0]-1, $curPosition[1]-2),
        array($curPosition[0]-2, $curPosition[1]-1)
    );
    
    //Remove invalid next positions
    foreach ($nextPositions as $key => $pos)
    {
        if (($pos[0] < 0) || ($pos[0] > 7) || ($pos[1] < 0) || ($pos[1] > 7) || in_array($pos, $occupiedPositions))
        {
            unset($nextPositions[$key]);
        }
    }

    //If no valid positions exist, abandon this thread
    if (!count($nextPositions))
    {
        echo "FAILURE after " . count($occupiedPositions)," moves<br>\n";
        return;    
    }
    
    //Call function again for each valid next position
    //starting from the current occupied positions
    foreach ($nextPositions as $key => $nextPos)
    {
        $newPositions = $occupiedPositions;
        $newPositions[] = $nextPos;
        getvalidmoves($newPositions);
    }
    return;
}

echo "\n  - Knight puzzle brute forcer by VGA -<br><br>\n";

$startPos = array(0,0);
$occupiedPositions[] = $startPos;
$validMoves = getvalidmoves($occupiedPositions);

echo "<pre>" . print_r ($validMoves, 1) . "</pre>";

?>

 

Note, I moved some logic around to be more efficient. For example, I check if max moves has been reached before trying to determine any next moves.

Edited September 19, 2013 by Psycho

[AnotherLife]

Thank you very much, I will dedicate a lot of time tomorrow to read your posts until I understand why my version is bugged and then I'll test your version.   

[AnotherLife]

I tried your code and it produced a valid 62-move sequence. Of course the puzzle was unsolvable because there were no more valid moves, so I changed the check for 63 moves and it's been running for at least 2 hours

 

Before I checked your version I fixed the bug you pointed out, here is my fixed version:

<?php

echo "\n  - Knight puzzle brute forcer - \n";
$start_time = microtime(true);
$currpos = array(0,0);
$occupiedpositions = array();
$validpositions = getvalidmoves($currpos, $occupiedpositions);

function getvalidmoves($currpos, $occupiedpositions) {

    $validpositions = array(
        array($currpos[0]+1,$currpos[1]-2),
        array($currpos[0]+2,$currpos[1]-1),
        array($currpos[0]+2,$currpos[1]+1),
        array($currpos[0]+1,$currpos[1]+2),
        array($currpos[0]-1,$currpos[1]+2),
        array($currpos[0]-2,$currpos[1]+1),
        array($currpos[0]-1,$currpos[1]-2),
        array($currpos[0]-2,$currpos[1]-1)
    );
    
    foreach ($validpositions as $key => $pos) {
        if (($pos[0] < 0) || ($pos[0] > 7) || ($pos[1] < 0) || ($pos[1] > 7) || in_array($pos,$occupiedpositions)) {
            unset($validpositions[$key]);
        }
    }
    
    if (sizeof($validpositions) > 0) {
        if (sizeof($occupiedpositions) == 62) {
            echo "\x07\n  Success after : ",(microtime(true)-$start_time)/1000000," seconds";
            print_r ($occupiedpositions);
            exit;
        }
    } else {
        //echo "FAILURE after ",sizeof($occupiedpositions)," moves \n";
        return;            
    }
    
    foreach ($validpositions as $key => $pos) {
        $newoccupiedpositions = $occupiedpositions;
        array_push($newoccupiedpositions,$currpos);
        $currpos = $pos;
        getvalidmoves($currpos, $newoccupiedpositions);
    }
    
    return;
}
?>

On my PC it takes 23 minutes to produce a result. Note that I check for 62 moves because I haven't added the current position yet. So it's 63 moves, and since there is at least another valid move, it seems correct to me that this sequence would be a puzzle-solver. Anyway, look at the result:

    [0] => Array
            [0] => 0
            [1] => 0
    [1] => Array
            [0] => 2
            [1] => 1
    [2] => Array
            [0] => 4
            [1] => 0
    [3] => Array
            [0] => 6
            [1] => 1
    [4] => Array
            [0] => 7
            [1] => 3
    [5] => Array
            [0] => 6
            [1] => 5
    [6] => Array
            [0] => 7
            [1] => 7
    [7] => Array
            [0] => 5
            [1] => 6
    [8] => Array
            [0] => 6
            [1] => 4
    [9] => Array
            [0] => 7
            [1] => 2
    [10] => Array
            [0] => 5
            [1] => 3
    [11] => Array
            [0] => 7
            [1] => 4
    [12] => Array
            [0] => 6
            [1] => 6
    [13] => Array
            [0] => 4
            [1] => 7
    [14] => Array
            [0] => 5
            [1] => 5
    [15] => Array
            [0] => 6
            [1] => 3
    [16] => Array
            [0] => 7
            [1] => 1
    [17] => Array
            [0] => 5
            [1] => 2
    [18] => Array
            [0] => 6
            [1] => 0
    [19] => Array
            [0] => 4
            [1] => 1
    [20] => Array
            [0] => 6
            [1] => 2
    [21] => Array
            [0] => 7
            [1] => 0
    [22] => Array
            [0] => 5
            [1] => 1
    [23] => Array
            [0] => 4
            [1] => 3
    [24] => Array
            [0] => 3
            [1] => 5
    [25] => Array
            [0] => 5
            [1] => 4
    [26] => Array
            [0] => 7
            [1] => 5
    [27] => Array
            [0] => 6
            [1] => 7
    [28] => Array
            [0] => 4
            [1] => 6
    [29] => Array
            [0] => 2
            [1] => 7
    [30] => Array
            [0] => 1
            [1] => 5
    [31] => Array
            [0] => 2
            [1] => 3
    [32] => Array
            [0] => 3
            [1] => 1
    [33] => Array
            [0] => 5
            [1] => 0
    [34] => Array
            [0] => 4
            [1] => 2
    [35] => Array
            [0] => 3
            [1] => 4
    [36] => Array
            [0] => 4
            [1] => 5
    [37] => Array
            [0] => 0
            [1] => 7
    [38] => Array
            [0] => 2
            [1] => 6
    [39] => Array
            [0] => 3
            [1] => 3
    [40] => Array
            [0] => 1
            [1] => 4
    [41] => Array
            [0] => 3
            [1] => 7
    [42] => Array
            [0] => 1
            [1] => 7
    [43] => Array
            [0] => 0
            [1] => 6
    [44] => Array
            [0] => 2
            [1] => 5
    [45] => Array
            [0] => 1
            [1] => 3
    [46] => Array
            [0] => 3
            [1] => 2
    [47] => Array
            [0] => 4
            [1] => 4
    [48] => Array
            [0] => 7
            [1] => 6
    [49] => Array
            [0] => 5
            [1] => 7
    [50] => Array
            [0] => 3
            [1] => 6
    [51] => Array
            [0] => 1
            [1] => 6
    [52] => Array
            [0] => 0
            [1] => 5
    [53] => Array
            [0] => 2
            [1] => 4
    [54] => Array
            [0] => 0
            [1] => 4
    [55] => Array
            [0] => 1
            [1] => 2
    [56] => Array
            [0] => 2
            [1] => 0
    [57] => Array
            [0] => 0
            [1] => 1
    [58] => Array
            [0] => 3
            [1] => 0
    [59] => Array
            [0] => 1
            [1] => 1
    [60] => Array
            [0] => 0
            [1] => 3
    [61] => Array
            [0] => 2
            [1] => 2
 

I was validating on a chessboard-like GUI I made and it was fine for the first 35 moves. But look at elements 35 and 36. It moved from (3,4) to (4,5)

What the heck

Edited November 10, 2013 by AnotherLife