| Bytes | Lang | Time | Link |
|---|---|---|---|
| 385 | Python3 | 250516T204508Z | Ajax1234 |
| 270 | JavaScript ES6 | 170504T141710Z | Arnauld |
| 051 | Jelly | 170504T170542Z | Jonathan |
| 034 | Brachylog | 170504T205739Z | Fatalize |
Python3, 385 bytes
E=enumerate
V=lambda B:len(K:=[tuple(i)for i in B if'.'not in i])==len({*K})
W=['1','0']
def f(b):
q=[b]
for b in q:
if(O:=[(x,y)for x,r in E(b)for y,v in E(r)if'.'==v])==[]:return b
x,y=O[0]
for i in W:
B=eval(str(b));B[x][y]=i;L=B+[*zip(*B)]
if any(any(j.count(k)>len(j)/2 for k in W)for j in L)or any(i*3in''.join(k)for k in L):continue
if V(B)and V(zip(*B)):q+=[B]
JavaScript (ES6), 274 270 bytes
Takes input as a 2D array, where empty cells are marked with 2. Prints all possible solutions to the console.
f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))
How it works
The first part of the code uses the M() function to check the validity of the current board, both horizontally and vertically.
M = z =>
!a.some((r, y) =>
/(0|1),\1,\1/.exec(
s = r.map((v, x) =>
(
v = z ? v : a[x][y],
b -= v & 1,
c -= !v,
m |= v & 2,
v
),
b = c = w / 2
)
) ||
b * c < 0 |
o[b * c || s] &
(o[s] = 1),
o = {}
)
It maps a full row or column to the string s. This is actually an array coerced to a string, so it looks like "1,2,2,0,2,2".
It uses:
- The regular expression
/(0|1),\1,\1/to detect 3 or more consecutive identical digits. - The counters b and c to keep track of the number of ones and zeros. Both counters are initialized to w / 2 and decremented each time a one or a zero (respectively) is encountered. This leads to either:
- b = c = 0 → b * c = 0 → the line is complete and correct (as many zeros as ones)
- b > 0 AND c > 0 → b * c > 0 → the line is not complete but correct so far (we don't have more than w / 2 zeros or more than w / 2 ones)
- b < 0 OR c < 0 → b * c < 0 → the line is invalid
- The flag m (for 'missing') which is non-zero if there's at least one remaining two on the board.
- The object o to keep track of all line patterns encountered so far.
If the board is invalid, we stop immediately. If the board is valid and complete, we print it to the console. Otherwise, the second part of the code attempts to replace each 2 with either a zero or a one with recursive calls:
[0, 1].map(n =>
(p = a[y][x]) == n |
p > 1 && (
a[y][x] = n,
f(a, z = (x + 1) % w, y + !z),
a[y][x] = p
)
)
Demo
f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))
console.log('Example #1')
f([
[1,2,2,0,2,2],
[2,2,0,0,2,1],
[2,0,0,2,2,1],
[2,2,2,2,2,2],
[0,0,2,1,2,2],
[2,1,2,2,0,0]
])
console.log('Example #2')
f([
[2,2,2,2,2,2,2,1,2,2],
[2,0,0,2,2,0,2,2,1,2],
[2,0,2,2,1,2,2,0,2,0],
[2,2,1,2,2,2,1,2,2,2],
[1,2,1,2,2,2,2,2,2,1],
[2,2,2,2,2,2,2,1,2,2],
[2,0,2,2,1,2,2,2,0,2],
[2,2,2,2,1,1,2,2,2,0],
[2,0,2,0,2,2,1,2,2,0],
[0,2,2,2,0,2,2,2,1,2]
])
Jelly, 53 51 bytes
ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ
Takes a list of lists representing the grid, containing 0, 1, and 2 (the spaces). Returns a list of lists of lists, each list of lists is in the same format (although with no 2s) and represents a possible solution to the input.
Try it online! (this wont run any of the question's test cases due to memory limitations - all 2nSpaces grids are created as a list of list of lists of integers - but I've put a relatively hefty case there with a single solution). The footer separates out and formats the grids.
Pure brute force method - implements the rules and checks them for each grid that could be formed by replacing any of the 2s with 1s or 0s.
ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3 - all contiguous slices of length 3 for €ach list
Ḅ - convert all results from binary
F - flatten into one list
f - filter keep values in:
0,7 - 0 paired with 7: [0,7]
L - length
SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
Ḥ - double
L - length (number of rows - OK since square)
n - not equal? (vectorises)
Ṁ - maximum (1 if any not equal)
ȯÇ - ... or last link (1) as a monad
⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
Q - unique
⁻ - not equal?
ȯÇ - ... or last link (2) as a monad
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F - flatten
ṣ©2 - split at 2s and copy the result to the register
L - length (# of such slices)
’ - decrement (# of 2s)
0,1 - 0 paired with 1
ṗ - Cartesian power (all binary lists of length # of 2s)
® - recall value from register (the flat version split at 2s)
ż@€ - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
F€ - flatten €ach
s€L - split €ach into chunks of length length(input) (into rows)
Ðḟ - filter discard if:
Ç - call last link(3) as a monad
Ðḟ - filter discard if:
$ - last two links as a monad:
Z - transpose
Ç - call last link(3) as a monad
Brachylog, 34 bytes
{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&
This is pretty damn slow, so the test case on TIO is 4x4. I am currently running the 6x6 test case on my computer to see how much time it takes.
This takes a list of lists as input. The unknown values should be indicated with variables, that is with all-uppercase strings (and they should all be different, as otherwise you would be indicating that some cells must have the same value)
Explanation
We constrain the values to be in {0,1}, then we try instantiations of the variables until one respects all 3 rules. This is why this is so slow (because it will try all of them until finding one; and because in that case Brachylog is not implemented well enough so that constraints can be imposed before trying a possible matrix).
& Output = Input
{ }ᵐ² Map two levels on the Input (i.e. each cell):
ℕ<2 The cell is either 0 or 1
&≜ Assign values to all cells
{ } Define predicate 2:
d? The Input with no duplicates is still the Input
(i.e. all rows are different)
?ọᵐctᵐ= All occurences of 1s and 0s for each rows are equal
&{ }ᵐ Map on rows:
ḅlᵐ Get the lengths of runs of equal values
⌉<3 The largest one is strictly less than 3
&\↰₂ Apply predicate 2 on the transpose of the Input
(i.e. do the same checks but on columns)