Friday, September 5, 2014

SuDoKu solver [Print all solutions for a given Puzzle] AI Java Implementation [SuDoKu][Java][Artificial Intelligence][9x9]

I made this SuDoKu solver in Java. Solves a board if it is possible to solve it, otherwise prints an error : Unsolvable.

First of all Rules for SuDoKu (9x9):

1. Every row and every column intersection number must be unique in that row and column.
2. Every 3x3 grid must have numbers from 1-9 with no repitition.

Keep in mind:

Not every random number placements on a 9x9 board is a SOLVABLE sudoku puzzle.
There MAY be multiple solutions for a given sudoku puzzle. [These are generally incomplete puzzles].

Algorithm applied:

1. Numbers already placed on the board initially are not to be touched! Just skip them.
2. Try to place every number from 1 to 9 on the next cell (using a recursive step - a recursive call for each cell placement).
3. If a number is placed. Call this same function on the next cell.
4. If current number did not get placed, successive recursive calls will get the board to fail, returning true(board failed) so the previous recursive call should try next number on that call's cell.
5. In between if an untouchable number (initially placed number) arrives, just skip it by calling recursion for next cell placement.
6. Function solve returns true is board fails to print "Unsolvable".
7. Remove the commented lines to see the actual calculations.

Note : A board is already given. If you don't feel like inputting a new one, just comment out inputBoard() in main.


Code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Board {

    int board[][] = {
        {0, 2, 0, 4, 0, 0, 7, 0, 0},
        {7, 0, 0, 0, 0, 6, 0, 0, 8},
        {0, 8, 3, 0, 0, 0, 0, 0, 1},
        {0, 0, 2, 6, 0, 0, 0, 0, 0},
        {0, 5, 0, 0, 0, 0, 0, 7, 0},
        {0, 0, 0, 0, 0, 3, 9, 0, 0},
        {9, 0, 0, 0, 0, 0, 8, 3, 0},
        {3, 0, 0, 5, 0, 0, 0, 0, 7},
        {0, 0, 1, 0, 0, 4, 0, 6, 0},};
}

class Cell {

    int x;
    int y;
    int value;

    Cell(int x, int y) {
        this.x = x;
        this.y = y;
        this.value = Sudoku9x9.boardInstance.board[x][y];
    }

    public String toString() {
        return "[" + x + ", " + y + "]";
    }

    public int hashCode() {
        return Integer.parseInt(x + "" + y);
    }

    public boolean equals(Object o) {
        Cell incoming = (Cell) o;
//        System.out.println("This = "+this.x+", "+this.y+". Incoming: "+incoming.x+", "+incoming.y);
        return this.x == incoming.x && this.y == incoming.y;
    }
}

public class Sudoku9x9 {

    static Board boardInstance = new Board();

    void printBoard() {
        System.out.println();
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                System.out.print(boardInstance.board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    Map<Integer, List<Cell>> pointGroups = new HashMap<>();

    void initializeMap() {
        for (int i = 1; i <= 9; ++i) {
            pointGroups.put(i, new ArrayList<Cell>());
        }

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                pointGroups.get(1).add(new Cell(i, j));
            }

            for (int j = 3; j < 6; ++j) {
                pointGroups.get(2).add(new Cell(i, j));
            }

            for (int j = 6; j < 9; ++j) {
                pointGroups.get(3).add(new Cell(i, j));
            }
        }

        for (int i = 3; i < 6; ++i) {
            for (int j = 0; j < 3; ++j) {
                pointGroups.get(4).add(new Cell(i, j));
            }

            for (int j = 3; j < 6; ++j) {
                pointGroups.get(5).add(new Cell(i, j));
            }

            for (int j = 6; j < 9; ++j) {
                pointGroups.get(6).add(new Cell(i, j));
            }
        }

        for (int i = 6; i < 9; ++i) {
            for (int j = 0; j < 3; ++j) {
                pointGroups.get(7).add(new Cell(i, j));
            }
            for (int j = 3; j < 6; ++j) {
                pointGroups.get(8).add(new Cell(i, j));
            }
            for (int j = 6; j < 9; ++j) {
                pointGroups.get(9).add(new Cell(i, j));
            }
        }

//        int i=1;
//        for(List<Cell> list:pointGroups.values()){
//            for(Cell cell:list){
//                System.out.println("Cell "+cell+" is in group "+i);
//            }
//            i++;
//        }
    }

