/* 

  Two-dimensional constrained channels in Picat.

  From 
  David McKay: 
  "Information Theory, Inference, and Learning Algorithms"
  page 262
  http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
  """
  These observations about crosswords were first made by Shannon (1948); I
  learned about them from Wolf and Siegel (1998). The topic is closely related
  to the capacity of two-dimensional constrained channels. An example of a
  two-dimensional constrained channel is a two-dimensional bar-code, as seen
  on parcels.

  Excercise 18.2
  A two-dimensional channel is defined by the constraint that,
  of the eight neighbours of every interior pixel in an N × N rectangular
  grid, four must be black and four white. (The counts of black and white
  pixels around boundary pixels are not constrained.)
  """ 

  Here's the first two solutions for N=13 (and M=4):
    {0,0,0,1,1,1,1,1,0,0,0,0,0}
    {1,1,1,1,1,0,0,0,0,0,1,1,1}
    {1,1,0,0,0,0,0,1,1,1,1,1,0}
    {0,0,0,0,1,1,1,1,1,0,0,0,0}
    {0,1,1,1,1,1,0,0,0,0,0,1,1}
    {1,1,1,0,0,0,0,0,1,1,1,1,1}
    {0,0,0,0,0,1,1,1,1,1,0,0,0}
    {0,0,1,1,1,1,1,0,0,0,0,0,1}
    {1,1,1,1,0,0,0,0,0,1,1,1,1}
    {1,0,0,0,0,0,1,1,1,1,1,0,0}
    {0,0,0,1,1,1,1,1,0,0,0,0,0}
    {1,1,1,1,1,0,0,0,0,0,1,1,1}
    {1,1,0,0,0,0,0,1,1,1,1,1,0}

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


  From N = 13 (and N=4) and onwards, it seems that there are always 78 solutions.

  N #solutions
  ------------
   1   2
   2  16
   3 140
   4 558
   5 748
   6 602
   7 262
   8 202
   9 166
  10 134
  11 126
  12  94
  13  78  <- from here on it seems to be alway 78 solutions
  14  78
  15  78
  16  78
  .....
  
  26  78

  .... 
  46  78
  ...
  
  
  This sequence is not in OEIS:
  2, 16, 140, 558, 748, 602, 262, 202, 166, 134, 126, 94, 78


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  nolog,
  N = 13,
  M = 4,
  channels(N,M,X),
  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,
  
  nl.
go => true.

/*
 1:    2
 2:   16
 3:  140
 4:  558
 5:  758
 6:  602
 7:  262
 8:  202
 9:  166
10:  134
11:  126
12:   94
13:   78
14:   78
15:   78
16:   78
17:   78
18:   78
19:   78
20:   78
21:   78
22:   78
*/
go2 =>
  nolog,
  member(N,1..22),
  Count = count_all(channels(N,4,_X)),
  printf("%2d: %4d\n", N, Count),
  fail,
  nl.

/*

  Number of solutions for N=13 and M=1..8

  1:    0
  2:    8
  3:    0
  4:   78
  5:    0
  6:    8
  7:    0
  8:    1

  When M=8, then it's all 1s in the matrix.

*/
go3 =>
  nolog,
  N = 13,
  member(M,1..8),
  Count = count_all(channels(N,M,_X)),
  printf("%2d: %4d\n", M, Count),
  fail,
  nl.


channels(N, M, X) =>
  X = new_array(N,N),
  X :: 0..1,

  foreach(I in 2..N-1, J in 2..N-1) 
    M #= sum([X[I+A,J+B] : A in -1..1, B in -1..1,
            I+A >= 1, J+B >= 1,
            I+A <= N, J+B <= N,
            not(A = 0, B = 0) % don't count cell X[I,J]
         ])
  end,
  solve($[degree,updown],X). % 12.052