Skip to content

Instantly share code, notes, and snippets.

@gaoyike
Created July 14, 2014 16:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gaoyike/dde3f5394b985122b526 to your computer and use it in GitHub Desktop.
Save gaoyike/dde3f5394b985122b526 to your computer and use it in GitHub Desktop.
include maker(notice that, not all sudoku can be solved)
import java.util.ArrayList;
import java.util.Random;
public class sudoku {
public int emptycnt(char[][] board) {
int reuslt = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
{
reuslt++;
}
}
}
return reuslt;
}
public void solveSudoku(char[][] board) {
ArrayList<Integer> empty = new ArrayList<Integer>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
{
empty.add(i * 9 + j);
}
}
}
int len = empty.size();
dfs(board, 0, len, empty);
}
char[][] result;
public boolean dfs(char[][] board, int cur, int len, ArrayList<Integer> empty) {
if (cur == len)
return true;
int index = empty.get(cur);
int row = index / 9;
int col = index % 9;
for (int v = 1; v <= 9; v++) {
if (isValid(board, v, row, col)) {
board[row][col] = (char) (v + '0');
if (dfs(board, cur + 1, len, empty)) {
result = board;
return true;
}
board[row][col] = '.';
}
}
return false;
}
public boolean isValid(char[][] board, int v, int row, int col) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == v + '0')
return false;
if (board[i][col] == v + '0')
return false;
int rows = 3 * (row / 3) + (i / 3);
int cols = 3 * (col / 3) + (i % 3);
if (board[rows][cols] == v + '0')
return false;
}
return true;
}
public void maker(char[][] board, int hardness) {
Random ran = new Random();
for (int i = 0; i < hardness; i++) {
int row = ran.nextInt(8);
int col = ran.nextInt(8);
int v = 1+ran.nextInt(8);
if (board[row][col] != '.')
{
i--;
continue;
}
while (!isValid(board, v, row, col)){
v = 1+ran.nextInt(8);
board[row][col] = '.';
}
board[row][col] = (char) (v + '0') ;
}
}
public static void main(String[] args) {
char[][] board = new char[9][9];
sudoku sudoku = new sudoku();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
board[i][j] = '.';
}
}
sudoku.maker(board, 31);
sudoku.solveSudoku(board);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println("");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment