problems with scc_grid repeated calls

[jf]

Hello,

I have run into a problem with scc.
My attempts to generate regions failed (too slow), so
I have tried to generate them with repeated call to scc_grid.
It fails for sat, cp and other solvers.

At first its running OK, but after some time it fails.
Picat 3.9#1, (C) picat-lang.org, 2013-2025, with regex compiled.

===========================
import sat.

% The size of each region is given if Board cell is ground,
% otherwise all possible regions for all sizes up to Max (= 5 here)
% are generated.
% 3 - - 5 -
% - 1 - - 2
% - 4 - 2 -
% 4 - - 3 -
% - 4 - - 4

main =>
   % test run
   Ax = {
      {0,_,_,_,1},
      {_,0,_,_,0},
      {_,0,_,0,_},
      {0,_,_,0,_},
      {_,0,_,_,0}},
   Ax :: [0,1],
   scc_grid(Ax, 5),
   Rgx = solve_all(Ax),
   printlist(Rgx),nl,nl,   % OK, end of test

   Board = {
      {3,_,_,5,_},
      {_,1,_,_,2},
      {_,4,_,2,_},
      {4,_,_,3,_},
      {_,4,_,_,4}},
   Rownum = 5,
   Colnum = 5,
   Coords = [],
   Max = 5,
   foreach ( Row in 1..Rownum, Col in 1..Colnum )
      if ( nonvar(Board[Row, Col]) ) then
         Coords := [{Row, Col, Board[Row, Col]}|Coords],
      end
   end,
   printlist(Coords),nl,

   foreach ( Row in 1..Rownum, Col in 1..Colnum )
      if ( nonvar(Board[Row, Col]) ) then
         Sizes = [Board[Row, Col]]
      else
         Sizes = 1..Max
      end,
      foreach ( Size in Sizes )
         A = new_array(Rownum, Colnum),
         A :: [0,1],
         foreach ( {R, C, S} in Coords )
            if ( S !== Size ) then
               A[R, C] #= 0  % forbidden cells of incompatible size
            end,
         end,
         A[Row, Col] #= 1,   % starting cell for scc
         scc_grid(A, Size),
         Rg = solve_all(A),  % not OK for rowcolsizerglen = [1,5,5,0] and up to the end
         nl,println(rowcolsizerglen=[Row,Col,Size,Rg.len()]),
         printlist(Rg)
      end,
   end.

printlist([L|Ls]):-
   println(L),
   printlist(Ls).
printlist([]).

===========================

Test run, for size 5 there are 5 possible regions (by lines)
{{0,0,0,1,1},{0,0,1,1,0},{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0}}
{{0,1,1,1,1},{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}
{{0,0,1,1,1},{0,0,1,0,0},{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0}}
{{0,0,1,1,1},{0,0,1,1,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}
{{0,1,1,1,1},{0,0,0,1,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}

Program output:
... (OK)

rowcolsizerglen = [1,5,1,1]
{{0,0,0,0,1},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}
size 1, so far OK

rowcolsizerglen = [1,5,2,1]
{{0,0,0,0,1},{0,0,0,0,1},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}
so far OK, only one possible region of size 2

rowcolsizerglen = [1,5,3,0]
size 3, impossible, so far OK

rowcolsizerglen = [1,5,4,0]
size 4, impossible, so far OK

rowcolsizerglen = [1,5,5,0]
Wrong, rglen should be 5 as in the test run

rowcolsizerglen = [2,1,1,0]
rowcolsizerglen = [2,1,2,0]
...
rowcolsizerglen = [5,5,4,0]

All remaining solutions have zero length, mostly wrong

--

Is the number of solver calls limited?

Best regards
Josef

[Hakan Kjellerstrand]

Hi, Josef.

Are you sure that there should be solutions for these that give 0 solutions? 

If this constraint is removed

   A[Row,Col] #= 1

then all instances gives some solutions.

Best,

Hakan

[jf]

Hi,

this is strange.

If I add println(A) before scc_grid for 1,5,5, I get

{0,_013a9e0::[0 ..1],_013a990::[0 ..1],_013a940::[0 ..1],1},
{_013a8a0::[0 ..1],0,_013a800::[0 ..1],_013a7b0::[0 ..1],0},
{_013a710::[0 ..1],0,_013a670::[0 ..1],0,_013a5d0::[0 ..1]},
{0,_013a530::[0 ..1],_013a4e0::[0 ..1],0,_013a440::[0 ..1]},
{_013a3f0::[0 ..1],0,_013a350::[0 ..1],_013a300::[0 ..1],0}

that is

{0,_,_,_,1},
{_,0,_,_,0},
{_,0,_,0,_},
{0,_,_,0,_},
{_,0,_,_,0}

(the test case above)

with solutions like

{0,_,1,1,1},
{_,0,1,1,0},

{_,0,_,0,_},
{0,_,_,0,_},
{_,0,_,_,0}

or 

{0,1,1,1,1},
{_,0,1,_,0},

{_,0,_,0,_},
{0,_,_,0,_},
{_,0,_,_,0}

etc...

And when I put the 1 at constant position

A[2, 3] #= 1

All instances gave some solution as well...

Strange.

Best regards

Josef

Dne středa 15. října 2025 v 10:08:28 UTC+2 uživatel Hakan Kjellerstrand napsal: