• Programming 14.12.2008

    Some years ago a friend of mine introduced to me a numerical puzzle called Sudoku. For every one who has not already heard of it, i will give a short description: The puzzle consists of a square field divided into 9 rows and 9 columns. Furthermore the 9×9 block is divided into nine 3×3 blocks. In every of the nine rows, nine columns and 3×3 blocks the numbers from 1 to 9 have to be positioned, so that every number occurs only once in every row, column and 3×3 square.

    At the start some, depending on difficulty, cells are already filled in. Then one has to conclude the missing numbers by logic. This can be done by a process of elimination.

    My solver sequentially checks the remaining possibilities for every cell. This is done by checking every cell in the same row, column and 3×3 field for the already filled in numbers. The remaining numbers are the possible for the cell. If there is only one, it is written to the cell. This is the simple version, but also the one that executes quicker.

    The more complex version compares the possible solutions for one cell with all the cells in the same row, column and 3×3 field. This allows to assign an number to a field, even if there are more than one possibilities, if one of them only is true for this cell.

    Some times the solution for one cell is ambigous. Then the solver chooses one of the remaining possibilities and then continues with the solution process. If the field can not be solved (when contradictions occur), the next possibility is checked until the field can be solved.

    The code may be a bit over complicated at some points because the strategy developed over time and was not planned in advance. Besides that, all (of the very few) comments are in german, as are all loging-outputs.

    Delphi 5 sourcecode can be downloaded here.

    Posted by Konstantin @ 03:42

    Tags: , ,

  • Leave a Reply

    Your email address will not be published. Required fields are marked *