Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I just started learning how to write code in Java. I want to turn the code to OOP with fewer methods, using classes like Sudoku rather than int[][] puzzle.

import java.util.Random;
//Generates a Sudoku puzzle through brute-force

public class SudokuPuzzle
{
    public int[][] puzzle = new int[9][9];        // Generated puzzle.
    public int[][] solved_puzzle = new int[9][9]; // The solved puzzle.

private int[][] _tmp_grid = new int[9][9]; // For the solver
private Random rand = new Random();
private short solution_count; // Should be 1

/**
 * Constructor generates a new puzzle, and its solution
 */
public SudokuPuzzle()
{
    generateSolvedPuzzle(0);
    generatePuzzle();
}

/**
 * Finds a solved puzzle through depth-first search
 */
private boolean generateSolvedPuzzle(int cur_cell)
{
    if (cur_cell > 80)
        return true;

    int col = cur_cell % 9;
    int row = cur_cell / 9;

    // create a sequence of the integers {1,...,9} of random order
    int [] numbers = new int[9];
    for (int i=0; i < 9; i++)
        numbers[i] = 1+i;
    shuffle_array(numbers);

    for (int i=0; i < 9; i++)
    {
        int n = numbers[i]; // for the next number in the array
        // if number is acceptable by Sudoku rules
        if (!existsInColumn(solved_puzzle, n, col)
                && !existsInRow(solved_puzzle, n, row)
                && !existsInSubGrid(solved_puzzle, n, row, col))
        {
            // attempt to fill in the next cell with the current cell set to number
            solved_puzzle[row][col] = n;
            if (generateSolvedPuzzle(cur_cell + 1))
                return true;
            solved_puzzle[row][col] = 0; // didn't work, reset cell and try the next number in sequence
        }
    }
    return false; // unreachable (since search is exhaustive and a solved puzzle must exist)
}

/**
 * Solves the Sudoku puzzle through depth-first, exhaustive search, and store the number of
 * solutions in solution_count. Currently, we want to use this only to detect if two solutions
 * exist. Hence, we stop the search as soon as two solutions have been found.
 *
 *
 */
private boolean _solvePuzzle(int cur_cell)
{
    if (cur_cell > 80)
    {
        solution_count++;
        if (solution_count > 1) // two solutions detected. notify caller to abort search
            return true;
        return false;
    }

    int col = cur_cell % 9;
    int row = cur_cell / 9;

    if (_tmp_grid[row][col] == 0) // if cell is unfilled
    {
        for (int n=1; n <= 9; n++) // for each number
        {
            // if number is acceptable by Sudoku rules
            if (!existsInColumn(_tmp_grid, n, col)
                    && !existsInRow(_tmp_grid, n, row)
                    && !existsInSubGrid(_tmp_grid, n, row, col))
            {
                // attempt to fill in the next cell with the current cell set to number
                _tmp_grid[row][col] = n;
                if (_solvePuzzle(cur_cell + 1)) // notified of two solutions being detected
                    return true; // notify caller to abort search
                _tmp_grid[row][col] = 0; // try with other numbers
            }
        }
    }
    else
        if (_solvePuzzle(cur_cell + 1)) // notified of two solutions being detected
            return true; // notify caller to abort search

    return false;
}

private void shuffle_array(int array[])
{
    // swap the first size elements with other elements from the whole array
    for (int i = 0; i < array.length; i++)
    {
        // find an index j (i<j<=array_length) to swap with the element i
        int j = i + rand.nextInt(array.length - i);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

/**
 * Returns whether a given number exists in a given column.
 *
 * @param col    column to check.
 * @param number number to check.
 * @return       true iff number exists in row.
 */
private boolean existsInColumn(int[][] puzzle, int number, int col)
{
    for (int row = 0; row < 9; row++)
        if (puzzle[row][col] == number)
            return true;
    return false;
}

/**
 * Returns whether a given number exists in a given row.
 *
 * @param row    row to check.
 * @param number number to check.
 * @return       true iff number exists in row.
 */
private boolean existsInRow(int[][] puzzle, int number, int row)
{
    for (int col = 0; col < 9; col++)
        if (puzzle[row][col] == number)
            return true;
    return false;
}

/**
 * Returns whether if the 3x3 sub-grid which includes (row, col) contains a
 * cell with the given number.
 *
 * @param row    a row in the sub-grid.
 * @param col    a col in the sub-grid.
 * @param number number to check.
 * @return       true iff sub-grid contains number.
 */
private boolean existsInSubGrid(int[][] puzzle, int number, int row, int col)
{
    int sub_grid_start_row = (row / 3)*3;
    int sub_grid_start_col = (col / 3)*3;
    for (int _row = sub_grid_start_row; _row < sub_grid_start_row + 3; _row++)
        for (int _col = sub_grid_start_col; _col < sub_grid_start_col + 3; _col++)
            if (puzzle[_row][_col] == number)
                return true;
    return false;
}

/**
 * Generates a Sudoku puzzle from a solved puzzle by setting up to 64 cells to 0.
 * (We cannot set more than 64 cells to 0. See http://www.math.ie/McGuire_V1.pdf)
 */
private void generatePuzzle()
{
    // copy solved_puzzle to puzzle
    for (int row = 0; row < 9; row++)
        for (int col = 0; col < 9; col++)
            puzzle[row][col] = solved_puzzle[row][col];

    // create a sequence of the integers {0,...,80} of random order
    int [] cell_sequence = new int[81];
    for (int i=0; i < 81; i++)
        cell_sequence[i] = i;
    shuffle_array(cell_sequence);

    // attempt to set each cell in the sequence to 0
    int count_set_to_zero = 0;
    for (int i=0; i < 81 && count_set_to_zero < 64; i++)
    {
        int cur_cell = cell_sequence[i];
        int col = cur_cell % 9;
        int row = cur_cell / 9;
        int sav = puzzle[row][col];
        puzzle[row][col] = 0;
        solution_count = 0;

        // copy puzzle to _tmp_grid for the solver to work on
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                _tmp_grid[r][c] = puzzle[r][c];

        if (_solvePuzzle(0)) // Puzzle allows more than 1 solution
            puzzle[row][col] = sav; // Revert to original puzzle
        else
            count_set_to_zero++;
    }
}

public void showSolution()
{
    for (int row = 0; row < 9; row++)
    {
        System.out.print("  ");
        for (int col = 0; col < 9; col++)
            System.out.print(" " + solved_puzzle[row][col]);
        System.out.println();
    }
}

public void show()
{
    for (int row = 0; row < 9; row++)
    {
        System.out.print("  ");
        for (int col = 0; col < 9; col++)
            System.out.print(" " + puzzle[row][col]);
        System.out.println();
    }
}

public static void main(String[] args)
{
    SudokuPuzzle sudoku_puzzle = new SudokuPuzzle();
    System.out.println("Puzzle:");
    sudoku_puzzle.show();
    System.out.println();
    System.out.println("Solution:");
    sudoku_puzzle.showSolution();
}
share|improve this question
add comment

1 Answer 1

Try to think of different components with different responsibilities, like:

  • SudokuTable, with basic functionality to store/change the table values
  • SudokuGenerator
  • SudokuSolver
  • SudokuVisualizer
  • MatrixUtils

as a later exercise, look at the components you defined and try to imagine possible subclasses for each one, e.g., ConsoleSudokuVisualizer, SwingSudokuVisualizer, RandomSudokuGenerator, FileBasedSudokuGenerator.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.