Brute force Algorithm for creation of Sudoku Board

Question

What I am developing is that initially the entire sudoku board is empty. One of the random cells(out of 81) is filled with a random value(1-9).

Now I want to fill all the remaining cells using brute force approach.
From what I came to know after googling is that we should start with the first cell and fill it with 1(if it's valid), then fill the second cell with 2(if it's valid, we will begin checking with a number greater than the last filled cell, which in this case is 1, once we reach 9, we reset it with 1).

The thing is that it's not working properly!

Can anyone link me to the exact algorithm.

Answer 1

Here's an implementation of the backtracking approach:

import java.util.Random;

public class Sudoku {

    public static void main(String[] args) {
        Random rand = new Random();
        int r = rand.nextInt(9);
        int c = rand.nextInt(9);
        int value = rand.nextInt(9) + 1;
        Board board = new Board();
        board.set(r, c, value);
        System.out.println(board);
        solve(board, 0);
        System.out.println(board);
    }

    private static boolean solve(Board board, int at) {
        if (at == 9*9)
            return true;
        int r = at / 9;
        int c = at % 9;
        if (board.isSet(r, c))
            return solve(board, at + 1);
        for (int value = 1; value <= 9; value++) {
            if (board.canSet(r, c, value)) {
                board.set(r, c, value);
                if (solve(board, at + 1))
                    return true;
                board.unSet(r, c);
            }
        }
        return false;
    }

    static class Board {
        private int[][] board = new int[9][9];
        private boolean[][] rs = new boolean[9][10];
        private boolean[][] cs = new boolean[9][10];
        private boolean[][][] bs = new boolean[3][3][10];
        public Board() {}
        public boolean canSet(int r, int c, int value) {
            return !isSet(r, c) && !rs[r][value] && !cs[c][value] && !bs[r/3][c/3][value];
        }
        public boolean isSet(int r, int c) {
            return board[r][c] != 0;
        }
        public void set(int r, int c, int value) {
            if (!canSet(r, c, value))
                throw new IllegalArgumentException();
            board[r][c] = value;
            rs[r][value] = cs[c][value] = bs[r/3][c/3][value] = true;
        }
        public void unSet(int r, int c) {
            if (isSet(r, c)) {
                int value = board[r][c];
                board[r][c] = 0;
                rs[r][value] = cs[c][value] = bs[r/3][c/3][value] = false;
            }
        }
        public String toString() {
            StringBuilder ret = new StringBuilder();
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++)
                    ret.append(board[r][c]);
                ret.append("\n");
            }
            return ret.toString();
        }
    }
}