    boolean uniqueInGroup(Cell cell) {
        int groupNumber = -1;
        for (int i = 1; i <= 9; ++i) {
            List<Cell> list = pointGroups.get(i);
            if (list.contains(cell)) {
//                System.out.println("Cell "+cell+" is in group "+i);
                groupNumber = i;
            }
        }

        List<Cell> list = pointGroups.get(groupNumber);
        for (int i = 0; i < 9; ++i) {
            if (list.get(i).equals(cell)) {
                continue;
            }
            if (boardInstance.board[list.get(i).x][list.get(i).y] == boardInstance.board[cell.x][cell.y] && boardInstance.board[cell.x][cell.y] != 0) {
//                System.out.println("Not unique");
                return false;
            }
        }
//        System.out.println("Unique");
        return true;
    }

    boolean isAlreadyPlaced(int number, int row, int column) {
        //Check column
        for (int i = 0; i < 9; ++i) {
            if (number == boardInstance.board[row][i] || number == boardInstance.board[i][column]) {
                return true; //duplicate exists
            }
        }
        Cell cell = new Cell(row, column);

        return false; //Unique
    }

    public boolean checkLoss(Cell cell) {
        for (int i = 1; i <= 9; ++i) {
            if (!isAlreadyPlaced(i, cell.x, cell.y)) {
                return false; //can be placed
            }
        }
        return true; //lost
    }

    public boolean place(Cell cell, int number) {
        if (!isAlreadyPlaced(number, cell.x, cell.y)) {
            boardInstance.board[cell.x][cell.y] = number;
            return true;    //placed
        }
        return false;   //coudln't place
    }

    public Cell getNextCell(Cell previousCell) {
        Cell cell = new Cell(previousCell.x, previousCell.y);

        if (previousCell.x == 8 && previousCell.y == 8) {
//            System.err.println("This can't happen");
            System.exit(0);
        }
        if (previousCell.y == 8) {
            cell.y = 0;
            cell.x++;
        } else {
            cell.y++;
        }
//        System.out.println("Returning next cell [" + cell.x + "][" + cell.y + "]");
        return cell;
    }

    public boolean solve(Cell cell) {

        if (boardInstance.board[cell.x][cell.y] != 0) {
            if (cell.x == 8 && cell.y == 8) {
                printBoard();
                System.exit(0);
            }
            Cell nextCell = getNextCell(cell);
            return solve(nextCell);

        }

        for (int i = 1; i <= 9; ++i) {
            if (checkLoss(cell)) { //Nothing can be placed
//                printBoard();
//                System.out.println("Nothing can be placed at cell " + cell+ " this board failed");
                break;
            }
            boolean placed = place(cell, i);

            if (!placed) {
//                System.out.println("Unable to place " + i + " at " + cell);
            }

            if (placed) { //placed
                if (!uniqueInGroup(cell)) {
                    continue;
                }
                if (cell.x == 8 && cell.y == 8) {
                    printBoard();
                    System.exit(0);
                }
//                System.out.println("Placed " + i + " at " + cell);
//                printBoard();
                Cell nextCell = getNextCell(cell);
//                System.out.println("Now getting next cell " + nextCell + " to solve");

                solve(nextCell);
            }
        }

        boardInstance.board[cell.x][cell.y] = 0;
//        System.out.println("This board failed! " + cell);
        return true; //Did not work well
    }

    public void checkCell(Cell c) {
        int value = boardInstance.board[c.x][c.y];
        boardInstance.board[c.x][c.y] = 0;
        int row = c.x;
        int column = c.y;
        for (int i = 0; i < 9; ++i) {

            if (boardInstance.board[i][column] == value) {
                System.err.println("You failed");
                System.exit(0);
            }
        }
        for (int i = 0; i < 9; ++i) {
            if (boardInstance.board[row][i] == value) {
                System.err.println("You failed");
                System.exit(0);
            }
        }
        boardInstance.board[c.x][c.y] = value;
    }

    void inputBoard() {
        Scanner scan = new Scanner(System.in);
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                boardInstance.board[i][j] = scan.nextInt();
            }
        }
    }

    public static void main(String[] args) {
        Sudoku9x9 sbt = new Sudoku9x9();
        System.out.println("Input board 9x9 (BLANK = 0 and digits must be seperated by space: ");
        sbt.inputBoard();
        sbt.initializeMap();
        if (sbt.solve(new Cell(0, 0))) {
            System.out.println("Puzzle unsolvable!");
            sbt.printBoard();
        }
        //Check correctness, if you like
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                sbt.checkCell(new Cell(i, j));
            }
        }
    }
}

Output:

1 2 6 4 8 5 7 9 3
7 9 4 3 1 6 2 5 8
5 8 3 9 7 2 6 4 1
8 3 2 6 9 7 4 1 5
6 5 9 1 4 8 3 7 2
4 1 7 2 5 3 9 8 6
9 6 5 7 2 1 8 3 4
3 4 8 5 6 9 1 2 7
2 7 1 8 3 4 5 6 9


Which is correct.

Sometimes a puzzle like

9 0 6 0 7 0 4 0 3
0 0 0 4 0 0 2 0 0
0 7 0 0 2 3 0 1 0
5 0 0 0 0 0 1 0 0
0 4 0 2 0 8 0 6 0
0 0 3 0 0 0 0 0 5
0 3 0 7 0 0 0 5 0
0 0 7 0 0 5 0 0 0
4 0 5 0 1 0 7 0 8

[Source of this particular puzzle board: http://sandwalk.blogspot.in/2007/06/i-knew-it-there-can-be-more-than-one.html]

can have multiple solutions. For this program to print all of them, just change the solve function to this:

public boolean solve(Cell cell) {

        if (boardInstance.board[cell.x][cell.y] != 0) {
            if (cell.x == 8 && cell.y == 8) {
                printBoard();
                return true;
//                System.exit(0);
            }
            Cell nextCell = getNextCell(cell);
            return solve(nextCell);

        }

        for (int i = 1; i <= 9; ++i) {
            if (checkLoss(cell)) { //Nothing can be placed
//                printBoard();
//                System.out.println("Nothing can be placed at cell " + cell+ " this board failed");
                break;
            }
            boolean placed = place(cell, i);

            if (!placed) {
//                System.out.println("Unable to place " + i + " at " + cell);
            }

            if (placed) { //placed
                if (!uniqueInGroup(cell)) {
                    continue;
                }
                if (cell.x == 8 && cell.y == 8) {
                    System.out.println("Found a solution: ");
                    printBoard();
//                    System.exit(0);
                    boardInstance.board[cell.x][cell.y] = 0; //Reset last cell
                    return true;
                }
//                System.out.println("Placed " + i + " at " + cell);
//                printBoard();
                Cell nextCell = getNextCell(cell);
//                System.out.println("Now getting next cell " + nextCell + " to solve");

                solve(nextCell);
            }
        }

        boardInstance.board[cell.x][cell.y] = 0;
//        System.out.println("This board failed! " + cell);
        return true; //Did not work well
    }

So that the output is now:

9 2 6 5 7 1 4 8 3
3 5 1 4 8 6 2 7 9
8 7 4 9 2 3 5 1 6
5 8 2 3 6 7 1 9 4
1 4 9 2 5 8 3 6 7
7 6 3 1 4 9 8 2 5
2 3 8 7 9 4 6 5 1
6 1 7 8 3 5 9 4 2
4 9 5 6 1 2 7 3 8


9 2 6 5 7 1 4 8 3
3 5 1 4 8 6 2 7 9
8 7 4 9 2 3 5 1 6
5 8 2 3 6 7 1 9 4
1 4 9 2 5 8 3 6 7
7 6 3 1 9 4 8 2 5
2 3 8 7 4 9 6 5 1
6 1 7 8 3 5 9 4 2
4 9 5 6 1 2 7 3 8

Puzzle unsolvable or no more solutions!

Which is correct.

No comments:

Post a Comment