The New Sudoku Players' Forum

[civiliza]

Please excuse me barging straight in with a major request.

I have a long running C++ project that generates Sudoku Puzzles en-batch.

The basic methodology is to randomly permutate one from a set of complete solutions, then take away cells that can be deduced until no more cells can be removed.

Each deduction method has it's own rating, and at every stage, a random cell is picked from those with the highest deduction rating.

So far I have coded the following deduction methods:

1) Unnamed - Look for single cell values when possible row values are matched against possible column values against possible block values
2) Simple Counting (Reiterative) - Is there only one destination for a single value in a row/column/block, and/or one value for a single cell
3) Sub-Group Analysis - If all the destinations for a value are in a row/block subgroup, they can be excluded from the rest of the row and block etc
4) Twin Analysis - Naked and Hidden Twins where all the twinned values are possible in all the twinned cells
5) Cyclic Analysis - Naked and Hidden Twins where the twinned values are cycled through the twinned cells
6) X Wing Analysis
7) XY Wing Analysis
8) Swordfish Analysis

Note - Although I have only labelled 2) as reiterative, everything except 1) is reiterative, and gets called in a loop until no more changes are possible and/or the potentially removable cell has been identified as deducable.

Does anyone have any suggestions as to which deduction method I could add next?

[daj95376]

Does anyone have any suggestions as to which deduction method I could add next?

XYZ-Wing might help. As will ...

Code: Select all

 +-----------------------+
 | . . 5 | . 8 . | . . . |
 | . . 8 | 9 5 . | 4 2 . |
 | 9 3 . | . . . | 5 . . |
 |-------+-------+-------|
 | . 8 . | 4 . . | . 9 . |
 | 4 9 6 | . . . | . . 5 |
 | . 1 . | . . 2 | . 3 . |
 |-------+-------+-------|
 | . . 3 | . . . | . . . |
 | . 7 . | 3 . 4 | . . . |
 | . . . | . 1 . | . . . |
 +-----------------------+

 BUG+1: r7c5=6 to prevent a grid with only solved and bilocation candidates
 *--------------------------------------------------*
 | 2    4    5    | 7    8    3    | 9    1    6    |
 | 7    6    8    | 9    5    1    | 4    2    3    |
 | 9    3    1    | 2    4    6    | 5    78   78   |
 |----------------+----------------+----------------|
 | 3    8    2    | 4    67   5    | 67   9    1    |
 | 4    9    6    | 1    3    78   | 2    78   5    |
 | 5    1    7    | 68   9    2    | 68   3    4    |
 |----------------+----------------+----------------|
 | 16   5    3    | 68   27+6 89   | 17   4    29   |
 | 16   7    9    | 3    26   4    | 18   5    28   |
 | 8    2    4    | 5    1    79   | 3    6    79   |
 *--------------------------------------------------*


Code: Select all

 +-----------------------+
 | 7 . . | . . . | 5 . . |
 | . 4 5 | 8 . . | . . . |
 | . 1 3 | . 7 . | 6 4 . |
 |-------+-------+-------|
 | . 6 . | 1 8 . | . . . |
 | . . 1 | 7 2 . | . . . |
 | . . . | . . . | 7 . 4 |
 |-------+-------+-------|
 | 3 . 2 | . . 9 | 4 . . |
 | . . 6 | . . . | . 3 . |
 | . . . | . . 7 | . . 1 |
 +-----------------------+

 Unique Rectangle Type 1: r7c9=8 or deadly pattern for <57> in (*) cells
 *--------------------------------------------------*
 | 7    28   9    | 4    6    1    | 5    28   3    |
 | 6    4    5    | 8    39   23   | 1    279  279  |
 | 28   1    3    | 59   7    25   | 6    4    289  |
 |----------------+----------------+----------------|
 | 459  6    7    | 1    8    45   | 3    259  259  |
 | 459  39   1    | 7    2    345  | 8    59   6    |
 | 25   23   8    | 59   39   6    | 7    1    4    |
 |----------------+----------------+----------------|
 | 3   *57   2    | 6    1    9    | 4    578 *57+8 |
 | 1   *57   6    | 2    4    8    | 9    3   *57   |
 | 89   89   4    | 3    5    7    | 2    6    1    |
 *--------------------------------------------------*


