Come generare una scheda -complet- sudoku? Errore algoritmo

Question

Sto provando a generare una scheda simile a Sudoku completa (cioè, ogni cella riempita con un numero). È per qualcos'altro che non ha nulla a che fare con il sudoku, quindi non mi interessa raggiungere un sudoku con quadrati bianchi che possono essere risolti, o qualsiasi cosa abbia a che fare con il sudoku. Non so se sai cosa intendo.

Ho fatto questo in Java:

private int sudokuNumberSelector(int x, int y, int[][] sudoku) { 


    boolean valid = true; 
    String validNumbers = new String(); 
    int[] aValidNumbers; 
    int squarexstart = 0; 
    int squareystart = 0; 
    int b = 0;       // For random numbers 
    Random randnum = new Random(); 
    randnum.setSeed(new Date().getTime()); 

    // Check numbers one by one 
    for(int n = 1; n < 10; n++) { 

     valid = true; 

     // Check column 
     for(int i = 0; i < 9; i++) { 
      if(sudoku[i][y] == n) { 
       valid = false; 
      } 
     } 

     // Check file 
     for(int j = 0; j < 9; j++) { 
      if(sudoku[x][j] == n) { 
       valid = false; 
      } 
     } 

     // Check square 
     switch (x) { 
     case 0: case 1: case 2: squarexstart = 0; break; 
     case 3: case 4: case 5: squarexstart = 3; break; 
     case 6: case 7: case 8: squarexstart = 6; break; 
     } 

     switch (y) { 
     case 0: case 1: case 2: squareystart = 0; break; 
     case 3: case 4: case 5: squareystart = 3; break; 
     case 6: case 7: case 8: squareystart = 6; break; 
     } 

     for(int i = squarexstart; i < (squarexstart + 3); i++) { 
      for(int j = squareystart; j < (squareystart + 3); j++) { 
       if(sudoku[i][j] == n) { 
        valid = false; 
       } 
      } 
     } 

     // If the number is valid, add it to the String 
     if(valid) { 
      validNumbers += n; 
     } 
    } 

    if(validNumbers.length() != 0) { 

     // String to int[] 
     aValidNumbers = fromPuzzleString(validNumbers); 

     // By this random number, return the valid number in its position 
     Log.d(TAG, "NUMBERS: " + validNumbers.length()); 

     // Select a random number from the int[] 
     b = randnum.nextInt((aValidNumbers.length)); 


     return aValidNumbers[b]; 

    } else { 
     return 0; 
    } 
} 

Questo metodo viene chiamato da questo pezzo di codice:

int[][] sudoku = new int[9][9]; 

for(int i = 0; i < 9; i++) { 
      for(int j = 0; j < 9; j++) { 
       sudoku[i][j] = sudokuNumberSelector(i, j, sudoku); 
      } 
     } 

ma non è così facile come sembrava! Quando l'algoritmo ha generato una parte della scheda come questo, e il ciclo è sulla cella in grassetto:

|||164527389||| 
|||983416257||| 
|||257938416||| 
|||719352648||| 
|||3256791**0**0||| 
|||000000000||| 
|||000000000||| 
|||000000000||| 
|||000000000||| 

ci sono numeri per mettere in questa cella, perché tutti i numeri secondo le regole di i sudoku sono già sulla colonna, riga o quadrato!

È un incubo per me. C'è un modo per farlo funzionare? Se no, credo che devo rifare tutto come se stessi facendo un gioco di Sudoku.

Grazie in anticipo.

Answer 1

Il problema è che non è possibile generare una scheda completa utilizzando numeri casuali nella maggior parte dei casi, è necessario utilizzare il backtracking nei casi in cui non è possibile eseguire la cella successiva. Ho scritto una volta un gioco di sudoku, quindi ecco il pezzo di codice che genera una tavola piena.

Questa è la classe della cella.

public class SudokuCell implements Serializable { 

    private int value; 
    private boolean filled; 
    private HashSet<Integer> tried; 

