Interesting Article Ref: Sudoku and Linear Algebraic aspects

[WWGD]

Hi,
This looked interesting. Determinant and Linear-Algebraic aspects of Sudoku puzzles:
http://www.student.montefiore.ulg.ac.be/~merciadri/docs/papers/sudoku.pdf

 

[StoneTemplePython]

I didn't understand the field being used here.

In particular part 9 "Orthgonality Discussion", which says “ The answer to this question is not known yet" -- i.e. whether a sudoku matrix can be orthgonal.

If we have an inner product, then it is very easy to show that the squared frobenius norm of any Sudoku matrix is far to large for it to be orthgonal. (Why? its minimum entry value is 1 and there is a 1 in every column -- all columns also have some number bigger than 1...).

If we don't have an inner product or anything "close" then I really cringe when people use a term like "orthogonal".

 

[WWGD]

I didn't understand the field being used here.

In particular part 9 "Orthgonality Discussion", which says “ The answer to this question is not known yet" -- i.e. whether a sudoku matrix can be orthgonal.

If we have an inner product, then it is very easy to show that the squared frobenius norm of any Sudoku matrix is far to large for it to be orthgonal. (Why? its minimum entry value is 1 and there is a 1 in every column -- all columns also have some number bigger than 1...).

If we don't have an inner product or anything "close" then I really cringe when people use a term like "orthogonal".

I think he may be working within $l(\mathbb Z)$ or $l(\mathbb Z^{*} )$ (working mod45 , IIRC, since $45= \frac {n(n+1)}{2}$ ), though, I am not even sure Sudoku matrices are a subspace; origin not likely included. I was kind of lazy to just drop this here without checking the details before :(. Altho, given the fact that all entries are positive, there are no orthogonal elements in whichever subspace he chooses, by most defs. of inner product I can think of.

 

[StoneTemplePython]

Yea, as it happens my preferred way to solve sudokus is to use linear programming.

An observation I've had but kind of forgotten about, is everything that is sufficiently constrained to have one answer (i.e. the puzzles that make it to the general public), can be solved with the relaxation of using reals in your LP, as opposed to the integer domain it seems to require. I was poking around for something about totally unimodular submatrices or whatever.

- - - -

btw Theorem 12 has an issue --- in some forms of super sudoku there are constraints along the diagonal (and anti-diagonal) which would necessarily make the trace constant.

 

[WWGD]

Yea, as it happens my preferred way to solve sudokus is to use linear programming.

An observation I've had but kind of forgotten about, is everything that is sufficiently constrained to have one answer (i.e. the puzzles that make it to the general public), can be solved with the relaxation of using reals in your LP, as opposed to the integer domain it seems to require. I was poking around for something about totally unimodular submatrices or whatever.

- - - -

btw Theorem 12 has an issue --- in some forms of super sudoku there are constraints along the diagonal (and anti-diagonal) which would necessarily make the trace constant.

Just curious: I have found I can solve ( "paper and pencil", no strategy or explicit method) certain Sudokus well, but not so others. Do you think a classifier method may help me understand some traits in each group; the solvable and the non-solvable?

 

[StoneTemplePython]

To be clear, do you mean "solvable" by you, or actually valid problems with feasible solutions? If the former, I guess it could be kinda fun to pass it to a classifier. Typically the way I think about problems and "machines think" about problems ends up being a bit different though. (I think it would be kinda fun to overfit some massive deep net on a few sample puzzles and publish a bunch of nonsense about it afterward though.)

I guess it comes to how much Sudoku you do, and whether computational insights will take too much of the mystery out of it.

 

[WWGD]

To be clear, do you mean "solvable" by you, or actually valid problems with feasible solutions? If the former, I guess it could be kinda fun to pass it to a classifier. Typically the way I think about problems and "machines think" about problems ends up being a bit different though. (I think it would be kinda fun to overfit some massive deep net on a few sample puzzles and publish a bunch of nonsense about it afterward though.)

I guess it comes to how much Sudoku you do, and whether computational insights will take too much of the mystery out of it.

No, I mean solvable by me. And, while classifying may take away some of the fun/mistery away, I am interested more in learning ML methodology. I guess I would enter them as a 2D array.

 

[WWGD]

Kind of weird: Sudoku puzzles seen as matrices have a determinant that is a multiple of 405. This means the inverse of a Sudoku/Matrix , with a determinant of 1/405, does not represent a Sudoku. EDIT: Nonsense on my part: Only Integer matrices that are invertible are those with determinant
$\pm 1$