code to generate random sudoku puzzles

Programs which generate, solve, and analyze Sudoku puzzles

Re: code to generate random sudoku puzzles

Postby StrmCkr » Fri Dec 09, 2016 6:38 am

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. Jami


yes and no to a point, the problem is a "randomizer" often adds clues to a grid that remove the eliminations of a technique, or render it obsolete.

some programs like "hodoku" have a hidden function to generate a puzzle with the desired "technique set" but there is no guarantee if it will be usable at each step. even then it generates thousands of them and tests for the existence of that technique, and terminates when it finds one.

an old Form user RuuD used to generate grids that had exactly 1 hard technique "one trick poney" that unlocked a puzzle. but same thing generating hundreds of grids and confirm that technique exists in the puzzle before finding a grid with it.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 610
Joined: 05 September 2006

Re: code to generate random sudoku puzzles

Postby m_b_metcalf » Fri Dec 09, 2016 5:29 pm

StrmCkr wrote: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.

If I understand correctly, you mean, for example, that if a given row has 4 unfilled cells and the number of distinct values of the remaining PMs on the row is less than 4, then the grid is invalid. Correct?

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8214
Joined: 15 May 2006
Location: Berlin

Re: code to generate random sudoku puzzles

Postby StrmCkr » Sat Dec 10, 2016 7:09 am

Yes
And it covered the case you mentioned two digit assignments on 1 cell.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 610
Joined: 05 September 2006

Re: code to generate random sudoku puzzles

Postby m_b_metcalf » Sat Dec 10, 2016 4:23 pm

StrmCkr wrote:Yes
And it covered the case you mentioned two digit assignments on 1 cell.

Fine. But where is the 'mathematical complexity'? This code, for rows:
Code: Select all
      do row = 1, 9
          if(count(sudoku(row, :) == 0) > count(sum(pm(row, :, :), dim=1 ) /= 0)) then
             zero_solutions = .true.
             exit
          end if
      end do

is very short, and came up with this configuration straight away (5 distinct values for 6 empty cells in row 1, printed here transposed):
Code: Select all
  1  .  .  4  6  .  2  9  .
  .  .  4  1  9  .  .  .  .
  .  9  .  .  .  .  .  4  .
  .  7  .  5  .  .  .  1  .
  2  4  .  .  8  1  .  .  9
  .  .  .  .  .  9  .  .  .
  3  .  .  .  .  .  .  .  5
  .  .  6  8  .  4  .  .  .
  .  .  .  .  1  .  4  .  .
  in row 1 candidates are (by column across):
  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  5  5  .  .  5  .  5  5
  .  6  6  6  .  6  .  .  .
  .  7  7  .  .  .  .  7  7
  .  8  8  8  .  8  .  .  8
  .  .  .  9  .  .  .  9  9


Regards,

Mike Metcalf
Last edited by m_b_metcalf on Sun Dec 11, 2016 10:18 am, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8214
Joined: 15 May 2006
Location: Berlin

Re: code to generate random sudoku puzzles

Postby docjohn » Sun Dec 11, 2016 1:26 am

I don't know the definition of a 'satisfactory' or 'proper' puzzle. As I stated earlier, I am only familiar with what is
known as a valid puzzle in that it is solvable and has only one solution.

Regarding my 'traditional solving techniques' , my program uses these techniques so far: (in this order)

Singles: naked
Singles: hidden
Doubles: naked
Doubles: hidden
Triples: naked
Triples: hidden
Quads: naked
Quads: hidden
Locked candidates
X-Wing
XY-Wing
XYZ-Wing
W-Wing
Swordfish
Jellyfish
Squirmbag
Finned Fish (finned X-Wing)
Finned Swordfish
Finned Jellyfish
Skyscraper
2 String Kite
Turbot Fish
X-Loop
Empty Rectangle (or Hinge)
Colors (Conjugate Pair Coloring)
X-Chain
XY-Chain

I don't use uniqueness tests (BUG etc) when testing validity.

My program uses these to prove a puzzles validity (only one solution) quickly in the vast majority of cases. I have an algorithm that uses strictly brute force but it is much slower that the "traditional" techniques listed. Especially when using some of Tarek's killer puzzles. I like the idea of using brute force backwards (9-1 rather than r9c9 to r1c1) and am working on that.

