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:

[Neng-Fa Zhou]

Generally you cannot call solve or solve_all multiple times in one program because before each solve the constraint store is cleared. You can call solve again if the constraints posted after the previous solve is completely independent. 

If the problem is to find multiple regions of given sizes, you should duplicate the base graph for each region and use the scc constraint to synthesize a subgraph, and then impose constraints on the subgraphs. In this way, you can synthesize multiple subgraphs with one call to solve or solve_all.

Take a look at the numberlink problem and its Picat solution:

https://picat-lang.org/sat/numberlink_b.pi

This problem involves synthesizing multiple paths for connecting number pairs. 

Cheers,

NF

[jf]

Thank you very much for your example, now my solution for fillomino

(https://www.janko.at/Raetsel/Fillomino/index.htm) works.

But for any larger problems, esp. those with no clues it is too slow (it is

brute force constraint solving).

The final solve works ok, but the generation of all possible pentomimos

takes most of the computer time:

https://www.janko.at/Raetsel/Fillomino/006.a.htm 1 minute

https://www.janko.at/Raetsel/Fillomino/075.a.htm 30 minutes...

Best regards

Josef

Dne čtvrtek 16. října 2025 v 18:00:21 UTC+2 uživatel Neng-Fa Zhou napsal: