# Fortran generated sudokus

FWIW, this book: * Charnick, Bernard (2023). Sudoku with Symmetry. lulu.com. pp. viii + 220. ISBN 978-1-4475-1761-0. contains puzzles generated by Fortran programs.

Mike

1 Like

In 2006, I wrote a Fortran program which can generate sudokus and solve them, with random strategies. But it was written in French for a student project. And the code was never modernized.

If someone is interested I could put it online. But I have no time to rework it fullyâ€¦

`````` Voici la grille de dĂ©part :
0 4 0 | 0 0 0 | 3 0 8
0 0 0 | 7 4 0 | 2 0 0
0 0 9 | 0 1 8 | 0 0 0
------+-------+------
0 7 0 | 0 0 0 | 9 0 0
8 0 0 | 3 0 5 | 0 6 0
0 0 0 | 0 8 7 | 0 5 3
------+-------+------
0 0 0 | 0 7 0 | 0 0 4
0 0 3 | 8 0 0 | 0 0 9
2 0 0 | 0 0 0 | 0 0 0

1 4 2 | 5 9 6 | 3 7 8
5 8 6 | 7 4 3 | 2 9 1
7 3 9 | 2 1 8 | 6 4 5
------+-------+------
3 7 5 | 1 6 4 | 9 8 2
8 9 1 | 3 2 5 | 4 6 7
6 2 4 | 9 8 7 | 1 5 3
------+-------+------
9 1 8 | 6 7 2 | 5 3 4
4 6 3 | 8 5 1 | 7 2 9
2 5 7 | 4 3 9 | 8 1 6
``````

In 1996 you wrote an article A Sudoku program in Fortran 95. Could you possibly post the code?

Ah, yes, so long ago. Iâ€™d have to work very hard to get it into a publishable form, and I leave home tomorrow for at least four weeks. So, sorry, no.

And vmagninâ€™s sudoku is, unfortunately, invalid. It has 2 solutions: the 1 and 4 in rows 5 and 6 of the solution grid can be interchanged.

Regards,

Mike

1 Like

Thanks to the efforts of @nbehrnd last summer, my 17 year-old Fortran sudoku program is now translated in English, with a modernized code (modern Fortran features, automatic tests, heavy refactoringâ€¦) and has become the ForSudoku project (of course based on fpm).

It is not as general as the program described by @m_b_metcalf in his 2006 paper as it can make only classical 9x9 sudokus but it offers many functionnalities:

`````` ForSudoku 1.0.0, copyright (c) 2006-2024 Vincent Magnin and Norwid Behrnd

1) Manual input (lines of comma separated 1 - 9, or 0 (empty cell)).
2) Read a grid from a text file (for permitted patterns, see the doc).
3) Save the current grid in a text file.
4) Check the validity of the current grid.
5) Display the current grid.
6) Create a random completed Sudoku grid.
7) Solve the puzzle grid currently stored in memory.
8) Create a minimal puzzle, starting from the grid in memory.
9) Create a minimal puzzle with exactly n given digits.
10) Create a puzzle grid (without guaranty for a unique solution).
0) Quit.
``````

Last week, I have written a new algorithm (8) to obtain a sudoku puzzle with a unique solution: we start from a shuffled list of the 81 cells (see line 437 in the `create_puzzle_with_unique_solution()` subroutine in the `src/sudoku.f90` file). We scan the list and try to remove each digit one by one: if that digit is the only possibility at this position (considering the validity rules for its row, column and region) it is removed and we go to the next one. When no digit can be anymore removed validly, the puzzle is ready (but you donâ€™t know a priori how many given digits will remain). It is a minimal puzzle.

It is evident that if I fill the puzzle by putting back each digit following the same reverse order from the n^{th} removed digit to the first one, I will obtain the original sudoku grid, as each digit is the only one possible at each step. What was really not clear in my mind at first sight, especially for half-empty grids, was the following question: can I find another solution to this puzzle if I follow a different path (therefore starting from another empty cell)? I have finally think to a recursive demonstration by absurd: letâ€™s suppose that there is another path toward another solution, we can first put back the last n^{th} digit we removed because anyway we know that it is the only possible in its cell (it can therefore not be affected by our new path, and it can not affect the other solution). Then we can start to find that different path, butâ€¦ The n^{th} digit being in place, we know that the n-1^{th} is also the only one possible in its cell, so we can put it back before starting to find another solution. And so onâ€¦ Finally we obtain the full original sudoku grid, without having even started to search another pathâ€¦ We can therefore conclude that there is no other solution to our puzzle.