Thanks for the replies. I'm still working on puzzle generation and your feedback is helpful.
docjohn
 
Posts: 13
Joined: 07 January 2011

Re: code to generate random sudoku puzzles

Postby StrmCkr » Sun Dec 11, 2016 5:17 am

m_b_metcalf wrote:Fine. But where is the 'mathematical complexity'? This code, for rows:
Code: Select all
      do row = 1, 9
          if(count(sudoku(row, :) == 0) > count(sum(pm(row, :, :), dim=1 ) /= 0)) then
             zero_solutions = .true.
             exit
          end if
      end do




thanks for that, to be honest i cannot read the syntax for the "code" per-say so I'm not sure how it functions exactly as i don't use C# code
.... my language of choice is free pascal with turbo pascal enabled...

i do get that it added up all the pm's across each row and fount out that it was missing a "4" for the row leaving 6 cells with 5 candidates.

yes pretty easy zero state check, i over thought it too much,

i have/had a balancing calculation that shows these areas are always equal in a non "zero" state...

Code: Select all
(R+C+B)*3 * 9 = cells * digits
(27)*3*9 =  81 * 9
729 = 729


the complicated part of my code is that it prevents it from selecting a clue addition randomly into a cell that would generate the above substate.

for example: using your grid i removed the 4 at R5C2

C2 & box 47 has 2 spots for digit 4 left which is a zero solution state.

Code: Select all
.---------------------.--------------------.------------------------.
| 1     358     3578  | 4      6     3578  | 2       9       378    |
| 5678  23568   4     | 1      9     23578 | 35678   35678   3678   |
| 5678  9       23578 | 237    2357  23578 | 135678  4       13678  |
:---------------------+--------------------+------------------------:
| -4689  7       389   | 5      234@   236   | 368     1       23468@  |
| 2     3456&   35    | 367    8     1     | 3567    3567    9      |
|-4568  -134568  1358  | 2367   2347@  9     | 35678   235678  234678@ |
:---------------------+--------------------+------------------------:
| 3     1248&   12789 | 2679   27    267   | 16789   2678    5      |
| 579   125     6     | 8      2357  4     | 1379    237     1237   |
| 5789  258     25789 | 23679  1     23567 | 4       23678   23678  |
'---------------------'--------------------'------------------------'

notes: the * cells remove all the "-" cells for candidate 4
& represents a grid state check error

this state exists from a previous clue adding i cannot guess what order the clues where added however picking an easy example is removing the "2" @

in short my old code would prevent me from adding any other clue except a "4" @ R5C1 because of the above state, without having to backtrack after adding said clue.
Code: Select all
.-----------------------.--------------------.------------------------.
| 1      358      3578  | 4      6     3578  | 2       9       378    |
| 25678  23568    4     | 1      9     23578 | 35678   35678   3678   |
| 25678  9        23578 | 237    2357  23578 | 135678  4       13678  |
:-----------------------+--------------------+------------------------:
|-24689  7        2389  | 5      234*   236   | 368     1       23468*  |
| 2456&  -23456    235   | 2367   8     1     | 3567    23567   9      |
|- 24568  -1234568  12358 | 2367   2347*  9     | 35678   235678  234678* |
:-----------------------+--------------------+------------------------:
| 3      1248*     12789 | 2679   27    267   | 16789   2678    5      |
| 2579   125      6     | 8      2357  4     | 1379    237     1237   |
| 25789  258      25789 | 23679  1     23567 | 4       23678   23678  |
'-----------------------'--------------------'------------------------'

notes: the * cells remove all the "-" cells for candidate 4
& represents a grid state check error

------------------
most of this is from memory on a code i wrote 3+ years back and haven't reviewed, the idea probably can be scrapped and upgraded with simpler code making it less "complicated " then i originally envisioned....

{once i find a copy of my generator and review it.. the loss of the programmers forum sucks i had copies posted on there and its all gone.}
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 610
Joined: 05 September 2006

Re: code to generate random sudoku puzzles

Postby m_b_metcalf » Sun Dec 11, 2016 10:21 am

