Du brauchst einen Algorithmus, der dir eine "volle" Lösung erstellt. Davon lässt du solange zufällig Zellen weg, wie die Lösung noch eindeutig ist.
Konzentriere dich zuerst auf das Spiel selber, nicht die Oberfläche. Schreibe eine Klasse für die Ein- und Ausgabe, die erst mal ganz simpel auf der Konsole arbeitet. Die kannst du dann später durch eine GUI-Klasse (wie schon vorgeschlagen nach dem MVC-Pattern) ersetzen.