这两天突然对数独产生了浓厚的兴趣,思考了一下如何用程序来解决数独问题。
解数独使用的方法为回溯法,按照顺序执行:
- 若已经填满,输出结果
- 对于没有填写数字的空格,检测在数独规则之下有哪些数字可填
- 任意填入一个可能的数字,对下一个未填的空格执行步骤1-4
- 当可填数字为空时说明填法出错,返回2选取另一个可填的数字
这样就获得了数独的解
其实人类解数独大概也是这样一个试错的过程,只不过人类不会死板地一切按照步骤观察并执行,而是进行模糊化的观察,这大概就是大部分人类解不出来高难度数独的原因吧233.
好的上代码,这里刻意选择了一个有多解的情况,当然了,正规的数独题目是单解的
python
#!/usr/bin/env python3 # -*-coding:utf-8 -*- def canWrite(n,position,sudoku): x=position%9 y=position//9 for i in range(9): if sudoku[y*9+i]==n: return False for j in range(9): if sudoku[j*9+x]==n: return False b_x=(x//3)*3 b_y=(y//3)*3 for k in range(3): for i in range(3): if sudoku[(b_y+k)*9+b_x+i]==n: return False return True def tryInsert(position,sudoku,resultNum): if position==81: resultNum[0]+=1 showSudoku(sudoku) print('='*17) print('found %d answer(s)'%(resultNum[0])) print('='*17+'\n\n') return 1 if sudoku[position]==0: for i in range(1,10): if canWrite(i,position,sudoku): sudoku[position]=i tryInsert(position+1,sudoku,resultNum) sudoku[position]=0 if sudoku[position]!=0: tryInsert(position+1,sudoku,resultNum) return 0 def showSudoku(sudoku): print('='*17) for i in range(81): print(sudoku[i],end=' ') if (i+1)%9 == 0: print('') print('='*17) if __name__ == '__main__': sudoku=[ 5,0,2,6,0,0,3,0,0, 0,0,0,0,0,8,0,1,0, 0,0,0,2,0,0,0,6,8, 2,4,0,0,0,0,0,0,9, 0,0,7,0,0,0,1,3,0, 6,0,0,0,0,0,8,0,0, 0,5,6,0,1,0,0,0,0, 9,0,0,0,0,0,6,0,1, 0,7,0,0,0,9,0,4,2 ] showSudoku(sudoku) print('') resultNum=[0] tryInsert(0,sudoku,resultNum) print('finished. found %d answer(s)'%(resultNum[0]))
C++
#include<iostream> using namespace std; int sudoku[81] = { 5,0,2,6,0,0,3,0,0, 0,0,0,0,0,8,0,1,0, 0,0,0,2,0,0,0,6,8, 2,4,0,0,0,0,0,0,9, 0,0,7,0,0,0,1,3,0, 6,0,0,0,0,0,8,0,0, 0,5,6,0,1,0,0,0,0, 9,0,0,0,0,0,6,0,1, 0,7,0,0,0,9,0,4,2 }; bool canWrite(int n,int position,int sudoku[81]); int tryInsert(int position, int sudoku[81],int resultNum[1]); void showSudoku(int sudoku[81]); int main() { int resultNum[1] = { 0 }; tryInsert(0, sudoku, resultNum); cout << endl << "finished. found" << resultNum[0] << "answer(s)" << endl; system("pause"); return 0; } bool canWrite(int n,int position, int sudoku[81]) { int x = position % 9; int y = position / 9; for (int i = 0; i < 9; i++) { if (sudoku[y * 9 + i] == n) return false; } for (int j = 0; j < 9; j++) { if (sudoku[j * 9 + x] == n) return false; } int p_x = (x / 3) * 3; int p_y = (y / 3) * 3; for (int k = 0; k < 3; k++) { for (int i = 0; i < 3; i++) { if (sudoku[(p_y + k) * 9 + p_x + i] == n) return false; } } return true; } int tryInsert(int position, int sudoku[81] ,int resultNum[1]) { if (position == 81) { resultNum[0]++; showSudoku(sudoku); cout << "=================" << endl; cout << "found " << resultNum[0] << " answer(s)" << endl; cout << "=================" << endl << endl; return 0; } if (sudoku[position] == 0) { for (int i = 1; i < 10; i++) { if (canWrite(i, position, sudoku)) { sudoku[position] = i; tryInsert(position + 1, sudoku, resultNum); sudoku[position] = 0; } } } else { tryInsert(position + 1, sudoku, resultNum); } return 0; } void showSudoku(int sudoku[81]) { cout << "=================" << endl; for (int i = 0; i < 81; i++) { cout << sudoku[i] << " "; if ((i + 1) % 9 == 0) cout << endl; } cout << "=================" << endl; }
Comments | NOTHING