Hi Xtian,
au contraire. The initial constraints do not add new constraints
but remove
existing ones. So instead of adding columns you remove rows (which
obviously
makes solution even faster rather than slower).
The rough plan is to (partly) emulate the DLX algorithm at APL
level.
Say you place digit D in row R and column C (which belongs to box
B = f(R, C) of
the 9×9 fields. That means that you should remove all lines of the
constraints
matrix where:
- any digit is placed on row R and column C, or
- D is placed in row R, or
- D is placed in
column C, or
- D is placed in box
B
Repeat that for all digits placed beforehand.
/// Jürgen
///
On 11/25/2016 03:50 AM, Christian
Robert wrote:
Juergen,
replacing all [2..9] by 1
seams to work is is *lightning* *fast*.
sortvn←{⍵[⍋⊃⍵]}
Display 9 9 ⍴ {⍵[1+⎕io]} ¨ sortvn { ⎕io + (⌊⍵÷9) (9|⍵) } ¨
⎕io-⍨ ⎕dlx z
┏━━━━┯━━━┯━━━━┳━━━━┯━━━┯━━━━┳━━━━┯━━━┯━━━━┓
┃ 1 │ 2 │ 3 ┃ 4 │ 5 │ 6 ┃ 7 │ 8 │ 9 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 7 │ 8 │ 9 ┃ 1 │ 2 │ 3 ┃ 4 │ 5 │ 6 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 4 │ 5 │ 6 ┃ 7 │ 8 │ 9 ┃ 1 │ 2 │ 3 ┃
┣━━━━┿━━━┿━━━━╋━━━━┿━━━┿━━━━╋━━━━┿━━━┿━━━━┫
┃ 3 │ 1 │ 2 ┃ 8 │ 4 │ 5 ┃ 9 │ 6 │ 7 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 6 │ 9 │ 7 ┃ 3 │ 1 │ 2 ┃ 8 │ 4 │ 5 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 8 │ 4 │ 5 ┃ 6 │ 9 │ 7 ┃ 3 │ 1 │ 2 ┃
┣━━━━┿━━━┿━━━━╋━━━━┿━━━┿━━━━╋━━━━┿━━━┿━━━━┫
┃ 2 │ 3 │ 1 ┃ 5 │ 7 │ 4 ┃ 6 │ 9 │ 8 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 9 │ 6 │ 8 ┃ 2 │ 3 │ 1 ┃ 5 │ 7 │ 4 ┃
┠────┼───┼────╂────┼───┼────╂────┼───┼────┨
┃ 5 │ 7 │ 4 ┃ 9 │ 6 │ 8 ┃ 2 │ 3 │ 1 ┃
┗━━━━┷━━━┷━━━━┻━━━━┷━━━┷━━━━┻━━━━┷━━━┷━━━━┛
Now, I have to figure-out how to setup the initial constraints
with some predetermined values. eg, dynamically building the "z"
matrix I suppose.
Can I just append a new set of constraints at the right side of
the "z" matrix ? (a 729x81 )
thanks,
Xtian.
On 2016-11-24 06:56, Juergen Sauermann wrote:
Hi Xtian,
the constraint matrix *B* for *⎕DLX B* should contain 0 1 or 2
(either
as numbers or as characters (blank is also allowed and means 0)
If the matrix contains other numbers or characters than you get
a DOMAIN ERROR.
Referring to Knuth's original paper, 1 stands for a primary
constraint while 2 stands
for a secondary constraint. A mix of 1 and 2 in the same column
is not allowed.
As far as I can see, in the sudoku case all constraints are
primary, so z should contain
only 0s and 1s.
I also believe that the number of rows (729 == 9×9×9) stated in
one of your links is correct,
but the number of columns (9×9×4=324) is maybe not. I would
suppose that it is 9×(9+9+9+2)=171
for 9 digits×(9 rows + 9 columns + 9 boxes + 2 main diagonals).
If you have a matrix *z* with numbers indicating the digits for
the different constraints (which is
easier to troubleshoot than a pure 0/1 matrix) , then instead of
*⎕DLX z* you can probably
simply use *⎕DLX ∼z∈0 '0 '*to avoid the DOMAIN ERROR. This
works, of course,
only if there are no secondary constraints involved, like for
sudokus.
/// Jürgen
|