- 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.
A sudoku puzzle...
...and its solution numbers marked in red.
class Solution {
final static int N = 9; // set the static field that do not change
public static int cellNum[] = new int[N * N]; // map each coordinate to a cell; 2d to 1d
public void solveSudoku(char[][] board) {
if (board == null || board.length != N || board[0].length != N)
throw new IllegalArgumentException("Board size must be 9x9"); // handle exception
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cellNum[i * 9 + j] = (i / 3) * 3 + (j / 3); // project 2d to 1d
// int as hashset to record nums already exist
int rows[] = new int[N];
int columns[] = new int[N];
int cells[] = new int[N];
int emptyCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == '.') {
emptyCount++;
continue;
}
int num = board[i][j] - '0' - 1;
// set up the in hashsets using bit manipulation
rows[i] |= (1 << num); // row i now has this num, so bit at num is now 1
columns[j] |= (1 << num); // col j now ...
cells[cellNum[i * 9 + j]] |= (1 << num); // cel 1d now ...
}
}
// coordinates for spots that need to be filled, a tuple maybe better as the (x, y) are usually read together
int[] emptyI = new int[emptyCount];
int[] emptyJ = new int[emptyCount];
int p = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (board[i][j] == '.') {
emptyI[p] = i; emptyJ[p] = j; p++;
}
helper(board, emptyI, emptyJ, 0, rows, columns, cells);
}
private boolean helper(char[][] board, int[] emptyI, int[] emptyJ, int p, int[] rows, int[] columns, int cells[]) {
if (p == emptyI.length) // recursion termination
return true;
int bestMask = (1 << 9) - 1; // 111111111
for (int k = p; k < emptyI.length; k++) {
int ii = emptyI[k], jj = emptyJ[k]; // coordinate of next vacant spot
int mask = ((1 << 9) - 1) & ~rows[ii] & ~columns[jj] & ~cells[cellNum[ii * 9 + jj]];
// the mask will be like 101001010 which translates into possible candidates are: 2, 4, 7, 9
// check which vacant spot has least candidates, swap it to the first of the vacant spot list
if (Integer.bitCount(mask) < Integer.bitCount(bestMask)) {
bestMask = mask;
int tmp = emptyI[p]; emptyI[p] = ii; emptyI[k] = tmp;
tmp = emptyJ[p]; emptyJ[p] = jj; emptyJ[k] = tmp;
}
}
int i = emptyI[p];
int j = emptyJ[p];
// System.out.printf("%d %d %s\n", i, j, Integer.toBinaryString(allNums));
// if the vacant spot has no candidates, return false
if (bestMask == 0)
return false;
// try each candidate
for (int k = 0; k < 9; k++)
if ((bestMask & (1 << k)) > 0) {
board[i][j] = (char) ('1' + k); // set vacant spot to one candidate
rows[i] |= (1 << k); // update row int hashset
columns[j] |= (1 << k); // update col
cells[cellNum[i * 9 + j]] |= (1 << k); // update cel
// depth first search
if (helper(board, emptyI, emptyJ, p + 1, rows, columns, cells))
return true;
// if did not go through, reset the int hashsets
rows[i] ^= (1 << k);
columns[j] ^= (1 << k);
cells[cellNum[i * 9 + j]] ^= (1 << k);
}
// when no candidate leads to a valid solution return false
return false;
}
}
my thoughts:
1. brutal force, iterate the board, try 1-9 for every spot. validate 9^81 boards in worst case.
2. solve board = solve (board + 1) till board is filled,
3. a) is the board valid? No -> stop, Yes ->b)
b) find the next move with smallest candidate set, if no next move ->stop, if one of the next move is impossible (candidate set is empty) ->
c) for all candidates, fill the move will the candidate, is the new board valid? No-> set the move to '.' Yes->b)
...
seems my logic is ok, but cannot form a valid recursion
my solution:
**********234ms
class Solution(object):
def findCan(self, i, j, board):
ss = set()
for k in range(9):
if board[i][k] != '.':
ss.add(board[i][k])
for k in range(9):
if board[k][j] != '.':
ss.add(board[k][j])
for x in (i/3*3, i/3*3+1, i/3*3+2):
for y in (j/3*3, j/3*3+1, j/3*3+2):
if board[x][y] != '.':
ss.add(board[x][y])
cands = '123456789'
can = []
for c in cands:
if c not in ss:
can.append(c)
return (len(can), i, j, can)
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.helper(board)
def helper(self, board):
bob = []
checker = True
for i in range(9):
for j in range(9):
if board[i][j] == '.':
checker = False
temp = self.findCan(i, j, board)
if temp[0] == 0:
#print board
return False
bob.append(temp)
#print bob
#print 'board: ', board
if checker:
return True
ro = -1
co = -1
msize = 10
for bo in bob:
if bo[0]<msize:
msize, ro, co = bo[0], bo[1], bo[2]
cans = bo[3]
#print cans, ro, co
#print board[ro][co]
for c in cans:
board[ro][co] = c
if self.helper(board):
return True
board[ro][co] = '.'
return False
**********Not Done
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
def build_set(b):
row = [None]*9
col = [None]*9
cell = [None]*9
for i in range(9):
row[i] = set()
for j in range(9):
if board[i][j] == '.':
continue
else:
row[i].add(board[i][j])
for j in range(9):
col[j] = set()
for i in range(9):
if board[i][j] == '.':
continue
else:
col[j].add(board[i][j])
for i in range(9):
cell[i] = set()
for x in (i/3*3, i/3*3+1, i/3*3+2):
for y in (i%3*3, i%3*3+1, i%3*3+2):
if board[x][y] == '.':
continue
else:
cell[i].add(board[x][y])
return (row, col, cell)
def find_next(b):
s = build_set(b)
row, col, cell = s[0], s[1], s[2]
cand = []
min_cand = ['1','2','3','4','5','6','7','8','9','0']
coor = (-1, -1)
for i in range(9):
for j in range(9):
if b[i][j] == '.':
for c in "123456789":
if c not in row[i] and c not in col[j] and c not in cell[j/3*3 + i%3]:
cand.append(c)
if len(cand) == 0: return ((-2,-2), [])
if len(cand)<len(min_cand):
min_cand = cand
cand = []
coor = (i, j)
return (coor, min_cand)
def move(b):
n = find_next(b)
i, j = n[0][0], n[0][1]
cand = n[1]
if i == -1: return True
if i == -2: return False
for c in cand:
b[i][j] = c
print b
print i, j, c, cand
if move(b): return
else:
print "hello", i, j, c, cand
b[i][j] = '.'
print b
#move(board)
def test(b):
if is_valid
test(board)
my comments:
if we need a func to return False/True do not expect it to return void at the same time!!!!
from other ppl's solution:
1. still lots to learn, 42ms:
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.board = board
self.val = self.possibleValue(board)
self.Solver()
def possibleValue(self, board):
nums = '123456789'
res, used = {}, {}
for r in range(9):
for c in range(9):
ele = board[r][c]
if ele != '.':
used[('r', r)] = used.get(('r', r), []) + [ele]
used[('c', c)] = used.get(('c', c), []) + [ele]
used[(r//3, c//3)] = used.get((r//3, c//3), []) + [ele]
else:
res[(r, c)] = []
for (i, j) in res:
inval = used.get(('r', i), []) + used.get(('c', j), []) + used.get((i//3, j//3), [])
res[(i, j)] = [n for n in nums if n not in inval]
return res
def Solver(self):
if len(self.val)==0:
return True
kee = min(self.val.keys(), key=lambda x: len(self.val[x]))
nums = self.val[kee]
for n in nums:
update = {kee:self.val[kee]}
if self.isValid(n, kee, update): # valid choice
if self.Solver(): # keep solving
return True
self.putBack(kee, update) # invalid choice or didn't solve it => undo
return False
def isValid(self, n, root, update):
self.board[root[0]][root[1]] = n
self.val.pop(root)
r, c = root
for key in self.val:
if n in self.val[key]:
if key[0] == r or key[1] == c or (key[0]//3, key[1]//3) == (r//3, c//3):
self.val[key].remove(n)
update[key] = n
if len(self.val[key]) == 0:
return False
return True
def putBack(self, root, update):
self.board[root[0]][root[1]] = '.'
for key in update:
if key not in self.val:
self.val[key] = update[key]
else:
self.val[key].append(update[key])
def undo(self, kee, update):
self.board[kee[0]][kee[1]]="."
for k in update:
if k not in self.val:
self.val[k]= update[k]
else:
self.val[k].append(update[k])
return None
2. python got time limit exceed:
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
digits="123456789";
def isok(self,board,c,m,n):
for i in range(9):
if board[m][i]==c or board[i][n]==c:
return False;
m=m-m%3;n=n-n%3;
for i in range(m,m+3):
for j in range(n,n+3):
if board[i][j]==c:return False;
return True;
def solve(self,board):
for i in range(9):
for j in range(9):
if board[i][j]=='.':
for c in self.digits:
if self.isok(board,c,i,j):
board[i][j]=c;
if self.solve(board):return True;
board[i][j]='.';
return False;
return True;
def solveSudoku(self, board):
self.solve(board);