4 ms·
This is something that bugged me for a long time. There are many other challenging algorithmic questions that I will share in a separate blog post later (e.g. w
by chedoku 4y ago
This is something that bugged me for a long time. There are many other challenging algorithmic questions that I will share in a separate blog post later (e.g. writing a efficient solver). If you have any idea how to do that I would love to hear about that.
- shmageggy 4y agoLooks like this could be translated into a SAT problem and solved with a SAT solver. Have you tried that?
- chedoku 4y agoI have actually used SAT solver before but I have no idea how to translate this into a SAT problem. I know it is too much to ask you to do it for me but maybe you can give me a hint (or link) on how to translate problems that deal with numbers into boolean expression that can be solved by a SAT solver.
- shmageggy 4y agoI’m not an expert in it either, but this problem is similar to both the N-queens problem and Sudoku, both of which can be solved via SAT, so tutorials for those should be a good start. Good luck!
- rcme 4y agoAlso some explanation of what makes a solution "perfect" would be nice.
- chedoku 4y agoThanks for you comment. I am working on it now. 1- Perfect solution, you get a green notification when you find the one, in which other squares with no number have zero threats. Pressing the 'solution' button reveal the perfect solution 2- Imperfect solution, you get a yellow notification when you find one, in which other squares with no number may be under one or more threats. A bit confusing so for now I try not to be strict about imperfect solutions.