    public SudokuCell() { 
     filled = false; 
     tried = new HashSet(); 
    } 

    public boolean isFilled() { 
     return filled; 
    } 

    public int get() { 
     return value; 
    } 

    public void set(final int number) { 
     filled = true; 
     value = number; 
     tried.add(number); 
    } 

    public void clear() { 
     value = 0; 
     filled = false; 
    } 

    public void reset() { 
     clear(); 
     tried.clear(); 
    } 

    public void show() { 
     filled = true; 
    } 

    public void hide() { 
     filled = false; 
    } 

    public boolean isTried(final int number) { 
     return tried.contains(number); 
    } 

    public void tryNumber(final int number) { 
     tried.add(number); 
    } 

    public int numberOfTried() { 
     return tried.size(); 
    } 
} 

Ecco la classe Field (è molto utile mantenere tutti i dati in un solo oggetto).

public class SudokuField implements Serializable { 

    private final int blockSize; 
    private final int fieldSize; 
    private SudokuCell[][] field; 

    public SudokuField(final int blocks) { 
     blockSize = blocks; 
     fieldSize = blockSize * blockSize; 
     field = new SudokuCell[fieldSize][fieldSize]; 
     for (int i = 0; i < fieldSize; ++i) { 
      for (int j = 0; j < fieldSize; ++j) { 
       field[i][j] = new SudokuCell(); 
      } 
     } 
    } 

    public int blockSize() { 
     return blockSize; 
    } 

    public int fieldSize() { 
     return fieldSize; 
    } 

    public int variantsPerCell() { 
     return fieldSize; 
    } 

    public int numberOfCells() { 
     return fieldSize * fieldSize; 
    } 

    public void clear(final int row, final int column) { 
     field[row - 1][column - 1].clear(); 
    } 

    public void clearAllCells() { 
     for (int i = 0; i < fieldSize; ++i) { 
      for (int j = 0; j < fieldSize; ++j) { 
       field[i][j].clear(); 
      } 
     } 
    } 

    public void reset(final int row, final int column) { 
     field[row - 1][column - 1].reset(); 
    } 

    public void resetAllCells() { 
     for (int i = 0; i < fieldSize; ++i) { 
      for (int j = 0; j < fieldSize; ++j) { 
       field[i][j].reset(); 
      } 
     } 
    } 

    public boolean isFilled(final int row, final int column) { 
     return field[row - 1][column - 1].isFilled(); 
    } 

    public boolean allCellsFilled() { 
     for (int i = 0; i < fieldSize; ++i) { 
      for (int j = 0; j < fieldSize; ++j) { 
       if (!field[i][j].isFilled()) { 
        return false; 
       } 
      } 
     } 
     return true; 
    } 

    public int numberOfFilledCells() { 
     int filled = 0; 
     for (int i = 1; i <= fieldSize; ++i) { 
      for (int j = 1; j <= fieldSize; ++j) { 
       if (isFilled(i, j)) { 
        ++filled; 
       } 
      } 
     } 
     return filled; 
    } 

    public int numberOfHiddenCells() { 
     return numberOfCells() - numberOfFilledCells(); 
    } 

    public int get(final int row, final int column) { 
     return field[row - 1][column - 1].get(); 
    } 

    public void set(final int number, final int row, final int column) { 
     field[row - 1][column - 1].set(number); 
    } 

    public void hide(final int row, final int column) { 
     field[row - 1][column - 1].hide(); 
    } 

    public void show(final int row, final int column) { 
     field[row - 1][column - 1].show(); 
    } 

    public void tryNumber(final int number, final int row, final int column) { 
     field[row - 1][column - 1].tryNumber(number); 
    } 

    public boolean numberHasBeenTried(final int number, final int row, final int column) { 
     return field[row - 1][column - 1].isTried(number); 
    } 

    public int numberOfTriedNumbers(final int row, final int column) { 
     return field[row - 1][column - 1].numberOfTried(); 
    } 