Please tell me if you agree with this demonstrationâ€¦ or if you think I am wrong.

If you are interested by improving the program, the `TODO.md` file contains a few ideas. But personally I think I will not go much further for the moment.

6 Likes

What you describe about adding clues back into a minimal puzzle is precisely what a solver does. Different solvers will take different paths, but all will arrive at the same, unique, solution.

BTW, the book of Fortran-generated puzzles that I referred to in an an earlier post

is also available in some countries through Amazon, for instance

Mike

2 Likes

Christian Terboven from RWTH Aachen uses a brute-force Sudoku solving algorithm as one of the examples in his lecture on OpenMP tasking. It would be nice to have the example in Fortran too.

2 Likes

I am not a Sudoku solver or setter myself but my late neighbour Richard Bird has written eloquently about using Haskell to solve Sudoku puzzles (https://www.cs.tufts.edu/~nr/cs257/archive/richard-bird/sudoku.pdf). Graham Hutton has followed this up with some code (https://www.cs.nott.ac.uk/~pszgmh/sudoku.lhs). This may inspire Fortranâ€™ersâ€¦ or not.

1 Like

One way of generating sudoku puzzles is to start off with a full grid and remove clues until the puzzle is minimal. Fifteen years ago I wrote the program below to generate random grids as an example of the use of recursion in Fortran. It generates a million 9x9 grids in 50s on my modest desktop. (For larger grids additional code is usually necessary, to detect deadlocks.) Solvers themselves are simple in principle but complicated in practice, and I donâ€™t have one that is really suitable for publication.

Mike

``````program grid
implicit none
integer, parameter              :: box = 3, size = box*box, size2 = size*size   !NEEDS ADDITIONAL CODE FOR box > 3
integer, dimension(size2)       :: sudoku
integer, dimension(size, size2) :: order
integer                         :: cell_index, j, k
logical                         :: complete
real                            :: t1, t2

call cpu_time(t1)
do k = 1, 100
complete = .false.
cell_index = 0
sudoku = 0
do j = 1, size2
order(:, j) = scatter(size)      !fill order with 9 candidates in each cell, in random order
end do
call cell
write(7, '(81i1)') sudoku
end do
call cpu_time(t2)
write(7, '(f7.1)' ) t2-t1

contains

recursive subroutine cell
integer :: ii
! Finds next valid value for this cell, and backs up one cell otherwise
cell_index = cell_index + 1
do ii = 1, size
if(.not.valid(order(ii, cell_index))) cycle
sudoku(cell_index) = order(ii, cell_index)
if(cell_index == size2) then
complete = .true.
return
else
call cell             !!! <--------------The recursive call
if(complete) return
end if
end do
sudoku(cell_index) = 0
cell_index = cell_index - 1
end subroutine cell

logical function valid(value)
integer, intent(in) :: value
integer             :: r_ind, c_ind, b_ind, bb, ncols
! Checks the row/column/box constaints
valid = .true.
r_ind = ((cell_index - 1)/size) * size
c_ind = cell_index - r_ind
ncols = mod(cell_index, size)
if(ncols == 0) ncols = size
if(any(sudoku(r_ind + 1 : r_ind + ncols - 1) == value)) then
valid = .false.
return
else if(any(sudoku(c_ind : c_ind + ((cell_index - 1)/size-1)*size : size) == value)) then
valid = .false.
return
else
b_ind = ((cell_index -1)/(size*box))*size*box + c_ind
b_ind =  ((b_ind - 1)/box)*box + 1
do bb = 0, box - 2
if(any(sudoku(b_ind + bb * size : b_ind + bb * size + box - 1) == value)) then
valid = .false.
return
end if
end do
end if
end function valid

function scatter(num)
integer, intent(in) :: num
integer             :: scatter(num), ii, index
real                :: numbers(num)
! Array-valued function that returns the integer values 1 to num in random order
call random_number(numbers)
do ii = 1, num
index = minloc(numbers, dim=1)
scatter(ii) = index
numbers(index) = 2.0
end do
end function scatter

end program grid

``````
2 Likes

Thanks to @fedebenelli a FORD documentation is now online:
https://vmagnin.github.io/ForSudoku/