数独
最近在网上看到数独，感觉非常有意思，所以就来实现以下。
一个数独题的网站（https://www.oubk.com/DailySudoku/17778/1），偷懒直接爬虫抓下来了，哈哈
代码实现
#!/usr/bin/python
# _*_ coding:utf-8 _*_
# Author:xiaoshubiao
# Time : 2018/9/4 10:41
import requests
from bs4 import BeautifulSoup
import math
import numpy class sudoku:
url = 'https://www.oubk.com/DailySudoku/17778/4'
one_value_list = []
def __init__(self):
self.bigtable = self.get_table()
self.sudo = self.get_table()
print('==============题目==========')
print(self.sudo)
self.current_x = 0
self.current_y = self.find_one()
self.current_v = 1
self.start()
# 通过爬虫直接获取数独的值
def get_table(self):
bigtable = numpy.zeros((9, 9))
web_data = requests.get(self.url)
soup = BeautifulSoup(web_data.text,'lxml')
tab = soup.select('table.ptb')[0]
inps = tab.select('input')
for i in range(0,len(inps)):
v = inps[i].get('value') or 0
bigtable[int(i / 9)][i % 9] = v
return bigtable
def start(self):
while self.current_x < 9:
while self.current_y < 9:
while self.current_v < 10:
if self.judge(self.current_x,self.current_y,self.current_v):
self.bigtable[self.current_x][self.current_y] = self.current_v
#每当有一个值确定之后，检查是否存现8缺一
self.current_v = 1
self.next_value()
if self.current_x == 9:
break
else:
self.current_v += 1
if self.current_x == 9:
one = self.find_one()
one_value = self.bigtable[0][one]
if one_value not in self.one_value_list:
print('==========答案============')
print(self.bigtable)
self.one_value_list.append(one_value)
self.bigtable = self.get_table()
one_value += 1
while one_value < 10:
if self.judge(0,one,one_value):
self.bigtable[0][one] = one_value + 1
self.current_x = 0
self.current_y = one + 1
self.current_v = 1
break
one_value += 1 else:
self.last_value()
if self.current_x < 0:
break
# 获取下一个值
def next_value(self):
self.current_y += 1
if self.current_y == 9:
self.current_x += 1
if self.current_x == 9:
self.current_y = 9
return
self.current_y = 0
if not self.bigtable[self.current_x][self.current_y] == 0:
self.next_value()
# 获取上一个值
def last_value(self):
# 判断当前值是否可以修改
if self.sudo[self.current_x][self.current_y] == 0:
self.bigtable[self.current_x][self.current_y] = 0
self.current_y -= 1
if self.current_y == -1:
self.current_x -= 1
self.current_y = 8
# 判断上个值是否可以修改
if self.sudo[self.current_x][self.current_y] == 0:
self.current_v = int(self.bigtable[self.current_x][self.current_y] + 1)
if self.current_v == 10:
self.last_value()
else:
self.last_value()
#检查8缺1
def check(self):
# 如果某行或者某列、某小方块有8个数确定，那么第九个数就是确定的
flag = True
while True:
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
d = 0
for i in range(0,9):
if self.bigtable[self.current_x][i] not in l:
d = i
else:
l.remove(self.bigtable[self.current_x][i])
if len(l) == 1:
if self.judge(self.current_x, d, l[0]):
# 8缺1 符合则填入该值
self.bigtable[self.current_x][d] = l[0]
else:
flag = False
break
# 检查列 =================================
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
d = 0
for i in range(0, 9):
if self.bigtable[i][self.current_y] not in l:
d = i
else:
l.remove(self.bigtable[i][self.current_y])
if len(l) == 1:
if self.judge(d,self.current_y,l[0]):
# 8缺1 符合则填入该值
self.bigtable[d][self.current_y] = l[0]
else:
flag = False
break
# 检查小方块
for x_small in range(0,3):
for y_small in range(0,3):
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
d = 0
for i in range(0, 3):
for j in range(0, 3):
if self.bigtable[i][j] not in l:
x = x_small*3 + i
y = y_small*3 + j
else:
l.remove(self.bigtable[i][j])
if len(l) == 1:
if self.judge(x, y, l[0]):
# 8缺1 符合则填入该值
self.bigtable[x][y] = l[0]
else:
flag = False
break
return flag
#判断当前值是否合适
def judge(self,x,y,v):
if v in self.bigtable[x]:
return False
for i in range(0, 9):
if v == self.bigtable[i][y]:
return False
# 检查9方块是否满足
x_small = math.floor(x / 3)
y_small = math.floor(y / 3)
for i in range(0, 3):
for j in range(0, 3):
if v == self.bigtable[i + x_small * 3][j + y_small * 3]:
return False
return True
#拿到数独第一个未知数的坐标
def find_one(self):
for i in range(0,9):
if self.sudo[0][i] == 0:
return i
s = sudoku()
整体思想：
从第一个位置开始暴力穷举，如果当前值（1-9）都不合适，就去找到当前值的上一个值+1，以此类推
千万不要用递归，会溢出的。用while循环、for循环都行。所有的递归都可以写成while（for）循环