How to create a suudoku board? algorithm error

Question

I am trying to create a complete (i.e. each cell filled with a number) ship-like board. This is for something else that has nothing to do with sudoku, so I am not interested in achieving sudoku with white squares that can be solved, or anything that is related to sudoku. I don’t know if you know what I mean.

I did this 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; } } 

This method is called from this piece of code:

 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); } } 

But it is not as simple as it seemed! When the algorithm generated a part of the board similar to this one, and the loop is in the cell in bold:

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

There are no numbers in this cell, because all numbers in accordance with Sudoku rules are already in a column, row or square!

This is a nightmare for me. Is there any way to work? If not, I think I need to repeat everything as if I were doing a Sudoku game.

Thanks in advance.

Answer 1

The problem is that in most cases it is impossible to create a complete board using random numbers, you need to use reverse tracking in cases where it is impossible to use the next cell. I once wrote a sudoku game, so here is a piece of code that generates a filled board.

This is the class Cell.

  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(); } } 

Here the Field class (it is very convenient to store all data in only one object).

  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; } } 

And finally, the function that fills the playing field

 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); } } } 

The point is that you save the numbers that you have already tried for each cell before moving on. If you have a dead end, you just need to try a different number for the previous cell. If none of them is possible, delete this cell and go back one cell. Sooner or later you will do it. (This action takes a little time).

Answer 2

Start with an allowed Sudoku as follows:

 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 

And then we rearrange it, switching columns and switching rows. If you switch only to the following groups: ABC, DEF, GHI, Sudoku is still resolved.

Swap version (switch columns):

 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 

And after some permutation (line switching):

 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 3

Your problem is that you are using Strings. Try using a recursive algorithm using integers. This algorithm will be useful for sudoku of any size. Choosing random numbers in each call, it works much longer. If you select a set of random numbers for passing, if the next cell does not work, then you will not use the same number again. This algorithm will create a unique puzzle every time.

 public class Sudoku { //box size, and game SIZE ==> eg 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 4

You will need to implement the backtracking algorithm.

• For each of 81 locations, generate a set of 1 to 9.
• Repeat until you decide
  • Decide on one location. Select one number from the set.
  • Remove this number from all sets in the same row, column and square.
  • If a conflict arises, retreat to a known good position and allow a different location.

You may have to use recursive functions so you can go back.

Answer 5

You have at least a few ways to do this, but usually you will need a repeat / refund. It would be nice to also have a solver, just to check if the partially completed puzzle has a solution (and a unique one to stop the criteria - if you want a real sudoku).

When doing backtracking / retrying, you will need

• to randomly select an available empty cell (you can optimize this step by measuring the digidts still free from that cell and then sorting)

• randomly select another available digit in this cell

• you fill in the cell and check if a solution exists, if so, go ahead, if not, take a step back.

Starting points: - starting from a completely empty puzzle - starting from a partially filled puzzle - starting from a solved puzzle (there are many transformations that do not change the existence of a solution, but make the difference a puzzle - i.e., reflection, rotation, transposition, separation of segments, line exchange / lines in segments, permutation, etc.)

I recently used the Janet Sudoku library, which provides solver, generator, and puzzle transform methods.

Janet Sudoku website

Check out the source code below available on GitHub

Sudoku Solver

Sudoku Generator

Sudoku Transformation

Using the library is quite simple, for example:

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

Yours faithfully,

Answer 6

Just generate a random number from 1 to 9 and you will see that it corresponds to a given cell [i] [j] it promises you a new set of numbers every time each cell number is randomly generated based on the current time system.

 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++; } } }