Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

250px-Sudoku-by-L2G-20050714.svg

A sudoku puzzle…

250px-Sudoku-by-L2G-20050714_solution.svg

…and its solution numbers marked in red.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: A program that solves Sudoku.

Q: What are the data?

A: A Sudoku puzzle. Actually a 9 x 9 character matrix, with partially filled cells. Empty cells are represented as ‘.’

Q: Any constraints?

A: None except for the Sudoku rules:

  • Each row must have the numbers 1-9 occuring just once.
  • Each column must have the numbers 1-9 occuring just once.
  • Each block (check the link above for details about block) must have the numbers 1-9 occuring just once.

Q: Have you played Sudoku before?

A: Not even once. I guess this is my first and last attempt to play Sudoku. Based on the rules, I guess I have an idea for solve it. Just like the N-queens problem we solved last time, we will probably need backtracking: At an empty cell, I try to find a suitable number from a set of candidates to put it there and then move on to the next empty cell. If one does not work out, I find the next suitable number. If none of the candidates works out, then the number I placed at the previous empty cell was a bad choice and I need to go back to deal with it. This seems like a pattern that requires backtracking.

Q: Good, now to work with backtracking, are there anything you need?

A: Yes, I believe we need something to keep track of whether I could place a number in an empty cell or not, and a set of candidates for each empty cell.

Q: How do you know if you can place a number in an empty cell or not?

A: Hmm I have to check the row, column and block it resides in to see if that number already exists. The empty cells on the same row will share the info of this row. The same applies to columns and blocks. So we need three 9 x 9 boolean matrix: rowStatus, colStatus and blockStatus. Initially all values are set to false. If a number n is placed at cell (i, j), then we go and update rowStatus[i][n-1] = true, colStatus[j][n-1]=true, and blockStatus[getBlockInd(i,j)][n-1]=true.

Q: Good. Now what about the candidates for each empty cells you mentioned? It seems like you need to keep a lot of numbers at hand.

A: Hmm not necessarily. For each cell, there are only 9 options at most. I could try all of them every time but that seems a bit brutal. I could keep track of a number called startInd to save the index of the last number I tried at a certain cell. Next time I need another number at this cell, just get the number at the next index. If the next index is out of bound, that means none is a good fit. In that case, we set the  startInd of this cell to 0 and go backtracking to the previous cell.

Q: Sounds good. Now can you write some pseudo-code?

A: Sure.

// Initialization
// scan through the board and keep track of all the empty cells
emptyCells = getEmptyCells(board);
// update the status based on the initial board
updateStatus(rowStatus, colStatus, blockStatus, board);

int i = 0; // the index of an empty cell we are dealing with
while(true){
    Cell cell = emptyCells.get(i);
    int row = cell.row;
    int col = cell.col;
    char num = getSuitableNum(row, col, rowStatus, colStatus, blockStatus);
    if(num == '.'){ // no suitable num, previous bad choice
        if(isOutofBound(--i, emptyCells.size())) return;
        Cell previousCell = emptyCells.get(i);
        row = previousCell.row;
        col = previousCell.col;
        char previousVal = board[row][col];
        board[row][col]='.';
        undoStatusChange(rowStatus, colStatus, blockStatus, row, col, previousVal);
    }else{
        board[row][col] = num;
        updateStatusChange(rowStatus, colStatus, blockStatus, row, col, num);
        if(isOutofBound(++i, emptyCells.size())) return;
    }
}

// for details of utility functions like undoStatusChange, isOutofBound, and getSuitableNum, please check the real Java code at the bottom link.

Q: I see you are passing the rowStatus, colStatus and blockStatus around a lot. Is there anyway that we can organize them in a better way?

A: Hmm maybe I should put them all in one Class so I could just pass in one object instead.

Q: Sounds good, now let’s solve this with real code.

A: OK 🙂

Code on github:

 

 

Enhanced by Zemanta
Advertisements
Sudoku Solver

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s