Talk:Diophantine linear system solving: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 46: | Line 46: | ||
::::Thanks for the pointers. I will try not to mess things up too badly. About the what Walter says, I don't think it was me; I'm pretty sure I didn't delete/change anything. --[[User:Plinio|Plinio]] ([[User talk:Plinio|talk]]) 12:51, 26 February 2022 (UTC) |
::::Thanks for the pointers. I will try not to mess things up too badly. About the what Walter says, I don't think it was me; I'm pretty sure I didn't delete/change anything. --[[User:Plinio|Plinio]] ([[User talk:Plinio|talk]]) 12:51, 26 February 2022 (UTC) |
||
Sorry, I did not see Pete's reply about the minesweeper problem. |
|||
I'm not sure I'm ready to give up yet. |
|||
I don't intend to clog this space with my silly endeavours, so I will just point out something of what I did and something of what I've found, just for the sake of completeness (and braggyness :). |
|||
Fist, what I did: |
|||
I will assume you know how the game works. If not, it's a really simple game, you would probably understand it's rules just by looking at it. |
|||
So, build the field by randomly tossing some N mines on a field. |
|||
This is the mine field behind the curtains, for reference. [https://ibb.co/cFNdK3y (image 1)] |
|||
After uncovering some tiles you end up with some clues. [https://ibb.co/cyTpZYm (image 2)] |
|||
Trace the perimeter tiles (the ones adjacent to at least one uncovered tile), |
|||
Label the perimeter tiles from left to right, from top to bottom. |
|||
Label the clue tiles following the same order. |
|||
[https://ibb.co/Mp4rt2k (image 3)] |
|||
You can see that: |
|||
clue n.1 (danger 1) is responsable for perimeter tile 1, 2, 3, 4, 5 and 7 |
|||
clue n.2 (danger 3) is responsable for perimeter tile 4, 5, 7, 9, 10 and 11 |
|||
clue n.3 (danger 2) is responsable for perimeter tile 5, 6, 8, 10, 11 and 12 |
|||
Now you have a list of perimeter tiles (unknowns) and a list of clue tiles (the B vector in the augmented matrix): |
|||
1 1 1 1 1 0 1 0 0 0 0 0| 1 |
|||
0 0 0 1 1 0 1 0 1 1 1 0| 3 |
|||
0 0 0 0 1 1 0 1 0 1 1 1| 2 |
|||
Plug this matrix in the task's algorithm and obtain the solution... [https://ibb.co/k0DHW0M (image 4)] |
|||
just one solution... |
|||
one of the shortest... |
|||
not the correct one. |
|||
First of all, this algorithm returns bomb tiles tagged as -1 and safe tiles tagged as 0, but I don't know what to make of the +1s in the solution. What do those represent? |
|||
Secondly, a bomb is 100% correct if (and only if), on the solution matrix, the rest of the corresponding tile's column has ONLY 0s, which is not the case for any tile, in this example. |
|||
Same for the safe tiles: a tile is 100% safe is the rest of the column contains ONLY 0s. (in this example no perimeter's tile is 100% safe) |
|||
This means that, as to be expected, there is no 100% safe solution for this situation, not even a partial one. |
|||
[https://ibb.co/S5N1bvf (image 5)] |
|||
Here's an example of safe tile: the fifth column has all 0s, which means that tile 5 is 100% safe. [https://ibb.co/NmTS38F (image 6)] |
|||
Can't get any further than that. |
|||
But if you had all valid bomb placements you could derive probabilities about tile's safety. |
|||
Now, going back to my original question: is there a "hack" to perform on this algorithm to make it spit out all valid solutions? |
|||
It looks like there must be something that can be done. |
|||
(http://www.numbertheory.org/php/axb.html) |
|||
To my mathly blind eyes it seems that this page solves the problem using the same algorytm, and if I plug in it the augmented matrix |
|||
3 |
|||
12 |
|||
1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 3 0 0 0 0 1 1 0 1 0 1 1 1 2 |
|||
I get exactly the kind of results I'm looking for. |
|||
The signs are inverted and, in some solutions, there still is the +1 -1 promiscuity, but if you discard those you are left with all the possible solutions applicable to the problem: 4 variations with 3 bombs, and 15 with 4 bombs. |
|||
I hope it made some sense. |
|||
As sayed, I won't keep bothering you guys any further with this frivolous dilemma. I just wanted to clarify that I'm pretty sure THERE IN a solution... |
|||
out there... |
|||
somewhere... :) |
|||
--[[User:Plinio|Plinio]] ([[User talk:Plinio|talk]]) 07:33, 27 February 2022 (UTC) |