Sudoku w javie, problem

0

Chciałbym napisać prosty program który będzie rozwiązywał łatwe tablice sudoku w javie. Napisałem do tego momentu i program wypełnia tablice ale robi błędy. Będę wdzięczny za każdą pomoc. Jak pisałem mój program ma znajdować rozwiązanie prostych tablic (nie musi znajdować ilości rozwiązań- jeśli dana tablica ma kilka rozwiązań). Czekam na jakieś wskazówki i opinie. Jestem początkujący więc krytyka mile widziana.

package Sudoku;

import java.util.*;

class Sudoku
{
        int[][] sudoku = { { 1, 4, 3,   5, 0, 0,   0, 0, 0 },
                           { 0, 0, 5,   0, 0, 0,   0, 2, 0 },
                           { 0, 0, 0,   0, 0, 6,   0, 0, 0 },
                            
                           { 4, 0, 0,   0, 9, 0,   7, 0, 5 },
                           { 6, 0, 0,   8, 0, 3,   0, 0, 2 },
                           { 9, 0, 1,   0, 7, 0,   0, 0, 8 },
                            
                           { 0, 0, 0,   2, 0, 0,   0, 0, 0 },
                           { 0, 8, 0,   0, 0, 0,   2, 0, 0 },
                           { 0, 0, 0,   0, 0, 8,   1, 6, 7 } };
        
    int tab_temp[][]=new int[9][9];
    
    public Sudoku()
    {
        wypelnij_temp();
        wypelnij();

    }

    
    int wypelnij()
    {
        int a=1, liczba, licz=0;
        int i2=0,j2=0;
  
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
               
                if(sudoku[i][j]==0)
                {
                    for(a=1;a<=9;a++)
                    {
                       
                       if(przeszukaj(i,j,a)==-1) 
                       {
                         sudoku[i][j]=a;
                          
                       }
                    }  
                }
            }
        }
 
        return -1;
    }
    
        int wypelnij_temp()
    {
        int a=1, liczba, licz=0;
        int i2=0,j2=0;
  
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
               
                if(sudoku[i][j]==0)
                {
                    for(a=1;a<=9;a++)
                    {
                       
                       if(przeszukaj(i,j,a)==-1) 
                       {
                        //   sudoku[i][j]=a;
                           tab_temp[i][j]=1;
                       }
                       
                      
                    }
                    
                }
            }
        }
 
        return -1;
    }
    
int przeszukaj(int y, int x, int liczba) //y wiersz,  x kolumna
{
int i=0, j=0;
   for(i=0;i<9;i++)   // sprawdz czy liczba wystepuje w wierszu lub kolumnie
   {
   if(sudoku[y][i]==liczba) {
   return 0;}
   if(sudoku[i][x]==liczba) {
   return 0;} 
   }
  
   int x1, y1;
   x1=3*(x/3);  // poczatek kolumny kwadratu 3 na 3
   y1=3*(y/3);  //  .....   wiersza  ......
   for(i=y1;i<=(y1+2);i++) // sprawdzanie czy liczba wystepuje w kwadracie.
     {
     for(j=x1;j<=(x1+2);j++)
         {                     
         if(sudoku[i][j]==liczba) 
             { 
             return 0;
             }    
         }                          
     }
     return -1;
}

int czyWpisal(int i,int j)
{
    if(sudoku[i][j]==0) return 0;
    if(sudoku[i][j]!=0) return -1;
    return 1;
}

    
        	public String wyswietl(){
		String wys="";
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++) wys+=""+sudoku[i][j]+"\t";
			wys+="\n"; 
		}
		return wys;
	}
                
                        	public String wyswietlTemp(){
		String wys="";
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++) wys+=""+tab_temp[i][j]+"\t";
			wys+="\n"; 
		}
		return wys;
	}
    
}

class Glowna
{
    public static void main(String[] args)
    {
        Sudoku s1=new Sudoku();
        
        System.out.println(s1.wyswietl());
        System.out.print(s1.wyswietlTemp());
    }
    
}
0

a jakie bledy robi?

pozdrawiam

0

Program wypluwa błędną tablice:

1 4 3 5 8 9 6 7 0
8 9 5 7 4 1 3 2 0
7 2 0 3 0 6 9 8 4
4 3 8 6 9 2 7 1 5
6 7 0 8 5 3 4 9 2
9 5 1 4 7 0 0 3 8
5 6 9 2 3 7 8 4 0
3 8 7 9 6 5 2 0 0
2 0 4 0 0 8 1 6 7

