# A FORTRAN code for solving Sudoku puzzle

1. Jan 26, 2013

### yabi

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. Jan 26, 2013

### jfgobin

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.

3. Jan 26, 2013

### Staff: Mentor

I'm sure sudoku is well-known to people here. What have you tried? What difficulties are you having?

4. Jan 26, 2013

### 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.

5. Jan 26, 2013

### yabi

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.

6. Jan 26, 2013

### yabi

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.

7. Jan 26, 2013

### AlephZero

8. Jan 26, 2013

### 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.

9. Jan 27, 2013

### yabi

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.