[Løst] Hjelp med recursive backtracking

[Fred7555]

Hei, har nå i oppgave å løse en sudoku via brute-force.

 

Så vidt jeg vet, er den beste måten å bruke recursive backtracking, siden du må ha muligheten til å kunne bevege deg bakover om du finner ikke-løsbare ruter.

 

Har prøvd litt på dette nå, og får det ca. til å funke, og det ser slik ut hittil:

Med rad-og kolonnenummer:

 

 

http://pastebin.com/9xBC3jt5

 public void solveWithout(int row, int col) {
 if(row > squares.length - 1) {
  solutions.insert(squares);
  return;
 }
 if(squares[row][col] instanceof PrefilledSquare)
  nextWithout(row, col);
 else {
  for (int value = 1; value <= squares.length; value++) {
	  if(squares[row][col].legalValue(value)) {
		  squares[row][col].setValue(value + "");
		  nextWithout(row, col);
	  }
  }
	  squares[row][col].setValue(0 + "");
 }
}

public void nextWithout(int row, int col) {
 if(col < squares.length - 1)
  solveWithout(row, ++col);
 else
  solveWithout(++row, 0);
}

 

 

 

Med neste-peker i Square:

 

 

http://pastebin.com/6RssQBfc

 public void fillInnRemainingOfBoard() throws Exception {
 if (next == null && this.legalValue(this.getNumericValue()))
  return;

 if (this instanceof PrefilledSquare)
  next.fillInnRemainingOfBoard();
 else {
  for (int value = 1; value <= row.getLength(); value++) {
if (legalValue(value)) {
 value = value + "";
 next.fillInnRemainingOfBoard();
}
  }
  value = 0 + "";
 }
}

 

 

 

Men jeg har problemer med 3 ting:

- Eneste muligheten å "lagre" løsningen på, er å møte på en exception (enter å kaste selv eller å ha feil i koden). Om jeg bare bruker return og lar den avslutte seg selv, oppdateres ikke value i Square. Dette skjønner jeg ikke helt hvorfor skjer, da jeg kan sa at verdiene lagres om jeg skriver de ut inni metoden.

 

- Jeg skal finne alle mulige løsningen for brett. Jeg har klart å finne 1 løsning nå, men jeg er usikker hvordan jeg skal finne alle. Slik jeg har det nå, så avslutter den om den er på siste rute og verdien stemmer, fordi da er brettet utfylt.

Tenker at jeg må få den til å begynne på nytt med kanskje en høyere verdi eller lignende, men klarer ikke å finne en god måte å løse det på.

 

- Koden klarer 6x6 og 9x9-brett, men fortsetter i det uendelige om den får høyere. Alt er dynamisk i forhold til det den leser inn, og i koden er A = 10, B = 11 ol., så usikker hvorfor den ikke klarer de, da selve metoden er akkurat lik.

Square har en value (som er String) og to metoder, getValue() og getNumericValue(), og den siste er brukt for sjekking om lovlige tall.

 

Noen som ser problemer med koden eller har ideer til løsninger på problemene?

 

Takk

Endret 7. april 2013 av Fred7555

[SkoMedHull]

Det siste punktet tror jeg rett og slett handler om kjøretiden til algoritmen din. Tviler på at den kjører evig, men husk at antallet mulige løsninger vil stige noe helt latterlig fort. I tillegg til dette vil programmet ditt bruke massevis av tid på å regne feil, og deretter gå tilbake.

 

Kort oppsummert tror jeg nok at det bare er programmet som bruker lang tid.

 

Når det gjelder det å finne alle løsninger så er det vel bare å lagre hver løsning når du finner den, spore så langt tilbake som du kan, og deretter velge en annen verdi en den som har blitt plassert tidligere.

 

Alt dette kommer til å ta helt grusomt lang tid, og jeg tror i grunn du bør finne en bedre tilnærming til problemet. Det å løse sudoku er ikke en grusomt vanskelig oppgave, hva med å løse den slik du ville løst den for hånd? Når mennesker klarer å løse det innen rimelig tid så burde det jo være en rimelig effektiv algoritme, eller hva?

[Fred7555]

Det kan ha rett med at det kun tar lang tid. Siden 9x9 kun brukte 1 sekund, testet jeg bare rundt 10 sekunder. Vil la den gå en god stund for å teste. Du hadde rett, den klarte det etter en stund.

 

Har planer om å innføre raskere algoritmer, men slik oppgaven er definert så skal brute-forcing brukes. Så må få den til før jeg begynner med andre algoritmer.

 

Tenker noe ala det samme med å alle løsninger, men sliter med å finne hvordan å begynne på neste.

Si at jeg nå har funnet en løsning, og på den siste ruten. Jeg kan da komme meg tilbake til den 1. ruten, men hvordan vet jeg hvilken verdi den brukte?

Må jeg ha en slags liste med alle verdier alle rutene ha brukt, for å så øke den 1. med en?

Om jeg eventuelt finner en til løsning slik, så er det kanskje en til løsning med at rute x og rute y kan bytte verdier i slutten av brettet.

 

Kan være mye enklere enn det jeg tenker, men klarer ikke å finne noe gjennomførbar metode akkurat nå.

Endret 7. april 2013 av Fred7555

[jonny]

Jeg ville gjort noe slikt:

 

public void fillInnRemainingOfBoard() {
 if (this instanceof PrefilledSquare) {
   if (next == null)
  board.saveSolution();
   else
  next.fillInnRemainingOfBoard();
 }
 else {
   for (int value = 1; value <= row.getLength(); value++) {
  if (legalValue(value)) {
    value = value + "";
    if (next == null)
	  board.saveSolution();
    else
	  next.fillInnRemainingOfBoard();
  }
   }
   value = 0 + "";
 }
}

 

Da må hver enkelt "square" vite hvilket "board" de er en del av, riktignok, slik at "saveSolution"-metoden kan lagre unna alle verdiene på brettet. Jeg har ikke testet denne koden, kan godt være jeg har glemt å tenke på noe.

[Fred7555]

Fant ut feilen med koden min.

 

Den i 1. eksempel skrev seg selv til 0 uansett etterpå, og eneste måten å lagre verdiene var en exception, da den hoppet ut av stacken.

 

Den i 2. eksmpel oppførte seg likt, siden jeg lagret løsningen i Board-klassen, og Square alt hadde tilbakestilt seg når det var gjort.

 

Eksempelet over funket bra, og klarer å finne alle løsninger.

Takk for hjelpen