X

# Multi-dimensional Sudoku Puzzles Set to Get Tougher

by Trilok Kapur on  February 13, 2010 at 12:27 PM Lifestyle News   - G J E 4
According to some mathematicians, Sudoku fans may have to rack their brains harder as the game may soon get a lot tougher.

Dr Paul Newton and Stephen DeSalvo of the University of Southern California in Los Angeles have published their report on Sudoku matrices in the Proceedings of the Royal Society A.

"I think it will help develop multi-dimensional Sudoku puzzles, and answer questions about how to give the initial [clues] in order to create a hard, but still solvable Sudoku puzzle," ABC Science quoted Newton, as saying.

A Sudoku puzzle solution comprises of a 9 x 9 matrix of numbers from 1 to 9.

Each number should only appear once along any row and once down any column, as well as only once in each of the three 3 x 3 sub-blocks that make up the matrix.

There is believed to be about 1021 different matrices.

Newton and DeSalvo created a "representative sample" of about 10,000 matricies and compared them to randomly-generated matrices.

They discovered that Sudoku matrices are more random than randomly-generated arrays.

According to Newton, this is surprising since one would expect the more constraints you have on a matrix, the less random it will be.

But he points out that in a randomly generated square, you may end up with a matrix made up entirely of one number, which is something you could never get given Sudoku's rules.

Newton believes the findings could help both the puzzle makers and puzzle solvers.

He says: "I think it will give people a lot of insight into how to produce better algorithms for constructing Sudoku matricies and it will enable ultimately the very fast learning algorithms that solve Sudoku matrices."

A Sudoku puzzle maker must provide clues - numbers already in place - to help someone work out the solution.

The more the clues, the easier it is to solve the puzzle.

But if the clues are too few, there will be more than one solution.

Currently the minimum number of clues required to ensure a unique solution is understood to be 17.

However, Newton says it may be possible to use his findings to construct harder puzzles.

He says: "I think it could help push that number down."

The findings could also help in the development of Sudoku-solving computer algorithms, and 3D Sudoku, states Newton.

Australian mathematician Dr Marcel Jackson of Latrobe University in Melbourne says while the findings that Sudoku squares are more random than randomly-generated squares initially sound counter-intuitive, he agreed with Newton that it makes sense when you think more deeply.

Jackson says Sudoku are a form of "Latin square", which have a 300-year history in mathematics.

He says understanding these are useful in the coding of information to minimise the effect of errors in transmission.

He also agrees it might help in making harder puzzles.

However, mathematician Dr Ian Wanless of Monash University in Melbourne offers a word of caution.

He believes Newton and DeSalvo's counter-intuitive finding, that Sudoku matricies are more random than randomly-generated ones, is a "red flag".

It suggests that the method they used to generate the Sudoku matricies was wrong, says Wanless.

He says even if the method was right, studying a "representative sample" of Sudoku matricies won't help people make harder puzzles.

The puzzles with the smallest number of clues that still have a unique solution will be "outliers", says Wanless.

Source: ANI
TRI