#       sudoku_solver_7.py
#		version 0.1
#
#       Copyright 2011 Daniel Veazey <danielveazey@gmail.com>
#
#       This program is free software; you can redistribute it and/or modify
#       it under the terms of the GNU General Public License as published by
#       the Free Software Foundation; either version 2 of the License, or
#       (at your option) any later version.
#
#       This program is distributed in the hope that it will be useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#       GNU General Public License for more details.
#
#       You should have received a copy of the GNU General Public License
#       along with this program; if not, write to the Free Software
#       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#       MA 02110-1301, USA.
#
#       
 
def quadfinder(find): # to figure out which quad to check for a position while solving
	global quad_position
	for quadcount in range(0, 9):
		if find in quad_position[quadcount]:
			return quadcount
 
print "Welcome to Daniel Veazey's Sudoku Solver 7."
print "http://www.danielveazey.com"
print "Please fill in the available numbers on the board,"
print "starting on the top row (Row 1), going left to right."
print "If a square is blank, put a 0 in its place."
print "Separate each position with a comma and a space."
print "Each position can be only one digit, 0 through 9."
print "Example:"
print "Row 1: 5, 6, 0, 0, 4, 1, 0, 0, 8"
print "Row 2: 1, 0, 0, 0, 0, 9, 0, 7, 0"
print "etc."
print
print "Let's get started."
print
print
 
## ask the user to populate the board by rows
row = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range(0, 9):
	row[x] = list(input("Row " + str(x+1) + ": "))
 
print
print
print "Original board:"
for x in range (0, 9):
	print row[x]
 
## define and populate the columns by referring to the rows
col = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range (0, 9):
	col[x] = [row[0][x], row[1][x], row[2][x], row[3][x], row[4][x], row[5][x], row[6][x], row[7][x], row[8][x]]
 
## define and populate quads by referring to slices of rows
quad = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad[0] = row[0][0:3] + row[1][0:3] + row[2][0:3]
quad[1] = row[0][3:6] + row[1][3:6] + row[2][3:6]
quad[2] = row[0][6:] + row[1][6:] + row[2][6:]
quad[3] = row[3][0:3] + row[4][0:3] + row[5][0:3]
quad[4] = row[3][3:6] + row[4][3:6] + row[5][3:6]
quad[5] = row[3][6:] + row[4][6:] + row[5][6:]
quad[6] = row[6][0:3] + row[7][0:3] + row[8][0:3]
quad[7] = row[6][3:6] + row[7][3:6] + row[8][3:6]
quad[8] = row[6][6:] + row[7][6:] + row[8][6:]
 
## populate list of single positions
position = list()
for z in range(0, 81):
	for x in range(0, 9):
		for y in range(0, 9):
			position.append(row[x][y])
 
## put list of possible answers in unsolved single positions
for x in range(0, 81):
	if position[x] == 0:
		position[x] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
## define which positions are in which quads
quad_position = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad_position[0] = [0, 1, 2, 9, 10, 11, 18, 19, 20]
quad_position[1] = [3, 4, 5, 12, 13, 14, 21, 22, 23]
quad_position[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]
quad_position[3] = [27, 28, 29, 36, 37, 38, 45, 46, 47]
quad_position[4] = [30, 31, 32, 39, 40, 41, 48, 49, 50]
quad_position[5] = [33, 34, 35, 42, 43, 44, 51, 52, 53]
quad_position[6] = [54, 55, 56, 63, 64, 65, 72, 73, 74]
quad_position[7] = [57, 58, 59, 66, 67, 68, 75, 76, 77]
quad_position[8] = [60, 61, 62, 69, 70, 71, 78, 79, 80]
 
################# SOLVING ######################################
## this program uses only a very simple method to solve the puzzle,
## just checking to see if a possible answer for a position
## is already in its row, column or quad. if so, the possible answer
## is eliminated from the list of possible answers.
 
did_change = True
while did_change == True:
	did_change = False
	for x in range(0, 81):
		if type(position[x]) == list:
			y = 0
			while type(position[x]) == list and y < len(position[x]): # to only keep checking if there are more items in the list of possible answers
				# check to see if the possible answer is already in a position in the row, column or quad
				if position[x][y] in row[x/9] or position[x][y] in col[x%9] or position[x][y] in quad[quadfinder(x)]: # quadfinder tells us which quad to check
					del position[x][y] ## delete the possible answer if it's found elsewhere
					did_change = True ## to keep the loop going
					if len(position[x]) == 1: ## if list of possible answers is only one item long,
						position[x] = position[x][0] ## remove the nested list
						row[x/9][x%9] = position[x] ## and copy the answer to the rows,
						col[x%9][x/9] = position[x] ## columns,
						for quad_count in range(0, 9): ## and quads
							if x in quad_position[quad_count]: ## similar to function quadfinder(), but used on its own here
								for z in range(0, 9):
									if x == quad_position[quad_count][z]:
										quad[quad_count][z] = position[x]
				else: y = y + 1 # to check the next item in the list of possible answers
 
## additional methods will go here in the future
 
## find out if the puzzle was solved:
solved = True
for x in range(0, 81):
	if type(position[x]) == list:
		solved = False
 
if solved == False:
	print
	print
	print "Here is a list of positions with either"
	print "the correct answers or"
	print "a list of possible correct answers:"
	for x in range(0, 81):
		print str(x+1) + ': ' + str(position[x])
 
	## also print board by rows
	print
	print
	print "This is as far as I got using the simple method Scroll up"
	print "to see a list of possible answers for each position on the board."
	for x in range (0, 9):
		print row[x]
else:
	print
	print
	print "I SOLVED IT!!!"
	for x in range (0, 9):
		print row[x]