soduko problem

[fonzali]

hi guys , I am interested in writing a code to do the soduko ( or sudoku ) , I found this code on the internet which is supposed to be the shortest soduko solver but it is so short that I can not undrestand it . can any one help please ?

def r(a): i=a.find('0') if i<0:print a [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]forj in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]r(raw_input())

thanx in advanceali

[katharnakh]

hi,

supposed to be the shortest soduko solver

yeah, intresting...

can any one help please ?

post the code with proper indentation.

kath.

[fonzali]

this is how it was written on the internet , all in one line , I just paste and copied it

[ffao]

There are basically two ways to solve a sudoku:

1) Solve it by logic, using simple rules such as the ones we, human beings, use, such as "if a square has only one possibility, than that number must be there". There are several solvers on the net that implement this kind of deductive solving, and reading the way they do it can probably give you an idea of what to do:

http://www.sudokusolver.co.uk/solvemethods.html
http://www.gwerdy.com/products/sudoku_solver/

2) Backtracking. Basically, using this method, you try every possible solution; if you reach a dead-end, you backtrack one square and try another number instead of the last number you tried. Googling for "sudoku solver" often reveals many pages about Donald Knuth's DLX algorithm, but I think something like that is better left to C.

[fonzali]

thanks , those links could be helpful . I have not read them yet

[BearofNH]

Request:

post the code with proper indentation.

Response:

this is how it was written on the internet , all in one line , I just paste and copied it

fonzali, what kind of excuse is that? katharnakh made a reasonable request; getting the line breaks and indents right (and having the program work) is the obvious first step in figuring out the logic. You might even learn something in the process.

[fonzali]

hi BearofNH , I did not mean to make excuses , the code looked pretty strange to me , this is how I figured it should be with proper indentation :

def r(a):
 i=a.find('0')
 if i<0:
     print a
 [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
 j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]
 r(raw_input())

this is the best I could come up with and if it helps , this is how to run it :
echo 000010000301400860900500200700160000020805010000097004003004006048006907000080000 | python sudoku.py
one of the many things which I don't undrestand is the '14**7*9' , I hope I have been helpful . sorry for not doing this earlier ali

[ffao]

#solve sudoku by backtracking
def solve_sudoku(board):
 
 #i is the first non-filled place, and the one we're going to try different values for
 i=board.find('0')
 
 #if i == -1, the puzzle is solved
 if i<0:
     print board

 #iterate over all squares j; if the big test returns true, then j is in the same column, block or row as i and needs to be considered
 #if the test is true, the value of j square is appended, meaning the final result is a list of all the values the i square surely cannot have

 # python has a nice feature called lazy evaluation. 
 # if the first clause is true, the result of the other one is irrelevant for the output of "or". 
 # therefore we use "a or b" to execute b only if a is false.
 exclusion_list = [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j] for j in range(81)]

#14**7*9 is 948721536, which contains all the digits from 1-9.
#therefore "for m in `14**7*9` and the below are equivalent.
#iterate through all the possible values for this square i.
 for m in "123456789":
 #lazy evaluation, again!
 #recursively call solve_sudoku itself with board[i] = m if this value of m is not on our exclusion list.
  [m in exclusion_list or solve_sudoku(board[:i]+m+board[i+1:])]

#solve sudoku puzzle
solve_sudoku(raw_input())

[fonzali]

hi ffao , thank you very much , now I undrestand what is going on . thanks again ali