2006-09-07

Genetic Sudoku Solver

I wasn't in the mood for "real" work this afternoon so I decided to bug my girlfriend instead. She has developed a serious Sudoku addiction lately and solves them by the dozen. I thought it was a beautiful problem for a genetic algorithm to solve so I gave it a shot. The whole thing took little over 3 hours to code, starting from scratch using only the STL and MFC. The result won't win any beauty prices and is most certainly not the fastest or most intelligent solver out there - but it works. I've used the most basic of all GAs, implementing truncation selection for selecting suitable parents. Childs are created by using the first n blocks of one parent and the last 9 - n from the other. Mutation is archieved by simply swapping random fields in a block. The fitness function counts how often a digit appears in a row or a column, every deviation from one counts as an error. Sudoku is a pretty hard problem for a GA because it has many solutions with the same error count, i.e. the same fitness. Such a multimodal error function needs a GA that is better capable of exploration vs exploitation than mine. Using truncation selection for inheritance is pretty bad, cause it will not usually try enough approaches and easily get stuck in local minima. I "solved" the problem by simply using a high chance for mutations and thus a high random factor. You can tell that the GA isn't very good for exploring because it is highly dependant on the initial parameters and population. Usually, if you choose the right GA for the problem at hand, GAs are pretty robust and don't change much with respect to initialization. As it is, the algorithm needs a couple of seconds and about five to ten thausand iterations to solve a moderately complex sudoku. For the fiendish and extra hard problems it'll take minutes and several hundred thausand iterations. Anyways - that was fun ;-)

8 comments:

  1. Lustige Idee! Ein SuDoku-Solver zu schreiben, hatte ich natürlich auch schon im Kopf, aber mit GA hätte ich es wohl nicht versucht. Ich wusste gar nicht, dass Anita SuDokus mag. Noch mehr wundere ich mich, dass gerade du MFC verwendest.

    VG
    VV

    ReplyDelete
  2. Lustige Idee! Ein SuDoku-Solver zu schreiben, hatte ich natürlich auch schon im Kopf, aber mit GA hätte ich es wohl nicht versucht. Ich wusste gar nicht, dass Anita SuDokus mag. Noch mehr wundere ich mich, dass gerade du MFC verwendest.

    VG
    VV

    ReplyDelete
  3. Eigentlich war ich erst bei der Vorschau. Das mit den Kommentaren lerne ich vielleicht noch ...

    ReplyDelete
  4. Eigentlich war ich erst bei der Vorschau. Das mit den Kommentaren lerne ich vielleicht noch.

    ReplyDelete
  5. LOL! Die wollen mich verarschen! Erst Serverfehler und kein neuer Eintrag, dann wieder gleich zwei.

    ReplyDelete
  6. Well, where can I downloasd the soduko solver

    ReplyDelete
  7. @FigBug: You can't download it. It's not anywhere near presentable quality source, just a quick "let's see if I can do it" hack. I'm working on more AI stuff, maybe I'll wrap it into a proper release later.

    regards,

    BuschnicK

    ReplyDelete
  8. das ist nicht lustig ;-)

    your girlfriend

    ReplyDelete