1 2 3
Posted: 12/5/2012 10:36 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
partyboy1a wrote:
another edit:
MEM_COLS = 0x020E3F64 
MEM_ROWS = 0x020E3FA8
...
[...] what does it give for grey squares though since the addresses I found seemed to "remember" the last black or white even if the tile was grey.
If you're in Puzzle Mode this doesn't matter, the number of rows and columns is saved too, so you always know which tiles are grey. For Challenge Mode, you may need test if the row counter gets updated again and again. Otherwise, find some one-byte value which always holds the current number of rows... And it might be a good idea to find the location of the next set of tiles which are dropping.
ais523 wrote:
Best attempt before brute-forcing:
A?A?A?A?A?A?A?*?*?*
? ? ? ? ? ? ? |   ?
A?A?A?A?A?A?A-+ . *
? |               ?
K-+ . . . . . . . L
?                 ?
M . . . . . . . +-N
?                 ?
O-+ . . . . . . . P
?                 ?
* . . . . . . . +-*
?               | ?
* . +-B?B?B?B?B?B?B
?   | ? ? ? ? ?   ?
*-+-+ B?B?B?B?B . *
?     ? ? ? ? ?   ?
* . +-B?B?B?B?B?B?B
?   | ? ? ? ? ? ?
*?*?*?B?B?B?B?B?B B
This should be detected as unsolvable.
Yeah, I noticed this rule too, and is probably the most useful rule for solving that I haven't implemented yet. I need to work out how to express it in Lua.
I marked the points where two rows are disconnected using the letters K,L,M,N,O,P. You need to find a route which uses regions A,B,N,O. You write down which regions can be connected in which way: A-K-M-O-B-P-N-L-A. Now you test all routes starting with the left endpoint: O-M-K-A-L-N-right endpoint (forced) -> failure, B wasn't visited O-B-P-N-right endpoint (forced) -> failure, A wasn't visited -------------------------- I uploaded an improved version of my solver, it can be found here. If a level requires a lot of brute-force, my solver works faster. examples: stage 05 is solved within 4 minutes, the program by ais523 requires more time. I should also say that it is entirely possible to use both programs at the same time: the program by ais can be used to eliminate useless line-flip combinations for example. And also, if there is a partial solution (or some guess about it), it can be used to construct a new puzzle: turn all tiles where we stepped on to black, set a forced endpoint for the last tile which was visited. Then either my program or the program by ais can try to solve the remaining puzzle.
Posted: 12/18/2012 5:00 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
Yay, I got most of the features of my solver reimplemented in C++. It made the solver about 2000 times faster, and made it use only 1/8th of the previously used RAM. Now it can solve puzzle 100 in about 4 minutes, and puzzle 9 is solved in one to two seconds. If you let me do so, I will take an attempt to "merge" our solvers in C++, basically replacing your depth-first search with my breadth-first search. The most important reasons for me to use this instead of Lua are the control about memory usage and the increased speed... If it becomes good enough, the interface can still be implemented to work with the emulator. -------------------------------------------------------------------------- Coming soon: some piece of software which converts the problem "find the shortest / fastest solution" into a boolean satisfiability problem. I hope those SAT solvers do already have a lot more optimizations than we can possibly find.
Posted: 1/2/2013 8:48 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
Some news: The solver which uses SAT solvers is working fine. For the benchmark puzzle, it required 80 seconds to find some solution, and 11 seconds to find the solution when the row pattern is predefined in a nice way. Output looks like that: 
solvingpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 

solvingpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 


validpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 

validpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 

WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
WARNING! DIMACS header mismatch: wrong number of variables.
WARNING! DIMACS header mismatch: wrong number of clauses.
|  Number of variables:         32676                                         |
|  Number of clauses:           49724                                         |
|  Parse time:                   0.05 s                                       |
|  Eliminated clauses:           0.18 Mb                                      |
|  Simplification time:          0.13 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   13564    49064   119444 |    17990      100    422 | 39.889 % |
|       250 |   13564    49064   119444 |    19789      250    336 | 39.889 % |
|       475 |   13564    49064   119444 |    21768      475    273 | 39.889 % |
|       812 |   13564    49064   119444 |    23944      812    269 | 39.889 % |
|      1318 |   13564    49064   119444 |    26339     1318    271 | 39.889 % |
|      2077 |   13564    49064   119444 |    28973     2077    234 | 39.889 % |
|      3216 |   13564    49064   119444 |    31870     3216    219 | 39.889 % |
|      4924 |   13564    49064   119444 |    35057     4924    201 | 39.889 % |
|      7486 |   13564    49064   119444 |    38563     7486    205 | 39.889 % |
|     11330 |   13564    49064   119444 |    42419    11330    209 | 39.889 % |
|     17096 |   13564    49064   119444 |    46661    17096    212 | 39.889 % |
|     25745 |   13564    49064   119444 |    51327    25745    216 | 39.889 % |
|     38719 |   13564    49064   119444 |    56460    38719    239 | 39.889 % |
|     58180 |   13564    49064   119444 |    62106    58180    239 | 39.889 % |
|     87372 |   13564    49064   119444 |    68317    35441    210 | 39.889 % |
|    131161 |   13564    49064   119444 |    75149    79230    269 | 39.889 % |
|    196845 |   13564    49064   119444 |    82664    86304    267 | 39.889 % |
|    295371 |   13564    49064   119444 |    90930    46382    234 | 39.889 % |
===============================================================================
restarts              : 766
conflicts             : 332362         (887 /sec)
decisions             : 1455603        (0.00 % random) (3885 /sec)
propagations          : 187711758      (501020 /sec)
conflict literals     : 107846413      (16.53 % deleted)
Memory used           : 182.00 MB
CPU time              : 374.659 s

SATISFIABLE
SAT
  **  **  **  19  18  **   6   5   4  **

  **  --  65  20  17  16   7   8   3   2

  62  63  64  21  14  15  10   9  --   1

  61  --  23  22  13  12  11  30  31  32

  60  59  24  25  26  27  28  29  --  33

  57  58  --  --  --  --  --  --  --  34

  56  --  --  --  --  --  --  --  36  35

  55  --  51  50  49  42  41  38  37  **

  54  53  52  47  48  43  40  39  --  **

  **  **  **  46  45  44  **  **  **  **


