latin square puzzles

Everything about Sudoku that doesn't fit in one of the other sections

latin square puzzles

Postby dukuso » Tue Sep 27, 2005 5:42 pm

just sudokus without the blocks.
Are they less interesting for the human solver ?

They are frequently used in math-research
and the rules are simpler, so I'd be interested
why/whether human puzzlers don't like them
as much as sudokus.
Posts: 479
Joined: 25 June 2005

Postby Pi » Tue Sep 27, 2005 5:52 pm

I asume that there is less logic required to solve them.

Sudoku's have an extra thing to think about, some variations on sudokus have colors as well, so that the squares that are the same color can only contain the numbers 1-9 once and only once as well.

I would be interested to see a latin square puzzle though.

No bdoubt the theory of latin squares is usefull when making computer programs about sudoku
Posts: 389
Joined: 27 May 2005

Postby dukuso » Tue Sep 27, 2005 6:01 pm

it's NP-complete, so there should be hard enough latin square puzzles.
The size can be any square, 9*9,10*10,...
not only 9*9,16*16,.. as with sudoku.

You can try them e.g. here
Posts: 479
Joined: 25 June 2005

Postby Pi » Tue Sep 27, 2005 6:44 pm

The site calls those sudoku's

I will try them some time
Posts: 389
Joined: 27 May 2005

Postby r.e.s. » Tue Sep 27, 2005 11:56 pm

Pi wrote:The site calls those sudoku's[...]

Right, he calls them Sudoku with "no boxes" -- it's a poor naming convention. Sudoku puzzles are special cases of Latin square puzzles, not vice versa.
Posts: 337
Joined: 31 August 2005

Postby tso » Wed Sep 28, 2005 3:23 am

Several people have created puzzles they have named "Latin Squares" in recent years, generally 6x6 squares with irregular shaped areas that serve the same purpose as boxes -- still three constraints.

Posts: 798
Joined: 22 June 2005

Postby dukuso » Wed Sep 28, 2005 5:07 am

is there some agreement that 3 constraints (or better 3*n)
is the optimum ?

Why not 2 or 4 ... ?
Crosswordpuzzles always have 2 constraints AFAIK.

These killer-sudokus have about 50 constraints, but no clues.
Normal sudokus have 27 constraints plus 25 clues
You could also add the pandiagonals for 36 constraints
or 45 with the blocks.

About 6*n seems to be about the maximum number
of constraints with n*n cells.
Posts: 479
Joined: 25 June 2005


Postby gfroyle » Wed Sep 28, 2005 6:19 am

A completed Sudoku grid is a 9-colouring of the 81-vertex Sudoko graph.

(That is, the vertices are the 81 cells, and there are edges between two vertices if and only if they are in the same row, column or block.)

A Sudoku puzzle specifies a partial colouring of the graph with the property that there is a unique completion of that partial colouring. The challenge is to deduce the colours of the remaining vertices from those given.

So, would it be fun (to anyone!) if we took an arbitrary graph and then asked you to complete a partial colouring in a unique way? And if not, then what is it about Sudoku that makes it more fun than other graphs.

I haven't thought this through fully, but there are a couple of things that seem to help make Sudoku useful in this way:

- firstly, the graph, and the colouring, are easy to visualize because it is defined geometrically (via the rows/cols/boxes) and humans are extremely good at abstraction from geometric information.

- secondly, I think the presence of lots of 9-cliques (each row, col, box) is important to make it fun. This is because each 9-clique MUST contain one of each colour. This gives two types of restriction - negative ones, where we can say that a cell CANNOT contain certain numbers, and positive ones where we deduce that a cell MUST contain (one of) certain numbers. The tension between this positive and negative information is what I think makes it more interesting than an arbitrary graph colouring problem (where we usually only have the negative information), and in fact is what makes the whole task a "logic" challenge rather than just an enumeration.

It might be fun to whip up some other graphs, and then to actually present them as puzzles and see if any of them are interesting or not..


Posts: 214
Joined: 21 June 2005

Postby tso » Thu Sep 29, 2005 5:12 pm

Optimum in what context?

I *enjoy* puzzles with 4 constraints -- but that's not very scientific.
Posts: 798
Joined: 22 June 2005

Return to General