What this forum is for

Programs which generate, solve, and analyze Sudoku puzzles

What this forum is for

Postby Pappocom » Sun Mar 06, 2005 7:47 pm

If you have created a program or a tool to assist solvers (at least, those solvers who want assistance!), post a notice in this forum about the program or tool. Please include details of where the program may be downloaded from, or include details of how the tool can be implemented.

Please note that Puzzles by Pappocom has no connection with any of the suppliers who post to this forum. None of the programs or tools is endorsed by Pappocom.

Note also that Pappocom's own Sudoku program can be used as a Solver. You can enter the clues using point-and-click and solve the puzzle, or ask to see the solution.

Please note that this is a forum for Solver Programs, not Generator Programs.

- Wayne Gould (Pappocom)
Pappocom
 
Posts: 599
Joined: 05 March 2005

Re: What this forum is for

Postby Philip Roe » Tue Oct 25, 2005 12:01 pm

Pappocom wrote:If you have created a program or a tool to assist solvers (at least, those solvers who want assistance!), post a notice in this forum about the program or tool. Please include details of where the program may be downloaded from, or include details of how the tool can be implemented.

Please note that Puzzles by Pappocom has no connection with any of the suppliers who post to this forum. None of the programs or tools is endorsed by Pappocom.

Note also that Pappocom's own Sudoku program can be used as a Solver. You can enter the clues using point-and-click and solve the puzzle, or ask to see the solution.

Please note that this is a forum for Solver Programs, not Generator Programs.

- Wayne Gould (Pappocom)

That is a distinction without a difference. A program which can solve a valid sudoku in about x millseconds can be turned into a program which generates a new puzzle in about 3x milliseconds. Put a few digits into the grid at random. Let the solver loose on it and in x milliseconds it tells you one of three things: (a) this puzzle is invalid because it has no solutions (so you take away one of the digits and iterate) (b) this puzzle is invalid because it has more than one solution (of course you tell it to stop at two and in this case you must add a digit or two chosen from one of the solutions and again iterate) or (c) this puzzle is valid; it has just one solution and here it is. In the last case the program also gives you various estimates of the difficulty such as the time taken, whether the puzzle is simple in the sense of admitting a forced move at each stage or whether it requires an exploration of dead ends and the number of forced moves available at each point. The programming trick is to treat solutions as though they were dead ends. That way you explore the whole "tree" of each proposed puzzle except that for practical purposes you stop at two solutions. A nerdish possibilty is to remove the stop-at-two condition and set the solver loose on the blank grid. Of course the computer finds all N possible ways of filling the grid but it takes Nx milliseconds, which, for any reasonable x (e.g. 1) you are limited by the heat death of the universe.

Incidentallly N has been published but not, as far as I know, a proof that the published value is correct.
Philip Roe
 
Posts: 12
Joined: 24 October 2005

Re: What this forum is for

Postby Philip Roe » Tue Oct 25, 2005 12:09 pm

Philip Roe wrote:
Pappocom wrote:If you have created a program or a tool to assist solvers (at least, those solvers who want assistance!), post a notice in this forum about the program or tool. Please include details of where the program may be downloaded from, or include details of how the tool can be implemented.

Please note that Puzzles by Pappocom has no connection with any of the suppliers who post to this forum. None of the programs or tools is endorsed by Pappocom.

Note also that Pappocom's own Sudoku program can be used as a Solver. You can enter the clues using point-and-click and solve the puzzle, or ask to see the solution.

Please note that this is a forum for Solver Programs, not Generator Programs.

- Wayne Gould (Pappocom)

That is a distinction without a difference. A program which can solve a valid sudoku in about x millseconds can be turned into a program which generates a new puzzle in about 3x milliseconds. Put a few digits into the grid at random. Let the solver loose on it and in x milliseconds it tells you one of three things: (a) this puzzle is invalid because it has no solutions (so you take away one of the digits and iterate) (b) this puzzle is invalid because it has more than one solution (of course you tell it to stop at two and in this case you must add a digit or two chosen from one of the solutions and again iterate) or (c) this puzzle is valid; it has just one solution and here it is. In the last case the program also gives you various estimates of the difficulty such as the time taken, whether the puzzle is simple in the sense of admitting a forced move at each stage or whether it requires an exploration of dead ends and the number of forced moves available at each point. The programming trick is to treat solutions as though they were dead ends. That way you explore the whole "tree" of each proposed puzzle except that for practical purposes you stop at two solutions. A nerdish possibilty is to remove the stop-at-two condition and set the solver loose on the blank grid. Of course the computer finds all N possible ways of filling the grid but it takes Nx milliseconds, which, for any reasonable x (e.g. 1) you are limited by the heat death of the universe.

