Some puzzle games have a unique solution that can be solved by deduction rather than guesswork (e.g. Slitherlink, Masyu). Using a computer to solve this puzzle it's pretty easy, we can use a backtracking method to find the best solution in second (in general, the puzzle size is not too big).

Is it possible to train a bot to solve this kind of puzzle by deduction?

I think by train it to watch a previous step-by-step solution several times the bot can find some implicit rules/patterns to solve a specific puzzle. Is this possible? are there any references for this method?

  • $\begingroup$ Deductive solutions work by constraining the search space and then executing a suitable search algorithm. As such they are typically solved by describing the puzzle in a notation your solver can read. $\endgroup$ – Paul Brown Aug 2 '19 at 20:43
  • $\begingroup$ The alternative is to still describe the problem and use reinforcement learning, which will find good search paths for similar domains. $\endgroup$ – Paul Brown Aug 2 '19 at 20:52
  • $\begingroup$ Hi @PaulBrown could you give a more detailed explanation as an answer maybe? $\endgroup$ – malioboro Aug 5 '19 at 3:49

What you are trying to achieve sounds a lot like inductive logic programming:

Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

| improve this answer | |
  • $\begingroup$ nice reference! thank you, I'll wait some time before giving you a green tick to look for another answer $\endgroup$ – malioboro Aug 5 '19 at 3:48
  • $\begingroup$ You're welcome. I guess statistical methods, deep learning and all that are more en vogue these days, but once in while it certainly can't hurt to take a look at what various people have done in other fields such as ILP. In particular the class of problems that you are interested in (deterministic, fully observable logic puzzles) should lend itself very well to it. $\endgroup$ – Jens Classen Aug 5 '19 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.