[Question]
  [
Consider a non-empty binary matrix **M** and a natural number *n*. For the purposes of this challenge, **M** is said to have blockiness *n* if it can be built using adjacent square blocks of size *n*, where each block has equal entries; and it cannot be formed using square blocks of any larger size. Intuitively, *n* can be thought of as the "pixel size" of the matrix.
**Example 1**: let the values of the matrix be represented as `+` and `o` for clarity.
```
++oo++++
++oo++++
oo++++++
oo++++++
```
has blockiness `2`. Although some entries can be considered to belong to larger blocks, `2` is the maximum block size that is valid for all entries. To be specific, the blocks are shown below, using `·` as separator:
```
++·oo·++·++
++·oo·++·++
···········
oo·++·++·++
oo·++·++·++
```
**Example 2**:
```
+++oo+++
+++oo+++
```
has blockiness `1`. Even if any entry can be seen as belonging to some "sliding" block of size `2`, it is not possible to form the matrix using adjacent blocks of that size.
# The challenge
Given a non-empty binary matrix, output its blockiness.
# Rules
* Any two consistent values can be chosen to define the matrix. Input format is flexible as usual (2D array, list of lists of numbers, flattened array and one or two numbers defining its shape, list of strings, ...).
* Input and output means are [flexible](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) as usual. [Programs or functions](http://meta.codegolf.stackexchange.com/a/2422/36398) are allowed. [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are forbidden.
* Code golf, shortest wins.
# Test cases
See also "inputs in common formats" at the end.
* Blockiness `1`:
```
+
ooo
+o
++
+++oo+++
+++oo+++
ooo+++
ooo+++
++++++
++oooo
ooooo
ooooo
ooooo
ooooo
```
* Blockiness `2`:
```
oo
oo
++++
++++
++oo++++
++oo++++
++oo++++
++oo++++
oo++++++
oo++++++
```
* Blockiness `3`:
```
++++++ooo
++++++ooo
++++++ooo
ooo+++ooo
ooo+++ooo
ooo+++ooo
+++ooo+++
+++ooo+++
+++ooo+++
```
* Blockiness `4`:
```
++++++++
++++++++
++++++++
++++++++
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
```
**Inputs in common formats**:
* [Numerical matrix, Matlab/Octave](https://tio.run/##bVAxDoAgDPxK4@Dg1M5dHEx8BGFwctHNzfj2WoRAAXMM7V17B5zbdYisw7yPi8hN4BAUHhwBMhBQKLXwkzIBQackYOkYqoYKOK9FY@QPaoiWDXEp2cY1@TkiCjXD0BGm@SWSe5VY7quqkc0Dk8z9thnyxbz3r7Kb04/mj3pe)
* [Character matrix, Matlab/Octave](https://tio.run/##bVAxDoAgDPxK46BRl3bu4mDiIwyDk4vGxc34dixKoIA5hvauvQP25dysnaqmP5phbevR2otgRhAYmAmQgYBcKYXphHFwOnkBY8eQNBTBYe0zRn4hhqhZF@eTdVyWHyI@IWUYCkI1v4R3TxLjfUVVsnqgl7ncVkMmmpf@SXZ2ytHwUfcD)
* [Nested list, Python](https://tio.run/##bVAxDsIwDPyK1YFIqEM8W5U6IDEzQuSBqR2AqRvi7cFuo8Rpqstg39l3Sd7P5RXjtXPBjdMHh9u9G6fTxYGgd4/FkRTcBy05j8xzjF@E4EHAEBA8AQJqKQWfhVGojknwpSOoGiygvLYZe1ohht6yGpeSbdwuP0dsQs0QNIRpDonkXiWW@4pqZPPAJFO7bYa4mLf@VfbutKP5o35/)
* [List of strings, Python](https://tio.run/##bVAxDsIwDPyK1QGrwGDPFhIDEm@gUQamdgCxdEGItweHRonTVM7gu7Pvkjzv8yOEa4cOz@Pw5p5Ptw4PL0X97oKCgEccZvRGnqYQPgyOQMuDYyABBo6tNn6vTKyocxKoIIEKcCnJa4sxyb/UkCwb41KyjVvl54hFqBmBhjBgk0juVWK5r6pGNg9MsrTbZsgX89a/yl6ddjR/1PcH)
* [Flattened array (row-major order) and shape (numbers of rows and columns)](https://tio.run/##bVAxDsIwDPyK6YAl1CGeLaQOSLyBRhkYUDMAUxeEeHtwaJo4DboM9p19l@Rxne8hnDu0OExPOl66YdrRbX9CtxLeIwh6HGfsQdjxJfJKeR/Cm8AaEDiwBIaBgGIphTsIExF1SoIpHUPVUAHntcXY8A9iaDQb41Kyjtvk54hFqBmGhlDNXyK5V4nlvqIqWT0wydxuqyFXzFv/Kntz2tH8UZ8v)
* If you think that some common format is missing, leave a comment and I'll try to generate it automatically.
  
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 33 bytes
```
GCD@@Length/@Split@Join[2#,#]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@9/d2cXBwSc1L70kQ98huCAns8TBKz8zL9pIWUf5fX97rNr/gKLMvJJoZQVdO4W0aOXYWAU1BX0HLoXq6mrj2lodLgUgy0hHAYRgXGMQG8RUADGNkYQhCKIcykVSiEUS1QJ0TUYEzMImDNdjhGG4EcLd5IkhGYgkj@F/THeiKkHxE3b3U0crsh9wBBoOSQwvoUafEY6YIF4eR8TjDH8y5dGFCSRLEuRxhhCehEqxJF5LsSTfUYU4FNbW/gcA "Wolfram Language (Mathematica) – Try It Online")
Take a 2d array of 2's and 3's, or any two values \$a\$, \$b\$ such that \$\{a,b\}\cap\{2a,2b\}=\{\}\$.
Split the array into runs of identical rows and columns, and take the GCD of the lengths of these runs.
Here `` is the postfix operator for matrix transpose.
[Answer]
# [J](http://jsoftware.com/), 24 bytes
```
+./@,&I.&(1#.0&,~:,&0)|:
```
[Try it online!](https://tio.run/##tVDBCsIwDL3nK4JCt5Jau@mpMhgIguDJq4gH2RAvObjj8Nfnturm1oEnD01eHi8vSe/VTAc5JhYDVGjQ1m@hcXs87CrSy1SJvRZhNNdGqKdVwsjSVhKK7FEkGrPrjVOb4MlimCvM09JKjCjgIMHzRl9igAgbbeNsgEAOamYeMcRAYxURMdehB55LQ3Incol9d245P0qIByrwOPpYe3w7lXrg0jf41SFhNZrULj@Jhlp38vsOD7nUfdwISVh7U7vvmwTTHdwv@JdCVi8 "J – Try It Online")
Port of [alephalpha's Mathematica answer](https://codegolf.stackexchange.com/a/237032/78410).
```
+./@,&I.&(1#.0&,~:,&0)|:    NB. Input: matrix M
     &                |:    NB. For M and its transpose:
             0&,            NB. M with a zero row prepended
                  ,&0       NB. M with a zero row appended
                ~:          NB. Elementwise unequal of the two
          1#.   NB. Row-wise sum
      I.&       NB. Indices; x[i] copies of i
+./@,           NB. Concatenate the two results and GCD reduce
```
---
# [J](http://jsoftware.com/), 39 bytes
```
1 i:~0,(2 2$#)\(];.3*/@,@e.0 1+[$1:)"2]
```
[Try it online!](https://tio.run/##tVA9D4IwEN3vV1yQBOphpcWphoTExMnJFYmDgajLDTL715EPBaEkTg69e/f67vNeOdIrMDboYYAhmvqtJO6Oh32l8GaeYeBr1O5CnPxsK6PlOgmSXIaoKHWVEY7OKgFl/ihjifnlykmMqcGi/vfYi7HOOWtQ2Cia8iEQiFHMzBOGGGiqIiLm2gzAqtKQ3Is6x3Z1bjnbCtAjFVgcfUpbfNuVBtC5b/ArQ0A06dQOP4vG2m7l9x4W6lx/uAkSsLG69uebBfMZPAz4l0BULw "J – Try It Online")
The input format is a matrix of 1's and 2's.
### How it works
```
1 i:~0,(2 2$#)\(];.3*/@,@e.0 1+[$1:)"2]    NB. input: matrix M having n rows
(2 2$#)\    NB. 3D block, each layer is 2x2 matrix of i where i <- 1..n
(...)"2]    NB. For each layer of above and the entirety of matrix M...
 ];.3       NB.  A: Extract ixi blocks of M, padding with zeros
            NB.  (when some padding exists, the test always fails)
 0 1+[$1:   NB.  B: 3D block having two layers: ixi of 1's and ixi of 2's
 */@,@e.    NB.  Test if every 2D cell of A exists as a cell in B
            NB.  i.e. Test if all ixi blocks of M are valid
1 i:~0,     NB. Extract the last 1-based index of 1
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~52~~ 42 bytes
```
ＷＳ⊞υιＩ⊟Φ⊕Ｌυ∧ι›⬤υ⬤λ⁼ν§§υ⁻μ﹪μι⁻ξ﹪ξι∨﹪Ｌυι﹪Ｌθι
```
[Try it online!](https://tio.run/##TY5BCoMwEEX3PUWWM2hP4EpKW4SWCj1BMEEDY6Ixab19mlQbOpv/@e/PMN3AbWc4hfAeFEkGjZ68ezqrdA@IrPXLAL5kCqtDG0MHJ744aM0EF0VO2rjQWTlK7aSAm9S9i33EktVagCrZ1UqeajVRupOESnaePacFdAxco4Vc4aexc1faLzBGY4Qnk5zCdHIDawbrBr7sYWFP8xOJ5u6ezph3EKsQisKYIs4hm03@TTi@iH8A "Charcoal – Try It Online") Link is to verbose version of code. Takes input as a newline-terminated list of strings. Explanation:
```
ＷＳ⊞υι
```
Input the matrix.
```
Ｉ⊟Φ⊕Ｌυ∧ι
```
Output the largest number from `1` to the height of the matrix...
```
›⬤υ⬤λ⁼ν§§υ⁻μ﹪μι⁻ξ﹪ξ
```
... for which each character equals that at the top left corner of its aligned submatrix ...
```
ι∨﹪Ｌυι﹪Ｌθι
```
... and which divides both its height and width.
[Answer]
# [J](http://jsoftware.com/), 57 51 50 48 44 43 39 bytes
```
<:@]^:(0 e.[:,[:="1[,;.3~2 2$])^:_<./@$
```
[Try it online!](https://tio.run/##tVA9D4JADN37KxpCgpfiyYfTwSUkJk5OrgQcDMS4dJDZv458KMgdiZPDta8vr6/t3VtHejVqhR76GKDq3lbi4Xw6tqnKilJtAqxkrvxcaSfM/UTGzwgjtxCluqRyl7mtgKZ6NFpidb1xpjFXWGNIHnsai0ReIoAQe0nvHwCBWNTMbDDEQKaKiJi7MAPLpSd5Eo2JbXceODsKiBYqsDj6WFv8MJVmMKZv8KtDQGxMGpZfRUvtePL7DguNafo4AwnYW1On71sF6x08L/iXQrQv "J – Try It Online")
*-4 thanks to Bubbler's idea of using 1-2 encoding to capitalize on automatic 0-padding*
Input is 1-2 matrix.
* `<./@$` - Starting with the smaller dimension of the input (call it `d`)...
* `<:@]` - Decrement `d` while...
* `^:...^:_` - Stuff (elaborated below) that checks if, when we tile the input with `d x d` tiles, any one of them is non-homogeneous:
	+ `0 e.` Is 0 an element of...
	+ `[:,` The flatten of...
	+ `[:="1` The catalog of... (the catalog of a list is all ones only for a homogeneous list)
	+ `[,;.3~2 2$]` Each `d x d` tile flattened. Partial tiles are 0 padded, and thus guaranteed to be non-homogeneous.
[Answer]
# [Python 3](https://docs.python.org/3/) with [numpy](https://numpy.org/doc/1.21/), 92 bytes
```
from numpy import*
f=lambda m,k=1:k<len(m)and f(m,k+1)or all(m==kron(m[::k,::k],eye(k)<2))*k
```
[Try it online!](https://tio.run/##1VE9c8MgDN39Kxgh9YDbjYvHdO3SzeeBNvji4/MU3MS/3sV2jsOuL2nHigOk9yQkIdf7kzUvw9CA1ch02vWo1c6C32VNqbj@OHKkc1kWTO6VMFgTbo6owQF7KogFxJXCuiwl2EBWjMk87DoXvcCS7J8J2cnBQ88yFORyapVA79CJ2R7FQWs8bjAH4D0WX1zh1rjOYzJKJq6fwnl0eHs9AFhgyPHzeaiqoq6zqqJ5WJNWhDsPZ3GzxjWykzYzCyRGRw@64Z9aM0@TSDrlfKzfImYsqS/JE9FYwyLv37zm3MsO1khSRfwZuuz7Drb6vVXPj7HE2pjQPWxd949p/RrZeCmZ3n9k6m8 "Python 3 – Try It Online")
Takes a numpy `ndarray`.
`m[::k,::k]` takes every `k`th element of `m` in both dimensions; `eye(k)<2` is a short way to make a `k`-by-`k` matrix with every entry `True` (which is equivalent to 1 here). With these arguments, `kron` expands each element from `m[::k,::k]` to a `k`-by-`k` block. Next, the equality check with `m` produces a matrix of individual Boolean results if the sizes are the same, or `False` if the sizes are different (deprecated); `all` turns this into a single Boolean representing whether the matrices are the same.
[Answer]
# [R](https://www.r-project.org/), ~~104~~ ~~97~~ ~~90~~ 85 bytes
*Edit: -3 bytes thanks to pajonk*
```
f=function(m,b=nrow(m))`if`(identical(m[i<-1:b<2,i,drop=F]%x%diag(b)^0,m),b,f(m,b-1))
```
[Try it online!](https://tio.run/##1VLBisIwEL3vfwgZGCGjVXYXe/ULvIli09plWJNKrejf16RiqUiayp6Wd8rLm5eZlylrdSjSXzb70ymu8zg/m7TiwgiNKjZlcREaYMf5TnC2NxWnyUHoNS/G9K0WE2TMyuIYLzej6yjj5Eco2ErUgApzZzEmgM4LQidVyVdh2Y9XNhUSLQAJp7jySMhKCAlwYuEXOci7tEV7dsWf3mLZKZQvJs92TbsRzgNmQTiTWchkyMwtnDjqFXvjCQUUKO69a8yjgDl50/cwYBfm640PHcK82cJjtnlPI4R/wvDgunP9Ex7saNRsd30D "R – Try It Online")
Recursive function: tests blockiness `b` starting with number of rows of matrix `m`, and recurses decreasing `b` until it finds one that fits.  
Blockiness test consists of calculating the kronecker product (`%x%` function in [R](https://www.r-project.org/)) of each `b`-th element of `m`, and a `bxb` matrix of `1`s: the result should be identical to `m` if `b` is the correct blockiness.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 6 bytes
```
xø«Åγ¿
```
[Try it online!](https://tio.run/##yy9OTMpM/f@/4vCOQ6sPt57bfGj////R0UY6qNAYAmN1hqRMLAA "05AB1E – Try It Online")
Port of [my Mathematica answer](https://codegolf.stackexchange.com/a/237032/78410).
Take a list of lists of 2's and 3's as input.
```
x       # Pop a and push a, 2a
 ø      # Transpose
  «     # Concatenate
   Åγ   # Run-length encode
     ¿  # GCD
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 118 bytes
```
f=->m,z=$.=m.size{x=[]
(0...$.).step(z){|r|y=[]
(0...m[0].size).step(z){|c|y+=[m[r][c]]*z}
x+=[y]*z}
x==m ?z:f[m,z-1]}
```
[Try it online!](https://tio.run/##1VPNCoMwDL73KTx40E1LvQ66PUjIYRNlOxSGbqC1PrurFrX@oNtxFNrk@5J@SUOz961smpSHZxFI7lIuaP6QSVVwQOIxSqlLfZq/kqcn/UplqhwIAQy7YIuPVXnkICBDiBEPsiaF9ktjcS6cizyloKXCCOsGCECEGOiDBXoZM9JGoPeod9vV8p1lqAkyXjCEsJUE2zM8s1NZJ7tv9ykGtGu0pEZ4qGOi/WOY0Z@2MUfsQoYHYtPuN7D5I84638csb2VSW9ii8sXUvkbWrrKm@I8MEoI0ucb3Sgn1dPTv0T/nAw "Ruby – Try It Online")
* Recursively (starting from one dimension length) try block sizes, return first valid value.
* Reconstructs the matrix by taking a value at each block, repeating it z times to form each block. Finally compare with original input.
Tried a [different approach](https://tio.run/##1VPLisMgFN37FV0NSScVsx1w5kNEigmGFrQTagZSH9@e2khTTUM7XRZB7z3nvi8e/6rT0OBh8y1NVkIoodprnkPFBa87Y7XtMaFAQs7q3VaJfc0znRurbP@JFeyO7KDaX8VTHkrWZh9fjWBdxw@5Az1kQvwYW9kKY1IRROlar7Vz3rJ3AwGElJQW/kGFP0EsvVD4u7yql3PhRylQCXILMJmgBYdYCzyKXdGY9rl8dQlgXGOU6gZPdSS5XzQL@dM25khcyDQglHb/AJsPcdb5cyzSFjb1CLur/G5r/0aWQkVbfEeGAkDHb2astO2qIZK64Qw "Ruby – Try It Online") by slicing each block but ended at 125B
```
->m{(1..m.size).select{|z|x=[]
m.each_slice(z){|s|x+=s.transpose.each_slice(z).map(&:flatten)}
x.all?{|b|b==[b[0]]*z*z}}.max}
```
[Answer]
# [Python 3](https://docs.python.org/3/), 108, 104, 97 bytes
-7 by borowing @m90's better control flow
```
f=lambda M,n=1:n<len(M)and f(M,n+1)or all(X==[*sum(zip(*n*[X[::n]]),())]for X in[M,[*zip(*M)]])*n
```
[Try it online!](https://tio.run/##1VPBasMwDL3nK0xOtmeKw25h/oTcA8IHjyYs4KqhcQfrz2eOU4ydhXY7DkMivfdkSRYav9zHGV/nuVfWnN6PhjQCVVXjm@2QNszgkfTUYy8VO1@IsZa2SgGfrid6G0bKkUMLdY1aM0EZ071XtWRAaATwoGiY5zjOrpvcpMqyBKi0LgCk8CdYlf8L/63u3nIWNlgrkyExOirkjj71Vl4mkTLkfG7fI1YsqS/JE9FYQ5b3b6o1d97BFkmqiC8j874fYJvX2/T8HEu8nQk9wrZ1/5jWr5Gdm5Lp/UdG@80owo4QRaD7NJY6RpZ1cn6dSGAO02gHR5kucrwuyHgZ0FEneh/F5m8 "Python 3 – Try It Online")
[Old version](https://tio.run/##1VPBasMwDL3nK0RgYAd3OOwW8Cf4HjA@eDRhAVcNjTfYDv31zHGKsbPQbsdhSKT39CzJQuOnezvjyzz3wprT69GAZCh4g2DwCMZa0gqhqun9RL6GkVRYqVY1DWpNGaFU9@cLtDCgkkxVIUJSzy1iBM/1RLLrAZ8OV9shkZTOrpvcJMqyVKrWulCKM3@CVfs/89/65i1nYYO1MhkS1TGC78Sn3srzRMlDzsf2TbFiSX1JnojGGrK8f4tac@cdbJGkivgyPO/7DrZ5vU3Pj7HE25nQPWxb949p/RrZuSmZ3n9ktN@MIuwICFDdh7HEUVjWzPk1g8A8T6MdHKG6yPGmgPEyoCOO9V5F528 "Python 3 – Try It Online")
Straight-forward approach; tries successively smaller block sizes until a working one is found.
Old, longer but more readable version:
```
f=lambda M,n=0:n and all(X[i::n]==X[::n]for i in range(n)for X in[M,[*zip(*M)]])and n or f(M,~-n%-~len(M))  
```
[Try it online!](https://tio.run/##1VPBasMwDL3nK0RgYBd3OOwW8CfkHjA@eDTZDJ4aElPYDv31zE6KsbPQbsdhiKX39CLJQsOnez/jyzz3wuqP15OGhqHgNYLGE2hrSStNXaMSopXh7s8jGDAIo8a3jiANQOsB2TB5@DIDOTRUKRrkCJ7rScOuR3w6Xm2HpKEUYHbd5CZRlqWUlVKFlJz5s1iVv5n/VjcvnMAu1spkSFTHCL4Tn3orzxMlX3I@tm@KFUvqS/JENNaQ5f1b1Jo772CLJFXEl@F533ewzetten6MJd7OhO5h27p/TOvXyM6fkun9R0b5zSiWHQEBsrtoSxyFsGgubN7CPE@DNY5QVeR4XcAwGnTEsd6r6PwN "Python 3 – Try It Online")
[Answer]
# JavaScript (ES6), ~~101 92 90~~ 89 bytes
*Saved 4 bytes thanks to @Neil, and ~~7~~ 8 more bytes from there*
```
m=>m.reduce(o=>++w*m.some(r=>r.some(v=>v-m[y-y%w][x-x++%w],x=0)*++y|x%w,y=0)|y%w?o:w,w=0)
```
[Try it online!](https://tio.run/##1VHLboMwELznK6xIUewAlrm2Mj21P5CjywGBSakwTm3CQ02/nToQIUNR0h4rSzA7s@vZ9b5HVaRjlR1Lr5AJ71LaCRoIrHhyijmUNHCceiewloJDRQM1oIoGlSdY67WbOmSN1ziOAW5DCdo5TntuNrXbmuBs9Cf5ULu1CTrFP06Z4nCb6i0yFlHykuV83xYxJAiXcl@qrDhAhPUxz0q4fi3WCKdSPUfxG9SABuBzBUDOSyAABbyKcqjRo6FiWWiZc5zLA0yhQIb8Qh1jfhiuGCOuOT3yzd81X/8aXc5F7dGgTJixeswgC/l2NOjEqiS95318rRg4qz/LZ2THHia@f8savKcTzBmri/FlyHTuG9zs9WYz3@esaGFDt7h53z@29Wtm4SZre/9RCb8B "JavaScript (Node.js) – Try It Online")
### Commented
```
m =>                 // m[] = input matrix
m.reduce(o =>        // for each row in m[], using o as an accumulator:
  ++w *              //   increment w
  m.some(r =>        //   for each row r[] in m[]:
    r.some(v =>      //     for each value v in r[]:
      v -            //       compare v with
      m[y - y % w]   //       the top-left corner of the submatrix of
      [x - x++ % w], //       width w in which we're currently located
                     //       increment x afterwards
      x = 0          //       start with x = 0
    )                //     end of inner some()
    * ++y            //     increment y
    | x % w,         //     force to fail if w does not divide x
    y = 0            //     start with y = 0
  )                  //   end of outer some()
  | y % w            //   force to fail if w does not divide y
  ?                  //   if failed:
    o                //     leave o unchanged
  :                  //   else:
    w,               //     update it to w
  w = 0              //   start with o = w = 0
)                    // end of reduce()
```
[Answer]
# [R](https://www.r-project.org/), ~~143~~ ~~139~~ 132 bytes
Or **[R](https://www.r-project.org/)>=4.1, 118 bytes** by replacing two `function` occurences with `\`s.
```
function(M,k=dim(M))for(n in k:1)if(!any(k%%n,tapply(M,(row(M)-1)%/%n*max(k)+(col(M)-1)%/%n,function(x)sum(table(x)|1)-1)))return(n)
```
[Try it online!](https://tio.run/##1VJBTsMwELzzinKItAtbkYW0AqQ@oTc@YEItWUmcyjgilfr3YAdhWhI3oJ6qucSzM2OPHdPJVScbnVtVa1hTsXpTFawRZW1Az5SeFc@MSsK10DsokkSTFdttuXNaMPWHk84Zk7tE31SihQJvIa/LH5ZCdovvTQVWvJYb971nr0A0G9sYDRo7CZWwRrXg6KuwyCElBySmB3o5nrCbMDHSvcNg5pF@KQLC2nsef3vSA3068B6n9GfKaDmeMQnvXUS8J/oEeE02pok2jnSe8Jyc9ZnZeCZH7zHCoHvfp@kX@Qvzz52/myyH@zOdhcnbOWxxITy6Rtz/nt0n "R – Try It Online")
Bases heavily on the `split` idea from [my answer to *Square chunk my matrix*](https://codegolf.stackexchange.com/a/229851/55372) (although here we have rectangular matices, which are a little trickier).
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 27 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
SgLR.Δδôøy©δô€`εSDËsgt®Q*}P
```
Inputs as list of strings.
[Try it online](https://tio.run/##yy9OTMpM/f8/ON0nSO/clHNbDm85vKPy0EoQ41HTmoRzW4NdDncXp5ccWheoVRvw/3@0krZ2fr42ECjpIDMhDFRmLAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfaVL6P/gdJ8gvXNTIorPbTm85fCOykMrQYxHTWsSzm0NdjncXZxecmhdoFZtwP9anf/R0UraSrE60Ur5@flgWjtfSUdJGyKmra2dnw8kwCJQJlQtRDQfSRrGyIeZlA9m6eCgISrAXJhdMIOgfLDZMDPxioMMgbsAzoSZCnYS3I3obIR/4K7DyoYwkAIDg42wDylIcDKRVecjO4rm3NhYAA).
**Explanation:**
```
S                # Convert the (implicit) input-list of strings to a flattened list of
                 # characters
 g               # Pop and push its length
  L              # Pop and push a list in the range [1,length]
   R             # Reverse it to [length,1]
    .Δ           # Find the first block-size `y` which is truthy for:
      δ          #  Map over each string in the (implicit) input-list:
       ô         #   Split it into substrings of size `y`
        ø        #  Zip/transpose; swapping rows/columns
           δ     #  Map over each inner list again:
         y  ô    #   And split it into blocks of size `y` again
          ©      #  Also store block-size `y` in variable `®` (without popping)
             €`  #  Flatten this list of lists of blocks one level down
      ε          #  Map over each `y` by `y` sized block (or smaller, if we couldn't
                 #  divide a row or column into size `y` with builtin `ô`)
       S         #   Convert the current block to a flattened list of characters
        D        #   Duplicate it
         Ë       #   Check if all characters are the same
          s      #   Swap so the list of characters is at the top again
           g     #   Push its length
            t    #   Take the square-root of that
             ®Q  #   Check if this is equal to block-size `®`
               * #   Check if both are truthy
      }P         #  After the map: check if all were truthy
                 # (after which the found result is output implicitly)
```
[Answer]
# [Core Maude](http://maude.cs.illinois.edu/w/index.php/The_Maude_System), ~~319~~ 317 bytes
```
mod M is pr LIST{Nat}*(op size to z). ops b n : Nat Nat ~> Nat . var A B M N
W X Y Z :[Nat]. eq b(M,W)= n(M,W s W). ceq n(M,W s N)= n(M,W N)if X A Y B Z :=
M /\ W rem N + z(M)quo W rem N =/= 0 or A + B == 1 and z(X)quo W quo N(z(X)rem W
quo N)== z(X A Y)quo W quo N(z(X A Y)rem W quo N). eq n(M,W s N)= N[owise]. endm
```
To obtain the result, reduce the `b` function with the matrix as a flattened list, and the row length. (Maude has a matrix type, but we're not using it.)
### Example Session
```
Maude> --- Blockiness 1
> 
> red b(
>     0,
>     1
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1,
>     3
> ) .
result NzNat: 1
Maude> 
> red b(
>     0 1
>     0 0,
>     2
> ) .
result NzNat: 1
Maude> 
> red b(
>     0 0 0 1 1 0 0 0
>     0 0 0 1 1 0 0 0,
>     8
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1 0 0 0
>     1 1 1 0 0 0
>     0 0 0 0 0 0
>     0 0 1 1 1 1,
>     6
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1 1 1
>     1 1 1 1 1
>     1 1 1 1 1
>     1 1 1 1 1,
>     5
> ) .
result NzNat: 1
Maude> 
> 
> --- Blockiness 2
> 
> red b(
>     1 1
>     1 1,
>     2
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 0 0
>     0 0 0 0,
>     4
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 1 1 0 0 0 0
>     0 0 1 1 0 0 0 0,
>     8
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 1 1 0 0 0 0
>     0 0 1 1 0 0 0 0
>     1 1 0 0 0 0 0 0
>     1 1 0 0 0 0 0 0,
>     8
> ) .
result NzNat: 2
Maude> 
> 
> --- Blockiness 3
> 
> red b(
>     0 0 0 0 0 0 1 1 1
>     0 0 0 0 0 0 1 1 1
>     0 0 0 0 0 0 1 1 1,
>     9
> ) .
result NzNat: 3
Maude> 
> red b(
>     1 1 1 0 0 0 1 1 1
>     1 1 1 0 0 0 1 1 1
>     1 1 1 0 0 0 1 1 1
>     0 0 0 1 1 1 0 0 0
>     0 0 0 1 1 1 0 0 0
>     0 0 0 1 1 1 0 0 0,
>     9
> ) .
result NzNat: 3
Maude> 
> 
> --- Blockiness 4
> 
> red b(
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0,
>     8
> ) .
result NzNat: 4
Maude> 
> red b(
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1,
>     12
> ) .
result NzNat: 4
```
### Ungolfed
```
mod M is
    pr LIST{Nat} * (op size to z) .
    ops b n : Nat Nat ~> Nat .
    var A B M N W X Y Z : [Nat] .
    eq b(M, W) = n(M, W s W) .
    ceq n(M, W s N) = n(M, W N)
        if X A Y B Z := M
        /\ W rem N + z(M) quo W rem N =/= 0
        or A + B == 1
        and z(X) quo W quo N (z(X) rem W quo N)
            == z(X A Y) quo W quo N (z(X A Y) rem W quo N) .
    eq n(M, W s N) = N [owise] .
endm
```
For a given `N`, we essentially test *every* partition of the input list into five sublists (including ones where `A` and `B` aren't single elements). Then we verify if that partition corresponds to an actual counter-example for `N`. This is very slow — the last case for blockiness 4 takes several minutes to run. But it terminates!
---
Saved 2 bytes by removing two pairs of parentheses. Parentheses don't often cost bytes in Maude because they can often replace a space due to tokenization weirdness, but in this case there were two pairs of parentheses next to each other.
]