Anonymous user
Talk:Diophantine linear system solving: Difference between revisions
Talk:Diophantine linear system solving (view source)
Revision as of 07:34, 27 February 2022
, 2 years agono edit summary
No edit summary |
No edit summary |
||
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)
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)
| |||