6
\$\begingroup\$

I have been programming for a long time, but nobody has given me any feedback if my code is good or not. Please review it, and give me feedback where I could be better.

The source code is also on GitHub.

GameEngine.java:

package com.marcellelek.sudoku;

import com.marcellelek.sudoku.view.sudokugrid.GameGrid;

import android.content.Context;

public class GameEngine {
private static GameEngine instance;

private GameGrid grid = null;

private int selectedPosX = -1, selectedPosY = -1;

private GameEngine(){}

public static GameEngine getInstance(){
    if( instance == null ){
        instance = new GameEngine();
    }
    return instance;
}

public void createGrid( Context context ){
    int[][] Sudoku = SudokuGenerator.getInstance().generateGrid();
    Sudoku = SudokuGenerator.getInstance().removeElements(Sudoku);
    grid = new GameGrid(context);
    grid.setGrid(Sudoku);
}

public GameGrid getGrid(){
    return grid;
}

public void setSelectedPosition( int x , int y ){
    selectedPosX = x;
    selectedPosY = y;
}

public void setNumber( int number ){
    if( selectedPosX != -1 && selectedPosY != -1 ){
        grid.setItem(selectedPosX,selectedPosY,number);
    }
    grid.checkGame();
}
}

MainActivity.java

package com.marcellelek.sudoku;

import android.app.Activity;
import android.os.Bundle;

public class MainActivity extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_main);


    GameEngine.getInstance().createGrid(this);
}

private void printSudoku(int Sudoku[][]) {
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            System.out.print(Sudoku[x][y] + "|");
        }
        System.out.println();
    }
}

SudokuChecker.java

package com.marcellelek.sudoku;