Incidentallly N has been published but not, as far as I know, a proof that the published value is correct.


My grammar is garbled: penultimate sentence "....,which, for any reasonable value...., is longer than the future of the universe" or "......, but, far any reasonable value..., you are limited by the heat death...."
Philip Roe
 
Posts: 12
Joined: 24 October 2005

Postby PaulIQ164 » Tue Oct 25, 2005 3:18 pm

Undoubtedly it is true that any solver program can fairly easily be modified to create puzzles (and the quality of the generator is defined by the quality of the solver). But in reality there's more difference than that, in that solver programs are less likely to give you features such as timers for your solving, graded difficulties, and most importantly, solver programs won't undercut the market of Pappocom, who host this forum advert-free and at no cost to us as users.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Philip Roe » Fri Nov 04, 2005 6:50 pm

PaulIQ164 wrote:Undoubtedly it is true that any solver program can fairly easily be modified to create puzzles (and the quality of the generator is defined by the quality of the solver). But in reality there's more difference than that, in that solver programs are less likely to give you features such as timers for your solving, graded difficulties, and most importantly, solver programs won't undercut the market of Pappocom, who host this forum advert-free and at no cost to us as users.

In the course of a puzzle we can usually find at least one move which has not been made yet but which must be made: a vacant square which can accommodate one and only one symbol or a row, column or block, one and only one of whose vacant squares can accommodate a certain symbol. The human solver finds one such move, makes it and looks for another. The machine solver finds all such moves and may as well count them. If the count remains high until the grid is nearly full the puzzle is easy because it is is easy for the human solver to find one such move if there are several. If the count drops to one or two while the grid is still sparsely populated the puzzle is difficult and Pappocom call it "fiendish". If the count is always positive we always know what to do and the puzzle is simple no matter how difficult it is. I wonder if there is a maximum difficulty simple puzzle, one whose count is always exactly one.

If the count drops to zero we are out of Pappocom territory and the puzzle is no longer simple so we might call it complex. The most we can say is (for instance) the 6 in row 3 must go in one of two squares, the 5 in column 6 into one of three....etc.; we grasp one of these forks and follow each of its prongs. Each prong leads (possibly via more forks) to a solution or to a dead end. It is easy to see that any fork will lead to all the solutions even though different forks lead to different collections of dead ends. By treating solutions and dead ends on the same footing we get all the solutions. If the puzzle is valid and so has just one solution we get a proof that this is so. If we want to know how complex a complex puzzle is we have a little more work to do: it is not quite enough to count dead ends; strictly we should try the effect of grasping different forks. Maybe the two placings of the 6 in row 3 both lead to further forks, giving one solution (and a proof of validity) and three dead ends while the three placings of the five all lead to simple situations, one soluble, two not, giving the unique solution with just two dead ends. A solver will always tell us whether a proposed puzzle is valid or not and, at no extra charge, whether it is simple or complex and, at almost no extra charge, whether it is easy or difficult.

A human solver working against the clock will sometimes treat a simple difficult puzzle as a complex one. This is what Vorderman did with both her published attempts at #89 from Wayne Gould's first book. You gallantly leap to her defence. I ungallantly maintain that a tournament chess player who failed to spot a mate in three in the middle game, went on to win the end-game and wrote it up for a column would present it as a blunder, not a triumph. The diagram would show the position where the mate was missed and the problem for the reader would be to do better at leisure than the writer did in the tournament.

I do not understand the comment about undercutting markets. I do not know who composes the puzzles published in books other than Wayne Gould's and newspapers other the The Times; it could be Pappocom or it could be a rival. If there are rivals out there let them undercut each other: that is what a market is.
Philip Roe
 
Posts: 12
Joined: 24 October 2005

Postby spiralmile » Sat Dec 03, 2005 3:43 am

Interesting.

It seems to me that a 'fiendish' puzzle published by Pappocom is one that can be 'just about' solved within the duration of a train commute to work.

That's perhaps anywhere between 20 to 90 minutes.

Now, if you analyse one of these puzzles in relation to the rules required to solve them, they are actually quite simple. They very rarely feature any hidden subsets, triples, quads, xw/sf etc.

The most they require is candidate pencilling to determine isolated single candidates.

[edited by Pappocom]
spiralmile
 
Posts: 2
Joined: 02 December 2005

Re: What this forum is for

Postby JasonLion-Admin » Thu May 27, 2010 1:31 pm

The definition of this forum has changed. These posts have been preserved for their historical interest.
User avatar
JasonLion-Admin
Site Admin
Site Admin
 
Posts: 72
Joined: 17 April 2010
Location: Silver Spring, MD, USA


Return to Software