Process returned 0 (0x0)   execution time : 376.794 s
I also tried it when the row pattern has been defined to be the worst possible one (every row has exactly 7 white tiles, and 1 black tile). It could be solved in about 80 minutes. At the moment, it just finds some solution, not the best one. Getting the shortest solution is not a problem though: just give some limit for the amount of allowed steps. If there is no way to complete it, but with one step more it can be completed, then you found the shortest solution. Finding the fastest solution is more complicated, because it is not easy to translate the calculation for the amount of frames into some boolean variables, but it's definitely possible.
Posted: 1/3/2013 4:01 PM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Nice work partyboy1a, sorry for my lack of input on this thread recently. About a month ago I was working on making a lua script to test luck manipulation (since it seems the only way to luck manipulate drops is by waiting x though I still didn't test this enough to see how far into the future you can affect thing) but ran into a few problems and lost interest for a while, mainly due to the fact emu.frameadvance doesn't work in desumume lua requiring you to use registered functions which makes it much more difficult to put in a specified sequence of input, as well as not being able to set stylus input since it's not documented very well at all. Did you do any more work on combining yours and ais' solvers since they can be much faster than the other depending on the puzzle it seems? If someone who has experience using desmume lua could give me some examples of setting stylus input and maybe a good method to send multiple frames of input in a row with registered functions (though now I've actually thought about it a bit more I've had a few more ideas).
Polarium
Posted: 1/3/2013 7:35 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
I managed to write the code which checks for "connectivity". It eliminates a few row patterns which split the puzzle into multiple parts if there are multiple separate regions, AND all of them can only be connected using the border, AND you can only go strictly clockwise or strictly counter-clockwise AND there are endpoints in regions which are not directly connected, THEN the row pattern is invalid... another 320 lines of code, as it is very specific... It's good enough to eliminate 26 row selections out of 168 (potentially) solvable ones. I couldn't combine the two solvers even more. And now, as I try to use such a generic program like a SAT solver, I might port it back to Lua again. Too bad that its performance doesn't seem to be better than our programs, at least for the smaller puzzles.. It needed half a second to 15 seconds (depending on an artificial step limitation) to find the fastest solution for stage 9, and another 4 minutes to prove that there is no faster solution. (And at the moment there are still some strange bugs in the code.) I still think it's worth the effort. The other solvers can have serious troubles when it comes to large areas of white tiles (or large areas of black tiles). In that case, the SAT solver approach might be the only way to find any solutions (or even the best one).
Posted: 1/3/2013 7:57 PM
Quote
ais523
Editor, Player (44)
Joined: 7/11/2010
Posts: 1022
Yeah, SAT solvers can typically be beaten if you have more information about the problem space than they do. I've been wondering about keeping a cache of the fastest solutions for variousy-shaped solid color areas (this is one of the things I was planning to do when I split the puzzle into regions in my solver), but that isn't implemented yet.
Posted: 1/4/2013 1:28 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
ais523 wrote:
Yeah, SAT solvers can typically be beaten if you have more information about the problem space than they do.
While they may have less information available, they are typically highly optimized, and can utilize all the available hardware trickery of today, so they should be able to find solutions faster than our strictly linear algorithms.
ais523 wrote:
I've been wondering about keeping a cache of the fastest solutions for variousy-shaped solid color areas (this is one of the things I was planning to do when I split the puzzle into regions in my solver), but that isn't implemented yet.
I don't think that is possible in most cases. It can only work if the number of exits is relatively small, and even then you would have to store one partial solution for every permutation of the exits. And you would need an insanely big amount of prepared areas, as you would need to consider every single "exit pattern".
Posted: 1/7/2013 10:08 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
I invented some new way to describe the puzzle to the SAT solver (after having a closer look into the solver from ais)... and now the performance definitely outbeats all the others! The "benchmark" puzzle is solved in just one minute for both the shortest and the fastest solution... So here comes the best solutions for these: (Sorry for all those long posts, but I think these news are worth it... There are still some bugs left, I'll fix them before this gets released.) The parameters given: Download main.cpp
Language: cpp
int main()
{
    PolariumPuzzle *p = new PolariumPuzzle();
    Solution s;

    unsigned char puz[] = {
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1
    };
    p->SetPuzzle(puz, 8, 8);
    //p->Solve();

    // prove that all solutions require at least 63 frames
    p->ConvertToCNF(s, 62, -1, -1);
    // prove that all solutions are at least 44 tiles long.
    p->ConvertToCNF(s, -1, 43, -1);
    // find a solution which is exactly 44 tiles long.
    p->ConvertToCNF(s, -1, 44, -1);
    // find a solution which requires 63 frames
    p->ConvertToCNF(s, 63, -1, -1);
    delete p;
}
Download output.txt
Language: txt
solvingpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 

solvingpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 


validpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 

validpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 


WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         35815                                         |
|  Number of clauses:          137659                                         |
|  Parse time:                   0.14 s                                       |
|  Eliminated clauses:           0.40 Mb                                      |
|  Simplification time:          0.45 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   23005   125256   477030 |    45927       99     10 |  2.706 % |
|       250 |   23005   125256   477030 |    50519      249     10 |  2.706 % |
|       475 |   23005   125256   477030 |    55571      474     10 |  2.706 % |
|       812 |   23004   125128   476476 |    61129      810     10 |  2.708 % |
|      1318 |   23003   123653   469868 |    67242     1315     10 |  2.711 % |
|      2077 |   23002   122891   466414 |    73966     2073     12 |  2.714 % |
|      3216 |   23001   122161   463177 |    81362     3211     14 |  2.717 % |
|      4924 |   23000   121392   459678 |    89499     4918     15 |  2.720 % |
|      7486 |   22998   119946   453165 |    98449     7478     16 |  2.725 % |
|     11330 |   22998   119946   453165 |   108293    11322     16 |  2.725 % |
|     17096 |   22998   119946   453165 |   119123    17088     16 |  2.725 % |
===============================================================================
restarts              : 82
conflicts             : 22894          (1192 /sec)
decisions             : 31340          (0.00 % random) (1632 /sec)
propagations          : 46316550       (2411667 /sec)
conflict literals     : 354771         (43.34 % deleted)
Memory used           : 25.00 MB
CPU time              : 19.2052 s

UNSATISFIABLE
no solution found!
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         50568                                         |
|  Number of clauses:          130856                                         |
|  Parse time:                   0.13 s                                       |
|  Eliminated clauses:           0.71 Mb                                      |
|  Simplification time:          0.52 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   29069   113210   375677 |    41510       98     11 |  1.805 % |
|       250 |   29048   113210   375677 |    45661      246     10 |  1.847 % |
|       475 |   29048   112702   373494 |    50227      471     13 |  1.847 % |
|       812 |   29048   112702   373494 |    55250      808     13 |  1.847 % |
|      1318 |   29048   112702   373494 |    60775     1314     15 |  1.847 % |
|      2077 |   28988   105341   340930 |    66852      941     11 |  1.966 % |
===============================================================================
restarts              : 15
conflicts             : 2575           (1617 /sec)
decisions             : 4631           (0.00 % random) (2909 /sec)
propagations          : 3351230        (2104913 /sec)
conflict literals     : 35041          (49.05 % deleted)
Memory used           : 29.00 MB
CPU time              : 1.5921 s

UNSATISFIABLE
no solution found!
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         51271                                         |
|  Number of clauses:          133003                                         |
|  Parse time:                   0.13 s                                       |
|  Eliminated clauses:           0.72 Mb                                      |
|  Simplification time:          0.53 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   29110   114006   379144 |    41802       98      9 |  1.818 % |
|       250 |   29110   113932   378991 |    45982      248     10 |  1.818 % |
|       475 |   29110   113932   378991 |    50580      473     13 |  1.818 % |
|       812 |   29110   113932   378991 |    55638      810     14 |  1.818 % |
|      1318 |   29090   113874   378875 |    61202     1315     14 |  1.857 % |
===============================================================================
restarts              : 10
conflicts             : 1545           (1215 /sec)
decisions             : 5911           (0.00 % random) (4647 /sec)
propagations          : 2194265        (1724944 /sec)
conflict literals     : 21216          (47.44 % deleted)
Memory used           : 29.00 MB
CPU time              : 1.27208 s

SATISFIABLE
row 1 was NOT flipped
row 2 was flipped
row 3 was NOT flipped
row 4 was flipped
row 5 was flipped
row 6 was NOT flipped
row 7 was NOT flipped
row 8 was flipped

VISITED FIELDS: 

0000000000
1100000000
1111111100
1100000000
1111111100
1011111110
1000000011
1100000001
0111111101
0000000111

START: (5,4)
END: (10,7)

SOLUTION: 

. . . . . . . . . . 
                    
x-x . . . . . . . . 
| |                 
x x-x-x-x-x-x-x . . 
|                   
x-x . . . . . . . . 
  |                 
x-x x-x-x-x x-x . . 
|   |     | | |     
x . x-x-x x-x x-x . 
|               |   
x . . . . . . . x-x 
|                 | 
x-x . . . . . . . x 
  |               | 
. x-x-x-x-x-x-x . x 
              |   | 
. . . . . . . x-x-x 
                    
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         36148                                         |
|  Number of clauses:          138325                                         |
|  Parse time:                   0.14 s                                       |
|  Eliminated clauses:           0.39 Mb                                      |
|  Simplification time:          0.44 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   23495   127201   483784 |    46640       98      8 |  3.093 % |
|       250 |   23494   127201   483784 |    51304      247      8 |  3.096 % |
|       475 |   23494   127201   483784 |    56434      472      8 |  3.096 % |
|       812 |   23492   125965   479068 |    62078      805      9 |  3.101 % |
|      1318 |   23491   123842   469597 |    68286     1310     12 |  3.104 % |
|      2077 |   23319   123319   467901 |    75114     2062     14 |  3.580 % |
|      3216 |   23319   123319   467901 |    82626     3201     16 |  3.580 % |
|      4924 |   23318   122580   464582 |    90888     4908     17 |  3.582 % |
|      7486 |   23317   121841   461269 |    99977     7469     18 |  3.585 % |
|     11330 |   23317   121841   461269 |   109975    11313     17 |  3.585 % |
|     17096 |   23317   121841   461269 |   120973    17079     17 |  3.585 % |
|     25745 |   23317   121841   461269 |   133070    25728     17 |  3.585 % |
===============================================================================
restarts              : 116
conflicts             : 31424          (1238 /sec)
decisions             : 45215          (0.00 % random) (1782 /sec)
propagations          : 54177150       (2135179 /sec)
conflict literals     : 523569         (43.51 % deleted)
Memory used           : 25.00 MB
CPU time              : 25.3736 s

SATISFIABLE
row 1 was NOT flipped
row 2 was flipped
row 3 was flipped
row 4 was NOT flipped
row 5 was flipped
row 6 was flipped
row 7 was NOT flipped
row 8 was flipped

VISITED FIELDS: 

0000000000
1100000000
1111111100
1011111111
1000000011
1011111111
1111111101
0100000001
0111111101
0000000111

START: (3,2)
END: (14,7)

SOLUTION: 

. . . . . . . . . . 
                    
x-x . . . . . . . . 
| |                 
x x-x-x-x-x-x-x . . 
|             |     
x . x-x-x-x-x-x x-x 
|               | | 
x . . . . . . . x x 
|               | | 
x . x-x-x-x-x-x-x x 
|   |             | 
x-x x-x-x-x-x-x . x 
  |               | 
. x . . . . . . . x 
  |               | 
. x-x-x-x-x-x-x . x 
              |   | 
. . . . . . . x-x-x
-------------------------------------------------------------------------------------- Yay, now everything is done, even some fine-tuning. Now it can even solve a benchmark puzzle which is a lot harder: Download puzzle_benchmark3.txt
Language: txt
12 12
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
It takes one hour to find the shortest, and the fastest solution, and it takes about 20 minutes to verify that a given solution is optimal. Note that no attempt was done for finding the fastest solution for a given amount of steps, but that's possible too. The solutions take 97 tiles, or 109 frames. So the solutions: Download fastest_puzzle_benchmark3.txt
Language: txt
SOLUTION: 

X#X#X . . . . . . . . . . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
X#X X#X#X#X#X#X#X#X#X#E . X 
#   #                     # 
X . X#X#X#X#X#X#X#X#X#X#X X 
#                       # # 
X . . . . . . . . . . . X#X 
#                           
X#X . . . . . . . . . . . . 
  #                         
X#X X#X#X#X#X#X#X#X#X#S . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X#X#X#X#X#X#X#X#X#X . X 
                      #   # 
. . . . . . . . . . . X#X#X
Download shortest_puzzle_benchmark3.txt
Language: txt
SOLUTION: 

X#X#X . . . . . . . . . . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X X#X X#X X#X E#X#X . X 
    # # # # # # #     #   # 
. . X#X X#X X#X X#X#X#X X#X 
                        #   
. . . . . . . . . . . . X#X 
                          # 
X#X . . . . . . . . . . . X 
# #                       # 
X X#X X#X X#X X#X X#X S . X 
#   # # # # # # # # # #   # 
X . X#X X#X X#X X#X X#X X#X 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X#X#X#X#X#X#X#X#X#X . X 
                      #   # 
. . . . . . . . . . . X#X#X
Posted: 1/15/2013 4:28 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
Get the solver NOW!
Posted: 1/16/2013 12:45 AM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Using codeblocks on windows I get this error when compiling, after opening the p-solver.cbp file: http://duks.co.uk/i/nxEA . All the other files are in the same directory so I don't think that it's not finding them. I've yet to try it in linux though. From what you've posted it's looking good and I'm guessing will solve the 9x9 and 9x10 puzzles needed for the challenge mode tas fairly quickly.
Polarium
Posted: 1/16/2013 1:15 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
That's looking like a linker error. Most of the time, this is happening because the compiler is incomplete, or because of a misconfiguration in the IDE. I use g++ for compiling right now. If you use another one, you might need to download that one separately, or specify the right path to the compiler, and linker inside CodeBlocks. (Well, and you need to look into the readme file, this program is very hard to setup on Windows, I'm sorry for that... There is a lot of additional work involved just for getting the solver working, you need to install Cygwin AND MinGW. Cygwin for minisat, MinGW for the compiler. Well, I chose MinGW to compile on Windows, which seems to work.) I promise this work will pay off... For "somewhat" easy puzzles, the solver from ais is faster, but for complex puzzles, mine is faster. And I'm pretty sure that the puzzle file "puzzle_benchmark" is much too hard for all the other solvers.
Posted: 1/16/2013 1:50 AM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
I got it to compile by changing the imports to: #include "P_Puzzle.cpp" #include "P_Solution.cpp" rather than #include "P_Puzzle.h" #include "P_Solution.h" Though I've never written a program bigger than 1 file in c++ before so don't know why this worked or if the program is running properly. It is outputting the shortest_puzzle_sample and fastest_puzzle_sample though. (and a file solution.txt containing just "UNSAT", though I'm guessing that's something to do with minisat.
Polarium
Posted: 1/16/2013 2:28 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
It is outputting the shortest_puzzle_sample and fastest_puzzle_sample though. (and a file solution.txt containing just "UNSAT", though I'm guessing that's something to do with minisat.
That's nice to know, it seems to work fairly well. shortest_puzzle_sample and fastest_puzzle_sample are just ordinary text files, so you can view them with any editor you like (I recommend Notepad++). And if you don't like the Linux way of text files, just append .txt to the puzzle files, this will work well solution.txt is just an intermediate file produced BY minisat, p_puzzle.cnf is just an intermediate file produced FOR minisat, containing all the rules of the game, but in a very unreadable way (for humans, computers like this one a lot better...)
Posted: 1/16/2013 2:41 AM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
partyboy1a wrote:
duksandfish wrote:
It is outputting the shortest_puzzle_sample and fastest_puzzle_sample though. (and a file solution.txt containing just "UNSAT", though I'm guessing that's something to do with minisat.
That's nice to know, it seems to work fairly well. shortest_puzzle_sample and fastest_puzzle_sample are just ordinary text files, so you can view them with any editor you like (I recommend Notepad++). And if you don't like the Linux way of text files, just append .txt to the puzzle files, this will work well solution.txt is just an intermediate file produced BY minisat, p_puzzle.cnf is just an intermediate file produced FOR minisat, containing all the rules of the game, but in a very unreadable way (for humans, computers like this one a lot better...)
Thanks for clarifying, I had looked at them in notepad++ but was just making sure. Any idea why I had to change the extensions on the #include(s) though? Since I'm also using mingw. Also it technically doesn't need cygwin to run, just 3 of the dlls: http://duks.co.uk/i/MFUT
Polarium
Posted: 1/16/2013 3:01 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
That's most likely some kind of misconfiguration in CodeBlocks. I could also produce these errors when I tried to compile the program by hand. There are multiple source files. It is not possible to compile AND link main.cpp right away, you first have to compile (but NOT link) P_Puzzle.cpp and P_Solution.cpp. If the IDE is configured right, all files get compiled first, and after ALL files have been compiled, they are linked. You have some kind of misconfiguration, your compiler tries both steps at once. This only works if you have exactly one source file. And by changing the includes, you basically copy-paste all six files into one big file. It does work, but this kind of workaround is not the best thing to do. Maybe it's enough to add "-c" to the compiler options somewhere. Just another idea a "complete rebuild" might help. I had to do this whenever I copied the project from my Linux PC to a Windows PC and vice versa. You can also try out puzzle_benchmark, it'll run for about an hour... but it will finish.
Posted: 1/17/2013 9:00 PM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
p-solver-v1.0.1, fixed a crash which could happen if the very first attempt was faster than all step-limited attempts afterwards.
Posted: 1/18/2013 6:58 PM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Thanks for the new version, as well as the puzzle mode solutions you gave me in the pm. I think my problem before was the cbp file from the 1.0 since loading this new one with the same config compiles correctly with no changes. In terms of the actual TAS, I could now make an optimal run of puzzle mode fairly easily, since actually inputting solutions isn't that hard (and could even be mostly scripted when I work out stylus inputs on desmume lua) but as discussed before (see page 1) a puzzle mode wouldn't be too interesting to watch though you do have some time to do "creative drawing" after each puzzle. As stated on the bad game choices page: "Many puzzle games where knowing the solution renders gameplay trivial, such as Sudoku. If you know the solution, a speed run just a matter of entering it as fast as possible." Though due to the amount of effort that has gone into the solver it might still be worth doing. Obviously this leaves challenge mode where there is a large amount of luck manipulation that can be done, which I am still working on and will post here if I make some more progress.
Polarium
Posted: 1/18/2013 8:49 PM
Quote
Warepire
He/Him
Editor
Joined: 3/2/2010
Posts: 2174
Location: A little to the left of nowhere (Sweden)
I don't see any reason to why a puzzle-mode TAS should not be publishable in the Vault tier.
Posted: 1/19/2013 11:17 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
Thanks for the new version, as well as the puzzle mode solutions you gave me in the pm. [...] In terms of the actual TAS, I could now make an optimal run of puzzle mode fairly easily, since actually inputting solutions isn't that hard.
Yeah, I gave it a try, and noticed it is faster to press "START" between the puzzles than to click away the "completed" message. I'm not that terribly creative when it comes to the play-around part, my best idea was to write a text like "tool-assisted superplay". You can do that run if you want (and maybe include me as a co-author for finding the solutions).
Warepire wrote:
I don't see any reason to why a puzzle-mode TAS should not be publishable in the Vault tier.
I think so too... and also, it would possibly be the first run on this page which has been PROVEN to be absolutely frame-perfect.
Posted: 1/21/2013 5:17 AM
Quote
ais523
Editor, Player (44)
Joined: 7/11/2010
Posts: 1022
You can never prove that, unless the movie's so short you can brute-force. There might always be a faster way to do menuing you missed, or some glitch you didn't expect.
Posted: 1/22/2013 7:35 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
Well, brute-forcing isn't gonna become possible at any time in the future. The amount of possible inputs is much too big for that, especially for the DS. All solutions have been proven to be optimal, there doesn't exist any solution which is faster. There are of course some assumptions necessary for this... One of these assumptions is p-solver is working correctly. Another one There are no glitches in this game which may provide a speed-up. Another one The menu navigation is done optimal. Another one sub-frame input won't make it possible to enter the solutions faster. (If this assumption is wrong, then p-solver does most likely not work correctly.) These assumptions will most likely never be provable... However accept the assumptions, and you cannot beat the movie. Prove one of the assumptions as wrong, and you're ready to create a shorter movie. In any case, it is still possible to create an equally-fast probably more entertaining movie, as there is a lot of spare time for creative drawings, and entertainment can definitely not be proven to be optimal...
Posted: 2/18/2013 10:03 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
I did see the "WIP" for the menus. Unfortunately, I cannot really do this TAS at the moment. I do not have a Windows PC at the moment. The Linux version of DeSMuME sucks, wine doesn't work good enough for the Windows version.
Posted: 2/18/2013 1:00 PM
Quote
duksandfish
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
I did some testing on this about 2 weeks ago after I uploaded that wip (progress here: http://www.youtube.com/watch?v=Ey20QsbBDqc can upload dsm when I get home if you want dsm here: http://tasvideos.org/userfiles/download/4687549396464802 (glitch visible from frame 1776)), but when I got to level 7 I found a glitch in the menus (and possibly the main game) where if either the places are close enough, or if you press on specific places, two clicks can be done in 6 frames rather than 7 (obviously you can't see this in the video but only in the dsm). Haven't done anymore testing outside of that though but if it affects the game then there's a chance it will cause the solver to be wrong in some places, so let's hope it doesn't.
Polarium
Posted: 2/20/2013 7:38 AM
Quote
partyboy1a
Player (136)
Joined: 9/18/2007
Posts: 389
The solver uses a quite simplistic way to measure the "score". It looks for turns in the path, and looks for long connections. If we find out that A-B-C can always be done in 6 frames, and A-B-C-D always requires 7 frames, it's easy to change the solver for that. It only matters to find the exact set of rules when we can use 6 frames for non-adjacent tiles. If the rules are really complicated, the solver might become slower, but that shouldn't be a problem.
Posted: 5/17/2013 9:24 PM
Post subject: Re: Polarium
Quote
YushiroGowa
Joined: 5/13/2013
Posts: 180
duksandfish wrote:
As there were a few requests for this game in the wish list topic, and it looked quite interesting, I decided to have a try at TASing the challenge mode of Polarium. Here is what I have so far: Link to video I've noticed a few places where it isn't optimal, so i'll redo it over the next few days. Edit: Updated the link since I deleted the old video over 2 years ago
Man, I remember when the DS first came out and I remember my dad taking me to GameStop and seeing this as a demo on the DS systems they had on display. Memories....:D
A wise man once said "Damn, that's one hell of a steak."
1 2 3