0
$\begingroup$

I looked a bit online for Sudoku solvers and it seems like all the answers I found involve a backtracking algorithm.

However, this is not how humans (at least not me) solve Sudoku. We don't place in the first empty square, the first digit that works and go on until we solve it or hit a dead end. Usually, we try to find an empty square (which can be anywhere on the board) where there is a unique solution and then we repeat this. We might have to do some backtracking-like approach if we are out of squares with unique solutions, but that is not the main part of our approach.

Are there any algorithms (even backtracking variations) that solve the sudoku in a way more similar to this approach?

$\endgroup$
0
0
$\begingroup$

Surely you can implement such algorithm, since you already know the details. Iterative steps:

  1. Determine possible numbers in all empty squares
  2. Find the square with the least number of possible numbers
  3. Does this square have an unique solution? If yes, set it and GOTO 1
  4. Else apply the backtracking logic and guess a number, GOTO 1

People who are good with sudokus know various advanced tricks, which I have seen on Youtube at Cracking The Cryptic channel. He has even tested a sudoku's difficulty on a specific solver site, in which you can choose that which advanced techniques you want it to apply. In my understanding the site's algorithm does not use any backtracking, and it might conclude that it cannot solve the problem with given techniques. Sadly I don't remember this website's name, or the video in which it was used.

Arguably this is more of a Computer Science answer than AI, but then again for example chess engines can be approached from either direction.

$\endgroup$

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.