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:


One possible format (for the standard 9x9case) is:
3
.94...13..............76..2.8..1.....32.........2...6.....5.4.......8..7..63.4..8

Alternatively, a more humanreadable format is:
3
.94...13.
.........
....76..2
.8..1....
.32......
...2...6.
....5.4..
.....8..7
..63.4..8

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:

Obviously numbers are involved, so their syntax must be specified.

Then the syntax of the separation must be specified (spaces, commas (dots??); what about endoflines?).

Finally, for such simple file formats, the order and semantics of entries is to be specified.

Likely XML is more approriate; a DTDspecification should be fully sufficient here, and tagnames can be (very) short.

Perhaps there are two formats: A "professional" XML format, and a "quickanddirty" text format.
 Todo:
 Complete implementation of OKlib::LatinSquares::SudokuProblem

An update of the following is needed, especially with regard to the works at Maximalevel.

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 clausesets are

Inj(rows): For all i in I_2: INJ({v_{i,j} : j in I_2}).

Inj(columns): For all j in I_2: INJ({v_{i,j} : i in I_2}).

Inj(boxes): For all i, j in I_1: INJ( { v_{(i,k), (k',j)} : k, k' in I_1 } ).

Additionally a list of domainrestrictions 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 clausesets)?!
 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 Sudokusolvers.
 Todo:
 Visualisation of the runs of solvers

Boolean SATsolvers

We have the general possibilities of visualising the run of a SAT solver. See part Visualisation (especially GraphDrawing/plans/general.hpp).

Additionally, we should try to exploit the special geometrical structure.

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 lookahead solvers).

Solvers with variables with domains {1,...,p^2} (assuming that this represents also the splitting possibilities, i.e., the literals are monosigned)

Again we have the general possibilities from part Visualisation.

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.