This is a small draft, I will write more after studying enough mathematics and understanding
the nature of my picture current limitations

Note: Perhaps this post will grow into some kind of summarizing of my current Discrete Mathematics
view, which will be interesting to compare with Calculus and its derivatives, such as
differential equations, essential for Science, when I will study those things.

  1. Some basic Discrete Mathematics foundations:
    • sets (and derived concepts – relations, mappings (including functions), Dequart products
    • mathematical logic
    • combinatorics
    • graphs
    • languages (as subsets of sets of all character sequences based on characters from alphabet)
    • finite automata
    • fundamental Calculators: Turing machine, Lambda calculus, etc. Their equivalence.
  2. Latin rectangles:
    • existence
    • count for different sizes, no generic formula (!), (1,n), (2,n) – Euler etc., (3,n)
    • relations to other fields
  3. Latin squares, a specific kind of 2

  4. Sudoku, a specific kind of 3

  5. Transformations:
    • not changing basic nature (~10 types)
    • beyond that
  6. Sudoku programming for any size:
    • generation of map
    • transformation (see 5)
    • making map for game, algorithms to choose blank places
    • other things
  7. Separate (reverse side) – solver programming

  8. Greko-Latin squares and their programming, Euler hypothesis

  9. Group Theory roots

  10. Lisp and regexes (?)

Basically, I read great “Quant” (scientific journal for high scholars) materials on Latin
rectangles and obtained a desire to investigate the topic further, as well as
decently implement sudoku (and also Greko-Latin squares and different stuff like that).

I wanted to cover some amount of theory, and then the program architecture and algorithms.
Basically, it is simple and relatively primitive:

  • providing one map for initial sudoku, firstly transferring it to the C-state (“consistent”
    state where all Sudoku rules are satisfied)
  • then it has a sequence of transfers between C-states, during each of which program knows that
    it moves from one consistent state to another. There is no overhead and no O(n!).
  • perhaps, because of this, the amount of matrixes which can be obtained with a finite sequence
    of transformations from the given matrix is quite limited
  • another part of the program (actually, it can be implemented being mixed with initial
    transferring part) prepares the playing board by calculating empty spaces (here we have two
    parts – one part determines which spaces can be the ones, and it is very stupid and based on
    simple randomizer, and the other one is the one which checks the possibility of finding the
    solution for the given position. Basically, in my case it is recursive and looks “parallel”,
    but this is only search parallelism, and not the one related to parallel assessing of
    position by complicated guessing, the algorithm of checking position eligibility to be
    cleared (such that the player can understand what had been there before it was cleared) is
    relatively simple and is internally based on sequential recursive checks for a single 0,
    which can be replaced unambiguously.
  • finally, the rest is mere engineering, no mathematical spirit – interface, calculating of
    user input etc. However, one thing here should be mentioned – the submitted map is directly (in
    virtual memory) compared with the initial map, and if there are any differences, the user is
    not considered as a winner, otherwise he is. However, it can be simply updated to checking of
    the proposed map without adding of additional overhead.

There is a problem, however, that all such games are nothing more than miserable part of deep
fundamental mathematical concepts, and the ones of Group Theory related to such games are not
familiar to me – although I will remedy this.
The prospective versions of the program should include Greko-Latin square handling,
sophisticated guessing and, the most important, other, more “mathematical” map generation patterns.

screenshotSome kind of crappy input while launching the
program in shell, usage string is shown

screenshotSimple sudoku for 4 elements (length and
element set size)

screenshotClassical sudoku for 9 elements (length and
element set size)

screenshotSudoku for 16 elements (length and element set