I want to create a minesweeper board as a 2D array of integers. (This board is created by randomly placing mines and then checking if the board is solvable without guessing.) I thought that I could speed up the generation by generating and checking multiple boards in parallel.
For this, I need multiple jobs that can work on their own until one of them finds a valid board. I want to take the result of the first job that completes the task and ignore the other jobs.
How could I react to the first job being finished, use its result (potentially big integer array) and terminate the others? Can I avoid to create a NativeArray big enough for all jobs to write their results into it?
Firstly I would ask, is there unsolvable solution of minesweeper at all?
I thought every combination has winning combination?
What I am missing? Or what you trying to check?
Ah, sorry, I am looking for guess free solutions, based on the first field opened. I already got that and it’s not important to the problem, I just wanted to give some background information on the data.
Thats fine. I understand that. But these are not unsolvable puzzles. Still got chance 50:50 as you said.
But if that are to be eliminated, then yes, multiple lookup could be useful.
Personally I would simply add some ‘skill’, which when clicked on unknown field, can show value.
This could add penalty to the game score, or simply limit to 1 or few uses only.
I am not sure, why you need multi threading for that. Can you elaborate a bit more?
Is not that you just check neighbor fields and expand in given direction, until find mine?
Probably you want look into flood algorithm, if I understand what you mean.
I still want to validate each board on a single job, but use other jobs to try out different boards with different mine positions. So there would be, say 4, jobs, each of them generating their own mine positions. Then they try to solve it. When one job finds a solution, I want to take that board to give it to the user and just terminate the other threads. I will try to add a sketch to the first post.
It is possible to use a system of linear equations where each line represents one of the covered fields (ignoring unreachable ones). Using Gaussian elimination, you can find all currently unambiguous steps and execute them. This is repeated until all mines are flagged or there are no unambiguous steps left.
Job cancelling (and scheduling jobs from a job) is prevented by design to allow safe API, so you cannot do dynamic programming style algorithm that might go overboard… a job must finish.
In unsafe job there should be a way, like having a pointer that becomes true once one job finished and if other jobs read and found this to be true then just return the Execute. I think you also need to put [NativeDisableUnsafePtrRestriction] on the pointer for that.
To be honest, I didn’t expect, that you could terminate jobs. But now confirmed.
However, what I would do in such case, is to generate set of multiple solution boards, on Jobs. Lets say 100. That will be lightning fast with burst anyway.
Then check them against best results on single thread. If I am happy with outcome, output best result. If not, repeat 100 jobs.
Then again, compare new results, including old result.
However, yes, you need store 100 boards in such case.
I would pregenarate required buffer arrays size on 100 enties. Then simply put them into jobs, to store your boards data. For 100x100 boards that is 10 000 fields. Mult by 100 that is 1 000 000. No big deal tho.
