mjhjmtu

ACROSS:

A. a square

C. a multiple of N Across

E. (C Down) $times$ (I Across)

G. a square root of A Down

I. a square root of D Down

J. (J Across) $times$ (K Across) = (F Down) $times$ (M Down)

K. (J Across) $times$ (K Across) = (F Down) $times$ (M Down)

L. a divisor of H Down

N. a divisor of O Down

P. a divisor of I Down

R. a multiple of P Down

S. a square of Q Down

DOWN:

A. a square of G Across

B. a square

C. not a square

D. $1000-$(A Across)

F. a power

H. (L Across) $times$ (N Across)

I. a multiple of P Across

L. (P Down) $times$ (Q Down)

M. a power

O. a multiple of N Across

P. a divisor of R Across

Q. a square root of S Across

Edit:

No numbers begin with digit 0 and all numbers are different. So the correct answer should contain twelve distinct 2-digit numbers and twelve distinct 3-digit numbers.

I found an answer:

I didn't really use a whole lot of logic to solve this. It was mostly a couple educated guesses and a whole lot of trial and error.

324 376
6 988 7
19 1 26
 48 54 
20 3 47
9 122 9
781 729

Technically, I think I have a cheaterpants solution to this:

I will definitely try to find a better answer though.