help with brute force solving idea:

Post the puzzle or solving technique that's causing you trouble and someone will help

help with brute force solving idea:

Postby StrmCkr » Sat Dec 24, 2016 4:11 am

lexicon minimal puzzle arrangement for the first 10 digits~
1234567894.......................................................................


is it possible to use the 3,359,232. isomorphic identities of a puzzle to manipulate an unknown grid into the lexicon state
then apply the first 10 digits as solved over-top the "rearranged givens" + some basic solving techniques before/after rearrangement to brute force a solution ?

thoughts?
idea's ?

can this concept work?

for example:
Code: Select all
*-----------*
 |5..|4..|...|
 |4..|713|...|
 |.97|...|...|
 |---+---+---|
 |.86|92.|.4.|
 |...|...|...|
 |.7.|.35|68.|
 |---+---+---|
 |...|...|46.|
 |...|394|..2|
 |...|..2|..8|
 *-----------*

changed to:
Code: Select all
.------------------.-----------------------.-----------------------.
| 1     2     3    | 4567    569    567    | 47      8       79    |
| 49    8     469  | 123467  12369  12367  | 1347    5       1379  |
| 459   4579  49   | 13457   13589  1357   | 2       13479   6     |
:------------------+-----------------------+-----------------------:
| 7     6     12   | 1235    1235   8      | 9       13      4     |
| 2489  149   1249 | 123567  12356  123567 | 135678  1367    13578 |
| 3     1     5    | 9       16     4      | 1678    167     2     |
:------------------+-----------------------+-----------------------:
| 245   145   124  | 8       12356  9      | 134567  123467  1357  |
| 6     3     8    | 125     7      125    | 145     1249    159   |
| 259   159   7    | 12356   4      12356  | 13568   12369   13589 |
'------------------'-----------------------'-----------------------'


apply the first 10 as solved ~
which gives this potential isomorphic grid
Code: Select all
.----------------.---------------------.----------------------.
| 1    2    3    | 4       5     6     | 7      8       9     |
| 4    8    69   | 1237    1239  1237  | 13     5       13    |
| 59   579  9    | 137     1389  137   | 2      134     6     |
:----------------+---------------------+----------------------:
| 7    6    12   | 1235    123   8     | 9      13      4     |
| 289  149  1249 | 123567  1236  12357 | 13568  1367    13578 |
| 3    1    5    | 9       16    4     | 168    167     2     |
:----------------+---------------------+----------------------:
| 25   145  124  | 8       1236  9     | 13456  123467  1357  |
| 6    3    8    | 125     7     125   | 145    1249    15    |
| 259  159  7    | 12356   4     1235  | 13568  12369   1358  |
'----------------'---------------------'----------------------'

and the puzzle cracks as all singles
Code: Select all
.---------.---------.---------.
| 1  2  3 | 4  5  6 | 7  8  9 |
| 4  8  6 | 7  9  2 | 1  5  3 |
| 5  7  9 | 1  8  3 | 2  4  6 |
:---------+---------+---------:
| 7  6  2 | 5  1  8 | 9  3  4 |
| 8  9  4 | 3  2  7 | 6  1  5 |
| 3  1  5 | 9  6  4 | 8  7  2 |
:---------+---------+---------:
| 2  4  1 | 8  3  9 | 5  6  7 |
| 6  3  8 | 2  7  5 | 4  9  1 |
| 9  5  7 | 6  4  1 | 3  2  8 |
'---------'---------'---------'
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 657
Joined: 05 September 2006

Re: help with brute force solving idea:

Postby JasonLion » Sat Dec 24, 2016 1:28 pm

That depends on how you are getting the puzzle into cononical form. Typically finding the canonical form requires using the solution grid. If you use an approach based on the solution grid, significant amounts of information are retained from the solution grid in the cononical form. That appears to be what happened in your example. There are other, less commonly used, definitions of cononical form that do not depend on the solution grid. However, I very much doubt that they will aid in finding the solution.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: help with brute force solving idea:

Postby eleven » Sat Dec 24, 2016 2:21 pm

StrmCkr, you must be joking.

The essence of the equivalence of puzzles is, that they have the same properties. So the only advantage of transforming a puzzle can be, that it looks better then (which e.g. makes it easier, if the puzzle is digit symmetric).

The common minlex form of a puzzle can only be calculated from the solution, and it is a tricky process, if you dont want to look at all the 9!*6^8*2 possibilities (see Minlex Form: Min and Max Lists / Chaining).
You cannot do that manually for an unsolved puzzle.
And there is not only one equivalent solution starting with 1234567894.

