Good evening everyone


The attached image is a Sudoku grid.

It's not just numbers and lines, it's solving a Sudoku grid.

The starting grid is defined as follows in the code :

#declare board = array[SIZE][SIZE] {
   {0,8,0,3,0,0,7,0,6},
   {6,0,3,2,0,8,4,0,0},
   {2,0,0,4,9,6,3,1,0},
   {8,0,0,0,6,4,0,0,0},
   {7,0,0,1,0,0,0,0,0},
   {0,9,6,0,0,7,0,4,2},
   {3,0,8,0,2,0,1,5,4},
   {4,0,9,8,0,1,6,0,0},
   {5,6,0,7,4,3,2,0,9}
   }


The starting digits in yellow, solution digits in blue.

Everything runs smoothly and quickly.
For this grid, the times are :
  - Parse Time : 0.124 sec
  - Render Time : 1.070 sec
  on an old Intel Core i5, 6 cores.


All seemed well, but, but... the greater the difficulty (fewer and fewer 
starting digits), the greater the level of recursivity of the main 
function and the POV hang with the tragic message "Too many nested 
conditionals or macros." :(

The same code in C works without a hitch whatever the level of difficulty



It's true that POV isn't really designed for big calculations.
I'm well aware that I'm overstepping my boundaries.

By the way, just to understand, what limits the level of nested calls?
Memory? (It's true that in 1986, machines didn't have much memory.)




So I need to find another method without recursive calls. The little 
information I've found on the web suggests replacing recursive calls 
with a loop... hum... hum...
I think I'm going to have a big headache this weekend!




If anyone's interested, I've also attached the text file containing the 
debug stream redirection.



-- 
kurtz le pirate
compagnie de la banquise

Post a reply to this message

Attachments:
Download 'sudoku_solver.txt' (2 KB) Download 'sudoku_solver_display.png' (159 KB)

Preview of image 'sudoku_solver_display.png'

kurtz le pirate <kur### [at] freefr> wrote:

> All seemed well, but, but... the greater the difficulty (fewer and fewer
> starting digits), the greater the level of recursivity of the main
> function and the POV hang with the tragic message "Too many nested
> conditionals or macros." :(
>
> The same code in C works without a hitch whatever the level of difficulty
>
>
>
> It's true that POV isn't really designed for big calculations.
> I'm well aware that I'm overstepping my boundaries.

(I think when I was doing my sorting macros)
jr pointed out that if you use dictionaries, you won't get the "too many
nested...." error.

Maybe try that and see if it works  :)

- BW

Post a reply to this message

hi,

kurtz le pirate <kur### [at] freefr> wrote:
> The attached image is a Sudoku grid.
> It's not just numbers and lines, it's solving a Sudoku grid.

nice.


> The starting grid is defined as follows in the code :
> #declare board = array[SIZE][SIZE] {
>    {0,8,0,3,0,0,7,0,6},
>    {6,0,3,2,0,8,4,0,0},
>    {2,0,0,4,9,6,3,1,0},
>    {8,0,0,0,6,4,0,0,0},
>    {7,0,0,1,0,0,0,0,0},
>    {0,9,6,0,0,7,0,4,2},
>    {3,0,8,0,2,0,1,5,4},
>    {4,0,9,8,0,1,6,0,0},
>    {5,6,0,7,4,3,2,0,9}
>    }
> ...
> If anyone's interested, I've also attached the text file containing the
> debug stream redirection.

interested in puzzle solvers ?  _yes_ </grin>, though I tend to use Tcl.

the board (above) doesn't tell me very much, how do you deal with the nine
sub-squares ?  how do keep track of the values a given cell (still) can take ?
(and many other such questions :-))


regards, jr.

Post a reply to this message

On 11/01/2025 09:23, jr wrote:
> 
> the board (above) doesn't tell me very much, how do you deal with the nine
> sub-squares ?  how do keep track of the values a given cell (still) can take ?
> (and many other such questions :-))
> 


Yes, I admit I didn't give much information.


On 10/01/2025 19:10, Bald Eagle wrote:
 > jr pointed out that if you use dictionaries, you won't get the
 > "too many nested...." error.

I don't see how dictionaries could help me at all.



Here's the macro code where I put a lot of comments.
'a' parameter containt the 9x9 array typically called by : Solve(board)

// ---------------------------------------------------------------------
// The recursive solve() procedure
// ---------------------------------------------------------------------
#macro Solve(a)

  /*
  // Counts the number of times the function calls itself.
  #declare solve_count = solve_count+1;
  #debug concat(" solve_count = ",str(solve_count,0,0),"\n")
  */

  // Set default value do false : sudoku not solved by default
  #local solve_value = false;

  // Find an empty cell (the first one)
  #local (Result,Row,Col) = find_empty(a);

  // find_empty say that there is no empty cell
  #if (!Result)
   // all cells are filled.
   // Sudoku is solved
   // Set solve_value to true.
   #local solve_value = true;

  #else
   // Yes, there is an empty cell at 'Row', 'Col'
   // Let's try to fill it.

   // For all digit from 1 to 9
   #for (num,1,SIZE)

    // If this candidate is good for this cell put it in this cell.
    // is_valid() check that 'num' is not on the line 'Row', not in the
    // column 'Col' an not in 3x3 square which contains (Row,Col).
    #if ( is_valid(a,num,Row,Col) )
     // Put 'num' in cell [Row][Col]
     #declare a[Row][Col] = num;

     // Tests if all cells are filled
     // ! RECURSION HERE !
     #if ( Solve(board) )
      // Yes! Soduku is solved.
      // Set the return value to true
      #local solve_value = true;
      // and exit this macros
      #break
     #end // #if ( solve(board) )

     // Reset candidate 'num' in this cell
     #declare a[Row][Col] = 0;

     // the 'num' candidate is wrong
    #end // #if ( is_valid(a,num,row,col) )

    // next digit candidate
   #end // #for (num,1,SIZE)

  // look if there is an other empty cell
  #end

  // Return state of solver
  solve_value

#end
// ---------------------------------------------------------------------



I've tried to remove the recursion, but so far without success.
Either I have an infinite loop, or the resolution is not complete.



regards

-- 
kurtz le pirate
compagnie de la banquise

Post a reply to this message

hi,

> On 10/01/2025 19:10, Bald Eagle wrote:
>  > ... dictionaries, ...
> I don't see how dictionaries could help me at all.

convenient to keep stuff (data and or "state") in a single, easy-to-pass-around
"bag".  for instance, say you'd want to solve "Jigsawdoku"s too, there'd be
additional info to store.


> Here's the macro code where I put a lot of comments.

thanks.  it's .. compact.  (as recursive code so often is)


regards, jr.

Post a reply to this message