soduko problem
 

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

Re: soduko problem
 

hi, yeah, intresting...
post the code with proper indentation.

kath.

Re: soduko problem
 

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

Re: soduko problem
 

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.

Re: soduko problem
 

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

Re: soduko problem
 

Request:
Response:
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.

Re: soduko problem
 

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

Re: soduko problem
 

#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())

Re: soduko problem
 

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