E.g. you could assume, your puzzle has minimal form, if you renumber it 5->1->8->5. Then candidates are possible for a 1234567894 start. But this is just a guess, you have to verify. It does not work - and now?
eleven
 
Posts: 1580
Joined: 10 February 2008

Re: help with brute force solving idea:

Postby StrmCkr » Sat Dec 24, 2016 5:37 pm

I'm not joking, i did miss when going from memory the minimal form starting cells digits
12345678945..

I created the 2nd grid, using a spreadsheet that doesn't know the solution
With manual targeting given the first ten digits as restraints for placement cycled rows bands stacks transposed and digit swaps
Until had a grid who's PMs and clues matched said restraints closely

Yes it could be luck
But it's an idea I've pondered for a while..


5,472,730,538 of them being essentially different


a grid with only 1 solution should have exactly 1 matching solution from the list above

{unless I'm out to lunch on how that essentially different list works, as each grid has 3,359,232 isomorphic layouts of the clues }

which is can be keyed to the canonical {thanks Jason for the name i forgotten} form seen from calculation of the above list {thanks for the link to an article i lost eleven}

if a grid has more then 1 solution it in theory would be matched to n different solutions from the list above.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 657
Joined: 05 September 2006

Re: help with brute force solving idea:

Postby StrmCkr » Sun Dec 25, 2016 6:36 am

the following was done once again without knowing the solution.

Code: Select all
.---------------.------------.-----------------.
| 5    478  1   | 2   6   3  | 789    78    49 |
| 34   6    247 | 1   8   9  | 237    5     34 |
| 9    238  28  | 7   5   4  | 2368   2368  1  |
:---------------+------------+-----------------:
| 2    9    3   | 6   4   8  | 5      1     7  |
| 48   478  478 | 59  19  15 | 236    236   36 |
| 1    5    6   | 3   2   7  | 4      9     8  |
:---------------+------------+-----------------:
| 7    38   5   | 4   19  6  | 1389   38    2  |
| 36   1    9   | 8   7   2  | 36     4     5  |
| 468  248  248 | 59  3   15 | 16789  678   69 |
'---------------'------------'-----------------'


original grid with pencil marks unsolved

isomorphic identical puzzle re arranged so that the first 11 digits restricts the cells to either having specific candidates or specific pencil marks.
so that the 11 digit order is conserved. {12345678945 in the first 11 cells }

Code: Select all
.---------------.-------------.-----------------.
| 1    278  3   | 4   5   6   | 79  28    289   |
| 247  5    67  | 1   8   9   | 67  3     246   |
| 48   468  9   | 2   3   7   | 1   4568  4568  |
:---------------+-------------+-----------------:
| 6    9    4   | 5   7   8   | 2   1     3     |
| 278  278  78  | 39  19  13  | 56  456   456   |
| 5    3    1   | 6   4   2   | 8   9     7     |
:---------------+-------------+-----------------:
| 3    68   2   | 7   19  15  | 4   568   15689 |
| 9    1    56  | 8   2   4   | 3   7     56    |
| 478  478  578 | 39  6   135 | 59  258   12589 |
'---------------'-------------'-----------------'


both these puzzles solve with almost identical move sets

and the solution to the 2nd puzzle is actually 12345678945.... etc

anyone have proof this isn't a coincidence, or solid evidence to show this wont work in at least 1 case.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 657
Joined: 05 September 2006

Re: help with brute force solving idea:

Postby eleven » Sun Dec 25, 2016 8:06 pm

There is no reason at all to go for the minlex form. As there are solution equivalences starting with 12345678945, there are such starting with say 54126378936 (possible in your original puzzle).

[Edit: These counts are wrong:]
E.g. this solution grid has 1152 equivalences starting with 12345678945, and 1729 starting with 54126378936.
(Btw your transformed puzzle does not solve to the canonical minlex form.)

If i made no mistake, in your puzzle you can find 51 different row (or column) pairs containing these candidates in the first 11 cells, for 15 of which 12345678945 is part of a solution, the others lead nowhere.
So what you are doing is just transforming the puzzle and guessing the missing numbers in the first 11 cells, here with a chance less than 1:3.
Moreover, if you look at rows 4 an 6, which are solved, you will find at least 2 ways to come to 12345678945, and it will help you nothing. 13 others only would bring you 2 numbers, probably not enough to solve the puzzle.

Of course these counts are different for other puzzles, there will be "better" and "worse" ones.

A similar, more direct approach is the known method, that you choose a row or column, and try the possible ways of filling it out one by one. E.g. in row 1 there are 4 ways, one of which is correct.
Last edited by eleven on Mon Dec 26, 2016 12:22 pm, edited 1 time in total.
eleven
 
Posts: 1580
Joined: 10 February 2008

Re: help with brute force solving idea:

Postby StrmCkr » Sun Dec 25, 2016 10:28 pm

(Btw your transformed puzzle does not solve to the canonical minlex form.)


i haven't been able to find any exacting definition for the canonical minlex forum
most other articles pointing towards it are gone {thanks to the disappearance of the programmers forum}
edit: now i found this

I'm using the givens as a keyed forum, rearranging the given grid using the pm's and solved cells in a way so that the first 11 digits could only be placed 1 way matching canonical forum
- so yes it could be i'm "guessing" that the first 11 digits must = 12345678945

even though the entire generated list of uniquely different solutions starts with 12345678945

1152 equivalences starting with 12345678945, and 1729 starting with 54126378936.

can the 1729 can be morphed to read the first ?

Code: Select all
if you look at rows 4 an 6, which are solved, you will find at least 2 ways to come to 12345678945, and it will help you nothing. 13 others only would bring you 2 numbers, probably not enough to solve the puzzle.
very true indeed, they would advance nothing, hence their use as an arrangement restriction instead of the first row.

A similar, more direct approach is the known method, that you choose a row or column, and try the possible ways of filling it out one by one. E.g. in row 1 there are 4 ways, one of which is correct.
fair enough,
backtracking the combination of clue assertion per, Row/Col/ box & {min row/col} works wonders :) and produces all solution sets nicely,