    public boolean checkNumberBox(final int number, final int row, final int column) { 
     int r = row, c = column; 
     if (r % blockSize == 0) { 
      r -= blockSize - 1; 
     } else { 
      r = (r/blockSize) * blockSize + 1; 
     } 
     if (c % blockSize == 0) { 
      c -= blockSize - 1; 
     } else { 
      c = (c/blockSize) * blockSize + 1; 
     } 
     for (int i = r; i < r + blockSize; ++i) { 
      for (int j = c; j < c + blockSize; ++j) { 
       if (field[i - 1][j - 1].isFilled() && (field[i - 1][j - 1].get() == number)) { 
        return false; 
       } 
      } 
     } 
     return true; 
    } 

    public boolean checkNumberRow(final int number, final int row) { 
     for (int i = 0; i < fieldSize; ++i) { 
      if (field[row - 1][i].isFilled() && field[row - 1][i].get() == number) { 
       return false; 
      } 
     } 
     return true; 
    } 

    public boolean checkNumberColumn(final int number, final int column) { 
     for (int i = 0; i < fieldSize; ++i) { 
      if (field[i][column - 1].isFilled() && field[i][column - 1].get() == number) { 
       return false; 
      } 
     } 
     return true; 
    } 

    public boolean checkNumberField(final int number, final int row, final int column) { 
     return (checkNumberBox(number, row, column) 
       && checkNumberRow(number, row) 
       && checkNumberColumn(number, column)); 
    } 

    public int numberOfPossibleVariants(final int row, final int column) { 
     int result = 0; 
     for (int i = 1; i <= fieldSize; ++i) { 
      if (checkNumberField(i, row, column)) { 
       ++result; 
      } 
     } 
     return result; 
    } 

    public boolean isCorrect() { 
     for (int i = 0; i < fieldSize; ++i) { 
      for (int j = 0; j < fieldSize; ++j) { 
       if (field[i][j].isFilled()) { 
        int value = field[i][j].get(); 
        field[i][j].hide(); 
        boolean correct = checkNumberField(value, i + 1, j + 1); 
        field[i][j].show(); 
        if (!correct) { 
         return false; 
        } 
       } 
      } 
     } 
     return true; 
    } 

    public Index nextCell(final int row, final int column) { 
     int r = row, c = column; 
     if (c < fieldSize) { 
      ++c; 
     } else { 
      c = 1; 
      ++r; 
     } 
     return new Index(r, c); 
    } 

    public Index cellWithMinVariants() { 
     int r = 1, c = 1, min = 9; 
     for (int i = 1; i <= fieldSize; ++i) { 
      for (int j = 1; j <= fieldSize; ++j) { 
       if (!field[i - 1][j - 1].isFilled()) { 
        if (numberOfPossibleVariants(i, j) < min) { 
         min = numberOfPossibleVariants(i, j); 
         r = i; 
         c = j; 
        } 
       } 
      } 
     } 
     return new Index(r, c); 
    } 

    public int getRandomIndex() { 
     return (int) (Math.random() * 10) % fieldSize + 1; 
    } 
} 

E infine la funzione che riempie il tavolo da gioco

private void generateFullField(final int row, final int column) { 
    if (!field.isFilled(field.fieldSize(), field.fieldSize())) { 
     while (field.numberOfTriedNumbers(row, column) < field.variantsPerCell()) { 
      int candidate = 0; 
      do { 
       candidate = field.getRandomIndex(); 
      } while (field.numberHasBeenTried(candidate, row, column)); 
      if (field.checkNumberField(candidate, row, column)) { 
       field.set(candidate, row, column); 
       Index nextCell = field.nextCell(row, column); 
       if (nextCell.i <= field.fieldSize() 
         && nextCell.j <= field.fieldSize()) { 
        generateFullField(nextCell.i, nextCell.j); 
       } 
      } else { 
       field.tryNumber(candidate, row, column); 
      } 
     } 
     if (!field.isFilled(field.fieldSize(), field.fieldSize())) { 
      field.reset(row, column); 
     } 
    } 
} 