StrmCkr wrote:thanks for that, to be honest i cannot read the syntax for the "code" per-say so I'm not sure how it functions exactly as i don't use C# code.

Actually, it's Fortran 95. I'm sorry for any confusion in that I printed the transpose of the result, and I've edited to post to make that clear. This code is potentially faster than what I have already, so thanks for the tip!

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8214
Joined: 15 May 2006
Location: Berlin

Re: code to generate random sudoku puzzles

Postby rjamil » Sun Dec 11, 2016 12:18 pm

Hi all,

docjohn wrote:I like the idea of using brute force backwards (9-1 rather than r9c9 to r1c1) and am working on that.

John Musgrave, many thanks for working on the brute force Sudoku generator using digit forward and backward uniqueness test.

m_b_metcalf and StrmCkr, are your Sudoku puzzle generators check invalidity after each random digit inserted in to a random cell and updated pencil mark within its 20 peer cells, i.e., a row, a column and a box, or whole grid?

I think checking Sudoku puzzle validity by just counting remaining digits equals to empty cell count within a row, a column and a box is sufficient and efficient way.

R. Jamil
rjamil
 
Posts: 115
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: code to generate random sudoku puzzles

Postby m_b_metcalf » Sun Dec 11, 2016 12:48 pm

I have various generators, but typically clues are placed fulfilling the basic Sudoku constraints and then the whole candidate puzzle is tested for not having zero solutions.

Regards,

Mike metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8214
Joined: 15 May 2006
Location: Berlin

Re: code to generate random sudoku puzzles

Postby StrmCkr » Sun Dec 11, 2016 3:21 pm

m_b_metthetcalf"StrmCkr wrote:thanks for that, to be honest i cannot read the syntax for the "code" per-say so I'm not sure how it functions exactly as i don't use C# code.

Actually, it's Fortran 95. I'm sorry for any confusion in that I printed the transpose of the result, and I've edited to post to make that clear. This code is potentially faster than what I have already, so thanks for the tip!

Regards,

Mike Metcalf[/quote]

Your welcome, now to figure out how your code can be written in turbo pascal :) thanks for your quick coding idea :)

Rjamil
Insert clue - > update pm - > CHECK ZERO STATE - > UPADE PM Via technique set -> check zero state
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 610
Joined: 05 September 2006

Re: code to generate random sudoku puzzles

Postby rjamil » Sun Dec 11, 2016 4:07 pm

Hi StrmCkr,

StrmCkr wrote:Rjamil
Insert clue - > update pm - > CHECK ZERO STATE - > UPADE PM Via technique set -> check zero state


Well my question still remain. In "check zero state" immediately after "insert clue" and "update pm", is it necessary to check entire grid for comparing the remaining digits vs remaining empty cells equality, i.e., all 27 units/groups/nonets/scopes/regions/zones, OR just three units, i.e., a row, a column and a box that contain "inserted clue"?

In other words, to check either all or just effected units?

However, after "update pm via technique set", it is feasible to check entire grid for zero state as there will be multiple reductions via multiple techniques possible at each step.

R. Jamil
rjamil
 
Posts: 115
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: code to generate random sudoku puzzles

Postby JasonLion » Sun Dec 11, 2016 5:45 pm

Checking the entire grid vs checking just the modified cells can go either way in terms of speed. The overhead of keeping track of what has been modified can be significant, or not, depending on the specific situation. A couple of the fastest solvers include a heuristic to decide which approach to take in each instance. In one particular fast solver, modifications to the placed digit grid are processed in batches. If there are more than three digits placed the heuristic rechecks the entire board, if 3 or fewer it only checks the affected cells. Another really fast solver considers placements of a single digit in an entire band of cells at once, so any change to a pm for that digit in the band triggers rechecking the entire band.

Unless you are after the absolutely fastest solver possible, it is better to keep the code as clean and understandable as possible. That usually means sticking to a single simple and obvious approach to making this kind of check.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: code to generate random sudoku puzzles

Postby StrmCkr » Sun Dec 11, 2016 7:09 pm

In other words, to check either all or just effected units?

Jason answered pretty good,

my check is out lined as "entire grid"
the way my generator works using a technique list to reduce pencil marks, until 1 solution was found by randomly assigning clues from a random cells valid pm's