however I'm not trying to build a known working method,

i am contemplating if it could work.

so far i have the 9!*6^8*2 transformations coded into my solver instead of using my spreadsheet lol
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 657
Joined: 05 September 2006

Re: help with brute force solving idea:

Postby eleven » Mon Dec 26, 2016 12:20 pm

Oops, please forget the numbers i posted, i was in hurry and had used an old program, which was hacked for another purpose. So only a part of the equivalent puzzles was calculated. Can't fix that now.
However the relations between wrong and right assumptions for the first 11 numbers for transformed puzzles should not be too bad.

To summarize: This method is yet another approach of guessing numbers (simultaneously) with the meaningless overhead for the puzzle transformations.
eleven
 
Posts: 1580
Joined: 10 February 2008

Re: help with brute force solving idea:

Postby eleven » Mon Dec 26, 2016 10:48 pm

Finally a hint, how you can use this method without transforming and renumbering:

Code: Select all
.---------------.------------.-----------------.
| 5    478  1   | 2   6   3  | 789    78    49 |
| 34   6    247 | 1   8   9  | 237    5     34 |
| 9    238  28  | 7   5   4  | 2368   2368  1  |
:---------------+------------+-----------------:
| 2    9    3   | 6   4   8  | 5      1     7  |
| 48   478  478 | 59  19  15 | 236    236   36 |
| 1    5    6   | 3   2   7  | 4      9     8  |
:---------------+------------+-----------------:
| 7    38   5   | 4   19  6  | 1389   38    2  |
| 36   1    9   | 8   7   2  | 36     4     5  |
| 468  248  248 | 59  3   15 | 16789  678   69 |
'---------------'------------'-----------------'

Look at the last 3 columns:
There are 2 ways to fill c9:
431|768|259, where you can have
34(in r12c9) also in r65c7 or r87c8
13(in r32c9) also in r78c7 or r98c7 or r45c8
67(in r54c8) also in r31c7 or r32c7 or
78(in r46c8) also in r23c7 or r97c7 or r31c8 or r97c8 or
68(in r56c9) also in r31c7 or r87c7 or r89c7 or r97c7 or r31c8 or r97c8
25(in r78c9) also in r54c7 or r32c8
29(in r79c9) also in r21c7 or r31c7 or r56c8
and
941|738|256, where you can have
19(in r31c9) also in r79c7 or r97c7 or r46c8
37(in r54c9) also in r21c7 or r31c7 or r32c7 or r79c7 or r89c7 or r31c8
....


For all these combinations you can find a possibly 12345678945 starting puzzle this way:
Take the pair in c7 or c8: switch it's band to band 1, and the rows, so that the 2 digits are in row 1 and 2.
Now switch the band with the digits in c9 to band 2, and the rows to have them in r45.
If the pair is in c7, switch columns 7 and 8.
Then renumber to have 123456789 in c9, which gives you 45 for the pair, also in r12c8.
Transpose the puzzle, and you have what you want.

So you don't need to do that, just guess the numbers to be one of these combinations.

So you can take any solution of a row/column and look for a pair of candidates in a minirow/column, which also is present in a minirow/column of the other 2 rows/columns of the band/stack. If you find one, set them to these values.
eleven
 
Posts: 1580
Joined: 10 February 2008


Return to Help with puzzles and solving techniques