OKlibrary  0.2.1.6
Sudoku.hpp File Reference

Plans for the Sudoku components. More...

Go to the source code of this file.


Detailed Description

Plans for the Sudoku components.

Todo:
Relations
Todo:
Input file format:
    1. One possible format (for the standard 9x9-case) is:
      3
      .94...13..............76..2.8..1.....32.........2...6.....5.4.......8..7..63.4..8
          
    2. Alternatively, a more human-readable format is:
      3
      .94...13.
      .........
      ....76..2
      .8..1....
      .32......
      ...2...6.
      ....5.4..
      .....8..7
      ..63.4..8
           
    3. In both cases the first line gives the box size.
  • OK: I do not understand the meaning of the above. One also needs to be more precise:
    1. Obviously numbers are involved, so their syntax must be specified.
    2. Then the syntax of the separation must be specified (spaces, commas (dots??); what about end-of-lines?).
    3. Finally, for such simple file formats, the order and semantics of entries is to be specified.
  • Likely XML is more approriate; a DTD-specification should be fully sufficient here, and tag-names can be (very) short.
  • Perhaps there are two formats: A "professional" XML format, and a "quick-and-dirty" text format.
Todo:
Complete implementation of OKlib::LatinSquares::SudokuProblem
  • An update of the following is needed, especially with regard to the works at Maxima-level.
  • Compare the handling of coordinates with ComputerAlgebra/Satisfiability/Lisp/ClauseSets/Generators.mac.
  • Given n in N, let I_1 := {1, ..., n} and I_2 := I_1^2, I_2' := {1,...,n^2}.
  • Variables are v_{i,j} for i, j in I_2 with domains D(v) = I_2'.
  • The active clause-sets are
    1. Inj(rows): For all i in I_2: INJ({v_{i,j} : j in I_2}).
    2. Inj(columns): For all j in I_2: INJ({v_{i,j} : i in I_2}).
    3. Inj(boxes): For all i, j in I_1: INJ( { v_{(i,k), (k',j)} : k, k' in I_1 } ).
  • Additionally a list of domain-restrictions can be specified.
  • In terms of latin squares we can express Inj(rows)+Inj(columns) as LS((v_ij)_ij).
  • Are all constraints stored together? Perhaps better we use the natural grouping into 3 groups?
  • Use the concepts of literals (what about entry_type?).
  • Compare with SATAlgorithms/plans/GenericBacktracking.hpp and with Concepts/plans/ClauseSets.hpp for the concept discussion.
Todo:
Complete implementation of OKlib::LatinSquares::Trivial_reduction_Sudoku
  • Likely this should be just a generic algorithm, applicable to any collection of constraints (active clause-sets)?!
Todo:
Test OKlib::LatinSquares::SudokuProblem
Todo:
Test OKlib::LatinSquares::Trivial_reduction_Sudoku
Todo:
Strong hypergraph colouring
  • It seems that everything we are doing can be done at the more general level of strong hypergraph colouring (see "Strong hypergraph colouring" in LatinSquares/plans/general.hpp).
  • So it seems sensible to generalise everything, and then to derive the Sudoku components by just instantiating the hypergraph colouring problem (using 3 N^2 hyperedges). Is there anything special for the Sudoku problem?
Todo:
Another representation of Sudoku uses one Latin square plus N*N bijectivity constraints (for the boxes).
Todo:
As a prototype, implement Sudoku-solvers.
Todo:
Visualisation of the runs of solvers
  • Boolean SAT-solvers
    1. We have the general possibilities of visualising the run of a SAT solver. See part Visualisation (especially GraphDrawing/plans/general.hpp).
    2. Additionally, we should try to exploit the special geometrical structure.
    3. One could visualise the current partial assignment for a node (online):
      • One could represent the p^6 variables by a p^3 x p^3 board.
      • A variable, of course, can be unassigned, 0 or 1.
      • And it can be a decision variable on the first branch, on the second branch, or inferred (this for look-ahead solvers).
  • Solvers with variables with domains {1,...,p^2} (assuming that this represents also the splitting possibilities, i.e., the literals are monosigned)
    1. Again we have the general possibilities from part Visualisation.
    2. Again representing the partial assignments, one could use a more condensed representation "unassigned vs. assigned" plus the above distinctions regarding decision variables and inferred variables.

Definition in file Sudoku.hpp.