OKlibrary  0.2.1.6
Sudoku.hpp File Reference

Plans for Maxima-generators related to Sudoku-like problems. More...

Go to the source code of this file.


Detailed Description

Plans for Maxima-generators related to Sudoku-like problems.

Todo:
Relations to other modules
Todo:
Implement the four mixed cases for the direct translation
Todo:
Further improve implementation
Todo:
Random Sudoku problems
  • For the creation of random Sudoku-problems the easiest approach seems to fix the number f of fixed fields, and then choose f random fields from the N^2 fields, and for each chosen field choose a random value from {1,...,N}. In other words, using the natural notion of (non-boolean) literals a random problem is just given by a random partial assignment with a fixed number of f variables.
    1. Such random Sudoku-problems should also undergo a phase transition (for fixed p and appropriate f) ?!
    2. Creation of the partial assignment (with non-boolean variables) simply as a random clause by the OKgenerator.
    3. For the analysis one can filter out partial assignments which are not r_k-consistent (so r_0-consistency just means that the partial assignment does not (directly) falsify a clause); no consistency check then would be "-1-consistency".
    4. To speed up the creation, filtering out of r_k-inconsistent partial assignments can be done already during the creation (without disturbing the probability distribution).
    5. However, even r_1-reduction for box-dimension 2 takes a long time in Maxima (90 s). Thus this filtering cannot be done in Maxima, but we need C++ components.
  • It seems however, that the most basic version should already exclude trivial inconsistencies:
    1. Thus best is likely to start with the list of all possible pairs [field, value].
    2. A random element is chosen, and this field together with the fields with the same value in the same line is removed.
    3. This process is repeated.
    4. This yields a different random process (fields with many values have a higher probability for being chosen), but this process is also natural.
Todo:
Enumerating all solutions
  • Likely this should go to a submodule of module CombinatorialMatrices/Lisp/LatinSquares.
  • Apparently for box-dimension 2 we have 288 solutions; this should be computed and made available.
  • There are 576 many latin squares of order 4; given that they are derived from just 4 reduced latin squares of order 4, it should be easy to make them available, and then to filter out the sudokus amongst them.
Todo:
Sampling of all solutions
  • Likely this should go to a submodule of module CombinatorialMatrices/Lisp/LatinSquares.
  • A solution is just a total assignment (fulfilling the Sudoku-constraints.
  • See Satisfiability/Enumeration/plans/general.hpp.
  • A natural approach seems to be to create random instances, remove the unsatisfiable ones, and pick a solution.
    1. Just picking the first solution might lead to a bias?
    2. So we could try to pick the second, third, ... solution.
    3. Perfectly, we would enumerate all solutions and pick one at random. But this is likely infeasible in most cases.
    4. But sampling the solution space of a problem instance might be more feasible.
    5. Of course, one could apply this approach just to the problem given by the empty partial assignment, and obtain in this way all solutions.
    6. However it might be worthwhile to first restrict the solution space.
  • Another approach just uses "random self-reduction":
    1. Start with the empty partial assignment.
    2. Create the list of all pairs (empty field)/values.
    3. Remove the obviously unsatisfiable extensions by one such pair.
    4. Choose a random pair from the list, and check whether this extension is still satisfiable; if not, remove from the list, and choose another pair (as long as the list is not empty, there must exist a satisfiable extension).
    5. Repeat until a full solution is obtained.
    6. The question is whether this process yields perfect sampling of all solutions? One should check this for box-dimension 2.
    7. This process is similar to the second process above for creating random Sudoku problems, only that above no satisfiability-cheque is performed.
Todo:
Sampling of minimally uniquely satisfiable problems
  • Here the task is to sample (count, enumerate etc.) all Sudoku problems which are minimally uniquely satisfiable (they are uniquely satisfiable, and removing any assignment creates further solutions).
  • So "minimal" here is related to the partial assignment (and not to the problem instance).
  • See http://magictour.free.fr/suexco.txt, where the generator "suexg" is described (also copied into this directory).
  • Regarding *minimum* uniquely satisfiable problems, that is, where the partial assignment has minimum size, the conjecture is that this size is 17; all known non-isomorphic cases are made available by Gordon Royle at http://units.maths.uwa.edu.au/~gordon/sudokumin.php .
  • The natural approach is to create a random solution (see "Sampling of all solutions" above), which is trivially uniquely satisfiable and then randomly remove assignments (i.e., literals) which can be removed without creating further solutions, until we obtain a minimally uniquely satisfiable problem.
    1. DONE (see minUNISAT in Satisfiability/Lisp/Generators/plans/PlantedSolutions.hpp) We should create a general procedure, which starts with some unique solution phi (could be a partial assignment in general), and then picks variables by some heuristics and removes them from phi.
    2. Using the boolean literals, in general we get a "fractured Sudoku instance", where fields have forbidden values.
    3. But if we use just a positive partial assignment, which only states the occupied fields (not the other forbidden values, which follow by UCP), then actually we get standard Sudoku problems, and don't need to use negatively monosigned literals.
    4. For Sudoku it should be most natural to start with some given total solution (represented by a partial assignment containing only positive literals).
    5. Interesting questions here are what heuristics to use for removing a variable (if there are several choices), and whether the solution we start with makes a difference.
    6. The first objective could be to use the OKsolver-2002, and to first maximise the number of nodes in the tree, second the number of 2-reductions.
    7. There should be instances which are not completely decided by 2-reduction; but we can also try maximise the number of 2-reductions for those instances decided by 2-reduction (where the OKsolver-2002 only needs one node).
    8. For specification purposes the Maxima functions are fine (of course), but they will be too slow, so that later a little C++ program is needed.
  • Is the discussion and implementation of a Sudoku generator at http://skas-blog.blogspot.com/2007/07/end-of-sudoku-road.html relevant for us?
    1. To me (OK) this looks rather amateurish; and, of course, completely ignored is the main perspective for us, that of generalised Sudoku as an NP-complete problem.
    2. In those discussions the "hardness" of a problem always plays a role; I think a good way to measure it is the least k such that r_k yields the solution (this only works for unique solutions; otherwise generalised reductions have to be used).
Todo:
Sudoku generator for the Minion constraint solver
  • This should be placed into a module for constraint satisfaction.
  • What is the meaning of "generator" here? Is this just a file-format, or, more meaningfully, do we first create a constraint-satisfaction-problem, using a suitable Maxima-representation of "constraints", and then output this in Minion-format?
  • Parameters: n (box size), N = n^2, M = N^2
  • Cells variables : {x_1,...,x_M}. dom(x_i) = {1,...,N} for i = 1...M. x_i = j means j is assigned to cell i.
  • Boxes are represented by vectors v_i (i = 1..N) of cell variables.
  • The Sudoku then consists of a single N x N matrix of cell variables.
  • Implementation:
    • Row constraints:
      alldifferent(row(m_0),i)
           
      for i = 1..N
    • Column constraints:
      alldifferent(col(m_0,i))
           
      for i = 1..N
    • Box constraints:
      alldifferent(v_i)
           
      for i = 1..N
  • Syntax: (what syntax?? the file-content?)
    sudoku_minion_format(boxsize, filename)
       

Definition in file Sudoku.hpp.