[civiliza]

OK, I think I've got my head around the BUG+1 - All pairs or singles except the +1, and it forms a BUG if the +1 value wasn't there. That being the case, the +1 must be the correct value & is thus deducable.

It's making my brain ache at the moment (not up on the terminology of this site yet, & never even heard of a Sudoku BUG before now). That being the case, I'll work on the BUG+1 deducer for now, and look at your second suggestion when that's done. One brainache at a time.

Thank you for such a prompt and pertinant reply.

Civiliza

[daj95376]

OK, I think I've got my head around the BUG+1 - All pairs or singles except the +1, and it forms a BUG if the +1 value wasn't there. That being the case, the +1 must be the correct value & is thus deducable.

It's making my brain ache at the moment (not up on the terminology of this site yet, & never even heard of a Sudoku BUG before now). That being the case, I'll work on the BUG+1 deducer for now, and look at your second suggestion when that's done. One brainache at a time.

Thank you for such a prompt and pertinant reply.

Note: there are a few puzzles where "all pairs" is incorrect. The most accurate test is to make sure that removing the correct value would result in all remaining candidates to occur twice in the row/column/box containing the cell. This is the critical contradiction you need in order to place a value in the cell.

[civiliza]

I have spent the best part of two days hammering away at the BUG+1 Analysis, and I have found that it just won't work in the context of my program.

The method I use is to temporarily take away a candidate cell, then keep applying rules like XY Wing, Hidden Pair etc until there are no more rules that can be applied and/or the cell has been deduced. (To make things worse, I do this an extra step ahead to help steer the puzzle towards things like X-Wings or Swordfish).

Without BUG+1 Analysis, this always seems to produce a valid puzzle,

Oddities early in the BUG+1 development process lead me to add a check as to whether the BUG+1 Analysis identifies the correct plus value (it help when you already know what the answer should be!).

Now at some point in every puzzle, the analysis always falls foul of this check - sure enough at the point that it does, the puzzle is no longer valid. My guess is that the candidate cell at that point is not deducable, but without restructuring the whole methodology, I'll have to stay away from Unique type tests.

Oh well, at least it lead me to tighen up some of my other techniques.

While proving that non-BUG analysis always leads to valid solutions, I came up with a puzzle that achived my highest ever Sudoku Explainer rating of 4.2 (usually they rate between 2 and 3 with the lowest ever being 1.5):

Code: Select all

000705000
007680000
830001900
000007540
000000000
410050020
500000800
000023094
700000103


Might I comment that the lowest but 1 rated method of Hidden Single (rating 1.2) is something that I personally find hard to find (prefer the Claiming and Pointing methods in Sub-Group Analysis) and so it gets a higher preference in my program - typical.

[civiliza]

Had a rethink today about the nature of Uniqueness methods in general (and BUG+1 in particular).

They work on the assumption that the puzzle leads to a unique solution at the time the method is applied.

My code starts with an answer and finds a puzzle by temporarily taking away cells and seeing if they can be re-deduced. If so, they are permanently removed, otherwise they are replaced.

As such, it constantly hops between unique and non-unique states which was why the BUG+1 error trap was always being called.

Knowing, as it does, the "right" value that BUG+1 should deduce, the solution is not to avoid the error trap, but to use it as a Go/No Go indicator to apply the deduced +1 elimination en-route to re-deducing the temporarily removed cell.

[ronk]

As such, it constantly hops between unique and non-unique states which was why the BUG+1 error trap was always being called.

What? Are you using uniqueness techniques while determining whether your puzzle has a unique solution?

[civiliza]

As such, it constantly hops between unique and non-unique states which was why the BUG+1 error trap was always being called.

What? Are you using uniqueness techniques while determining whether your puzzle has a unique solution?

Not quite - I'm sort of reverse engineering a puzzle from a solution. I "feel" my way to the best puzzle by temporarily taking a cell away, then seeing if any combination of solving techniques is capable of putting it back again.

At each stage, I test each of the remaining cells as above, if none of the cells can be put back, I know that the puzzle is complete, otherwise I remove the cell that required the highest (arbitrary) rated technique to put it back then go on to the next stage.

The more techniques I can test against, the better (hopefully) the eventual puzzle.

