Search code examples
algorithmprologheuristicssudoku

Is my heuristic algorithm correct? (Sudoku solver)

First of -yes this IS a homework- but it's primarily a theoretical question rather than a practical one, I am simply asking a confirmation if I am thinking correctly or any hints if I am not.

I have been asked to compile a simple Sudoku solver (on Prolog but that is not so important right now) with the only limitation being that it must utilize a heuristic function using Best-First Algorithm. The only heuristic function I have been able to come up with is explained below:

1. Select an empty cell. 
  1a. If there are no empty cells and there is a solution return solution.
      Else return No.
2. Find all possible values it can hold. %% It can't take values currently assigned to cells on the same line/column/box.
3. Set to all those values a heuristic number starting from 1.
4. Pick the value whose heuristic number is the lowest && you haven't checked yet.
   4a. If there are no more values return no.
5. If a solution is not found: GoTo 1.
   Else Return Solution.

// I am sorry for errors in this "pseudo code." If you want any clarification let me know.

So am I doing this right or is there any other way around and mine is false? Thanks in advance.

Solution

  • The heuristic I would use is this:

    1. Repeatedly find any empty spaces where there is only one possible number you can insert. Fill them with the number 1-9 that fits.
    2. If every empty space has two or more possibilities, push the game state onto a stack, then pick a random square to fill in with a random value.
    3. Go to step 1.

    If you manage to fill every square, you've found a valid solution.

    If you get to a point where there are no valid options, pop the last game state off the stack (i.e. backtrack to the last time you made a random choice.) Make a different choice and try again.

    As an interesting sidenote, you've been told to do this using a greedy heuristic approach, but Sudoku can actually be reduced to a boolean satisfiability problem (SAT problem) and solved using a general-purpose SAT solver. This is very elegant and can actually be faster than a heuristic approach.