Sachverhalt: Sachverhalt: A. Im Jahr 1987 zog die deutsche Staatsangehörige Y._ mit ihrem damaligen Ehemann und dem gemeinsamen Sohn A._ (1983) nach Neuseeland, wo sie ihren zweiten gemeinsamen Sohn B._ (1988) zur Welt brachte. Nach dem Wegzug ihres Mannes nach Japan liess sie sich mit den Söhnen innerhalb von Neuseeland in Hastings nieder, wo sie X._ kennen lernte. Aus dieser Beziehung gingen die beiden Kinder C._ (geb. 1993) und D._ (geb. 1994) hervor. Die Parteien haben nie geheiratet, wohnten aber längere Zeit zusammen. Nach ihrer Trennung im Jahr 1997 wegen Gewalttätigkeiten von X._ lebte Y._ mit ihren Kindern allein in Hastings, wobei jener alle 14 Tage ein begleitetes Besuchsrecht von zwei Stunden hatte ("protection order" des Bezirksgerichts Hastings vom 5. März 1997). Am 14. Mai 1998 erwirkte X._ eine Anordnung des Familiengerichts Hastings, die Y._ und den Kinder die Ausreise aus Neuseeland verbot. Am 1. Oktober 1999 erhielt sie jedoch die Erlaubnis, ihre kranke Mutter in Deutschland zu besuchen, wobei sie verpflichtet wurde, die Kinder am 28. Januar 2000 nach Hastings zurückzubringen. Am 14. Mai 1998 erwirkte X._ eine Anordnung des Familiengerichts Hastings, die Y._ und den Kinder die Ausreise aus Neuseeland verbot. Am 1. Oktober 1999 erhielt sie jedoch die Erlaubnis, ihre kranke Mutter in Deutschland zu besuchen, wobei sie verpflichtet wurde, die Kinder am 28. Januar 2000 nach Hastings zurückzubringen. B. Nachdem Y._ mit den Kindern nach Ablauf der Frist in Deutschland verblieben war, leitete X._ am 8. März 2000 ein Verfahren nach dem Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung (HEntfÜ, SR 0.211.230.02) ein. Mit ihren Entscheiden vom 26. Januar 2001 und 14. Mai 2001 ordneten sowohl das Amtsgericht Düsseldorf als auch das Oberlandesgericht Düsseldorf die Rückführung der beiden Kinder an. Nachdem das Bundesverfassungsgericht die dagegen erhobene Verfassungsbeschwerde am 21. August 2001 nicht angenommen hatte, floh die Mutter mit ihren Kindern Ende August in die Schweiz. In der Folge leitete der Kindsvater am 28. November 2001 erneut ein Verfahren nach HEntfÜ ein. Mit Entscheid vom 2. April 2002 verpflichtete das Richteramt Dorneck-Thierstein die Mutter zur Rückführung der Kinder nach Hastings. In Gutheissung ihres Rekurses wies das Obergericht des Kantons Solothurn den Antrag auf Rückgabe der beiden Kinder mit Urteil vom 12. August 2002 ab. Mit Urteil vom 18. November 2002 hob das Bundesgericht den Entscheid des Obergerichts auf (5P.310/2002), worauf dieses den Rekurs der Mutter am 16. Dezember 2002 abwies. Nachdem das Bundesverfassungsgericht die dagegen erhobene Verfassungsbeschwerde am 21. August 2001 nicht angenommen hatte, floh die Mutter mit ihren Kindern Ende August in die Schweiz. In der Folge leitete der Kindsvater am 28. November 2001 erneut ein Verfahren nach HEntfÜ ein. Mit Entscheid vom 2. April 2002 verpflichtete das Richteramt Dorneck-Thierstein die Mutter zur Rückführung der Kinder nach Hastings. In Gutheissung ihres Rekurses wies das Obergericht des Kantons Solothurn den Antrag auf Rückgabe der beiden Kinder mit Urteil vom 12. August 2002 ab. Mit Urteil vom 18. November 2002 hob das Bundesgericht den Entscheid des Obergerichts auf (5P.310/2002), worauf dieses den Rekurs der Mutter am 16. Dezember 2002 abwies. C. In der Folge bemühten sich die neuseeländische Zentralbehörde und das Bundesamt für Justiz im Einvernehmen mit den Parteien um eine gütliche Regelung der Rückführung. Das Bundesamt erklärte die Bemühungen am 27. Mai 2003 für gescheitert. Am 25. Juli 2003 ersuchte X._ beim Oberamt Dorneck-Thierstein um Vollstreckung des rechtskräftigen Rückführungsentscheides. Das Oberamt erliess am 25. September 2003 den Vollstreckungsbefehl und verpflichtete Y._ zur Rückführung der beiden Kinder nach Neuseeland. In einer Einsprache verlangte diese jedoch eine vorgängige kinderpsychiatrische Abklärung. In Gutheissung der Einsprache und Aufhebung des Vollstreckungsbefehls verfügte das Oberamt am 15. Januar 2004 u.a. Folgendes: 4. Dem KJPD Bruderholz wird (...) ein Gutachten über die Kinder (...) in Auftrag gegeben, das aussagekräftig das Kindeswohl bei einer zwangsweisen Rückführung (Reisefähigkeit, Trennung Mutter Kind etc.) abklärt. Ebenfalls ist zu überprüfen, ob die Kinder vom Alter, ihrer Urteilsfähigkeit und Reife her zum Rückführungsantrag zu befragen sind und ihr Wille entsprechend zu berücksichtigen ist. 5. Der Gesuchsteller hat dem Oberamt bekanntzugeben und beweiskräftig zu belegen, wie die Organisation einer schonenden Rückkehr, der Empfang und die Betreuung der Kinder vorgesehen ist. 6. Der Gesuchsteller hat bei einer ev. Zwangsvollstreckung dafür zu sorgen, dass die Vollstreckungskosten vorgeschossen werden. 7. Das Vollstreckungsverfahren wird bis zum Vorliegen des kinderpsychiatrischen Gutachtens sistiert. Dagegen hat X._ am 29. Januar 2004 Beschwerde erhoben. Das Verwaltungsgericht des Kantons Solothurn wies diese mit Urteil vom 30. März 2004 ab. Dagegen hat X._ am 29. Januar 2004 Beschwerde erhoben. Das Verwaltungsgericht des Kantons Solothurn wies diese mit Urteil vom 30. März 2004 ab. D. Gegen diesen Entscheid hat X._ am 19. April 2004 staatsrechtliche Beschwerde eingereicht mit den Begehren um dessen Aufhebung und um aufschiebende Wirkung. Ferner hat er ein Gesuch um unentgeltliche Rechtspflege gestellt. Das Verwaltungsgericht und die Beschwerdegegnerin haben in ihren Vernehmlassungen vom 23. April bzw. 10. Mai 2004 auf Abweisung der Beschwerde geschlossen. Mit Präsidialverfügung vom 13. Mai 2004 ist dieser die aufschiebende Wirkung erteilt worden in dem Sinn, dass die Erstellung des vom Oberamt Dorneck-Thierstein mit Verfügung vom 15. Januar 2004 angeordneten kinderpsychologischen Gutachtens zu unterbleiben habe und die auf Grund der Verfügung des Präsidenten des Verwaltungsgerichts des Kantons Solothurn vom 3. Februar 2004 beim Verwaltungsgericht hinterlegten Identitätspapiere dort zu belassen seien.