#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0

    Sudoku solver school project error help!


    Hello,

    I am working on a sudoku solver with a friend for a school project. We have made a script were you can put in an image of a sudoku and it makes an output with the image solved. we don't get an error but it gets stuck or something if we run it. Does someone knows what we do wrong?

    here is the main script:
    Code:
    import cv2
    import numpy as np
    import time,sys
    from perfect import solve_sudoku
    
    ##############  Load OCR data for training #######################################
    samples = np.float32(np.loadtxt('feature_vector_pixels.data'))
    responses = np.float32(np.loadtxt('samples_pixels.data'))
    
    model = cv2.KNearest()
    model.train(samples, responses)
    
    #############  Function to put vertices in clockwise order ######################
    def rectify(h):
    		''' this function put vertices of square we got, in clockwise order '''
    		h = h.reshape((4,2))
    		hnew = np.zeros((4,2),dtype = np.float32)
    
    		add = h.sum(1)
    		hnew[0] = h[np.argmin(add)]
    		hnew[2] = h[np.argmax(add)]
    		
    		diff = np.diff(h,axis = 1)
    		hnew[1] = h[np.argmin(diff)]
    		hnew[3] = h[np.argmax(diff)]
    
    		return hnew
    		
    ################ Now starts main program ###########################
    
    img =  cv2.imread(sys.argv[1])
    gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    
    thresh = cv2.adaptiveThreshold(gray,255,1,1,5,2)
    contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    
    image_area = gray.size	# this is area of the image
    
    for i in contours:
    	if cv2.contourArea(i)> image_area/2: # if area of box > half of image area, it is possibly the biggest blob
    		peri = cv2.arcLength(i,True)
    		approx = cv2.approxPolyDP(i,0.02*peri,True)
    		#cv2.drawContours(img,[approx],0,(0,255,0),2,cv2.CV_AA)
    		break
    
    #################      Now we got sudoku boundaries, Transform it to perfect square ######################
    
    h = np.array([ [0,0],[449,0],[449,449],[0,449] ],np.float32)	# this is corners of new square image taken in CW order
    
    approx=rectify(approx)	# we put the corners of biggest square in CW order to match with h
    
    retval = cv2.getPerspectiveTransform(approx,h)	# apply perspective transformation
    warp = cv2.warpPerspective(img,retval,(450,450))  # Now we get perfect square with size 450x450
    
    warpg = cv2.cvtColor(warp,cv2.COLOR_BGR2GRAY)	# kept a gray-scale copy of warp for further use
    
    ############ now take each element for inspection ##############
    
    sudo = np.zeros((9,9),np.uint8)		# a 9x9 matrix to store our sudoku puzzle
    
    smooth = cv2.GaussianBlur(warpg,(3,3),3)
    thresh = cv2.adaptiveThreshold(smooth,255,0,1,5,2)
    kernel = cv2.getStructuringElement(cv2.MORPH_CROSS,(3,3))
    erode = cv2.erode(thresh,kernel,iterations =1)
    dilate =cv2.dilate(erode,kernel,iterations =1)
    contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    
    for cnt in contours:
    	area = cv2.contourArea(cnt)
    	if 100<area<800:
    	
    		(bx,by,bw,bh) = cv2.boundingRect(cnt)
    		if (100<bw*bh<1200) and (10<bw<40) and (25<bh<45):
    			roi = dilate[by:by+bh,bx:bx+bw]
    			small_roi = cv2.resize(roi,(10,10))
    			feature = small_roi.reshape((1,100)).astype(np.float32)
    			ret,results,neigh,dist = model.find_nearest(feature,k=1)
    			integer = int(results.ravel()[0])
    			
    			gridy,gridx = (bx+bw/2)/50,(by+bh/2)/50	# gridx and gridy are indices of row and column in sudo
    			sudo.itemset((gridx,gridy),integer)
    sudof= sudo.flatten()
    strsudo = ''.join(str(n) for n in sudof)
    ans = solve_sudoku(strsudo)		# ans is the solved sudoku we get as a string
    
    #################### Uncomment below two lines if you want to print solved 9x9 matrix sudoku on terminal, optional ####################
    
    #l = [int(i) for i in ans]		# we make string ans to a list 
    #ansarray = np.array(l,np.uint8).reshape((9,9))  # Now we make it into an array of sudoku
    
    ############### Below print sudoku answer on our image.  #########################################
    
    for i in xrange(81):
    	if strsudo[i]=='0':
    		r,c = i/9, i%9
    		posx,posy = c*50+20,r*50+40
    		cv2.putText(warp,ans[i],(posx,posy),cv2.FONT_HERSHEY_SIMPLEX,1,(0,255,0),2)
    		
    cv2.imshow('img',warp)
    
    cv2.waitKey(0)
    cv2.destroyAllWindows()
    here is perfect.py:
    Code:
    ''' this module solves a sudoku.
    
    This is taken from website of Peter Norvig
    
    You can get complete code and explanation of this code from http://norvig.com/sudoku.html
    
    So whereever this code is used, give due to credits to real author, Peter Norvig
    
    '''
    
    def cross(A, B):
        "Cross product of elements in A and elements in B."
        return [a+b for a in A for b in B]
    
    digits   = '123456789'
    rows     = 'ABCDEFGHI'
    cols     = digits
    squares  = cross(rows, cols)
    unitlist = ([cross(rows, c) for c in cols] +
                [cross(r, cols) for r in rows] +
                [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
    units = dict((s, [u for u in unitlist if s in u]) for s in squares)
    #print(units)
    peers = dict((s, set(sum(units[s],[]))-set([s])) for s in squares)
    
    def parse_grid(grid):
        """Convert grid to a dict of possible values, {square: digits}, or
        return False if a contradiction is detected."""
        ## To start, every square can be any digit; then assign values from the grid.
        values = dict((s, digits) for s in squares)
        for s,d in grid_values(grid).items():
            if d in digits and not assign(values, s, d):
                return False ## (Fail if we can't assign d to square s.)
        return values
    
    def grid_values(grid):
        "Convert grid into a dict of {square: char} with '0' or '.' for empties."
        chars = [c for c in grid if c in digits or c in '0.']
        assert len(chars) == 81
        return dict(zip(squares, chars))
    
    def assign(values, s, d):
        """Eliminate all the other values (except d) from values[s] and propagate.
        Return values, except return False if a contradiction is detected."""
        other_values = values[s].replace(d, '')
        if all(eliminate(values, s, d2) for d2 in other_values):
            return values
        else:
            return False
    
    def eliminate(values, s, d):
        """Eliminate d from values[s]; propagate when values or places <= 2.
        Return values, except return False if a contradiction is detected."""
        if d not in values[s]:
            return values ## Already eliminated
        values[s] = values[s].replace(d,'')
        ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
        if len(values[s]) == 0:
            return False ## Contradiction: removed last value
        elif len(values[s]) == 1:
            d2 = values[s]
            if not all(eliminate(values, s2, d2) for s2 in peers[s]):
                return False
        ## (2) If a unit u is reduced to only one place for a value d, then put it there.
        for u in units[s]:
            dplaces = [s for s in u if d in values[s]]
            if len(dplaces) == 0:
                return False ## Contradiction: no place for this value
            elif len(dplaces) == 1:
                # d can only be in one place in unit; assign it there
                    if not assign(values, dplaces[0], d):
                        return False
        return values
    
    def display(values):
        "Display these values as a 2-D grid."
        width = 1+max(len(values[s]) for s in squares)
        line = '+'.join(['-'*(width*3)]*3)
        for r in rows:
            print (''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
            if r in 'CF': print(line)
        print
    
    def solve(grid): return search(parse_grid(grid))
    
    def search(values):
        "Using depth-first search and propagation, try all possible values."
        if values is False:
            return False ## Failed earlier
        if all(len(values[s]) == 1 for s in squares): 
            return values ## Solved!
        ## Chose the unfilled square s with the fewest possibilities
        n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
        return some(search(assign(values.copy(), s, d)) 
            for d in values[s])
    
    def some(seq):
        "Return some element of seq that is true."
        for e in seq:
            if e: return e
        return False
    
    import time, random
    
    def solve_all(grids, name='', showif=0.0):
        """Attempt to solve a sequence of grids. Report results.
        When showif is a number of seconds, display puzzles that take longer.
        When showif is None, don't display any puzzles."""
        def time_solve(grid):
            start = time.clock()
            values = solve(grid)
            t = time.clock()-start
            ## Display puzzles that take long enough
            if showif is not None and t > showif:
                display(grid_values(grid))
                if values: display(values)
                print ('(%.2f seconds)\n' % t)
            return (t, solved(values))
        times, results = zip(*[time_solve(grid) for grid in grids])
        N = len(grids)
        if N > 1:
            print ("Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % (sum(results), N, name, sum(times)/N, N/sum(times), max(times)))
    
    def solved(values):
        "A puzzle is solved if each unit is a permutation of the digits 1 to 9."
        def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
        return values is not False and all(unitsolved(unit) for unit in unitlist)
    
    def from_file(filename, sep='\n'):
        "Parse a file into a list of strings, separated by sep."
    #    return file(filename).read().strip().split(sep)
        pass
    
    def random_puzzle(N=17):
        """Make a random puzzle by making N assignments. Restart on contradictions.
        Note the resulting puzzle is not guaranteed to be solvable, but empirically
        about 99.8% of them are solvable."""
        values = dict((s, digits) for s in squares)
        for s in random.sample(squares, N):
            if not assign(values, s, random.choice(values[s])):
                return random_puzzle(N) ## Give up and make a new puzzle
        return ''.join(values[s] if len(values[s])==1 else '.' for s in squares)
    
    def shuffled(seq):
        "Return a randomly shuffled copy of the input sequence."
        seq = list(seq)
        random.shuffle(seq)
        return seq
    
    grid1  = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
    grid2  = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
    hard1  = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
    grid3 =  '79......3.......6.8.1..4..2..5......3..1......4...62.92...3...6.3.6.5421.........'
    extreme ='.26....1.75......2..86.1.9......3....9.4.8.2....1......1.5.92..6......57.3....98.'
    #result = solved(grid_values(extreme))    
    def solve_sudoku(s):
    	k=solve(s)
    
    	keys = k.keys()
    	keys.sort()
    	ans = ''.join(k[i] for i in keys)
    	return ans
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    Dr. Norvig's sudoku solver seems to work. This computer vision thing looks cool. While I install it why don't you explain better about the input and where you think your program gets stuck?

    As we await the cv2 installation, note that python has a divmod function.

    r,c = i/9, i%9

    r,c = divmod(i,9)

    Where do I get these files?
    feature_vector_pixels.data
    samples_pixels.data

    Wow! I haven't seen the Hershey fonts since 1985. Love-'em. Because they are vector fonts they readily map onto surfaces.
    Last edited by b49P23TIvg; November 14th, 2012 at 11:19 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0
    Thank you very much for your help.
    I have the files here but how can i post them? i already tried a filedrop site but i may not post url's.

    Shall I email the files to you? Then i can send you everything
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    Sure send some files. I'd like to try this computer vision code.

    b49p23tivg@yahoo.com

    Inspected only by request.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0
    i have sended you all the files
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    Don't expect immediate answer...
    Code:
    $ python sudoku.py sudoku.jpg 
    OpenCV Error: Unspecified error (The function is not implemented. Rebuild the library with Windows, GTK+ 2.x or Carbon support. If you are on Ubuntu or Debian, install libgtk2.0-dev and pkg-config, then re-run cmake or configure script) in cvShowImage, file /tmp/OpenCV-2.4.3/modules/highgui/src/window.cpp, line 620
    Traceback (most recent call last):
      File "sudoku.py", line 107, in <module>
        cv2.imshow('img',warp)
    cv2.error: /tmp/OpenCV-2.4.3/modules/highgui/src/window.cpp:620: error: (-2) The function is not implemented. Rebuild the library with Windows, GTK+ 2.x or Carbon support. If you are on Ubuntu or Debian, install libgtk2.0-dev and pkg-config, then re-run cmake or configure script in function cvShowImage
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    OK, your program is amazing. I'll try it later with more images. Your python program says
    cv2.waitKey(0)
    If I mouse click the solution window (or otherwise set it to have active input, or it may already be active) then press a key on my keyboard, say, the space bar, the program terminates.

    (img:13887): Gdk-CRITICAL **: IA__gdk_error_trap_pop: assertion `gdk_error_traps != NULL' failed

    I don't know what to do about that message other than direct stderr to /dev/null
    [code]Code tags[/code] are essential for python code and Makefiles!
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0

    error


    Hello,

    I finished the script by ending it with showing the image,
    but my problem now is that it only works on most of the images that i got from internet. but if i make a picture (what should work) then he gives an error. i really don't know what it's problem is.

    so i finished the script with:
    Code:
    cv2.namedWindow("Sudoku solved",0)
    cv2.imshow("Sudoku solved", warp)
    cv2.waitKey(0)
    but when i make a photo of a sudoku and put it in:
    Code:
    Traceback (most recent call last):   File "C:\Documents and Settings\Administrator\Bureaublad\sudoku_v0.0.6\sudoku.py", line 95, in <module>     ans = solve_sudoku(strsudo)		# ans is the solved sudoku we get as a string   File "C:\Documents and Settings\Administrator\Bureaublad\sudoku_v0.0.6\perfect.py", line 159, in solve_sudoku     keys = k.keys() AttributeError: 'bool' object has no attribute 'keys'
  16. #9
  17. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    Interesting. The unix file command identifies file type when it can. In this case, the answer is revealing. s[123].jpg are photos of sudoku puzzle I took with my fine camera. Your program does not work with my new pictures. I haven't quickly found a way to convert images to jpeg JFIF 1.02.
    Code:
    $ file *.jpg
    s1.jpg:     JPEG image data, JFIF standard 1.01, comment: "Created with GIMP"
    s2.jpg:     JPEG image data, JFIF standard 1.01, comment: "Created with GIMP"
    s3.jpg:     JPEG image data, JFIF standard 1.01
    sudoku.jpg: JPEG image data, JFIF standard 1.02
    Last edited by b49P23TIvg; November 30th, 2012 at 02:00 PM. Reason: typo correction
    [code]Code tags[/code] are essential for python code and Makefiles!
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0

    Thnx


    Thank you!!! ;D
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0

    identify file


    i wonder how you checked the file extension.
    now i made this script but it only print's '6'.

    Code:
    import string
    import os
    
    root = "plaatje"
    jpg = string.find(file(os.path.join(root,"sudoku.jpg"),'rb').read(),'JFIF')
    print jpg
    what am i doing wrong, and why do i get '6' as answer
    ?
  22. #12
  23. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    http://linux.die.net/man/1/file

    If you aren't lucky enough to use a unix system, that is, if you're stuck with Microsoft, install cygwin/X11

    Then use the file command, like I showed in previous post.
    [code]Code tags[/code] are essential for python code and Makefiles!
  24. #13
  25. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    7
    Rep Power
    0

    py2exe


    Hi!

    We figured out that the resolution of the photo had to do a lot with the problem. So it actually works.

    But now i want to convert my python file to a .exe
    The problem is that i get an error if i want to open the converted file. It says that the program doesn't work anymore.. I think it has something to do with the fact i use tkinter opencv en numpy. Can you please help me??

    this is the final script:
    Code:
    import time,sys
    import cv2
    import Tkinter as tk
    import numpy as np
    from perfect import solve_sudoku
    
    
    class App:
        def __init__(self, master):
            self.display_button_entry(master)
    
        def setup_window(self, master):
            self.f = tk.Frame(master, height=200, width=300, padx=10, pady=12)
            self.f.pack_propagate(0)
    
        def display_button_entry(self, master):
            self.setup_window(master)
            v = tk.StringVar()
            label = tk.Label(master, text="Vul de bestandsnaam van uw sudoku in")
            self.e = tk.Entry(self.f, textvariable=v)
            button = tk.Button(self.f, text="Solve", command=self.solve)
            self.e.pack()
            label.pack()
            button.pack()
            self.f.pack()
    
        def solve(self):
            bestand = self.e.get()
            print bestand
            if bestand == 0:
                print 'Voer uw sudoku in'
            else:
                print 'het bestand '+bestand+' is opgelost'
            ##############  Tekenherkenning data #######################################
            samples = np.float32(np.loadtxt('feature_vector_pixels.data'))
            responses = np.float32(np.loadtxt('samples_pixels.data'))
    
            model = cv2.KNearest()
            model.train(samples, responses)
    
            #############  Rangschikking hoeken ######################
            def rectify(h):
    		
                            h = h.reshape((4,2))
                            hnew = np.zeros((4,2),dtype = np.float32)
    
                            add = h.sum(1)
                            hnew[0] = h[np.argmin(add)]
                            hnew[2] = h[np.argmax(add)]
    		
                            diff = np.diff(h,axis = 1)
                            hnew[1] = h[np.argmin(diff)]
                            hnew[3] = h[np.argmax(diff)]
    
                            return hnew
    		
            ################ hoofdgedeelte ###########################
    
            img =  cv2.imread(bestand)
            gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    
            thresh = cv2.adaptiveThreshold(gray,255,1,1,5,2)
            contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    
            image_area = gray.size	# gebied van de afbeelding
    
    
            for i in contours:
                    if cv2.contourArea(i)> image_area/2: # als het gebied van het vierkant de helft is van het totaal, zou het de grootste kunnen zijn
                            peri = cv2.arcLength(i,True)
                            approx = cv2.approxPolyDP(i,0.02*peri,True)
                            cv2.drawContours(img,[approx],0,(0,255,0),2,cv2.CV_AA)
                            break
    
            #################      Perfect vierkent van het oppervlak maken ######################
    
            h = np.array([ [0,0],[449,0],[449,449],[0,449] ],np.float32)	# nieuwe hoeken
    
            approx=rectify(approx)
    
            retval = cv2.getPerspectiveTransform(approx,h)	# perspectief transformeren
            warp = cv2.warpPerspective(img,retval,(450,450))  # creeŽrt vierkant met ingevulde afmetingen
    
            warpg = cv2.cvtColor(warp,cv2.COLOR_BGR2GRAY)	# grijze kopie
    
            ############ elk gedeelte analyseren ##############
    
            sudo = np.zeros((9,9),np.uint8)		# een 9x9 getallenschema maken
    
            smooth = cv2.GaussianBlur(warpg,(3,3),3)
            thresh = cv2.adaptiveThreshold(smooth,255,0,1,5,2)
            kernel = cv2.getStructuringElement(cv2.MORPH_CROSS,(3,3))
            erode = cv2.erode(thresh,kernel,iterations =1)
            dilate = cv2.dilate(erode,kernel,iterations =1)
            contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    
            for cnt in contours:
                    area = cv2.contourArea(cnt)
                    if 100<area<800:
                
                            (bx,by,bw,bh) = cv2.boundingRect(cnt)
                            if (100<bw*bh<1200) and (10<bw<40) and (25<bh<45):
                                    roi = dilate[by:by+bh,bx:bx+bw]
                                    small_roi = cv2.resize(roi,(10,10))
                                    feature = small_roi.reshape((1,100)).astype(np.float32)
                                    ret,results,neigh,dist = model.find_nearest(feature,k=1)
                                    integer = int(results.ravel()[0])
                                
                                    gridy,gridx = (bx+bw/2)/50,(by+bh/2)/50
                                    sudo.itemset((gridx,gridy),integer)
            sudof = sudo.flatten()
            strsudo = ''.join(str(n) for n in sudof)
            ans = solve_sudoku(strsudo)
    
    
    
            ############### Antwoord projecteren in onze afbeelding  #########################################
    
            for i in xrange(81):
                    if strsudo[i]=='0':
                            r,c = i/9, i%9
                            posx,posy = c*50+20,r*50+40
                            cv2.putText(warp,ans[i],(posx,posy),cv2.FONT_HERSHEY_SIMPLEX,1,(0,255,0),2)
    		
            cv2.namedWindow("Sudoku opgelost",0)
            cv2.imshow("Sudoku opgelost",warp)
            cv2.waitKey(0)
    
            cv2.destroyAllWindows()
    
    
    def main():
        root = tk.Tk()
        root.title('Sudoku Solver')
        root.resizable(width=tk.NO, height=tk.NO)
        app = App(root)
        root.mainloop()
    
    main()
  26. #14
  27. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    Congratulations! I do not know how to continue from there.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo