The New Sudoku Players' Forum

[rjamil]

Hi experts,

I have got an idea about how to utilize only 5184 templates of 8 rows only (instead of 46656 templates of 9 rows) for all possible combination of each digit of a puzzle.

Just share the idea. Please do not hesitate to ask if explanation is needed.

// Global constant variable declaration with initializations
int P[5184][8];

int T[9][8] = { // Pointers to POM column for each puzzle column cell position containing digit
{ 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 2, 3, 4, 5, 6, 7, 8}, { 0, 1, 3, 4, 5, 6, 7, 8},
{ 4, 5, 0, 1, 2, 6, 7, 8}, { 5, 3, 0, 1, 2, 6, 7, 8}, { 3, 4, 0, 1, 2, 6, 7, 8},
{ 7, 8, 0, 1, 2, 3, 4, 5}, { 6, 8, 0, 1, 2, 3, 4, 5}, { 6, 7, 0, 1, 2, 3, 4, 5}};

Note: Next, I am thinking about how to skip (jump) templates for remaining 8 rows.

int J[9] = {864, 288, 48, 12, 6, 2, 1, 0};

R. Jamil

[P.O.]

Hi R. Jamil, is it possible for you to use an example to detail the application of your ideas?

[rjamil]

Hi P.O.,

Hi R. Jamil, is it possible for you to use an example to detail the application of your ideas?

Let me explain in detail shortly as I am now trying to code the same in highly optimized way. Also source code will be shared once finalized. Don't know how long it will take time.

Added: I have updated RJSudoku.c and RJSukaku.c solver in my GitHub. These programs included the unoptimized versions of POM.

Now I am working to implement my proposed optimization by removing the swap routine and skipping the templates as per described in my above post.

R. Jamil

[yzfwsf]

Hi P.O.
I think if you include hidden single, you don't need to combine templates to exclude some invalid templates.

[P.O.]

Hi yzfwsf, my Singles procedure includes naked and hidden single.

[yzfwsf]

What I mean is that the POM process should add the function of Hidden Single, so as to reduce unnecessary combinations.

[P.O.]

my pom procedure uses Singles and therefore both naked and hidden single

[rjamil]

Hi experts,

I have an idea to speed up the searching procedure of POM, without swapping and complexity, by adding a reference table of two dimensional array T[9, 60] containing 8 remaining disjoint subset of particular digit for each first row's cell; and, with template skipping as proposed earlier.

Here I am sharing disjoint cells reference table:

Hidden Text: Show

Code: Select all

           T[9][60] = {      // Pattern Overlay Method Reference Table
  {12,13,14,15,16,17,21,22,23,24,25,26,28,29,30,31,32,33,34,35,
   37,38,39,40,41,42,43,44,46,47,48,49,50,51,52,53,55,56,57,58,
   59,60,61,62,64,65,66,67,68,69,70,71,73,74,75,76,77,78,79,80},
  {12,13,14,15,16,17,21,22,23,24,25,26,27,29,30,31,32,33,34,35,
   36,38,39,40,41,42,43,44,45,47,48,49,50,51,52,53,54,56,57,58,
   59,60,61,62,63,65,66,67,68,69,70,71,72,74,75,76,77,78,79,80},
  {12,13,14,15,16,17,21,22,23,24,25,26,27,28,30,31,32,33,34,35,
   36,37,39,40,41,42,43,44,45,46,48,49,50,51,52,53,54,55,57,58,
   59,60,61,62,63,54,66,67,68,69,70,71,72,73,75,76,77,78,79,80},
  { 9,10,11,15,16,17,18,19,20,24,25,26,27,28,29,31,32,33,34,35,
   36,37,38,40,41,42,43,44,45,46,47,49,50,51,52,53,54,55,56,58,
   59,60,61,62,63,64,65,67,68,69,70,71,72,73,74,76,77,78,79,80},
  { 9,10,11,15,16,17,18,19,20,24,25,26,27,28,29,30,32,33,34,35,
   36,37,38,39,41,42,43,44,45,46,47,48,50,51,52,53,54,55,56,57,
   59,60,61,62,63,64,65,66,68,69,70,71,72,73,74,75,77,78,79,80},
  { 9,10,11,15,16,17,18,19,20,24,25,26,27,28,29,30,31,33,34,35,
   36,37,38,39,40,42,43,44,45,46,47,48,49,51,52,53,54,55,56,57,
   58,60,61,62,63,64,65,66,67,69,70,71,72,73,74,75,76,78,79,80},
  { 9,10,11,12,13,14,18,19,20,21,22,23,27,28,29,30,31,32,34,35,
   36,37,38,39,40,41,43,44,45,46,47,48,49,50,52,53,54,55,56,57,
   58,59,61,62,63,64,65,66,67,68,70,71,72,73,74,75,76,77,79,80},
  { 9,10,11,12,13,14,18,19,20,21,22,23,27,28,29,30,31,32,33,35,
   36,37,38,39,40,41,42,44,45,46,47,48,49,50,51,53,54,55,56,57,
   58,59,60,62,63,64,65,66,67,68,69,71,72,73,74,75,76,77,78,80},
  { 9,10,11,12,13,14,18,19,20,21,22,23,27,28,29,30,31,32,33,34,
   36,37,38,39,40,41,42,43,45,46,47,48,49,50,51,52,54,55,56,57,
   58,59,60,61,63,64,65,66,67,68,69,70,72,73,74,75,76,77,78,79}}

Where as:
0-6 position represent 2nd row disjoint cells;
6-11 => 3rd;
12-19 => 4th;
20-27 => 5th;
28-35 => 6th;
36-43 => 7th;
44-51 => 8th; and
52-59 => 9th.

I will then temper the Myth Jellies POM Template stored in two dimensional array of 46656 X 9 elements, by giving credit to him, as follows:

I'll take only the first 5184 rows X 8 columns, omitting rest of the 41,472 rows X first column.
Now, carefully change the first column values from 12-17 to 0-5;
second => from 21-26 to 6-11;
third => from 28-35 to 12-19;
fourth => from 37-44 to 20-27;
fifth => from 46-53 to 28-35;
sixth => from 55-62 to 36-43;
seventh => from 64-71 to 44-51; and
eight => from 73-80 to 52-59.

In this way, I will be able to point each templates to its corresponding reference table, which is pre-ordered reference to the original Sudoku grid.

This will definitely made an ultra fast POM searching routine.

Hope my above proposed logic is understandable for everyone.

R. Jamil

[P.O.]

Hi R Jamil, an example with a puzzle would be welcome to understand what you are doing

[rjamil]

Hi P.O.,

Hi R Jamil, an example with a puzzle would be welcome to understand what you are doing

If you are familiar with my tempered POM, disjoint cells reference table and POM skips/jumps then I am going to show you how to search POM eliminations and placements as follows:

I have stored Sudoku puzzle in two different arrays, i.e., s[81] contain clues + solved; and g[81] contain pencilmarks.

1) for x = 1; x < 10; ++x // for each digit
2) k[81] = {0}; // assign array holding digit count, initializing with 0's
3) for y = 0; y < 9; ++y // for each cell in first row
4) if s[y] or g[y] not contain digit x then goto 3 // if digit not found in cell
5) for z = 0; z < 5184; z += 864 // loop for each POM template
6) for a = 0; a < 8; ++a // loop for each POM cell
7) if s[t[p[z][a]] or g[t[p[z][a]] not contain digit x then goto 5
8) next a
9) if a > 7 then increment each cell in k array as digit count
10) next z
...

Hope my above logic is simple to understand as I am yet to start coding/programming.

R. Jamil

Added as on 20241026: Wish to inform that, I have implemented the template skipping/stepping in POM routine and updated my GitHub site. Now, working on removal of the swap routine, without loosing any scenario. My POM routine will then become robust and exhaustive.

Slightly change the values of T[8] = {863,287,47,11, 5, 1, 0, 0}