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

Have a look at the following. Note that I have not run it, so I can't vouch for its claims:

http://www.codeproject.com/KB/game/SudokuGen.aspx

The code is in VB.NET, but the algorithm will be the same in C#.

There is a C# version here:

http://www.codeproject.com/KB/game/sudokuincsharp.aspx

The link supplied by @Bill the Lizard does a nice job explaining things, as opposed to the implementation links I supplied above.

Answer 2

There are a few algorithms outlined on Algorithmics of sudoku. What you're describing sounds like a backtracking approach.

Answer 3

I recently did a series in my blog on creating a Sudoku solver in C#; you can probably adapt the simple backtracking algorithm I present to your purposes.

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

Answer 4

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

Answer 5

This simple random walk algorithm should work too (but is inefficient- use at your own risk!!!):

EDIT: - added fix for unresolvable solutions.

For each empty cell in grid
    array = Get_Legal_Numbers_for_cell(row,col);
    If (array is empty) {
        Clear_All_cells()
    } else {
        number = Random_number_from(array);
        Put_Number_in_Cell(number);
    }

EDIT 2

If someone are interested here are described methods for solving sudoku with random-based search.