0
$\begingroup$

I am a new contributor and have no experience in ML, so this first question is a general one. I've developed a sudoku solving app and since then I wonder whether it would be feasible to design a ML-based algorithm/software which would mimic the thinking process of a human for solving a sudoku puzzle.
Maybe there exists already such a software? I don’t mean any existing brute-force algorithm a human cannot apply! I see many challenges in the design of such an algorithm, e.g. determine that the solution is not unique, uncover the highly sophisticated solving techniques that only talented players know and can apply to hard puzzles.
My thoughts even go so far as to imagine that such an algorithm would "discover" a solving technique that we humans have not yet discovered.

Update

I posted on kaggle a notebook titled Artificial Sudoku Player. I intended to launch a code competition on the subject but I face a problem of specifying a proper metrics. All metrics proposed on kaggle are statistical metrics for ML models, but the goal of this competition is to design a learnable RL model of the deterministic sudoku solving process. Any constructive suggestion is welcome. https://www.kaggle.com/code/sudokoach/artificial-sudoku-player. Check out for a description of the competition: https://github.com/Sudokoach/Artificial-Sudoku-Player/blob/main/Artificial%20Sudoku%20Player.pdf

$\endgroup$
3
  • 1
    $\begingroup$ Related: ai.stackexchange.com/q/33994/32722 $\endgroup$
    – NikoNyrh
    Nov 3, 2022 at 16:49
  • $\begingroup$ maybe imitation learning, or inverse reinforcement learning $\endgroup$
    – maxy
    Apr 4, 2023 at 16:51
  • $\begingroup$ @maxy Thank you for this reading. Since I posted the question I put my thoughts on paper that I'd like sharing. My conclusion is that's an RL application. However the implementation is far beyond my competencies because I know nothing about ML/RL and above all it's a team work! That's why I'm looking for a community which would be interested in such a development. May be you know one? $\endgroup$
    – SudoKoach
    Apr 5, 2023 at 8:56

2 Answers 2

0
$\begingroup$

Your problem here is not the application of ML techniques to solving Sudoku. Reinforcement learning might be a reasonable search method, and you could augment it with results from other search methods, to enable it to learn in reasonable time.

Your problem is trying to train AI to behave "like a human" whilst having little to no definition for what that is. Supervised learning will require a large dataset of how humans solve the puzzles to copy. Reinforcement learning will require you to provide a reward signal that gives better rewards for when it behaves like a human.

What professional puzzle setters do is write variations of traditional AI search methods that they tune to score difficulties of different search steps, depending on how they define "easy" or "hard", and take some aggregate score to rate the puzzle as a whole. As an example, you could take the search depth of testing different initial guesses to resolve a single number and look at the consequences. Higher search depth required, and larger number of initial guesses available make finding a number harder.

Some Sudoku setters keep their "human-like" search methods proprietary because publishing puzzles is a business. You may be able to find some examples online though.

$\endgroup$
-1
$\begingroup$

Its feasible to do so, not sure about `new techniques'. one can use RL by desigining your reward function (state space is just the current state of sudoku puzzle, action would be putting a particular number at some square), and solve using available methods. One can combine this with ml (perhaps approximating the reward function using past data).

however this seems easier to solve using methods from more conventional AI at first glance - i am not fully aware of the nuances of 'hard puzzles'.

Either way, you shoudl read more about standard AI, ml and then rl if interested.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .