Sudoku Solver Java - TutorialFlow

Sudoku is an interesting game of filling numbers from 1 to 9 with the logic of non repeating filling of numbers., which improves our solving skills and increase our solving strategies.
The following code is developed in Java to solve any Sudoku game., by following Sudoku rules and also by randomly trying numbers if there are few unique values to fill.,
Simply run the program to fill the sudoku values in the 9X9 box.

import java.util.ArrayList;
import java.util.List;
import java.util.Random; 
public class  SolveRecursionByCheck {
    final static short BOXSIZE = 3; 
    public static void main(String args[]) { 
        new  SolveRecursionByCheck(); 
    }
    short[][] boardOriginal = {
        { 8,0,0,0,0,0,0,0,0 },
        { 0,0,3,6,0,0,0,0,0 },
        { 0,7,0,0,9,0,2,0,0 },
        { 0,5,0,0,0,7,0,0,0 },
        { 0,0,0,0,4,5,7,0,0 },
        { 0,0,0,1,0,0,0,3,0 },
        { 0,0,1,0,0,0,0,6,8 },
        { 0,0,8,5,0,0,0,1,0 },
        { 0,9,0,0,0,0,4,0,0 }   
    }; 
    List numStates = new ArrayList();
    Random rand = new Random(); 
    public  SolveRecursionByCheck() { 
        int x;
        do {
            System.out.println((((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) * 100) / Runtime.getRuntime().totalMemory()));
            x = solve(getClone(boardOriginal));
            if (x == 1) {
                break;
            }
        } while (x == 0); 
        if (x == 1) {
            System.out.println("Solved");
        }
        if (x == 0) {
            System.out.println("Unsolvable");
        }
        if (x == -1) {
            System.out.println("Error while solving");
        } 
        //System.out.println(numStates);
    } 
    public short solve(short[][] board) {
        short[][] tmpBoard = board;
        short solveStatus = 0; 
        //Point
        nextPoint = getNextPoint(tmpBoard);
        Point nextPoint = getNextPointByCheck(tmpBoard); 
        short nextPossibleNumber =
            getNumberByPoint(tmpBoard, nextPoint); 
        if (nextPossibleNumber <= 0) {     
            return 0;
        }  
        tmpBoard[nextPoint.getX()][nextPoint.getY()] = nextPossibleNumber; 
        if (!isComplete(tmpBoard)) {     
            solveStatus = solve(tmpBoard);
        } else {     
            solveStatus = 1;     
            display(tmpBoard);
        } 
        return solveStatus;
    } 
    private Point getNextPoint(short[][] tmpBoard) {
        Point nextPoint = null;
        skipLoop: {     
            for (short i = 0; i < tmpBoard.length; i++) {         
                for (short j = 0; j < tmpBoard[0].length; j++) {             
                    if (tmpBoard[i][j] == 0) {                 
                        nextPoint = new Point(i, j);                 
                        break skipLoop;             
                    }         
                }     
            }
        }
        return nextPoint;
    } 
    private Point getNextPointByCheck(short[][] tmpBoard) {
        Point nextPoint = null;
        int leastCount  = 99;            
        for (short i = 0; i < tmpBoard.length; i++) {         
            for (short j = 0; j < tmpBoard[0].length; j++) {             
                if (tmpBoard[i][j] == 0) {                   
                    List  possibleList = getNextPossibleNumbers(tmpBoard, new Point(i, j));                 
                    if (possibleList.size() < leastCount) {                     
                        nextPoint = new Point(i, j);                     
                        leastCount = possibleList.size();                 
                    }             
                }         
            }           
        } 
        return nextPoint;
    } 
    private List getNextPossibleNumbers(short[][] tmpBoard, Point point) {
        short nextPossibleNumber = 0;
        List numbers = new ArrayList();
        for (short i = 1; i <= 9; i++) {     
            numbers.add(i);
        } 
        for (short i = 0; i < tmpBoard.length; i++) {
            short numX = tmpBoard[(int) point.getX()][i];
            if (numX > 0) {         
                numbers.remove(new Short(numX));     
            }     
            short numY =
                tmpBoard[i][point.getY()];     
            if (numY > 0) {         
                numbers.remove(new Short(numY));     
            }
        } 
        short startX = (short)((point.getX() / BOXSIZE) * BOXSIZE);
        short startY = (short)((point.getY() / BOXSIZE) * BOXSIZE);
        short endX = (short)(startX + BOXSIZE);
        short endY = (short)(startY + BOXSIZE); 
        for (short i = startX; i < endX; i++) {     
            for (short j = startY; j < endY; j++) {
                short num = tmpBoard[i][j];
                if (num > 0) {             
                    numbers.remove(new Short(num));         
                }     
            }
        }
        return numbers;
    } 
    private short getNumberByPoint(short[][] tmpBoard, Point point) {
        short nextPossibleNumber = 0;
        List numbers = getNextPossibleNumbers(tmpBoard, point);
        if (numbers.size() > 0) {     
            int r = rand.nextInt(numbers.size());     
            nextPossibleNumber = (short) numbers.get(r);
        }
        return nextPossibleNumber;
    } 
    private short getNextPossibleNumberByList(short[][] tmpBoard, Point point) {
        short nextPossibleNumber =
            0;
        List numbers = new ArrayList();
        for (short i = 1; i <= 9; i++) {
            numbers.add(i);
        } 
        for (short i = 0; i < tmpBoard.length; i++) {  
            short numX = tmpBoard[point.getX()][i];
            if (numX > 0) {         
                numbers.remove(new Short(numX));     
            }     
            short numY = tmpBoard[i][point.getY()];     
            if (numY > 0) {         
                numbers.remove(new Short(numY));     
            }
        } 
        short startX = (short)((point.getX() / BOXSIZE) * BOXSIZE);
        short startY = (short)((point.getY() / BOXSIZE) * BOXSIZE);
        short endX   = (short)(BOXSIZE - startX % BOXSIZE);
        short endY   = (short)(BOXSIZE - startY % BOXSIZE); 
        for (short i = startX; i < endX; i++) {     
            for (short  j = startY; j < endY; j++) {
                short num = tmpBoard[i][j];
                if (num > 0) {             
                    numbers.remove(new Short(num));         
                }     
            }
        } 
        if (numbers.size() > 0) {     
            int r = rand.nextInt(numbers.size());     
            nextPossibleNumber = (short) numbers.get(r);
        } 
        return nextPossibleNumber;
    } 
    public void display(short[][] board) {
        System.out.println("**************");
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j]);
                System.out.print(",");
            }
            System.out.println();
        }
        System.out.println("**************");
    }  
    private boolean isComplete(short[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    } 
    private short[][] getClone(short[][] originalArray) {
        short[][] clonedArray = new short[originalArray.length][originalArray[0].length];
        for (int  i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                clonedArray[i][j] = originalArray[i][j];
            }
        }
        return clonedArray;
    } 
    class Point {
        int x;
        int y;
        public Point(short i, short j) {
            x = (int) i;
            y = (int) j;
        }
        public int getX() {
            return x;
        }
        public void setX(int x) {
            this.x = x;
        }
        public int getY() {
            return y;
        }
        public void setY(int y) {
            this.y = y;
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

import java.util.ArrayList;

import java.util.List;

import java.util.Random;

public class SolveRecursionByCheck {

final static short BOXSIZE = 3;

public static void main(String args[]) {

new SolveRecursionByCheck();

}

short[][] boardOriginal = {

{ 8,0,0,0,0,0,0,0,0 },

{ 0,0,3,6,0,0,0,0,0 },

{ 0,7,0,0,9,0,2,0,0 },

{ 0,5,0,0,0,7,0,0,0 },

{ 0,0,0,0,4,5,7,0,0 },

{ 0,0,0,1,0,0,0,3,0 },

{ 0,0,1,0,0,0,0,6,8 },

{ 0,0,8,5,0,0,0,1,0 },

{ 0,9,0,0,0,0,4,0,0 }

};

List numStates = new ArrayList();

Random rand = new Random();

public SolveRecursionByCheck() {

int x;

do {

System.out.println((((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) * 100) / Runtime.getRuntime().totalMemory()));

x = solve(getClone(boardOriginal));

if (x == 1) {

break;

}

} while (x == 0);

if (x == 1) {

System.out.println("Solved");

}

if (x == 0) {

System.out.println("Unsolvable");

}

if (x == -1) {

System.out.println("Error while solving");

}

//System.out.println(numStates);

}

public short solve(short[][] board) {

short[][] tmpBoard = board;

short solveStatus = 0;

//Point

nextPoint = getNextPoint(tmpBoard);

Point nextPoint = getNextPointByCheck(tmpBoard);

short nextPossibleNumber =

getNumberByPoint(tmpBoard, nextPoint);

if (nextPossibleNumber <= 0) {

return 0;

}

tmpBoard[nextPoint.getX()][nextPoint.getY()] = nextPossibleNumber;

if (!isComplete(tmpBoard)) {

solveStatus = solve(tmpBoard);

} else {

solveStatus = 1;

display(tmpBoard);

}

return solveStatus;

}

private Point getNextPoint(short[][] tmpBoard) {

Point nextPoint = null;

skipLoop: {

for (short i = 0; i < tmpBoard.length; i++) {

for (short j = 0; j < tmpBoard[0].length; j++) {

if (tmpBoard[i][j] == 0) {

nextPoint = new Point(i, j);

break skipLoop;

}

return nextPoint;

}

private Point getNextPointByCheck(short[][] tmpBoard) {

Point nextPoint = null;

int leastCount = 99;

for (short i = 0; i < tmpBoard.length; i++) {

for (short j = 0; j < tmpBoard[0].length; j++) {

if (tmpBoard[i][j] == 0) {

List possibleList = getNextPossibleNumbers(tmpBoard, new Point(i, j));

if (possibleList.size() < leastCount) {

nextPoint = new Point(i, j);

leastCount = possibleList.size();

}

return nextPoint;

}

private List getNextPossibleNumbers(short[][] tmpBoard, Point point) {

short nextPossibleNumber = 0;

List numbers = new ArrayList();

for (short i = 1; i <= 9; i++) {

numbers.add(i);

}

for (short i = 0; i < tmpBoard.length; i++) {

short numX = tmpBoard[(int) point.getX()][i];

if (numX > 0) {

numbers.remove(new Short(numX));

}

short numY =

tmpBoard[i][point.getY()];

if (numY > 0) {

numbers.remove(new Short(numY));

}

short startX = (short)((point.getX() / BOXSIZE) * BOXSIZE);

short startY = (short)((point.getY() / BOXSIZE) * BOXSIZE);

short endX = (short)(startX + BOXSIZE);

short endY = (short)(startY + BOXSIZE);

for (short i = startX; i < endX; i++) {

for (short j = startY; j < endY; j++) {

short num = tmpBoard[i][j];

if (num > 0) {

numbers.remove(new Short(num));

}

return numbers;

}

private short getNumberByPoint(short[][] tmpBoard, Point point) {

short nextPossibleNumber = 0;

List numbers = getNextPossibleNumbers(tmpBoard, point);

if (numbers.size() > 0) {

int r = rand.nextInt(numbers.size());

nextPossibleNumber = (short) numbers.get(r);

}

return nextPossibleNumber;

}

private short getNextPossibleNumberByList(short[][] tmpBoard, Point point) {

short nextPossibleNumber =

List numbers = new ArrayList();

for (short i = 1; i <= 9; i++) {

numbers.add(i);

}

for (short i = 0; i < tmpBoard.length; i++) {

short numX = tmpBoard[point.getX()][i];

if (numX > 0) {

numbers.remove(new Short(numX));

}

short numY = tmpBoard[i][point.getY()];

if (numY > 0) {

numbers.remove(new Short(numY));

}

short startX = (short)((point.getX() / BOXSIZE) * BOXSIZE);

short startY = (short)((point.getY() / BOXSIZE) * BOXSIZE);

short endX = (short)(BOXSIZE - startX % BOXSIZE);

short endY = (short)(BOXSIZE - startY % BOXSIZE);

for (short i = startX; i < endX; i++) {

for (short j = startY; j < endY; j++) {

short num = tmpBoard[i][j];

if (num > 0) {

numbers.remove(new Short(num));

}

if (numbers.size() > 0) {

int r = rand.nextInt(numbers.size());

nextPossibleNumber = (short) numbers.get(r);

}

return nextPossibleNumber;

}

public void display(short[][] board) {

System.out.println("**************");

for (int i = 0; i < board.length; i++) {

for (int j = 0; j < board[i].length; j++) {

System.out.print(board[i][j]);

System.out.print(",");

}

System.out.println();

}

System.out.println("**************");

}

private boolean isComplete(short[][] board) {

for (int i = 0; i < board.length; i++) {

for (int j = 0; j < board[i].length; j++) {

if (board[i][j] == 0) {

return false;

}

return true;

}

private short[][] getClone(short[][] originalArray) {

short[][] clonedArray = new short[originalArray.length][originalArray[0].length];

for (int i = 0; i < originalArray.length; i++) {

for (int j = 0; j < originalArray[i].length; j++) {

clonedArray[i][j] = originalArray[i][j];

}

return clonedArray;

}

class Point {

int x;

int y;

public Point(short i, short j) {

x = (int) i;

y = (int) j;

}

public int getX() {

return x;

}

public void setX(int x) {

this.x = x;

}

public int getY() {

return y;

}

public void setY(int y) {

this.y = y;

}

Leave a Reply Cancel reply