My opening post in this thread asked for techniques, and until today, I've been wrestling with the suggested BUG+1 technique.

Here is the end result:

Code: Select all

000301400
005400003
010000900
586070000
300000100
700008000
000006001
090020060
000803040


[daj95376]

Not quite - I'm sort of reverse engineering a puzzle from a solution. I "feel" my way to the best puzzle by temporarily taking a cell away, then seeing if any combination of solving techniques is capable of putting it back again.

At each stage, I test each of the remaining cells as above, if none of the cells can be put back, I know that the puzzle is complete, otherwise I remove the cell that required the highest (arbitrary) rated technique to put it back then go on to the next stage.

This is very similar to the approach I took when I developed my first Sudoku solver and puzzle generator. I've since worked on a new solver, but I've not addressed a new puzzle generator.

I'll tell you now that I worked long and hard getting the puzzle generator to produce modest puzzles that I can share in another forum. There are two major obstacles: 1) having enough techniques, and 2) designing a reliable rating system for the intermediate puzzles. I'm short on (1) in my original solver, and (2) seems impossible.

As a side note, it doesn't sound like you have an embedded backtracking solver implemented to verify that a puzzle with a unique solution remains after you've removed a cell from the "givens". Without it, your testing for a solution will probably take longer and longer as you add techniques.

Regards, Danny

[civiliza]

As a side note, it doesn't sound like you have an embedded backtracking solver implemented to verify that a puzzle with a unique solution remains after you've removed a cell from the "givens". Without it, your testing for a solution will probably take longer and longer as you add techniques.

Regards, Danny

Sounds about right - while I was able to implement BUG+1 (since it was a whole puzzle method - either go or no-go), UR is proving impossible.

I've changed UR to a two run method - one run looks for any UR's that give invalid simplifications, and the second (alteration making) run only goes ahead if none exist. Trouble is that this go/no-go relies on a partial uniqueness test. Without knowing for sure the overall uniqueness state, methods that rely on it being unique are worse than useless.

I've still got a couple of more techniques to throw at the generator, fins, "blocky" fish (row or column vs block instead of the current row vs column), and the more modern three rows/columns of three swordfish (currently using only three columns/rows of two).

Beyond that, I think I'll have to put the generator on ice until I can work out a way to determine the overall uniqueness state of the puzzle at any given moment.

--

Having spent some time with the Sudoku Explainer, I am curious where some of my current/potential techniques fall. Of particular interest are my Cyclic Twins
(three values cycled through three pairs, four values cycled through either four pairs or four triplets) and finned fish. Also would eg a "blocky" xwing have the same rating as a more conventional one?

EDIT - Well, I've managed to find one answer, my Cyclic Twins are just degenerate versions of the standard twin - so Hidden Cyclic Triplets are just degenerate Hidden Triplets. Finned fish still seem to be alive, but many of you seem to be hunting the less evolved ones into extinction.

EDIT 2 - Forgive me all those who knew this all along, but after coding and trying out a "blocky" xwing algorithm, I have realised that the preconditions for a "blocky" xwing include a pointing/claiming set in the non-xwing block. That's another upgrade that's not required.

[civiliza]

For anyone who cares, I have finally managed to get the UR Type 1 analysis sorted.

I had one coding error that was applying changes to the wrong block, and one logic problem where I was allowing UR analysis on four block rectangles instead of the required two block rectangle.

After solving these, I was invariably producing puzzles with non-unique answers.

The final breakthrough was to add extra code to the "return false" breakouts used in both my BUG+1 and UR1 routines on detecting a non-unique state.

On detecting a non-unique state, I added code to clear a new global StillUnique variable. Future calls to either routine were then excluded if StillUnique was clear.

It turns out that while I was correctly using detected non-unique states to prevent a single BUG+1 or UR1 change, I was still performing uniqueness based techniques beyond the point where a non-unique state had been established.

Proof of the pudding:

Code: Select all

000030500
046007001
000104000
000000400
900002065
500098000
010020000
470300000
050700180


[BryanL]

hi civiliza,

daj mentioned a backtracking solver to test whether your puzzles have unique solutions.

I think everybody generating puzzles eventually realises that a backtracking solver is the best approach, and then once you know you have a valid puzzle, you can set about rating it.

