Sudoko Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
def solveSudoku(self, board):
self.board = board
self.solve()
def findUnassigned(self):
for row in range(9):
for col in range(9):
if self.board[row][col] == ".":
return row, col
return -1, -1
def solve(self):
row, col = self.findUnassigned()
#no unassigned position is found, puzzle solved
if row == -1 and col == -1:
return True
for num in ["1","2","3","4","5","6","7","8","9"]:
if self.isSafe(row, col, num):
self.board[row][col] = num
if self.solve():
return True
self.board[row][col] = "."
return False
def isSafe(self, row, col, ch):
boxrow = row - row%3
boxcol = col - col%3
if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
return True
return False
def checkrow(self, row, ch):
for col in range(9):
if self.board[row][col] == ch:
return False
return True
def checkcol(self, col, ch):
for row in range(9):
if self.board[row][col] == ch:
return False
return True
def checksquare(self, row, col, ch):
for r in range(row, row+3):
for c in range(col, col+3):
if self.board[r][c] == ch:
return False
return TrueRelated Problems
Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.
Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.
Return the shortest such subarray and output its length.
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1