Is my heuristic algorithm correct? (Sudoku solver)

Posted by Aposperite on Stack Overflow See other posts from Stack Overflow or by Aposperite
Published on 2012-04-12T23:51:57Z Indexed on 2012/04/13 11:28 UTC
Read the original article Hit count: 329

Filed under:
|
|
|

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.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about homework