For absolute speed the bit based solvers bb_sudoku, jsolve and fsss are the go. Dancing links is pretty quick but a bit of effort to get right. Otherwise a brute force backtracker is still reasonably quick and you could probably roll your own.

Also, some of the programs that people have made publicly available (like gsf's sudoku) will tell you if your puzzle is valid or not.

[civiliza]

Thanks for the reminder Bryani - I have an awful suspicion that you and daj are right. I just find the thought of starting on a backtracker too daunting.

Getting my Generator to it's current state of inefficiency has been the result of several years of incremental development (admittedly with long periods of inactivity). I can face bolting on new techniques providing I can get my head around them (most of this forum makes my head spin), but an entire backtracker sounds like too much work.

Standalone solvers are of little use since my Generator relies on hopping back and forth across the uniqueness boundary during generation to fine tune the final puzzle. (I am already using Sudoku Explainer as a standalone tester anyway) .

Like much of this forum I find Sudoku Explainer off-puttingly superior to my own attempts - not only in the number of methods recognised, but in it's ability to generate puzzles to a defined difficulty at a remarkable speed. The difficulty of my own puzzles is purely a matter of luck.

In trying to find bb_sudoku on this forum, I came across a thread in which daj posted that he had developed his backtracker from gsf's code (kudos daj) - this would seem to be the way ahead if I was to go down the backtracker path.

Truth be told with the recent additions of XY Wing, XYZ Wing, BUG+1 and UR Type 1 my generator is already creating puzzles I have difficulty solving without Sudoku Explainer.

For now I will limit my eforts to a parallel project that uses javascript and forms to access/run several sudokus offline after a single online connection using my new Kindle 3. All the offerings currently out there (including one remarkably capable downloadable javascript app pointed to from this site) are either mis-sized for the Kindle 3's screen, or unavailable in the UK (EA Sudoku). For the curious, I am using http://www.civiliza.webspace.virginmedia.com/SDKForm.htm as my current development area.

It is curious that the first puzzle has a glaringly obvious UR Type 1 despite said method not being implemented at the time the puzzle was generated. Maybe that is why Sudoku Explainer fails to identify it - although it is glaringly obvious to the eye, SE uses a Swordfish at that point in the solution process.

[BryanL]

Thanks for the reminder Bryani - I have an awful suspicion that you and daj are right. I just find the thought of starting on a backtracker too daunting.

Yeah i can understand, but like so many efforts, once you start getting your hands dirty, even after a few wrong paths and restarts, you will be able to see the way ahead and once finished will be that bit more confident in your abilities...

I will give you some pointers and links later...

It is curious that the first puzzle has a glaringly obvious UR Type 1 despite said method not being implemented at the time the puzzle was generated. Maybe that is why Sudoku Explainer fails to identify it - although it is glaringly obvious to the eye, SE uses a Swordfish at that point in the solution process.

That is because SE rates a swordfish below a UR.

You would not be alone if you wondered at SE's rating scheme, but i won't go there as it is the topic of (sensitive?) debate elsewhere...

[BryanL]

You will find plenty on bit based solvers and dancing links - dlx here

http://www.setbb.com/phpbb/?mforum=sudoku

Brute force back tracker pseudo code probably not the most elegant but it worked

Code: Select all

function brute force (grid)

tempgrid1 = grid  // copy of grid

do while not solved and candidate available

  solved = (tempgrid1 cell count = 81)

  if solved

    result = 1

  else

    get next candidate // systematically iterate over each cell and return first available candidate

    if candidate available

      tempgrid2 = tempgrid1 // copy of tempgrid1

      apply candidate to tempgrid1 cell and remove candidate from other peer cells

      tempgrid1 cell count ++

      if applied candidate leaves valid tempgrid1  // test every none given cell has at least one candidate

        bfresult = brute force (tempgrid1) // recursively call brute force function with new cell set

        if bfresult = 1 then

          grid = tempgrid1

          solved = true

          result = 1

        else if bfresult = 2

          remove candidate as a possible from grid

          tempgrid1 = grid

      else

        tempgrid1 = tempgrid2

        remove candidate as a possible from tempgrid1

    else

      result 2

return result