Il punto è che si salva i numeri che hai già provato per ogni cella prima di passare. Se si ha il vicolo cieco, è sufficiente provare un altro numero per la cella precedente. Se nessuno è possibile, cancella quella cella e torna indietro di una cella. Prima o poi lo farai.(Attuatore richiede una piccola quantità di tempo).

Answer 2

Dovrai implementare un algoritmo backtracking.

• Per ciascuna delle 81 posizioni, generare l'insieme 1 a 9.
• Ripetere fino risolto
  • risolvere un'unica posizione. Scegli un numero dal set.
  • Rimuovere quel numero da tutti i set nella stessa riga, colonna e quadrato.
  • Se si verifica un conflitto, tornare a una posizione nota e risolvere una posizione diversa.

Probabilmente si dovrà utilizzare le funzioni ricorsive in modo da poter tornare indietro.

Answer 3

iniziare con un risolta Sudoko simili:

ABC DEF GHI 
329 657 841 A 
745 831 296 B 
618 249 375 C 

193 468 527 D 
276 195 483 E 
854 372 619 F 

432 716 958 G 
587 923 164 H 
961 584 732 I 

E poi permutate esso passando colonne e righe di commutazione. Se cambi solo all'interno dei seguenti gruppi ABC, DEF, GHI, il Sudoku è ancora risolto.

(colonne commutazione)

Una versione permutati:

BCA DFE IGH 
293 675 184 A 
457 813 629 B 
186 294 537 C 

931 486 752 D 
762 159 348 E 
548 327 961 F 

324 761 895 G 
875 932 416 H 
619 548 273 I 

e dopo alcuni più permutazione (righe commutazione):

BCA DFE IGH 
293 675 184 A 
186 294 537 C 
457 813 629 B 

931 486 752 D 
548 327 961 F 
762 159 348 E 

875 932 416 H 
619 548 273 I 
324 761 895 G 

Answer 4

sufficiente generare un numero casuale tra 1 e 9 e vederlo si adatta alla cella data [i] [j] ti promette un nuovo insieme di numeri ogni volta che ogni numero di cella viene generato casualmente in base al tempo corrente del sistema.

public int sudokuNumberSelector(int i, int j, int[][] sudoku) { 
    while (true) { 
     int temp = (int) ((System.currentTimeMillis()) % 9) + 1;//Just getting some random number 
     while (temp < 10) { 
     boolean setRow = false, setColomn = false, setBlock = false; 
      for (int a = 0; a < 9; a++) { 
       if (sudoku[a][j] == temp) { 
        setRow = true; 
        break; 
       } 
      } 

      for (int a = 0; a < 9; a++) { 
       if (sudoku[i][a] == temp) { 
        setColomn = true; 
        break; 
       } 
      } 
      for (int a = i - (i % 3); a < i - (i % 3)+ 3; a++) { 
       for (int b = j - (j % 3); b < j - (j % 3)+3; b++) { 
        if (sudoku[a][b] == temp) { 
         setBlock = true; 
         a = 3; 
         b = 3; 
        } 
       } 
      } 
      if(setRow | setColomn | setBlock == false){ 
       return temp; 
      } 
      temp++; 
     } 
    } 
} 

Answer 5

Il problema è che si utilizzano stringhe. Prova un algoritmo ricorsivo usando interi. Questo algoritmo sarà utile per un sudoku di qualsiasi dimensione. Mentre la scelta di numeri casuali all'interno di ogni chiamata funziona, ci vorrà molto più tempo. Se scegli una serie di numeri casuali da passare se la cella successiva non funziona, non utilizzerai più lo stesso numero. Questo algoritmo creerà un puzzle unico ogni volta.

public class Sudoku { 
    //box size, and game SIZE ==> e.g. size = 3, SIZE = 9 
    //game will be the game 
    private int size, SIZE; 
    private int[][] game; 

    public Sudoku(int _size) { 
     size = _size; 
     SIZE = size*size; 
     game = generateGame(); 
    } 

