Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A FORTRAN code for solving Sudoku puzzle

  1. Jan 26, 2013 #1
    For few days I am thinking to write a code in FORTRAN to solve the sudoku puzzle.
    At first it seams simple but I have no luck writing this code.
    I am wondering if there is any written code to solve this puzzle.
    I hope Sudoku puzzle is known for members here.
    en.wikipedia.org/wiki/Sudoku
     
  2. jcsd
  3. Jan 26, 2013 #2
    You can get some inspiration from my own solution in python: on my blog.

    You may find some help in this book (I haven't read it, but I was told some great things about it).

    J.
     
  4. Jan 26, 2013 #3

    Mark44

    Staff: Mentor

    I'm sure sudoku is well-known to people here. What have you tried? What difficulties are you having?
     
  5. Jan 26, 2013 #4

    jedishrfu

    Staff: Mentor

    Trying to write a sudoku generator is a lot easier than writing a sudoku solver especially if you start with an existing solution and then use the transformation rules for sudoku:

    1) you can reorder any row or col within a group and still have a valid puzzle
    2) you can reorder any 3-row or 3-col groups and still have a valid puzzle

    from that you can see that you can generate a lot of different but related puzzles.

    One question I had though was whether you could generate the complete set of sudoku puzzles or not given one solution and these transformations.
     
  6. Jan 26, 2013 #5
    Dear Mark
    Thanks for your reply. I am trying to draw a flowchart of solution in FORTRAN.
    My methodology is as follows:
    1- Select each cell with zero value (empty cells are zero) in big square (9x9) starting from top left
    2- Put value 1 to the first zero cell.
    3- Check this cell with all cells in same row. If they have same value, add one to previous value of cell and check again.
    4- repeat item 2 and 3 for same column
    5- repeat item 2 and 3 for small square (3x3)
    Go to next step.

    This methodology is not a wise method and even if it is able to solve, it will take lots of time.
    So I think there must be a better solution strategy.
     
  7. Jan 26, 2013 #6
    Dear Jedish
    Thanks for comments. I was unaware of transformations you mentioned. They are interesting however I don't think they might help me to draw a flowchart for solution.
    As you wrote, making a generator is lot easier than writing a solution. But I don't have a solution for a given Sudoku.
     
  8. Jan 26, 2013 #7

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

  9. Jan 26, 2013 #8

    jedishrfu

    Staff: Mentor

    Okay so a brute force scheme would be to assign all blank cells with the value of 1 and then consider the cells together as a monster number that you can count thru like 1111111111111111 then 1111111111111112...

    Next provide a method to validate a potential solution, ie is the 3x3 square valid, does the row have a duplicate, does the col have a duplicate... if it fails then increment the cell and try again when it hits 9 increment the next cell and reset the first cell to 1 and repeat incrementing the first cell...

    Another method would be to generate a set of potential solutions and use a genetic algorithm to merge solutions and a scoring function to evaluate solutions.
     
  10. Jan 27, 2013 #9
    Dear AlephZero and jedishrfu

    Thanks for replies. I have seen the wikipedia page but wanted to try a personal way for solving.
    It seams that there are many discussions on the issue and I was unaware of them.
    I will read the brute force algorithm thoroughly and let you know what am I up to do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A FORTRAN code for solving Sudoku puzzle
  1. Running a Fortran code (Replies: 4)

  2. Help with fortran code (Replies: 17)

  3. Help with fortran code (Replies: 4)

Loading...