the length of time each step took to complete increased exponentially as i added technique sets to my list.
to cut down on iterations of my code ie stop it from cycling the "solve" section of my code was to pre-check the entire grid for a zero state

However, after "update pm via technique set", it is feasible to check entire grid for zero state as there will be multiple reductions via multiple techniques possible at each


you could "flag" every R,C,B that was changed/updated by inserting a clue, and/or updated from technique reduction
and "check" those zones specifically for zero states instead of the whole grid. {that way its executes only on the minimal}
but then the complexity of your code increases as well has heap/stack size

as jason said its personal preference if u want to gird or localized
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 610
Joined: 05 September 2006

Re: code to generate random sudoku puzzles

Postby rjamil » Sun Dec 11, 2016 8:49 pm

Hi Jason and StrmCkr,

Many thanks for your valuable feedback.

StrmCkr wrote:you could "flag" every R,C,B that was changed/updated by inserting a clue, and/or updated from technique reduction
and "check" those zones specifically for zero states instead of the whole grid. {that way its executes only on the minimal}
but then the complexity of your code increases as well has heap/stack size

as jason said its personal preference if u want to gird or localized

I will consider the same when planning to code for Sudoku generator in future.

JasonLion wrote:Unless you are after the absolutely fastest solver possible, it is better to keep the code as clean and understandable as possible. That usually means sticking to a single simple and obvious approach to making this kind of check.

Extremely sorry for my solver is not as clean and understandable as possible to others. Actually, I tried coding based on Brian Turner's BB_Sudoku commonalities terminology.

As for example (and off topic), currently I am trying to analyze WXYZ-Wings (compiled by StrmCkr) and rearranging different types for grouped coding as follows:
Code: Select all
00) Type 0:-
 .  wz   . | .  . . | . .  .
-Z wxyz -Z | . xz . | . . yz
 .   .   . | .  . . | . .  .

01) Type 1:-
 .  wz   . | .  .  . | .  .  .
-Z wxyz -Z | . xyz . | . xyz .
 .  .    . | .  .  . | .  .  .

02) Type 2:-
 .  xyz  . | .  . . | . . .
-Z wxyz -Z | . wz . | . . .
 .  xyz  . | .  . . | . . .

03) Type 3:-
 .  wz    .  | .  .  . | . . .
-Z wxyz wxyz | . xyz . | . . .
 .   .    .  | .  .  . | . . .

04) Type 4:-
 .  xyz   .  | .  . . | . . .
-Z wxyz wxyz | . wz . | . . .
 .   .    .  | .  . . | . . .

05) Type 1a:-
 .  wz  . | .  . . | -Z -Z  -Z
-Z wxy -Z | . xy . |  . xyz  .
 .  .   . | .  . . |  .  .   .

06) Type 1b:-
 .  wz  . | . . . | -Z  -Z  -Z
-Z wxy -Z | . . . | xyz xyz  .
 .  .   . | . . . |  .   .   .

07) Type 2a:-
 . xyz  . | -Z -Z -Z | . . .
-Z wxy -Z |  . wz  . | . . .
 .  xy  . |  . .   . | . . .

08) Type 2b:-
 . xyz xyz | -Z -Z -Z | . . .
-Z wxy  -Z |  . wz  . | . . .
 .  .    . |  . .   . | . . .

09) Type 3a:-
 .  wz  .  | -Z -Z  -Z | . . .
-Z wxy wxy |  . xyz  . | . . .
 .  .   .  |  .  .   . | . . .

10) Type 4a:-
 . xyz  .  | -Z -Z -Z | . . .
-Z wxy wxy |  . wz  . | . . .
 .  .   .  |  .  .  . | . . .

11) Type 5:-
 . wyz  . | . . . | wx -Z -Z
xy  -Z -Z | . . . |  . xz  .
 .  .   . | . . . |  .  .  .

12) Type 5a:-
 . wyz  . | . . . | wxz -Z -Z
xy  -Z -Z | . . . |  .  xz  .
 .  .   . | . . . |  .   .  .

R. Jamil
rjamil
 
Posts: 115
Joined: 15 October 2014
Location: Karachi, Pakistan

Previous

Return to Software