February 17, 2015 at 12:26Visual brute force on the example of solving a 3D puzzle
Once upon a time, friends presented this puzzle:
I could not assemble it myself (there was always one fragment left). Therefore, it was decided to write a program.
For those who do not like to read, the solution is available by reference (attention, it heavily loads the processor).
So, we have a puzzle consisting of 25 identical elements that need to be put in a 5x5x5 cube, where the smallest edge of the element is taken as the unit of measurement.
The choice of language fell on JavaScript. Sacrificing performance for the sake of visualization (I really wanted to make visualized bruteforce, like in a movie), the benefit of the search process was not promised to be too long (why, it will be written below).
The main assembly process will take place in a three-dimensional integer array (5x5x5), let's call it “boxes”, where we denote by a non-negative value the cell occupied by the element’s cube. For greater information content, this value will be the serial number of the position of the element in three-dimensional space. In total, there are 24 positions of the element in three-dimensional space if the rotation angle around each axis is a multiple of 90 °. For ease of counting the number of positions, I presented arubik's cube , in which the sides are painted in different colors. Each time he turns to us with a new face and rotates four times clockwise 90 ° so that this face always looks at us. Total 6 faces x 4 turns = 24 positions in the space where our eyes are motionless.
Knowing the number of positions of an object in three-dimensional space and supplementing it with a reflection of each state (the other two reflections, both together and separately, will give either the same cube or its first reflection after torsion), we obtain that for each unique puzzle solution there can be more than one , there are 47 more of its variations, and therefore, the time required for the solution will be less than the time of exhaustive search. Unfortunately, I can’t deduce a formula for calculating the number of moves to find a solution, so if anyone can, please write in the comments, I will add to the article.
The position of the element in space will be the relative coordinates of the five unit cubes of which the element consists: the coordinates will be taken relative to the base point (its coordinates [0,0,0], respectively). The main condition for the location of the base point is its mandatory location on the element so that when this element is filled with a cube, the base point is located at the base level of the cube. By the basic level we mean the level along the Z axis at which the assembly is currently taking place (the levels below are completely filled). Thus, we have simplified for ourselves (and not only) further calculations.
The assembly order is determined by the puzzle itself: we collect from the bottom up, as soon as the level is completely filled, go to the next one. The order of the brute force is determined by the array of positions of the elements in space. If after partial filling of the level for some free point it is impossible to find the position, the previous found element is considered incorrect, the current state and the box are removed from the array, and the search continues.
As for visualization, a three-dimensional representation of the cube is made in the form of five slices along the Z axis, along a slice for each level.
Slices are 5x5 tables filled with cells with non-negative numbers from the box. Cells are additionally colored in different colors to separate puzzle elements from each other. To reduce the load, the state of the array will be displayed once per second or at critical moments: start, pause, stop when an answer is found. In addition, we will use the “save line” to work, with which you can pause, make changes to the code and continue searching from the pause place, and not from the beginning. Also, we display the number of cycles (at the end of the cycle we take the moment of displaying the current state of the array), the number of "searches" for the last cycle and the total number of "searches".
Of the features, it is worth noting that in the prelaunch preparation at the beginning an array of possible positions is created for each “box” coordinate, in order to cut off positions that cannot be located at this point in advance. Also, for versatility, I added the ability to change the “box” size values in all three coordinates. To increase the speed of visualization, I added an array of slice table cells.
Full code with comments:
- GitHub
- JSFiddle
We start, wait (it took 114 cycles on Google Chrome, going through 96969659 options), we look at the answer and collect it already in real life.
UPD On the advice of Serator, he added the possibility of using web workers, but it is not possible to parallelize the calculations, since the next calculation depends on the results of the previous one, so the calculations themselves are separately made in the web worker, and the visualization was left in the main stream.
The results of the work are given below in the tables *. The fraction indicates the calculation time with the active calculation tab / with the inactive calculation tab. All additions and extensions at the time of the calculation were disabled.
Using web worker **:
Without web worker:
* - The results of the work depend on the total load of the machine, therefore, the tables show the average values. The measurement error was about 5%.
** - The result of the work is given when sending values for visualization every 50 thousand searches, for other values the result fit into the error.
You can verify it yourself by running the script on the local web server.
As a matter of fact, parallelization of the calculation process itself did not occur, therefore, the time it took to calculate with the web worker was longer than without it, but its use may be useful for carrying out the calculation in the background (when the calculation tab is inactive). In addition, Firefox turned out to be the slowest for calculating with a web worker, and is comparable in time when performing calculations without it. Separately, it is worth noting that thanks to the web worker, visualization can be redrawn more often, which looks much more beautiful than without it.
I could not assemble it myself (there was always one fragment left). Therefore, it was decided to write a program.
For those who do not like to read, the solution is available by reference (attention, it heavily loads the processor).
So, we have a puzzle consisting of 25 identical elements that need to be put in a 5x5x5 cube, where the smallest edge of the element is taken as the unit of measurement.
The choice of language fell on JavaScript. Sacrificing performance for the sake of visualization (I really wanted to make visualized bruteforce, like in a movie), the benefit of the search process was not promised to be too long (why, it will be written below).
Divide the puzzle elements into cubes with a single side
The main assembly process will take place in a three-dimensional integer array (5x5x5), let's call it “boxes”, where we denote by a non-negative value the cell occupied by the element’s cube. For greater information content, this value will be the serial number of the position of the element in three-dimensional space. In total, there are 24 positions of the element in three-dimensional space if the rotation angle around each axis is a multiple of 90 °. For ease of counting the number of positions, I presented a
Knowing the number of positions of an object in three-dimensional space and supplementing it with a reflection of each state (the other two reflections, both together and separately, will give either the same cube or its first reflection after torsion), we obtain that for each unique puzzle solution there can be more than one , there are 47 more of its variations, and therefore, the time required for the solution will be less than the time of exhaustive search. Unfortunately, I can’t deduce a formula for calculating the number of moves to find a solution, so if anyone can, please write in the comments, I will add to the article.
The position of the element in space will be the relative coordinates of the five unit cubes of which the element consists: the coordinates will be taken relative to the base point (its coordinates [0,0,0], respectively). The main condition for the location of the base point is its mandatory location on the element so that when this element is filled with a cube, the base point is located at the base level of the cube. By the basic level we mean the level along the Z axis at which the assembly is currently taking place (the levels below are completely filled). Thus, we have simplified for ourselves (and not only) further calculations.
24 positions
//x,y,z
var elems=[
[[0,0,0],[1,0,0],[1,1,0],[2,1,0],[3,1,0]],//0
[[0,0,0],[1,0,0],[2,0,0],[0,0,1],[-1,0,1]],//1
[[0,0,0],[1,0,0],[1,-1,0],[2,-1,0],[3,-1,0]],//2
[[0,0,0],[1,0,0],[1,0,1],[2,0,1],[3,0,1]],//3
[[0,0,0],[1,0,0],[2,0,0],[2,-1,0],[3,-1,0]],//4
[[0,0,0],[1,0,0],[2,0,0],[2,0,1],[3,0,1]],//5
[[0,0,0],[1,0,0],[2,0,0],[2,1,0],[3,1,0]],//6
[[0,0,0],[1,0,0],[0,0,1],[-1,0,1],[-2,0,1]],//7
[[0,0,0],[0,1,0],[1,1,0],[1,2,0],[1,3,0]],//8
[[0,0,0],[0,1,0],[0,1,1],[0,2,1],[0,3,1]],//9
[[0,0,0],[0,1,0],[-1,1,0],[-1,2,0],[-1,3,0]],//10
[[0,0,0],[0,1,0],[0,2,0],[0,0,1],[0,-1,1]],//11
[[0,0,0],[0,1,0],[0,2,0],[-1,2,0],[-1,3,0]],//12
[[0,0,0],[0,1,0],[0,0,1],[0,-1,1],[0,-2,1]],//13
[[0,0,0],[0,1,0],[0,2,0],[1,2,0],[1,3,0]],//14
[[0,0,0],[0,1,0],[0,2,0],[0,2,1],[0,3,1]],//15
[[0,0,0],[0,0,1],[0,0,2],[0,1,2],[0,1,3]],//16
[[0,0,0],[0,0,1],[0,0,2],[-1,0,2],[-1,0,3]],//17
[[0,0,0],[0,0,1],[0,0,2],[0,-1,2],[0,-1,3]],//18
[[0,0,0],[0,0,1],[0,0,2],[1,0,2],[1,0,3]],//19
[[0,0,0],[0,0,1],[0,1,1],[0,1,2],[0,1,3]],//20
[[0,0,0],[0,0,1],[-1,0,1],[-1,0,2],[-1,0,3]],//21
[[0,0,0],[0,0,1],[0,-1,1],[0,-1,2],[0,-1,3]],//22
[[0,0,0],[0,0,1],[1,0,1],[1,0,2],[1,0,3]]//23
];
The assembly order is determined by the puzzle itself: we collect from the bottom up, as soon as the level is completely filled, go to the next one. The order of the brute force is determined by the array of positions of the elements in space. If after partial filling of the level for some free point it is impossible to find the position, the previous found element is considered incorrect, the current state and the box are removed from the array, and the search continues.
As for visualization, a three-dimensional representation of the cube is made in the form of five slices along the Z axis, along a slice for each level.
Slices are 5x5 tables filled with cells with non-negative numbers from the box. Cells are additionally colored in different colors to separate puzzle elements from each other. To reduce the load, the state of the array will be displayed once per second or at critical moments: start, pause, stop when an answer is found. In addition, we will use the “save line” to work, with which you can pause, make changes to the code and continue searching from the pause place, and not from the beginning. Also, we display the number of cycles (at the end of the cycle we take the moment of displaying the current state of the array), the number of "searches" for the last cycle and the total number of "searches".
Of the features, it is worth noting that in the prelaunch preparation at the beginning an array of possible positions is created for each “box” coordinate, in order to cut off positions that cannot be located at this point in advance. Also, for versatility, I added the ability to change the “box” size values in all three coordinates. To increase the speed of visualization, I added an array of slice table cells.
Full code with comments:
- GitHub
- JSFiddle
We start, wait (it took 114 cycles on Google Chrome, going through 96969659 options), we look at the answer and collect it already in real life.
Answer
Save string for anyone who wants to do a reflection check
[[5,0,0,0,0], [5,0,4,0], [12,3,0,0], [12,4,1,0]]
UPD On the advice of Serator, he added the possibility of using web workers, but it is not possible to parallelize the calculations, since the next calculation depends on the results of the previous one, so the calculations themselves are separately made in the web worker, and the visualization was left in the main stream.
The results of the work are given below in the tables *. The fraction indicates the calculation time with the active calculation tab / with the inactive calculation tab. All additions and extensions at the time of the calculation were disabled.
Using web worker **:
| Google Chrome 40.0.2214.115 (no hardware acceleration) | 168.08 sec. / 160.932 sec. |
|---|---|
| Google Chrome 40.0.2214.115 (with hardware acceleration) | 175.644 sec. / 168.802 sec. |
| Yandex Browser 12/14/2125.10034 | 163.975 sec. / 202.875 sec. |
| Internet Explorer 11 | 243.778 sec. / 246.766 sec. |
| Mozilla Firefox 35.0.1 | 731.949 sec. / 707.266 sec. |
| Opera 27.0.1689.69 | 213.088 sec. / 189.991 sec. |
Without web worker:
| Google Chrome 40.0.2214.115 (no hardware acceleration) | 139.894 sec. / 1769.311 sec. |
|---|---|
| Google Chrome 40.0.2214.115 (with hardware acceleration) | 112.115 sec. / 1738.033 sec. |
| Yandex Browser 12/14/2125.10034 | 137.854 sec. / 1901.142 sec. |
| Internet Explorer 11 | 240.888 sec. / 227.489 sec. |
| Mozilla Firefox 35.0.1 | 173.205 sec. / 2056.301 sec. |
| Opera 27.0.1689.69 | 130.07 sec. / 1904.973 sec. |
* - The results of the work depend on the total load of the machine, therefore, the tables show the average values. The measurement error was about 5%.
** - The result of the work is given when sending values for visualization every 50 thousand searches, for other values the result fit into the error.
You can verify it yourself by running the script on the local web server.
As a matter of fact, parallelization of the calculation process itself did not occur, therefore, the time it took to calculate with the web worker was longer than without it, but its use may be useful for carrying out the calculation in the background (when the calculation tab is inactive). In addition, Firefox turned out to be the slowest for calculating with a web worker, and is comparable in time when performing calculations without it. Separately, it is worth noting that thanks to the web worker, visualization can be redrawn more often, which looks much more beautiful than without it.