# Doing more with check_sudoku

 2 I figure that if you wanted to write a program to actually solve sudoku puzzles, the checking whether a square is valid or not would probably be the most difficult part. Once we have check_sudoku defined, there are just a few more things we need to do. Define a function that takes as its input an incomplete sudoku square, then exhaustively enumerate all possible combinations of numbers, calling check_sudoku for each one until a solution is found or all possible combinations have been tried. Then, with a bit of work, check_sudoku could be modified to check diagonals, and (tricky) boxes, and you'd never have to do another sudoku puzzle in your life! Not worrying about modifying check_sudoku for the moment, but I'm going to have a go at the first task. My approach will be to write a loop that counts the blank spaces in the input (designated with a special character), creates a variable for each blank space, then increment those variables, each time generating a new list containing them and checking it. Shouldn't be too difficult, I'll post the code if I get it working. While I was thinking about this I noticed that you can't have a variable as an element of a list, including a variable just includes that variable's value in the list. What's the reason for this? Would it not be useful to be able to have dynamic elements in lists? asked 16 Mar '12, 17:05 curiousborg 659●2●10●31 accept rate: 41% There is a way to simulate a variable in a list, but it's not pretty. Use a list (and store one value in it). However, the variable won't be named in the usual way, and it will make it a little awkward to use. Later on, they should introduce objects (or dictionaries), and you'll kinda get what you want in a neater way. (16 Mar '12, 21:52) Charles Lin

 3 If you run into difficulties (or even if you don't), you might be interested in this essay (with Python code for a sudoku solver) by Peter Norvig: Solving Every Sudoku Puzzle answered 16 Mar '12, 17:23 Lisa McLean 3.4k●14●35 Great, thanks! (16 Mar '12, 20:23) curiousborg
 1 It might take quite a while to run if you're not clever in how you implement it. There are 9!= 362 880 different possible rows for a single row in a 9x9 sudoku board. If you know there is a particular square in that row can't contain a given digit, then there are still 322 560 different possibilities for that row. If it has a set digit in it then it drops to 40 320 possible arrangements of the rest. Sounds like an interesting and fun project though. answered 16 Mar '12, 17:19 fnenu-1 ♦♦ 18.5k●19●81●231 Then there is the question of supplying solvable problems to the program. You need at least 17 filled blocks to have a sudoku that's solvable without guessing. (16 Mar '12, 22:24) elssar Some googling led me to this which has a load of sudoku puzzles in a format that is easy to convert into a list of lists. The following code will do so(empty squares represented by an empty list): def single_line_to_list(s): result = [] for i in range(9): result.append([]) for j in range(9): char = s[9*i+j] if "1" <= char <= "9": result[i].append(int(char)) else: result[i].append([]) return result  (17 Mar '12, 00:54) Matthew Atki...
 0 I think it would need a little bit of 'recursion' and 'backtracking' to get it working , it isn't so easy , but not that hard too waiting for your code :) answered 17 Mar '12, 01:03 aur 172●1●3●14
 0 My effort, messy and inefficient, but seems to work. It starts off by creating a list containing the numbers 1-9 in all the empty squares, It then repeatedly scans through these elements, removing all numbers that are already in the same row, column or 3x3 square. If this doesn't get a result (it does for some puzzles), it sets the 1st undetermined element to each of the possible values and tries to solve. The count < 650 test creates a lot of pointless looping, i need to make a better way to test if anything was changed in the last iteration. Criticism/comments/suggestions welcome. #! /usr/bin/env python import copy def swap_column_rows(inlist): result = [] for i in range(len(inlist)): result.append([]) for j in range(len(inlist)): result[i].append(inlist[j][i]) return result def swap_squares_rows(inlist): """Input must be len(9)""" result = [] for a in range(len(inlist)): result.append([]) for i in range(0, len(inlist) / 3): for j in range(0, len(inlist) / 3): result[a].append(inlist[ ( a / 3 * 3) + i][(a % 3) * 3 + j]) return result def check_sudoku(sudoku_list): for row in sudoku_list: #check is square if len(row) != len(sudoku_list): return False for square_list in (sudoku_list, swap_column_rows(sudoku_list), swap_squares_rows(sudoku_list)): for row in square_list: numbers = range(1, len(row) + 1) for element in row: if element in numbers: numbers.remove(element) else: return False if numbers != []: return False return True def single_line_to_list(s): result = [] for i in range(9): result.append([]) for j in range(9): char = s[9*i+j] if "1" <= char <= "9": result[i].append(int(char)) else: result[i].append([]) return result def fill_empty_elements(inlist): """takes a square list of lists of len(9) and replaces elements that are not integers from 1 - 9 with range(1,10)""" for i in inlist: k = 0 for j in i: if type(j) is not int and len(j) == 0: i[k] = range(1,10) k += 1 def get_coords(x, y): """returns a list of coordinates in the same row, column and square as input""" result = [] lx = range(9) lx.remove(x) for i in lx: result.append((i, y)) ly = range(9) ly.remove(y) for i in ly: result.append((x, i)) squarex = range(x / 3 * 3, x / 3 * 3 + 3) squarex.remove(x) squarey = range(y / 3 * 3, y / 3 * 3 + 3) squarey.remove(y) for i in squarex: for j in squarey: result.append((i, j)) return result coord_dict = {} for i in range(9): for j in range(9): coord_dict[(i,j)] = get_coords(i,j) def is_not_possible(n, x, y, inlist): """returns True if n already exists in the same row, column or square""" coords = coord_dict[(x,y)] for elem in coords: if type(inlist[elem[1]][elem[0]]) is int: if inlist[elem[1]][elem[0]] == n: return True return False def is_solved(inlist): solved = True for i in inlist: for j in i: if type(j) is not int: solved = False return solved def solve_sudoku_wrap(inlist): result = copy.deepcopy(inlist) fill_empty_elements(result) return solve_sudoku(result) def solve_sudoku(inlist): result = copy.deepcopy(inlist) count = 0 while not is_solved(result) and count < 650: y = 0 for i in result: x = 0 for j in i: if type(j) is not int: if len(j) == 1: i[x] = j[0] else: for num in j: if is_not_possible(num,x,y,result): j.remove(num) x += 1 y += 1 count += 1 if count >= 650: for i in result: for j in i: if type(j) is not int: tmp = j tmp_index = i.index(j) for p in tmp: i[tmp_index] = p attempt = solve_sudoku(result) if check_sudoku(attempt): return attempt return result return result answered 17 Mar '12, 03:44 Matthew Atki... 1.9k●3●9●30 1 Adding a boolean "has_changed", setting it to false at the start of each loop and true when changing the list speeds it up massively, don't know why i didn't before. (17 Mar '12, 04:29) Matthew Atki... Reading the essay by Peter Norvig linked above, it seems I was along the right lines, but could have used better data structures. My program manages the puzzles I linked above almost instantly, however the hard puzzle he labels "grid2" takes about 5 minutes. Stepping through it one level at a time, it sets the first few rows to obviously false values(two of the same, I would have thought the first half of the "solve_sudoku" function would have prevented this) and then spends ages messing about with the lower half with no hope of success. (17 Mar '12, 05:44) Matthew Atki...
Question text:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

×15,266
×118
×56
×14
×4