The New Sudoku Players' Forum

[docjohn]

Greetings

I wrote a free solver/helper a few years ago called Jet Sudoku
Please feel free to download it here: http://manifestmaster.com/jetsudoku

I'm trying to update it to create new puzzles at random. This brings up
the issue of determining puzzle validity. As you know, a sudoku puzzle
is only valid if it is solvable and has only one solution.

One can prove that a puzzle is solvable by using traditional solving techniques,
but that does not prove that it cannot have more than one solution.

I had to come up with my own algorithm which I believe works but I'd like to
hear feedback from other programmers. Here's what Jet Sudoku does now:

Step 1: Solve the puzzle using brute force only, starting from r1c1 to r9c9
moving left to right.

Step 2: Solve the puzzle again using brute force only but starting from r9c9 to r1c1
moving right to left.

Compare the two solutions. If they're identical then I believe that the puzzle only
has one solution.

But I wonder if this is good enough.

I've considered using brute force two more times going down columns instead of across
rows, then doing it backwards.

I would appreciate any thoughts or feedback.

[JasonLion]

Normally you would use a brute force solver that enumerates all of the solutions, and have it abort when/if it finds a second solution. This is typically very easy to code. When you find a solution you note it, and then continue looking for other solutions as if it was not a solution.

The approach you describe can work. However, if it works all the time or only sometimes depends on the details of the solver design. If the brute force solver is straight-forward in it's operation it will generally work. But many brute force solvers have optimizations that override the ordering when they see a way to speed up the process which can cause the same solution to be found regardless of nominal search order.

[rjamil]

Hi John Musgrave and Jason,

I thought that there is one more brute force scenario to check puzzle uniqueness, i.e.:

Start filling empty cells from either straight-forward direction or some optimized way, fill each cell with digit from candidates in ascending order first and than fill each cell in descending order, i.e., from 1 to 9 and then from 9 to 1 digit order, and compare both the results. If both are same than its unique puzzle otherwise multi-solution puzzle.

In this way, I think, there is no more than 2 ways searching option.

R. Jamil

[Pat]

One can prove that a puzzle is solvable by using traditional solving techniques,
but that does not prove that it cannot have more than one solution.

which "traditional solving techniques" ?

as long as your solving techniques make no assumption re number of answers,
once they reach an answer -- it is the only the answer.

[rjamil]

Hi Pat,

One can prove that a puzzle is solvable by using traditional solving techniques,
but that does not prove that it cannot have more than one solution.

which "traditional solving techniques" ?

What I think is that John Musgrave is trying to say as follows:

One can prove that a puzzle is satisfactory puzzle,
but that does not prove that it is proper puzzle.

But he has rights to disagree with me and express the same in his own wordings.

R. Jamil

[StrmCkr]

One can prove that a puzzle is solvable by using traditional solving techniques,
but that does not prove that it cannot have more than one solution.

what pat was referring to is specific solving techniques: {not limited to this specifically as there is a lot of other:}
Unique Rectangles,

find eliminations based on the assumption the puzzle already is predetermined to have 1 solution as this style of techniques remove the possibility of it having multiple solutions as its elimination candidate.

if you never use uniqueness assumptions it is possible to have a generator build puzzles.

in fact this is how my generator worked until i rebuilt the foundations of my solving code and haven't re implemented it as the engine didn't translate to my new storage system.

a short over view:

1: generate a random cell, check that cell isn't already assigned else random a new cell.
1a: generate a random Clue check that the cell can use this random clue against its pencil marks
if no random a new clue until the cell can use it
notes: if the cell has 1 pencil mark left skip random and insert that clue
{ or you could also random a new position as well
(I recommend skipping all cells with 1 pencil mark let) }

1b: update pencil marks
1c: run solving technique perform eliminations

2: check grid state for illegal state {no solution = locations with no pencil marks or row,col,box lacking any Candidates or a Given for N }
2a if still valid grid state go to step 1,
else
delete last clue added, backtrack Pencil mark state to previous step.

3. repeat until a grid that can be solved by enclosed technique set is created.

the last step:

4. to minimize the puzzles clue count {skip if the grid is already @ 17 clues as no valid puzzle may have less}
delete random Clues added and see if your solving technique can still solve the puzzle, if so delete that clue and repeat.

it is a fun way to build grids when u want it to contain up to specific technique sets {harder/easier}

strmckr

[rjamil]

Hi StrmCkr,

I like the way how your program generate the puzzles.

But the question still remain. How you check the puzzle uniqueness if it is unsolvable by any/all techniques (I mean if solver has either limited techniques implemented or the puzzle is only solvable by trial and error method)?

R. Jamil

[StrmCkr]

There is no trial and error nor unsolvable grid produced via my described method.
as logic only removes invalid pencil marks, and the generator adds clues until the solving list can solve the puzzle in full thus making it unique.

My last working generator used this list. (this is not a fast generator by any means)

Naked, hidden singles
Box line reduction
Naked hidden pairs
Xwing
Naked hidden triple
Naked hidden quad

Xy wing
Xyz wing

2string kite
Finned sashimi x wing(skyscraper)
Empty rectangle
Basic Fish size 3-4
Wxyz wing
W, m, s, l, h - wingz
Xy chains
Als-xz rule.
Als-xy rule
NxM+k Fish

[rjamil]

Hi StrmCkr,

Thanks for your quick response.

However, you are talking about uniqueness of a puzzle that is generated by applying limited set of techniques/strategies.

In general, how your program check uniqueness of a puzzle that is generated by some other resources?

R. Jamil

[StrmCkr]

In general, how your program check uniqueness of a puzzle that is generated by some other resources?

R. Jamil

that's a different question out side the scope of my generator, as it doesn't worry about what some one else did, however


in general for some one else grids that are generated, I would use DLX {dancing links} as the fastest method to check for singular solution.

[m_b_metcalf]

2: check grid state for illegal state {no solution = locations with no pencil marks or row,col,box lacking any Candidates or a Given for N }

A third test for an illegal state is to test for a clash: whether any two candidate values appear only once each but in the same single cell in a r/c/b.

Regards,

Mike Metcalf

[rjamil]

Hi all,

This thread is become interesting for how to generate a puzzle.

I have one more question regarding the same.

While generating a puzzle, is it a way that will guaranteed to solve the generated puzzle with at least one or few strategies included along with other strategies as optional?

I mean, to generate a puzzle that will solve with at least one wxyz-wings type 4 move inclusive.

R. Jamil

[JasonLion]

The normal method is to generate a puzzle at random, then check to see if it has the property you want, repeating as many times as needed until you find one with the desired property.

There are easy ways to create puzzles that only require techniques from a given set of techniques. But there is no simple way to insure that puzzles actually require a specific technique.

[rjamil]

Hi,

Is it possible to generate a puzzle with required specific technique/techniques on each step first, if failed then generate with given set of techniques. If still failed then backtrack?

R. Jamil

[StrmCkr]

2: check grid state for illegal state {no solution = locations with no pencil marks or row,col,box lacking any Candidates or a Given for N }

A third test for an illegal state is to test for a clash: whether any two candidate values appear only once each but in the same single cell in a r/c/b.

Regards,

Mike Metcalf

thanks Mike, nice and directly the way you have it written out, ie multiple digit assignment to a single cell. forgotten about that crevit.

i have another rule i use as well but its mathematically complex as it involves checking pencil mark counts vr empty cells count, and quantifying that there isn't enough pm assignments to satisfy all empty cells.