Talk:Diophantine linear system solving

From Rosetta Code

Hello everyone.

I wrote a standard C port of the FreeBasic program. It's a pretty much verbatim rewriting. All the tests give the same exact result. I'm willing to put it in here but:

1) I don't know how to proceed. Do I just have to edit the "Diophantine linear system solving" page? Is there a correct way to do that?

2) I read the talk. This is a quote from --Pete Lomax (talk) 15:01, 26 December 2021 (UTC): "From my point of view I'd like to know more about how this might be used/prove useful in some future (non-rc) project". I've actually done the porting for that exact reason. I had a problem, a really important one at that. I wanted to solve minesweeper. I needed a way to find ALL possible combinations of bombs, given the constraints of the minefield in a particular situation. Sadly enough this method gives only one solution. One valid solution, but not necessarily the correct one. So mine is the question of the lazy person that I am (read "math impaired"): where do I need to look in this procedure to find something to change in order to being able to obtain all the possible solutions, not just one of the simplest?

I hope it makes some sense (my inglysch sucks).

ps: again, how do i insert the code? who do i need to send i to?

pps: never mind point 1. i think i got it. let me know if you try it and there is any problem. point 2 still applies :)

Re point 2: Unfortunately I suspect you'd be better off attacking the minesweeper problem a completely different way. --Pete Lomax (talk) 12:03, 26 February 2022 (UTC)

OOps: edit this page to see how the following is to be entered :-) -- fixed --Pete Lomax (talk) 11:44, 26 February 2022 (UTC)

ad 1 Edit the task and add these lines in the proper place (PL: as they look, not as I've just mangled them)

=={{header|C}}==
<lang c>your program</lang>
{{out}}
<pre>your output</pre>

Then save the task with Summary 'added C' ad 2 Under tasks open it --Walter Pachl 14:04, 25 February 2022 (UTC)

Thank you very much. I've updated the page.

Hi Plinio and welcome. You're doing fine, don't worry. Two more little things: 1) we keep entries in alphabetical order so you need to move your C entry above FreeBasic, and 2) on talk pages please sign your comments with two dashes and four tilde, ie --~~~~ (without the nowiki bits), which will be replaced with your username and the time and date. --Pete Lomax (talk) 04:05, 26 February 2022 (UTC)
I added a sentence here and moved the C-code in the task. All disappeared! did someone dislike what I did? --Walter Pachl 10:01, 26 February 2022 (UTC)
Not me! Are you sure you didn't dream it? Nothing in the history. Yeah that would be weird. --Pete Lomax (talk) 11:44, 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. --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. (image 1)

After uncovering some tiles you end up with some clues. (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. (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... (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. (image 5)

Here's an example of safe tile: the fifth column has all 0s, which means that tile 5 is 100% safe. (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 IS a solution... out there... somewhere... :)

--Plinio (talk) 07:33, 27 February 2022 (UTC)

Oh, don't worry at all about disturbing people, there's well over 5,000 talk pages on this site and most of us only pay attention to a tiny fraction of them. Anyway, here's a quick little ditty I knocked up to show a possible alternative approach, probably much saner and certainly exponentially easier to tweak and adjust.
constant msprob = {{1,{},{1,2,3,4,5,7}},
                   {3,{4,5,7},{9,10,11}},
                   {2,{5,10,11},{6,8,12}}}
sequence field = repeat(0,12)

procedure solve(integer tdx=1)
    if tdx>length(msprob) then
        ?{field,find_all(1,field,true)}
    else
        {integer tgt, sequence fixed, sequence play} = msprob[tdx]
        tgt -= sum(extract(field,fixed))
        if tgt<0 or tgt>length(play) then return end if
        field = reinstate(field,play,repeat(0,length(play)-tgt)&repeat(1,tgt))
        bool found = true
        while found do
            solve(tdx+1)
            found = false
            integer nxt = play[$]
            for idx=length(play)-1 to 1 by -1 do
                integer prv = play[idx]
                if field[prv]=0 and field[nxt]!=0 then
                    field[prv] = 1
                    field[nxt] = 0
                    found = true
                    sequence slamright = play[idx+2..$]
                    field = reinstate(field,slamright,sort(extract(field,slamright)))
                    exit
                end if
                nxt = prv
            end for
        end while
    end if
end procedure
solve()

output

{{0,0,0,0,0,0,1,0,0,1,1,0},{7,10,11}}
{{0,0,0,0,0,0,1,0,1,0,1,1},{7,9,11,12}}
{{0,0,0,0,0,0,1,1,1,0,1,0},{7,8,9,11}}
{{0,0,0,0,0,1,1,0,1,0,1,0},{6,7,9,11}}
{{0,0,0,0,0,0,1,0,1,1,0,1},{7,9,10,12}}
{{0,0,0,0,0,0,1,1,1,1,0,0},{7,8,9,10}}
{{0,0,0,0,0,1,1,0,1,1,0,0},{6,7,9,10}}
{{0,0,0,0,1,0,0,0,1,0,1,0},{5,9,11}}
{{0,0,0,0,1,0,0,0,1,1,0,0},{5,9,10}}
{{0,0,0,1,0,0,0,0,0,1,1,0},{4,10,11}}
{{0,0,0,1,0,0,0,0,1,0,1,1},{4,9,11,12}}
{{0,0,0,1,0,0,0,1,1,0,1,0},{4,8,9,11}}
{{0,0,0,1,0,1,0,0,1,0,1,0},{4,6,9,11}}
{{0,0,0,1,0,0,0,0,1,1,0,1},{4,9,10,12}}
{{0,0,0,1,0,0,0,1,1,1,0,0},{4,8,9,10}}
{{0,0,0,1,0,1,0,0,1,1,0,0},{4,6,9,10}}
{{0,0,1,0,0,0,0,0,1,1,1,0},{3,9,10,11}}
{{0,1,0,0,0,0,0,0,1,1,1,0},{2,9,10,11}}
{{1,0,0,0,0,0,0,0,1,1,1,0},{1,9,10,11}}
I don't think that misses any, but I could be wrong. Enjoy. --Pete Lomax (talk) 12:12, 27 February 2022 (UTC)
PS There are of course many points in the game of minesweeper where you are forced to make a guess, the start screen being one, and this example being another.
The results suggest 9 is the most likely to be a mine and any of {1,2,3} your best gambol. --Pete Lomax (talk) 12:45, 27 February 2022 (UTC)