The New Sudoku Players' Forum

[StrmCkr]

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.

[m_b_metcalf]

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

[StrmCkr]

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

[m_b_metcalf]

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

[docjohn]

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.

[StrmCkr]

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

[m_b_metcalf]

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

[rjamil]

Hi all,

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

[m_b_metcalf]

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

[StrmCkr]

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

[rjamil]

Hi StrmCkr,

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

[JasonLion]

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.

[StrmCkr]

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

[rjamil]

Hi Jason and StrmCkr,

Many thanks for your valuable feedback.

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.

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

[StrmCkr]

for references of terms data used within this code see my thread Stormdoku

Generator: Show

Code: Select all

procedure generator;
type
hold= array of integer;
Var

xn,n,k,g2,w,j:integer;
used:numberset;
attempt: nums;

h:hold;
s2: array [cell] of nums;
output: text;

begin
Randomize;


For J:= 1 to 1 do {# of grids to generate}

begin

initiate;
setpm;
sbrc;
//wpm(1);

w:=0;

setlength(h,0);

for k in [0..80] do
 s2[k]:=[];

used:=[0..80];
   repeat

begin

  xn:= (Random(82) -1);

   if (xn in used)
   and ((S[xn] = [])  and (nm[xn] > 1) )
    then
       begin
        inc(w);
        setlength(h,w+1);

        h[w]:=xn;

        attempt:=pm[xn];

         repeat

         n:= Random(10);

          if (n in pm[xn] )  and ( n in attempt)
            then
              begin
               attempt:=attempt - [n];

               Rd[Rx[xn]]:=  rd[Rx[xn]] + S[xn];
               Cd[Cy[xn]]:=  Cd[Cy[xn]] + S[xn];
               Bd[Bxy[xn]]:= Bd[Bxy[xn]] + S[xn];

               s[xn]:=[n];

               setpm;
               sbrc;
              // wpm(1);

errorcheck;
              if unique = true
               then
               begin

              solve2(w);
               setpm;
               sbrc;
errorcheck;

              // wpm(1);


                 end; {solving techniques included}

               if unique = true
                then
                  used:= used - [xn];  {removes cell from selectable}

               if  unique = false  {back tracks current selected and implmented digit}
                 then
                  begin
                   Rd[Rx[xn]]:=  rd[Rx[xn]] + S[xn];
                   Cd[Cy[xn]]:=  Cd[Cy[xn]] + S[xn];
                   Bd[Bxy[xn]]:= Bd[Bxy[xn]] + S[xn];

                   s[xn]:=[];

                     for k:= 0 to 8 do
                     begin
                      covered2[k+1]:=[0..80];
                       for g2:= 1 to 9 do
                        covered[Rset[k,(g2-1)]]:=[1..9];
                      end;

                     setpm;
                    sbrc;
                   //wpm(1);


                   end; {back track current lvl}
              end;

        until (unique = true) or (attempt = []);

      end;


  if (attempt = []) and (unique = true)
             then
                   begin

                   used:= used + [h[w]];

                   dec(w);
                   setlength(h,w+1);

                   xn:=h[w];

                   Rd[Rx[xn]]:=  rd[Rx[xn]] + S[xn];
                   Cd[Cy[xn]]:=  Cd[Cy[xn]] + S[xn];
                   Bd[Bxy[xn]]:= Bd[Bxy[xn]] + S[xn];

                   s[xn]:=[];

                     for k:= 0 to 8 do
                     begin
                      covered2[k+1]:=[0..80];
                       for g2:= 1 to 9 do
                        covered[Rset[k,(g2-1)]]:=[1..9];

                      end;

                    setpm;
                    sbrc;
                    //wpm(1)


                 end;

end;

    until (used = []) or (Countpm = 0 ) or (countpm <  count)  or (count + countpm = 81) or (Countpm+count < 81)  or  (countpm <  (81 - count)) ;

 //wpm(1);

 if (count+ countpm  =81)
  then
    begin


     for N:= W downto 1 do
        begin
           xn:=h[n];

                   S2[xn]:=s[xn];

                   Rd[Rx[xn]]:=  rd[Rx[xn]] + s[xn];
                   Cd[Cy[xn]]:=  Cd[Cy[xn]] + s[xn];
                   Bd[Bxy[xn]]:= Bd[Bxy[xn]] + s[xn];

                   s[xn]:=[];

                     for k:= 0 to 8 do
                     begin
                      covered2[k+1]:=[0..80];
                       for g2:= 1 to 9 do
                        covered[Rset[k,(g2-1)]]:=[1..9];

                      end;

                    setpm;
                    sbrc;
                    //wpm(1);

           solve2(w);
            setpm;
            sbrc;
           // wpm(1);

           if (count + countpm = 81)
             then
              begin
               // writexy(2,61,'delted a number');
                //wpm(1);
               end
              else
               begin
                 // writexy(2,61,'undo delete');

                   Rd[Rx[xn]]:=  rd[Rx[xn]] + S[xn];
                   Cd[Cy[xn]]:=  Cd[Cy[xn]] + S[xn];
                   Bd[Bxy[xn]]:= Bd[Bxy[xn]] + S[xn];

                   s[xn]:=s2[xn];
                   s2[xn]:=[];

                     for k:= 0 to 8 do
                     begin
                      covered2[k+1]:=[0..80];
                       for g2:= 1 to 9 do
                        covered[Rset[k,(g2-1)]]:=[1..9];

                      end;
                    setpm;
                    sbrc;
                    //wpm(1);
              end;


         END;

   end;

gotoxy(2,60);
assign(output,'C:\sudoku\Generator\Generated.txt');
 append(output);
  writeln(output);
       for k:= 0 to 80 do
        if s[k] <> []
         then
           begin
             for G2:= 1 to 9 do
               if g2 in s[k]
                then
                 write(output,g2)
           end
        else
          write(output,'.');


       close(output);

end; { generate j puzzles}

end;

error checks: Show

Code: Select all

procedure errorcheck;
var
XN,N,YN,count,s,f:INTEGER;
count2:RCBnums;
Begin
UNIQUE:= TRUE;

  {redundant checks as they are found below}
{FOR XN:= 0 TO 80 Do
 BEGIN

 //no cell and pm can be empty
 IF (s[XN] = [])  AND (nm[XN] =0 )
  THEN
    UNiQUE:= FALSE;

 //no peer cell of xn, can have the same solved digit
 FOR N IN S[XN] Do
 FOR YN IN PEER[XN] DO
   IF N IN S[YN]
     THEN
       UNIQUE:= FALSE;
END;  }


For xn:= 0 to 26 do
begin

if (nsector[xn] <>  [1..9]-ssector[xn] )  { and (nsector[xn] <> [])} {shows mutiple digits pms are missing in full}
 then
  unique:=false;

if (Nsector[xn] <> []) and (nsector[xn] = [1..9] - ssector[xn]) then
 begin
 Count:= 0;
 count2:=[];

{no sector can have less digits then unsolved cells
no sector can have more digits then unsolved cells}
   for n in Nsector[xn] do
     begin
      inc(count);
      count2:= Rnsector[xn,n] + count2;
      end;
     if popcnt(dword((count2))) <> count
      then
      unique:= false;

 if (count > 2)  then
case (count) of
3: begin s:=9; F:= 128; end;
4: begin s:=9; F:= 254; end;
5: begin s:=9; F:= 380; end;
6: begin s:=9; F:= 464; end;
7: begin s:=9; F:= 500; end;
8: begin s:=9; F:= 509; end;
9: begin s:=9; F:= 510; end;
end; {case count}

     { no subset can have less cells then the subset digit count}
if  (count > 2)   then
for yn:= s to f do
  if comboset[yn] * Nsector[xn] = comboset[yn]
    then
    begin
     Count:= 0;
      count2:=[];

   for n in Nsector[xn] * comboset[yn] do
     begin
      inc(count);
      count2:= Rnsector[xn,n] + count2;
      end;
     if popcnt(dword((count2))) < count
      then
        unique:= false;
    end;
 end;


end;


END;