Web Game Category - Base computer Heuristic Algorithm
Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same 9x9 playing board row or column or in any of the nine 3x3 subregions of the 9x9 playing board.
The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It became an international hit in 2005
Although the 9×9 grid with 3×3 regions is by far the most common, variations abound. Sample puzzles can be 4×4 grids with 2×2 regions; 5×5 grids with pentomino regions have been published under the name Logi-5; the World Puzzle Championship has featured a 6×6 grid with 2×3 regions and a 7×7 grid with six heptomino regions and a disjoint region. Larger grids are also possible. The Times offers a 12×12-grid Dodeka sudoku with 12 regions of 4×3 squares. Dell regularly publishes 16×16 Number Place Challenger puzzles (the 16×16 variant often uses 1 through G rather than the 0 through F used in hexadecimal). Nikoli offers 25×25 Sudoku the Giant behemoths. Sudoku-zilla, a 100x100-grid was published in print in 2010.
Another common variant is to add limits on the placement of numbers beyond the usual row, column, and box requirements. Often the limit takes the form of an extra "dimension"; the most common is to require the numbers in the main diagonals of the grid also to be unique. The aforementioned Number Place Challenger puzzles are all of this variant, as are the Sudoku X puzzles in the Daily Mail, which use 6×6 grids.
Example of a Killer Sudoku problem.
Solution to the example above.
The same example problem, as it would be printed in black an white.
Killer sudoku (also killer su doku, sumdoku, sum doku, addoku, or samunamupure) is a puzzle that combines elements of sudoku and kakuro. Despite the name, the simpler killer sudokus can be easier to solve than regular sudokus, depending on the solver's skill at mental arithmetic; the hardest ones, however, can take hours to crack.
Why another tutorial? Because you don't really need to know many tricks. I
show this using a relatively hard puzzle by Wayne Gould, who creates
puzzles
for "The Times" of London. These are rated in difficulty from mild (the
simplest) to fiendish (the one on the left). Gould claims that none of his puzzles ever need trial and
error solutions. If you follow this example through you will find that you never
really need very complicated tricks either. Another way of solving this very puzzle
is given by Roger Walker in one of his tutorials. Our methods differ: I try to
illustrate some often-used tricks in this example.
"When you have eliminated the impossible whatever remains, however
improbable, is the truth", said Sherlock Holmes. This is the principle
by which we put the 3 in the top row. 1, 2 and 7 are eliminated by the
clues in the row; 4, 5, 6 and 9 by those in the column, and 8 by the cell.
This leaves the truth. I don't see it as very improbable; but one must
give the master some poetic license. This rule may or may not be useful to
begin things off, but it is indispensible in the end game (especially when
it is coupled with the hidden loner rule of Step 8).
Let's see how to place a 4 in the bottom right cell. The blue lines show that it must
go right into the bottom-most row, because the other two rows already have a 4 in them.
These are the slices. Now one of the three squares in the bottom row of the cell already
has a clue in it. The other square is eliminated by dicing. The green line shows that
the middle column is ruled out, because it already contains a 4 in another cell. So we
have finished the second move in a fiendish puzzle and found out what slicing and dicing
is.
We can place two more 4s, shown in black in the picture on the left. This requires
slice and dice exactly as before. Another example: we can place a 1 by slice and dice as
shown in the picture on the right.
Angus Johnson has this to say about hidden pairs: "If two squares in a group contain
an identical pair of candidates and no other squares in that group contain those two
candidates, then other candidates in those two squares can be excluded safely." In
the example on the right, a 2 and a 3 cannot appear in the last column. So, in the
middle rightmost cell these two numbers can only appear in the two positions where
they are "pencilled in" in small blue font. Since these two numbers have to be in these two
squares, no other numbers can appear there.
We want to place an 8 in the bottom right cell. The last column can be sliced out by
the locked candidate rule. Other slicing and dicing is normal, leading to the placement
of the 8 as shown.
The first element of the bootstrap is to place 8s in the middle row of cells.
The picture on the left shows where the 8s must be placed in the middle left
cell. The picture on the right shows the placement in the central cell.
Next we extend the logic of the locked candidates. The 5th and 6th rows
must each have an 8: one of them has it in the middle left cell, and the other in the
central cell. Therefore the 8 in the middle right cell cannot be in either of these
rows. From what we knew before, the 8 must be in the top right corner square of the
cell, as shown in the picture on the right. This is almost magical. Putting together
imprecise information in three different cells, we have reached precise information
in one of the cells.
And now the final step of the bootstrap is shown in the picture on
the left. The placement of the 8 dictates that the 6 must be just
below it, and therefore the 7 in the remaining
square. The diabolical magic is complete: reason enough for this
to be classified as a fiendish puzzle. One of Roger Walker's tutorials
is a solution of precisely this puzzle, by a different route. But before
going there, I invite you to try your hand at completing the solution
which we have started upon here.
The worst is over. We are now truly into the end game. First complete cell C entirely
by the "loner" trick: filling 6, 5, 3 and 7 in that order. Next complete
the cell F. Then finish the 7th column, place the 5 in the cell D, and complete that
row, in order to get the picture on the left. We are more than half done. From now
on common sense prevails: fill things in one by one. Don't panic, there are no
sharks circling the boat. No swordfish either.
The last rule, I promise. And it is hardly one, although you could call it the
"hidden loner" rule. The only reason one should give it a name is
that it fixes this very useful method in one's mind. So here is the example:
In the 6th row there's more than one choice in each square. However there is only
one place where the 5 can go (it is excluded from the squares with X's in them).
So there is a loner hidden in this row: hence the name. I stop here, but you
can go on to solve a fiendish puzzle by the simplest tricks exclusively.
Mike Godfrey wrote to me to point out a much simpler way of solving this
particular puzzle. After step 3, as before, one can fill in the 6 shown in
blue in the figure here, by noting that all other numbers can be eliminated
by requiring that they do not appear in the same row, column or block. After
this the remaining puzzle can be solved by spotting singles.
Mike writes that this puzzle "is not too fiendish perhaps". Perhaps. But that opens up the question of how to rate puzzles. I haven't found much discussion of this aspect of the mathematics of Su Doku: partly because commercial Su Doku generators (by that I mean the humans behind the programs) are not exactly forthcoming about their methods, but also because the problem is not terribly well-defined. This is a wide open field of investigation.
The minimum Su Doku shown alongside (only 17 clues) requires only two tricks to
solve: identifying hidden loners and simple instances of locked candidates. The
key is to apply them over and over again: to each cell, row and column. The
application of constraints repeatedly in order to reduce the space of possibilities
is called constraint programming in computer science.
"Pencilling in" all possible values allowed in a square, and then
keeping the pencil marks updated is part of constraint programming.
This point has been made by many people, and explored systematically by
Helmut Simonis.
Many known hard problems are of a type called nondeterministic-polynomial. In this class, called NP, generating a solution of a problem of size M takes longer than any fixed power of M, but given a solution, it takes only time of order some fixed power of M to check it (ie, a polynomial in M). If enumeration were the only way of counting the number of Su Doku solutions, then this would be harder than NP. If someone tells me that the number of Su Doku solutions is 6670903752021072936960, I have no way to check this other than by counting, which I know to takes time larger than polynomial in M. At present there is no indication that the counting problem of Su Doku is as easy as NP.
One sure fire way of solving any Su Doku puzzle is to forget all these tricks and just blindly do a trial-and-error search, called a depth-first search in computer science. When programmed, even pretty sloppily, this can give a solution in a couple of seconds. If we use this method on M×M Super Doku, then the expected run time of this program on the trickiest puzzles (called worst-case in computer science) would grow faster than any fixed power of M, but (of course) it is guaranteed to solve the puzzle. If trial-and-error were the only algorithm to solve any Su Doku puzzle whatsoever, and one were able to show that the state space of a puzzle grows faster than a fixed power of M, then this would prove that Su Doku is an NP problem.
Helmut Simonis has results which might indicate that trial-and-error is never needed, and a small bag of tricks with hyper arc consistency always answers the Su Doku question. However, one needs to ask how many times the consistency check has to be applied to solve the worst-case problem, and how fast this grows with M, in order to decide whether constraint programming simplifies the solution.
....................................................... Like -- Join Us and Help
Us Searching for
How to Play Sudoku - Fast and Easy
1- ExplanationMeaning Sudoku 数独 sūdoku The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.
Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same 9x9 playing board row or column or in any of the nine 3x3 subregions of the 9x9 playing board.
The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It became an international hit in 2005
Although the 9×9 grid with 3×3 regions is by far the most common, variations abound. Sample puzzles can be 4×4 grids with 2×2 regions; 5×5 grids with pentomino regions have been published under the name Logi-5; the World Puzzle Championship has featured a 6×6 grid with 2×3 regions and a 7×7 grid with six heptomino regions and a disjoint region. Larger grids are also possible. The Times offers a 12×12-grid Dodeka sudoku with 12 regions of 4×3 squares. Dell regularly publishes 16×16 Number Place Challenger puzzles (the 16×16 variant often uses 1 through G rather than the 0 through F used in hexadecimal). Nikoli offers 25×25 Sudoku the Giant behemoths. Sudoku-zilla, a 100x100-grid was published in print in 2010.
Another common variant is to add limits on the placement of numbers beyond the usual row, column, and box requirements. Often the limit takes the form of an extra "dimension"; the most common is to require the numbers in the main diagonals of the grid also to be unique. The aforementioned Number Place Challenger puzzles are all of this variant, as are the Sudoku X puzzles in the Daily Mail, which use 6×6 grids.
Mini Sudoku
A variant named "Mini Sudoku" appears in the American newspaper USA Today and elsewhere, which is played on a 6×6 grid with 3×2 regions. The object is the same as standard Sudoku, but the puzzle only uses the numbers 1 through 6.Cross Sums Sudoku
Another variant is the combination of Sudoku with Kakuro on a 9 × 9 grid, called Cross Sums Sudoku, in which clues are given in terms of cross sums. The clues can also be given by cryptic alphametics in which each letter represents a single digit from 0 to 9. An excellent example is NUMBER+NUMBER=KAKURO which has a unique solution 186925+186925=373850. Another example is SUDOKU=IS*FUNNY whose solution is 426972=34*12558.Killer Sudoku
.
Killer sudoku (also killer su doku, sumdoku, sum doku, addoku, or samunamupure) is a puzzle that combines elements of sudoku and kakuro. Despite the name, the simpler killer sudokus can be easier to solve than regular sudokus, depending on the solver's skill at mental arithmetic; the hardest ones, however, can take hours to crack.
A Killer Sudoku puzzle
Solution for puzzle to the left
Hypersudoku puzzle
Solution numbers for puzzle to the left
A Wordoku puzzle
Solution in red for puzzle to the left
How to Fast win - My Two Trick
Step 1: Singletons: find the "loner"
Step 2: Basic "slice and dice"
Step 3: Applied "slice and dice"
Step 4: Simple "hidden pairs"
Step 5: "Locked candidates"
Angus Johnson again: "Sometimes a candidate within a cell is restricted to one row or column. Since one of these squares must contain that specific candidate, the candidate can safely be excluded from the remaining squares in that row or column outside of the cell." Since the hidden pair 2 and 3 prevent anything else from apearing in the first two columns of the middle rightmost cell, an 8 can only appear in the last column. Now we apply the locked candidates rule.
Step 6: Bootstrap by extending the logic of "locked candidates"
To get to the first step of the bootstrap from the last picture shown above, we need to slice and dice to place an 8 in the center bottom cell. You must be an expert at this method by now, so I leave that in your capable hands.
Step 7: The beginning of the end
Step 8: "Hidden loner": almost not worth naming
Not so fiendish?
Mike writes that this puzzle "is not too fiendish perhaps". Perhaps. But that opens up the question of how to rate puzzles. I haven't found much discussion of this aspect of the mathematics of Su Doku: partly because commercial Su Doku generators (by that I mean the humans behind the programs) are not exactly forthcoming about their methods, but also because the problem is not terribly well-defined. This is a wide open field of investigation.
From tricks to methods: the roots of mathematics
Constraint programming
Non-polynomial state space
This is where much of the counting appears. Before clues are entered into a M×M Su Doku puzzle, and the constraints are applied, there are MM2 states of the grid. This is larger than any fixed power of M (this is said to be faster than any polynomial in M). If depth-first enumeration were the only way of counting the number of possible Su Dokus, then this would imply that counting Su Doku is a hard problem. Application of constraints without clues is the counting problem of Su Doku. As clues are put in, and the constraints applied, the number of possible states reduces. The minimum problem is to find the minimum number of clues which reduces the allowed states to one. The maximum problem is analogous.Many known hard problems are of a type called nondeterministic-polynomial. In this class, called NP, generating a solution of a problem of size M takes longer than any fixed power of M, but given a solution, it takes only time of order some fixed power of M to check it (ie, a polynomial in M). If enumeration were the only way of counting the number of Su Doku solutions, then this would be harder than NP. If someone tells me that the number of Su Doku solutions is 6670903752021072936960, I have no way to check this other than by counting, which I know to takes time larger than polynomial in M. At present there is no indication that the counting problem of Su Doku is as easy as NP.
Trial-and-error: is Su Doku an NP complete problem?
The Su Doku problem is to check whether there is an unique solution to a given puzzle: the yes/no answer would usually, but not necessarily, produce the filling of the grid which we call a solution. It would be in NP if the time an algorithm takes to solve the M×M Su Doku problem grows faster than any fixed power of M. It is not known whether the Su Doku problem is in NP.One sure fire way of solving any Su Doku puzzle is to forget all these tricks and just blindly do a trial-and-error search, called a depth-first search in computer science. When programmed, even pretty sloppily, this can give a solution in a couple of seconds. If we use this method on M×M Super Doku, then the expected run time of this program on the trickiest puzzles (called worst-case in computer science) would grow faster than any fixed power of M, but (of course) it is guaranteed to solve the puzzle. If trial-and-error were the only algorithm to solve any Su Doku puzzle whatsoever, and one were able to show that the state space of a puzzle grows faster than a fixed power of M, then this would prove that Su Doku is an NP problem.
Helmut Simonis has results which might indicate that trial-and-error is never needed, and a small bag of tricks with hyper arc consistency always answers the Su Doku question. However, one needs to ask how many times the consistency check has to be applied to solve the worst-case problem, and how fast this grows with M, in order to decide whether constraint programming simplifies the solution.
The controversy over trial-and-error
From this formal point of view, one can see the debate raging currently on Michael Mepham's web site and other discussion boards on Su Doku as an argument between the search enthusiasts and the constraint programming wallahs: with Mepham slowly giving ground in his defence of search. But does the debate just boil down to choosing which algorithm to use? Yes, if the Su Doku problem is easy (ie, in P) and constraint programming solves it faster. However, if Su Doku is hard, then there is a little more to it.Backdoors: defining "satisfactory puzzles"
In many instances of NP complete problems, the average run time of programs can be substantially less than the worst-case. Gomes and Selman conjecture that this is due to the existence of "backdoors", ie, small sets of tricks which solve these average problems. Here human intuition (called heuristics in computer science) can help to identify the backdoors and often crack the nut faster than the sledge hammer of systematic algorithms. These I call "satisfactory puzzles". One of the open problems for Su Doku is to define precisely the nature of such backdoors, and the classes of problems which contain them.Zen and the art of gardening
We have introduced elsewhere a method of counting Su Dokus by a depth first enumeration of trees (called the garden of forking paths). It is clear that some of the branches of these trees are much longer than the average. As M grows, this imbalance also grows (polynomially, or faster?). This is one way of visualizing the difference between the average case (satisfactory puzzles) and the worst case (diabolical puzzles). My challenge is a gardening problem: how do you make the trees come out balanced and symmetric? It is like a Zen puzzle: if you solve it, then you reduce human intuition (heuristics) to an algorithm; even if it is impossible you gain insight by contemplating the problem........................................................ Like -- Join Us and Help
Us Searching for
No comments:
Post a Comment