Sudoku, exempel
Uppgiften är att konstruera ett program i vilket man kan lösa Sudoku-problem. Som du säkert vet utgörs en Sudoku-plan av ett rutnät med nio rader och nio kolumner. Denna plan är dessutom indelad i nio delplaner, s.k. block, bestående av tre rader och tre kolumner. Detta demonstreras i nedanstående figur.
Sudoku, exempel
Varje ruta kan innehålla en siffra eller vara blank. I varje Sudoku-problem är siffrorna i vissa rutor givna. Dessa har markerats med grå bakgrundsfärg i exemplet. Det gäller sedan att fylla i planen på ett sådant sätt att varje rad, kolumn och block innehåller exakt en förekomst av siffrorna ett till nio, så som visas i nästa figur.
Löst Sudoku
När man kör programmet kan man ladda in ett nytt Sudoku-problem genom att klicka på knappen New och sedan välja en textfil som innehåller problemet. Filen skall innehålla nio rader med nio tecken i varje rad. Om ett tecken inte är en siffra i intervallet ett till nio tolkas det som en blank ruta. Filen med problemet ovan har t.ex. följande utseende:
3...8....
...7....5
1........
......36.
..2..4...
.7.......
....6.13.
.452.....
......8..Den som kör programmet kan sedan försöka fylla i lämpliga siffror i rutorna. Om man försöker fylla i en siffra som redan finns i den aktuella raden eller kolumnen eller i det aktuella blocket skall programmet vägra att lägga in denna siffra och istället ge ifrån sig ett ljud (beep). Man skall också kunna ångra siffror man fyllt i genom att klicka på knappen Undo. Detta skall kunna göras inte bara för den sista siffran, utan för alla inmatade siffror. På motsvarande sätt skall man med hjälp av knappen Redo återställa siffror som man ångrat. Om man vill att programmet skall visa lösningen på problemet klickar man på knappen Solve. Knappen Make Solvable, slutligen, tar bort de senaste siffrorna man lagt in tills alla siffror i planen är korrekta och problemet därför är lösbart.
I uppgiften skall den s.k. Model-View-Controller tekniken användas för att strukturera programmet på ett bra sätt. Detta kan du läsa om t.ex. i avsnitt 12.10 i kursboken. Laborationen kan lösas i tre steg där man i varje steg koncentrerar sig på var och en av dessa komponenter.
I detta steg skall du konstruera en modell som beskriver en Sudoku-plan. Det naturliga sättet att beskriva en sådan är att använda sig av en tvådimensionell array med nio rader och nio kolumner där elementen har typen int och bara får innehålla värden i intervallet 0-9. Man låter då värdet 0 betyda en blank ruta. Konstruera därför en klass med namnet MySudokuModel som innehåller en sådan array som privat instansvariabel. Modellen skall vara så utformad att den alltid garanterar att det inte finns flera siffror av samma slag i en rad, en kolumn eller ett block. (Däremot skall det vara möjligt att lägga in data som beskriver icke lösbara problem eller problem som inte har en unik lösning.)
Klassen MySudokuModel skall ha två konstruktorer, en parameterlös som initierar modellen så att alla rutor blir tomma och en kopieringskonstruktor som skapar en kopia av en redan existerande modell.
I klassen skall också metoden toString överskuggas (override). Denna skall ge samma resultat som metoden getBoard (se nedan).
Utforma klassen så att den (till att börja med) implementerar gränssnittet SudokuModel:
public interface SudokuModel {
void clear();
void setBoard(int row, int col, int val);
void setBoard(String input);
int getBoard(int row, int col);
String getBoard();
boolean isLegal(int row, int col, int val);
boolean solve();
boolean isSolvable();
boolean isUnique();
}Metoden clear är enkel. Den skall nollställa alla rutorna i modellen.
Det första versionen av setBoard skall sätta värdet i en viss ruta. Det andra versionen av setBoard skall sätta värden i alla rutorna. Som indata får den en String som skall bestå av nio rader med nio tecken på varje rad enligt formatet angivet ovan. Raderna avgränsas med tecknet '\n'. Alla tecken som inte är siffror i intervallet 1-9 skall uppfattas som tomma rutor och skall alltså representeras med talet 0 i modellen. Båda versionerna av setBoard skall kontrollera att man inte försöker placera flera siffror av samma slag i en rad, i en kolumn eller i ett block. Om man försöker det ska en exception av typen IllegalArgumentException genereras. Den andra versionen av setBoard skall dessutom kontrollera att den String den får som indata innehåller det rätta antalet rader och antal tecken per rad. Om så inte är fallet skall den också då generera en exception av typen IllegalArgumentException. Exceptions som genereras skall innehålla lämpliga felmeddelanden.
Det första versionen av getBoard skall avläsa värdet i en viss ruta. Den andra versionen av getBoard skall som resultat ge en String som innehåller värdet av samtliga rutor. Formatet på denna String skall vara samma in inparametern till den andra versionen av setBoard. Blanka rutor kan t.ex. representeras med tecknet ´.´.
Metoden isLegal skall kontrollera att det går att lägga in det angivna värdet val i en viss ruta. Den skall alltså kontrollera att det i så fall inte kommer att finnas flera siffror av samma slag i en rad, i en kolumn eller i ett block. Tänk på att det alltid skall gå att lägga in en blank ruta och att om modellen hittills är legal så skall man alltid i en ruta kunna lägga in samma siffra som den redan innehåller.
De tre sista metoderna i gränssnittet ovan blir förstås lite mer komplicerade. Metoden solve skall försöka lösa Sudoku-problemet utgående från det tillstånd modellen befinner sig i. Om solve hittar en lösning skall den fylla i lösningen i modellen och returnera värdet true. Om solve inte hittar någon lösning skall den lämna modellen i samma tillstånd som när den anropades och returnera värdet false. Metoden solve skall vara rekursiv enligt följande idé:
För att denna teknik skall vara effektiv är det viktigt att man väljer en tom ruta för vilken det finns så få siffror som möjligt som kan läggas i rutan. Man kan därför välja en ruta för vilken summan av antalet tomma rutor i dess rad, kolumn och block är minimal.
Metoden isSolvable blir nu enkel. Eftersom metoden solve returnerar ett värde av typen boolean kan man anropa denna för att se om ett problem är lösbart. Men om man anropar metoden solve för den aktuella modellen kommer den att fyllas i med lösningen och detta är inte meningen att isSolvable skall göra. Ett enkelt knep är därför att skapa en kopia av den aktuella modellen och anropa metoden solve för kopian.
Metoden isUnique kan faktiskt göras förvånansvärt enkel med hjälp av ett annat knep. Man anpassar solve eller den rekursiva hjälpmetod som solve använder så att det finns en tillståndsvariabel som håller reda på om man letar efter en lösning eller om man vill avgöra om det finns flera lösningar. När solve har funnit en lösning undersöker den tillståndsvariabeln. Om den säger att men vill avgöra om det bara finns en lösning så bortser den från lösningen som just hittats och markerar att man inte längre söker på detta sätt. Därefter fortsätter sökningen. Om man hittar en lösning till kommer solve säga att det finns en lösning och då finns minst två, alltså lösningen är inte unik.
När du fått färdigt klassen MySudokuModel så här långt kan du testa den med hjälp av det färdiga klassen SudokuTest1. Denna innehåller en main-metod som låter dig läsa in Sudoku-problem från filer och som försöker lösa dem med hjälp av din modell-klass. Det finns ett stort antal filer med Sudoku-problem i komprimerade mappen SudokuProblem.zip. Där finns också filer med felaktiga data så att man kan testa att metoden getBoard gör de rätta kontrollerna.
Gå inte vidare till nästa moment förrän din modell-klass fungerar som den skall.
Nu skall klassen MySudokuModel utökas så att den kan användas i Model-View-Controller konceptet. Utgå från följande gränssnitt med namnet Model:
import java.beans.*;
import java.io.*;
public interface Model extends Serializable {
void addPropertyChangeListener(PropertyChangeListener l);
void removePropertyChangeListener(PropertyChangeListener l);
}och justera sedan gränssnittet SudokuModel från förra avsnittet så att det utökar detta gränssnitt:
public interface SudokuModel extends Model {
som tidigare
}Detta innebär att din klass MySudokuModel måste implementera de två metoderna i gränssnittet Model. Använd dig av hjälpklassen PropertyChangeSupport på det sätt som diskuteras i kursboken och som visas i Javas API. Förutom att implementera de två metoderna måste klassen MySudokuModel utökas så att den rapporterar ändringar i modellen till eventuella lyssnare. På tre ställen måste det rapporteras att hela modellen ändrats. Detta gäller när man nollställt hela modellen, när man lagt in ett nytt sudoku-problem med hjälp av den andra versionen av metoden setBoard samt när man löst problemet och fyllt i lösningen i modellen. Då kan man använda metoden firePropertyChange. Man skall också i den första versionen av metoden setBoard rapportera när en enstaka ruta ändrats. Det är då lämpligt att använda metoden fireIndexedPropertyChange. Denna skall som extra parameter ha ett index som anger vilken egenskap som ändrats. Man kan där ge rutans nummer (radnummer * 9 + kolumnnummer).
Vyn utgörs förstås av av en panel som innehåller ett rutnät med nio gånger nio rutor såsom framgår av figurerna ovan. Skriv en klass MySudokuView som beskriver denna panel. Se då till att de nio blocken också markeras. Eftersom vyn skall vara lyssnare till händelser som uppstår i modellen måste den implementera gränssnittet PropertyChangeListener. Konstruktorn måste ha två parametrar; en referens av typen SudokuModel och en referens av typen SudokuController. Den första behövs för att vyn skall kunna fråga modellen vilket värde som finns i en viss ruta. Den andra behövs för att de enskilda rutorna i vyn också kommer att fungera som inmatningsfält i vilka användaren kan skriva data. (Detta diskuteras senare).
Börja med att i vyns konstruktor skapa rutnätet. Ett bra tips är att låta varje ruta vara ett objekt av en egendefinierad subklass Square till JTextField. Låt objekt av klassen Square förutom texten (som den ärver från sin superklass) även innehålla rutans rad och kolumnnummer. Detta underlättar programmeringen senare när du skall skriva lyssnare för inmatade värden.
När händelser av typen PropertyChangeEvent mottas från modellen skall vyn uppdateras. Om händelsen är av subklassen IndexedPropertyChangeEvent skall bara den enskilda ruta det gäller ändras, annars måste alla rutorna ritas om. I det senare fallet kan alla rutor som inte är tomma sättas som icke ändringsbara. Det är nämligen då fråga om att man läst in ett nytt problem eller att man visar en lösning.
När du kommit så här långt kan du testa din vyklass med hjälp av testprogrammet SudokuTest2. Detta program visar vyn och kopplar ihop den med din modellklass. När du klickar på knapparna Fill och Clear i programmet skall din vy uppdateras.
Användaren måste kunna skriva in siffror i rutorna. För att rutorna i vyn också skall kunna användas för inmatning, måste man i klassen MySudokuView lyssna efter händelser i dessa. Det hade kunnat gå att använda händelser av typen ActionPerformed, men det hade haft nackdelen att användaren hade varit tvungen att trycka på Enter-tangenten efter varje inmatning. Det är därför bättre att lyssna efter händelser av typen keyReleased. Man kan då direkt, genom att anropa metoden getKeyChar, känna vilket tecken användaren skrev.
Vyn måste rapportera till controllern vad som matats in. Controllern skall implementera gränssnittet SudokuController, vilket är mycket enkelt. Det innehåller bara en metod, med namnet input. Det är denna metod som vyn skall anropa för att skicka det inmatade tecknet vidare till controllern.
public interface SudokuController {
boolean input(int row, int col, char value);
}Metoden input ger som resultat värdet true om värdet som skickades vidare till controllern var korrekt och kunde läggas in i modellen. Annars returneras false. I så fall kan man i vyn anropa metoden beep och lägga i en blank text i den aktuella rutan.
Det är alltså omöjligt att helt upprätthålla skillnaden mellan vy och controller. Men om man inte behandlar några indata i vyn utan bara skickar dem vidare, så kan strukturen hållas ren i alla fall.
Du kan använda testprogrammet SudokuTest2 också för att testa att din vyklass tar hand om inmatade data på rätt sätt. När ett tecken matats in skall programmet skriva ut vilket tecken som matats in och i vilken ruta det skett.
Controllern skall sköta kommunikationen med användaren och uppdatera modellen. Grafiskt utgörs controllern av raden med knappar längst ner i fönstret. Den tar också emot rapporter från vyn när användaren skrivit något i en ruta. Konstruera en klass med namnet MySudokuController. Klassen skall vara en JPanel och dessutom implementera gränssnittet SudokuController. Den måste förstås också kunna lyssna efter knapptryckningar.
Börja med att skriva den del av klassen som skall exekveras när användaren klickar på knappen New. Då skall en fildialogruta (se t.ex. avsnitt 14.7 i kursboken) öppnas i vilken användaren kan välja en fil med ett Sudoku-problem. Om filen inte går att öppna skall ett felmeddelande visas. Därefter skall informationen från filen läggas in i modellen. Ett lämpligt felmeddelande skall visas om filen visade sig innehålla felaktiga data. Man skall också visa ett felmeddelande om det inte finns någon lösning till problemet eller om en lösning inte är unik.
Skriv därefter metoden input som anropas från vyn när användaren skrivit ett tecken i en ruta. När detta är gjort går det att börja testa hela programmet. Detta kan du göra med hjälp av den färdiga klassen SudokuMain som skapar modellen, vyn och controllern, kopplar ihop dem och lägger in vyn och controllern i ett fönster. Så här ser denna klass ut:
import java.awt.*;
import javax.swing.*;
public class SudokuMain extends JFrame {
public SudokuMain() {
SudokuModel model = new MySudokuModel();
MySudokuController ctrl = new MySudokuController(model);
MySudokuView view = new MySudokuView(model, ctrl);
add(view, BorderLayout.CENTER);
add(ctrl, BorderLayout.SOUTH);
setSize(420,420);
setLocationRelativeTo(null); // centrera
setVisible(true);
setDefaultCloseOperation(EXIT_ON_CLOSE);
}
public static void main(String[] arg) {
new SudokuMain();
}
}Det kan sedan vara lämpligt att skriva de delar av programmet som hanterar tryckningar på knappen Solve. Tänk på att ett problem kan ha blivit olösbart om användaren skrivit in siffror i rutorna. Vill du lösa problemet kan du behöva ladda in ursprungsproblemet igen.
Ett frilligt tillägg är att implementera den historiemekanism som behövs för att hantera tryckningar på knapparna Undo, Redo och Make solvable. Man måste för varje drag, d.v.s. siffra som användaren placerar ut i spelplanen, komma ihåg vilken ruta det gäller och rutans tidigare och nya värde. För detta kan man använda objekt av en enkel hjälpklass Move (som man förstås måste konstruera själv). Man kan sedan lägga Move-objekt i en lista som utökas för varje nytt drag. Om användaren klickar på Undo kan man då gå tillbaka och återställa det tidigare värdet i en ruta. Man kan emellertid inte då utan vidare stryka de drag som är gjorda från listan eftersom det skall vara möjligt att göra Redo. Om användaren har backat och sedan skriver in något nytt värde i en ruta kan man emellertid ta bort de drag som ligger senare i listan.
När användaren klickar på Make solvable kan man helt enkelt backa i listan tills problemet är lösbart. Det bör man också göra när användaren klickat på Solve.
Utöka lyssnaren för tangenttryckningar i vyn så att man kan använda piltangenterna för att förflytta sig mellan de olika rutorna.
Lägg till två menyer, File och Actions. Låt t.ex. File-menyn innehålla alternativen Clear, New/Open, Save och Exit och Actions-menyn alternativen Solve, Test och Make solvable. Alternativet New/Open skall göra samma sak som knappen New och Save skall spara data från modellen i en valfri fil så att användaren vid ett senare tillfälle kan läsa in filen och fortsätta. (Det kan vara lämpligt att göra modellen lösbar innan man sparar den.) Alternativet Test kan testa och meddela om modellen har en lösning och i så fall om lösningen är unik. Tips. Skapa en JMenuBar i main-metoden och ge en referens till den som parameter till controllerns konstruktor. Då kan controllern skapa menyerna och alternativen och ta hand om händelserna.
Lägg till en metod i controllern som genererar ett nytt Sudoku-problem. Du kan t.ex. lägga till ett menyalternativ Generate som aktiverar metoden. Ett sätt att skapa ett nytt problem är att börja med att i ett antal (t.ex. 9) slumpmässigt valda rutor lägga in slumpmässiga värden. Därefter låter man programmet lösa problemet och struntar i att det eventuellt finns flera lösningar. I nästa steg utgår man från den funna lösningen som naturligtvis i sig är unik. Man väljer sedan en ruta i taget slumpvis och låter den bli blank. Detta fortsätter man med så länge som lösningen fortfarande är unik.
Skicka in er källkodsfiler inkl. de interface som ges i uppgiften (d.v.s. .java-filer). Inga andra filer och ej testprogrammen. Alla filer ska skickas lösa, d.vs. ej inuti .zip eller dylikt).
Placera inte era java-filer i något paket, d.v.s. de ska inte innehålla någon rad package .... Det förenklar för oss när vi ska testköra era program.
Tänk på att följa de allmänna riktlinjerna för programmeringsstil som anges på sidan Laborationer.