https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
規則滿簡單的，但是玩起來說實在滿花時間的，這東西大概1998年，我還在當兵時流行了一陣子，現在還是會在一些報紙、雜誌中看到，在1998年時，就寫了一個簡單的 C code來計算答案。
最近公司導入新的制度，面試要考類似 leetcode 的coding題目，由於要出題，左想右想，覺得Sudoku 這是個不錯的好題目，規則簡單，實作上會用到些程式的觀念，也是現實生活中會看到的題目，而不是為了 coding 而 coding 的題目。
說實在二十年前的程式想法，早就已經忘光了，只好重新構思解法，年紀與經驗增長，同時加上 google 的威力，其實很快就大概有了方向。
好像還差了什麼？Yes，如果目前的位置所有的數字都不合規則的話，就必需再回頭改一下上一次位置的數字，這樣子的話才可以把所有的狀況都試完，用 recursive 的 function 來說就是要做到 Recursive backtracking 回溯的功能。
想法有了就是寫 code 了，之前用 C，現在學習 AI 都用 Python，改用 Python 來試試好了。感謝google的威力，網路上就是現成的 Python code了。
https://stackoverflow.com/questions/1697334/algorithm-for-solving-sudoku
只是要做為 interview 的解答，希望要求再高一些，程式可讀再高一些，stackoverflow 上面的，還有些改善的空間。
規則滿簡單的，但是玩起來說實在滿花時間的，這東西大概1998年，我還在當兵時流行了一陣子，現在還是會在一些報紙、雜誌中看到，在1998年時，就寫了一個簡單的 C code來計算答案。
最近公司導入新的制度，面試要考類似 leetcode 的coding題目，由於要出題，左想右想，覺得Sudoku 這是個不錯的好題目，規則簡單，實作上會用到些程式的觀念，也是現實生活中會看到的題目，而不是為了 coding 而 coding 的題目。
說實在二十年前的程式想法，早就已經忘光了，只好重新構思解法，年紀與經驗增長，同時加上 google 的威力，其實很快就大概有了方向。
- 首先看來需要一個 "檢查" 規則的 function
- 然後就是需要一個產生 1~9 的 function，產生後就把數字填入試試看，符合規則的話，就再試下一個空格的數字。
好像還差了什麼？Yes，如果目前的位置所有的數字都不合規則的話，就必需再回頭改一下上一次位置的數字，這樣子的話才可以把所有的狀況都試完，用 recursive 的 function 來說就是要做到 Recursive backtracking 回溯的功能。
想法有了就是寫 code 了，之前用 C，現在學習 AI 都用 Python，改用 Python 來試試好了。感謝google的威力，網路上就是現成的 Python code了。
https://stackoverflow.com/questions/1697334/algorithm-for-solving-sudoku
只是要做為 interview 的解答，希望要求再高一些，程式可讀再高一些，stackoverflow 上面的，還有些改善的空間。
- isValid function : 可讀可以再加強些，稍微改成 check row, check colum and check grid 看來就完美多了
- findNextCellToFill function : 這個只是找出下一個要填的位置，功用不大，其實可以不用這個 function
- solveSudoku function : 這個 recursive function，傳入 i, j 當作位置，要解決的位置，其實可以整合成 position 一個變數就好，上面的 findNextCellToFill 就可以變成簡單的 position + 1
- 最後加上些 test case，看看輸出是否正確就完成了
以下就是修正完的 code，看來比之前的好一些，思路變清楚，結構也易讀，以下是source code 的部分。
# -*- coding: utf-8 -*-
"""
Created on Thu Dec 6 11:26:29 2018
@author: Robin_Chiu
"""
# A standard Sudoku puzzle consists of a grid of 9 blocks. Each block contains 9 boxes arranged in 3 rows and 3 columns.
# · Each column must contain all of the numbers 1 through 9 and no two numbers in the same column of a Sudoku puzzle can be the same.
# · Each row must contain all of the numbers 1 through 9 and no two numbers in the same row of a Sudoku puzzle can be the same.
# · Each block must contain all of the numbers 1 through 9 and no two numbers in the same block of a Sudoku puzzle can be the same.
def isValid(grid, i, j, e):
# check the row
rowOk = all([e != grid[i][x] for x in range(9)])
if not rowOk:
return False
# check the column
columnOk = all([e != grid[x][j] for x in range(9)])
if not columnOk:
return False
# check the grid
# finding the top left x,y co-ordinates of the section containing the i,j cell
secTopX, secTopY = 3 *(i//3), 3 *(j//3) #floored quotient should be used here.
for x in range(secTopX, secTopX+3):
for y in range(secTopY, secTopY+3):
if grid[x][y] == e:
return False
# pass all the check return True
return True
def solveSudoku(grid, pos=0):
# calculate the i, j position
i = pos//9
j = pos%9
# if it's the end stop the recursive
if pos == 81:
for each in grid:
print(each)
# if there is number in it, check the next one
elif grid[i][j] != 0:
solveSudoku(grid, pos+1)
# find the valid number in i, j
else:
for e in range(1,10):
if isValid(grid,i,j,e):
grid[i][j] = e
solveSudoku(grid, pos+1)
# Undo the current cell for backtracking
grid[i][j] = 0
def main():
puzzle1 = [[5, 1, 7, 6, 0, 0, 0, 3, 4],
[2, 8, 9, 0, 0, 4, 0, 0, 0],
[3, 4, 6, 2, 0, 5, 0, 9, 0],
[6, 0, 2, 0, 0, 0, 0, 1, 0],
[0, 3, 8, 0, 0, 6, 0, 4, 7],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 9, 0, 0, 0, 0, 0, 7, 8],
[7, 0, 3, 4, 0, 0, 5, 6, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
puzzle2 = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
solveSudoku(puzzle1)
print()
solveSudoku(puzzle2)
if __name__ == '__main__':
main()