Cały problem w tym, że nie wiem jak zmodyfikować ten algorytm żeby poprawiał te zera które zostają.

0

No tak, a może jakiś opis algorytmu, co jest do czego? Tak z kodu czytać to ciężko by było zgadnąć zwłaszcza, że nie działa. Dla przykładu w piątym wierszu jest zero zamiast jedynki. Ale nie może być jedynki, bo ta jest już w kolumnie. Dlatego ci algorytm nie wypełnia do końca. Pewnie są błędy w samej logice, stąd też przydałby się opis.

0

Właśnie tego nie wiem jak zrobić- algorytm leci po kolei i sprawdza każdy wiersz i kolumnę poprzez wywołanie w metodzie wypełnij metody przeszukaj. Jeśli argument "a" nie powtarza się w podanym wierszu, kolumnie i małym trójkącie(3x3) to jest on wpisany. Tutaj pojawia się problem- algorytm może wypełnić dane pole błędnie- bo bierze pierwszą liczbę która pasuje a nie tą która jest poprawna. Dlatego później występują błędy w postaci zostawienia zera. Tutaj nie wiem co dalej:/. Jak zrobić, żeby algorytm jeśli zostawi zero(czyli nie wpisze żadnej liczby w miejscu gdzie było zero) cofnął się do miejsc w których wpisał poprzednio i spróbował wpisać inną wartość tak, żeby w końcu ostatecznie poprawnie wypełnić tablice.

0

No, to się wyjaśniło. problem jest raczej w algorytmie, a nie w javie. Nie możesz zrobić tak jak piszesz, bo to nie działa, czego przykład też masz. Sudoku zwykle jest tak napisane, że ma tylko jedno rozwiązanie. Jeżeli wstawisz na siłę pierwszą pasującą liczbę, a w rozwiązaniu w tym miejscu jest inna, to oczywiście dojdzie gdzieś do sprzeczności. Proponuję rozważyć takie sposoby:
Pierwszy: wykorzystanie algorytmu rekurencji z powrotami - w pierwsze wolne pole wstawiasz po kolei wszystkie liczby, które tam mogą być i przechodzisz do następnego. W momencie dojścia do sprzeczności należy powrócić i sprawdzać dla kolejnej liczby... trochę to zawiłe w tłumaczeniu. W google znajdziesz opis problemu przy hasłach 8 hetmanów i ruchy skoczka.
Drugi sposób: do każdego pola przypisana jest tablica możliwych wartości. Jeżeli tablica ma tylko jeden element, to jest on wpisywany i już się nie zmieni. Po wpisaniu aktualizowane są tablice dla wiersza, kolumny i kwadratu poprzez wykreślenie ze wszystkich tej liczby, bo już tam nie może być. Wstawianie odbywa się również, jeżeli w wierszu, kolumnie lub polu występuje jakaś liczba tylko w jednej takiej tablicy.
Ten sposób pozwala na rozwiązanie łatwiejszych diagramów, przy trudniejszych może być konieczność wpisania jakiejś liczby z tablicy i sprawdzenia co będzie dalej, a potem znów powrotu. Tutaj można całe diagramy wrzucić w kolejkę, bo nie powinno ich być dużo.

0

Dziękuję za odpowiedź i pomoc. Teraz kolejny problem- chciałbym dodać do programu klasę, która generowałaby losową tablice sudoku. Zapisywałaby ją w tablicy dwuwymiarowej "sudoku" a następnie zostałaby rozwiązana przez algorytm. Czy ktoś ma pomysł jak wygenerować taką tablice?

0

Z generowaniem tablicy to jest raczej większy problem, niż z rozwiązaniem już gotowej. Gdzieś czytałem ile trzeba podać liczb, żeby uzyskać jednoznaczne rozwiązanie i to było chyba 27 albo 28. Podanie każdej następnej już na samym początku może prowadzić do tego, że diagram nie będzie miał rozwiązania. Ja to widzę tak, że rozwiązujesz sobie diagram, który ma zadaną jakąś małą ilość liczb. W przypadku, kiedy czegoś się nie da rozstrzygnąć wybierasz losowo. Ostatecznie masz cały diagram wypełniony prawidłowo. Teraz z niego trzeba wybrać pewną ilość pól i sprawdzić, czy da się rozwiązać. Tak pewnie można zrobić, ale gdybym miał się za to zabierać, to przedtem poszukałbym jakieś materiały na temat sudoku. Może to całkiem inaczej trzeba podejść do tego?...

1 użytkowników online, w tym zalogowanych: 0, gości: 1