public class SudokuChecker {
private static SudokuChecker instance;

private SudokuChecker(){}

public static SudokuChecker getInstance(){
    if( instance == null ){
        instance = new SudokuChecker();
    }
    return instance;
}

public boolean checkSudoku( int[][] Sudoku){
    return (checkHorizontal(Sudoku) || checkVertical(Sudoku) || checkRegions(Sudoku));
}

private boolean checkHorizontal(int[][] Sudoku) {
    for( int y = 0 ; y < 9 ; y++ ){
        for( int xPos = 0 ; xPos < 9 ; xPos++ ){

            if( Sudoku[xPos][y] == 0 ){
                return false;
            }
            for( int x = xPos + 1 ; x < 9 ; x++ ){
                if( Sudoku[xPos][y] == Sudoku[x][y] || Sudoku[x][y] == 0 ){
                    return false;
                }
            }
        }
    }

    return true;
}

private boolean checkVertical(int[][] Sudoku) {
    for( int x = 0 ; x < 9 ; x++ ){
        for( int yPos = 0 ; yPos < 9 ; yPos++ ){

            if( Sudoku[x][yPos] == 0 ){
                return false;
            }
            for( int y = yPos + 1 ; y < 9 ; y++ ){
                if( Sudoku[x][yPos] == Sudoku[x][y] || Sudoku[x][y] == 0 ){
                    return false;
                }
            }
        }
    }

    return true;
}

private boolean checkRegions(int[][] Sudoku) {
    for( int xRegion = 0; xRegion < 3; xRegion++ ){
        for( int yRegion = 0; yRegion < 3 ; yRegion++ ){
            if( !checkRegion(Sudoku, xRegion, yRegion) ){
                return false;
            }
        }
    }
    return true;
}

private boolean checkRegion(int[][] Sudoku , int xRegion , int yRegion){
    for( int xPos = xRegion * 3; xPos < xRegion * 3 + 3 ; xPos++ ){
        for( int yPos = yRegion * 3 ; yPos < yRegion * 3 + 3 ; yPos++ ){
            for( int x = xPos ; x < xRegion * 3 + 3 ; x++ ){
                for( int y = yPos ; y < yRegion * 3 + 3 ; y++ ){
                    if( (( x != xPos || y != yPos) && Sudoku[xPos][yPos] == Sudoku[x][y] ) || Sudoku[x][y] == 0 ){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
}

SudokuGenerator.java

package com.marcellelek.sudoku;

import java.util.ArrayList;
import java.util.Random;

public class SudokuGenerator {
private static SudokuGenerator instance;

private ArrayList<ArrayList<Integer>> Available = new ArrayList<ArrayList<Integer>>();

private Random rand = new Random();

private SudokuGenerator(){}

public static SudokuGenerator getInstance(){
    if( instance == null ){
        instance = new SudokuGenerator();
    }
    return instance;
}

public int[][] generateGrid(){
    int[][] Sudoku = new int[9][9];

    int currentPos = 0;


    while( currentPos < 81 ){
        if( currentPos == 0 ){
            clearGrid(Sudoku);
        }

        if( Available.get(currentPos).size() != 0 ){
            int i = rand.nextInt(Available.get(currentPos).size());
            int number = Available.get(currentPos).get(i);

            if( !checkConflict(Sudoku, currentPos , number)){
                int xPos = currentPos % 9;
                int yPos = currentPos / 9;

                Sudoku[xPos][yPos] = number;

                Available.get(currentPos).remove(i);

                currentPos++;
            }else{
                Available.get(currentPos).remove(i);
            }

        }else{
            for( int i = 1 ; i <= 9 ; i++ ){
                Available.get(currentPos).add(i);
            }
            currentPos--;
        }
    }


    return Sudoku;
}

public int[][] removeElements( int[][] Sudoku ){
    int i = 0;

    while( i < 3 ){
        int x = rand.nextInt(9);
        int y = rand.nextInt(9);

        if( Sudoku[x][y] != 0 ){
            Sudoku[x][y] = 0;
            i++;
        }
    }
    return Sudoku;

}

private void clearGrid(int [][] Sudoku){
    Available.clear();

    for( int y =  0; y < 9 ; y++ ){
        for( int x = 0 ; x < 9 ; x++ ){
            Sudoku[x][y] = -1;
        }
    }

    for( int x = 0 ; x < 81 ; x++ ){
        Available.add(new ArrayList<Integer>());
        for( int i = 1 ; i <= 9 ; i++){
            Available.get(x).add(i);
        }
    }
}

private boolean checkConflict( int[][] Sudoku , int currentPos , final int number){
    int xPos = currentPos % 9;
    int yPos = currentPos / 9;

    if( checkHorizontalConflict(Sudoku, xPos, yPos, number) || checkVerticalConflict(Sudoku, xPos, yPos, number) || checkRegionConflict(Sudoku, xPos, yPos, number) ){
        return true;
    }

    return false;
}

/**
 * Return true if there is a conflict
 * @param Sudoku
 * @param xPos
 * @param yPos
 * @param number
 * @return
 */
private boolean checkHorizontalConflict( final int[][] Sudoku , final int xPos , final int yPos , final int number ){
    for( int x = xPos - 1; x >= 0 ; x-- ){
        if( number == Sudoku[x][yPos]){
            return true;
        }
    }

    return false;
}

private boolean checkVerticalConflict( final int[][] Sudoku , final int xPos , final int yPos , final int number ){
    for( int y = yPos - 1; y >= 0 ; y-- ){
        if( number == Sudoku[xPos][y] ){
            return true;
        }
    }

    return false;
}

private boolean checkRegionConflict( final int[][] Sudoku , final int xPos , final int yPos , final int number ){
    int xRegion = xPos / 3;
    int yRegion = yPos / 3;

    for( int x = xRegion * 3 ; x < xRegion * 3 + 3 ; x++ ){
        for( int y = yRegion * 3 ; y < yRegion * 3 + 3 ; y++ ){
            if( ( x != xPos || y != yPos ) && number == Sudoku[x][y] ){
                return true;
            }
        }
    }

    return false;
}
}

ButtonsGridView.java

package com.marcellelek.sudoku.view.buttonsgrid;

import com.marcellelek.sudoku.R;

import android.app.Activity;
import android.content.Context;
import android.util.AttributeSet;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.widget.BaseAdapter;
import android.widget.GridView;

public class ButtonsGridView extends GridView{


public ButtonsGridView( Context context , AttributeSet attrs ){
    super(context , attrs);

    ButtonsGridViewAdapter gridViewAdapter = new ButtonsGridViewAdapter(context);

    setAdapter(gridViewAdapter);
}

class ButtonsGridViewAdapter extends BaseAdapter {

    private Context context;

    public ButtonsGridViewAdapter(Context context) {
        this.context = context;
    }

    @Override
    public int getCount() {
        return 10;
    }

    @Override
    public Object getItem(int position) {
        return null;
    }

    @Override
    public long getItemId(int position) {
        return position;
    }

    @Override
    public View getView(int position, View convertView, ViewGroup parent) {
        View v = convertView;

        if( v == null ){
            LayoutInflater inflater = ((Activity) context).getLayoutInflater();
            v = inflater.inflate(R.layout.button, parent , false);

            NumberButton btn;
            btn = (NumberButton)v;
            btn.setTextSize(10);
            btn.setId(position);

            if( position != 9 ){
                btn.setText(String.valueOf(position + 1));
                btn.setNumber(position + 1);
            }else{
                btn.setText("DEL");
                btn.setNumber(0);
            }
            return btn;
        }

        return v;
    }

}
}

NumberButton.java

package com.marcellelek.sudoku.view.buttonsgrid;

import com.marcellelek.sudoku.GameEngine;

import android.content.Context;
import android.util.AttributeSet;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;

public class NumberButton extends Button implements OnClickListener{

private int number;

public NumberButton(Context context, AttributeSet attrs) {
    super(context, attrs);
    setOnClickListener(this);
}

@Override
public void onClick(View v) {
    GameEngine.getInstance().setNumber(number);
}

public void setNumber(int number){
    this.number = number;
}
}

BaseSudokuCell.java

package com.marcellelek.sudoku.view.sudokugrid;

import android.content.Context;
import android.view.View;

public class BaseSudokuCell extends View{


private int value;
private boolean modifiable = true;

public BaseSudokuCell(Context context) {
    super(context);
}

@Override
protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    super.onMeasure(widthMeasureSpec, widthMeasureSpec);
}

public void setNotModifiable(){
    modifiable = false;
}

public void setInitValue(int value){
    this.value = value;
    invalidate();
}

public void setValue( int value ){
    if( modifiable ){
        this.value = value;
    }

    invalidate();
}

public int getValue(){
    return value;
}
}

SudokuCell.java

package com.marcellelek.sudoku.view.sudokugrid;

import android.content.Context;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.graphics.Paint.Style;
import android.graphics.Rect;

public class SudokuCell extends BaseSudokuCell {

private Paint mPaint;

public SudokuCell( Context context ){
    super(context);

    mPaint = new Paint();

}

@Override
protected void onDraw(Canvas canvas) {
    super.onDraw(canvas);

    drawNumber(canvas);
    drawLines(canvas);
}

private void drawNumber(Canvas canvas){
    mPaint.setColor(Color.BLACK);
    mPaint.setTextSize(60);
    mPaint.setStyle(Style.FILL);

    Rect bounds = new Rect();
    mPaint.getTextBounds(String.valueOf(getValue()), 0, String.valueOf(getValue()).length(), bounds);

    if( getValue() != 0 ){
        canvas.drawText(String.valueOf(getValue()), (getWidth() - bounds.width())/2, (getHeight() + bounds.height())/2  , mPaint);
    }
}

private void drawLines(Canvas canvas) {
    mPaint.setColor(Color.BLACK);
    mPaint.setStrokeWidth(3);
    mPaint.setStyle(Style.STROKE);

    canvas.drawRect(0, 0, getWidth(), getHeight(), mPaint);
}
}

SudokuGridView.java

package com.marcellelek.sudoku.view.sudokugrid;

import com.marcellelek.sudoku.GameEngine;
import com.marcellelek.sudoku.R;

import android.app.Activity;
import android.content.Context;
import android.util.AttributeSet;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.widget.AdapterView;
import android.widget.BaseAdapter;
import android.widget.GridView;
import android.widget.Toast;

public class SudokuGridView extends GridView{

private final Context context;

public SudokuGridView(final Context context , AttributeSet attrs) {
    super(context,attrs);

    this.context = context;

    SudokuGridViewAdapter gridViewAdapter = new SudokuGridViewAdapter(context);

    setAdapter(gridViewAdapter);

    setOnItemClickListener(new OnItemClickListener() {

        @Override
        public void onItemClick(AdapterView<?> parent, View view, int position, long id) {
            int x = position % 9;
            int y = position / 9;

            GameEngine.getInstance().setSelectedPosition(x, y);
        }
    });
}

@Override
protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    super.onMeasure(widthMeasureSpec, widthMeasureSpec);
}

class SudokuGridViewAdapter extends BaseAdapter{

    private Context context;

    public SudokuGridViewAdapter(Context context) {
        this.context = context;
    }

    @Override
    public int getCount() {
        return 81;
    }

    @Override
    public Object getItem(int position) {
        return null;
    }

    @Override
    public long getItemId(int position) {
        return 0;
    }

    @Override
    public View getView(int position, View convertView, ViewGroup parent) {
        return GameEngine.getInstance().getGrid().getItem(position);
    }
}
}

GameGrid.java

package com.marcellelek.sudoku.view.sudokugrid;

import com.marcellelek.sudoku.SudokuChecker;

import android.content.Context;
import android.widget.Toast;

public class GameGrid {
private SudokuCell[][] Sudoku = new SudokuCell[9][9];

private Context context;

public GameGrid( Context context ){
    this.context = context;
    for( int x = 0 ; x < 9 ; x++ ){
        for( int y = 0 ; y < 9 ; y++){
            Sudoku[x][y] = new SudokuCell(context);
        }
    }
}

public void setGrid( int[][] grid ){
    for( int x = 0 ; x < 9 ; x++ ){
        for( int y = 0 ; y < 9 ; y++){
            Sudoku[x][y].setInitValue(grid[x][y]);
            if( grid[x][y] != 0 ){
                Sudoku[x][y].setNotModifiable();
            }
        }
    }
}

public SudokuCell[][] getGrid(){
    return Sudoku;
}

public SudokuCell getItem(int x , int y ){
    return Sudoku[x][y];
}

public SudokuCell getItem( int position ){
    int x = position % 9;
    int y = position / 9;

    return Sudoku[x][y];
}

public void setItem( int x , int y , int number ){
    Sudoku[x][y].setValue(number);
}

public void checkGame(){
    int [][] sudGrid = new int[9][9];
    for( int x = 0 ; x < 9 ; x++ ){
        for( int y = 0 ; y < 9 ; y++ ){
            sudGrid[x][y] = getItem(x,y).getValue();
        }
    }

    if( SudokuChecker.getInstance().checkSudoku(sudGrid)){
        Toast.makeText(context, "You solved the sudoku.", Toast.LENGTH_LONG).show();
    }
}
}
\$\endgroup\$
6
\$\begingroup\$

Singletons

You have made your GameEngine and SudokuChecker as singletons, meaning that you are preventing multiple instances from being created. Why? To me it feels like you just want the easy way out, so that you can anywhere write GameEngine.getInstance(). I would recommend you to use Dependency Injection instead and avoid using singletons when you don't absolutely have to. (Hint: You pretty much never have to).

Using only a single instance is perfectly okay, but enforcing the use of only a single instance is bad.

I'd also recommend you to read an answer to So Singletons are bad, then what? at the Stack Exchange site Software Engineering.

Especially your SudokuChecker and SudokuGenerator should definitely not be singletons. Just ask yourself: Would there be a problem with having two instances of SudokuGenerator? What if you wanted to generate 10 boards and then choose one that you liked best?

Validating the board

Your current algorithm for checking if there's a duplicate in a row or column or region is currently of time complexity \$O(n^2)\$. For each item you compare it with (almost) each other item. This is a bit slow.

Instead you can use a Set<Integer> to keep track of the numbers you have seen.

Example rewrite of your checkHorizontal method:

private boolean checkHorizontal(int[][] sudoku) {
    for (int y = 0 ; y < 9 ; y++) {
        Set<Integer> found = new HashSet<Integer>();
        for (int xPos = 0 ; xPos < 9 ; xPos++) {
            int number = sudoku[xPos][y];
            if (number == 0) {
                return false;
            }
            if (!found.add(number)) {
                // this will happen if the number was already added
                return false;
            }
        }
    }
    return true;
}

Stylistic stuff

Please lookup Google's Java Style Guide and follow it. Use the automatic formatting feature of your IDE. Name the parameters to your methods according to the conventions.

\$\endgroup\$
  • 1
    \$\begingroup\$ You may also be interested in my Sudoku C# solver with Advanced features \$\endgroup\$ – Simon Forsberg Aug 20 '16 at 12:28
  • \$\begingroup\$ There's no reason for SudokuChecker not to be singleton; it's only a data manipulator and doesn't need to store anything or to hold any references to anything. The generator can generate 10 boards just fine, just not at the same time. It can generate them in parallel. I suppose you have a point there? \$\endgroup\$ – Pimgd Aug 20 '16 at 21:32
  • \$\begingroup\$ @Pimgd The fact that SudokuChecker does not store anything is a very good reason for why it absolutely doesn't need to be a singleton. All those methods could be static, if anything. Just because it can be just one instance doesn't mean that it should be enforced to only be one instance. The default should be to not use a singleton, not to use one. What I'd like to see is to use one SudokuGenerator instance for each SudokuBoard that is created. No more, no less. \$\endgroup\$ – Simon Forsberg Aug 20 '16 at 22:40
  • \$\begingroup\$ I'm just saying it's not swinging either way. Which is great because on that front we seem to be agreeing. "There's no reason for this to be a singleton." "There is also no reason for this to not be a singleton." "Default to not enforcing singleton-ness." \$\endgroup\$ – Pimgd Aug 20 '16 at 22:49
0
\$\begingroup\$
    for( int xPos = 0 ; xPos < 9 ; xPos++ ){

        if( Sudoku[xPos][y] == 0 ){
            return false;
        }
        for( int x = xPos + 1 ; x < 9 ; x++ ){
            if( Sudoku[xPos][y] == Sudoku[x][y] || Sudoku[x][y] == 0 ){
                return false;
            }
        }
    }

Because you check ALL xPos, it is not needed to check for Sudoku[x][y] in the inner for loop. In fact, checking this is a waste of time, as you'll eventually get to it anyway.

I don't like the way you handle checking regions, lines and columns, given that you go through 3x9x(8+7+6+5+4+3+2+1) iterations for validating a completed board. That's a total of 972 checks.

Consider using a Set<Integer> to keep track of visited numbers - if the adding fails, you'll know that you have found a duplicate.

Like that, you check the entire row with 9 iterations. This makes the algorithm 9x3 - 9 iterations to check a group, and three sets of groups of 9 elements each: the rows, the columns and the regions. This would make 9x9x3, 243 iterations.

\$\endgroup\$
  • 2
    \$\begingroup\$ I think that your 9x9x9x8x7x6x5x4x3x2x1 calculation is incorrect, there is nowhere near that many iterations here. I'm also not a fan of your suggestion to using a 9-bit integer, although it could work if implemented correctly there's a high risk of using it incorrectly as it makes things unclear. \$\endgroup\$ – Simon Forsberg Aug 20 '16 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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