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
Voici la grille résolue (validité vérifiée) :
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
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
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
**************************** MENU **********************************
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.
Type your choice and 'Enter':
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