    //This will return the game 
    private int[][] generateGame() { 
     //Set everything to -1 so that it cannot be a value 
     int[][] g = new int[SIZE][SIZE]; 
     for(int i = 0; i < SIZE; i++) 
      for(int j = 0; j < SIZE; j++) 
       g[i][j] = -1; 

     if(createGame(0, 0, g)) 
      return g; 
     return null; 
    } 

    //Create the game 
    private boolean createGame(int x, int y, int[][] g) { 
     //An array of integers 
     Rand r = new Rand(SIZE); 

     //for every random num in r 
     for(int NUM = 0; NUM < size; NUM++) { 
      int num = r.get(NUM); 

      //if num is valid 
      if(isValid(x, y, g, num)) { 
       //next cell coordinates 
       int nx = (x+1)%SIZE, ny = y; 
       if(nx == 0) ny++; 

       //set this cell to num 
       g[x][y] = num; 

       //if the next cell is valid return true 
       if(createGame(nx, ny, g)) return true; 

       //otherwise return false 
       g[x][y] = -1; 
       return false; 
      } 
     } 
     return false; 
    } 

    private boolean isValid(int x, int y, int[][] g, int num) { 
     //Rows&&Cols 
     for(int i = 0; i < SIZE; i++) 
      if(g[i][y] == num || g[x][i] == num) return false; 
     //Box 
     int bx = x - x%size;, by = y - y%size; 
     for(int i = bx; i < bx + size; i++) { 
      for(int j = by; j < by + size; j++) { 
       if(g[i][j] == num)return false; 
      } 
     } 
     return true; 
    } 
} 

public class Rand { 
    private int rSize; 
    private int[] r; 
    public Rand(int _size) { 
     rSize = _size; 
     r = new int[size]; 
     for(int i = 0; i < rSize; r++)r[i] = i; 
     for(int i = 0; i < rSize*5; r++) { 
      int a = (int)(Math.random()*rSize); 
      int b = (int)(Math.random()*rSize); 
      int n = r[a]; 
      r[a] = r[b]; 
      r[b] = n; 
    } 
    public void get(int i) { 
     if(i >= 0 && i < rSize) return r[i]; return -1; 
    } 
} 

Answer 6

Hai almeno alcuni modi per farlo, ma di solito avrai bisogno di ricorrenza/backtracking. Sarebbe bello avere anche il risolutore, solo per verificare se il puzzle parzialmente riempito ha una soluzione (e l'unica - per fermare i criteri - se vuoi il vero sudoku).

Durante l'esecuzione di backtracking/ricorrenza è necessario:

• per selezionare in modo casuale a disposizione cella vuota (è possibile ottimizzare questo passaggio misurando digidts ancora libero sul cellulare dato, e quindi l'ordinamento)

• per selezionare in modo casuale la cifra disponibile in quella cella

• si riempie la cella e si verifica se la soluzione esiste, se sì - andare oltre, in caso contrario - eseguire il passo indietro.

Punti di partenza: - iniziano con completamente vuoto di puzzle - iniziando con il puzzle parzialmente riempito - iniziano puzzle risolto (ci sono molte trasformazioni non cambiano l'esistenza soluzione, ma rendendo il puzzle diverso - ossia : riflessione, rotazione, trasposizione, scambio di segmenti, scambio di colonne/righe all'interno di segmenti, permutazione, ecc.)

Recentemente ho utilizzato la libreria Janet Sudoku che fornisce metodi di trasformazione di solutori, generatori e puzzle.

Janet Sudoku website

prega di fare riferimento ai seguenti codici sorgenti disponibili sul GitHub

Sudoku Solver

Sudoku Generator

Sudoku Transformations

utilizzo Biblioteca è abbastanza semplice, vale a dire:

SudokuGenerator g = new SudokuGenerator(); 
int[][] puzzle = g.generate(); 
SudokuSolver s = new SudokuSolver(puzzle); 
s.solve(); 
int[][] solvedPuzzle = s.getSolvedBoard(); 

Con i migliori saluti,