Sudoku Solver Stanford University-Books Pdf

Sudoku Solver Stanford University
16 Dec 2019 | 49 views | 0 downloads | 10 Pages | 892.61 KB

Share Pdf : Sudoku Solver Stanford University

Download and Preview : Sudoku Solver Stanford University


Report CopyRight/DMCA Form For : Sudoku Solver Stanford University



Transcription

As mentioned these steps are very common across Sudoku solvers Another. implementation described on the web is a guide by MathWorks on how to solve the puzzle from. an image using MATLAB 4 The steps are pretty much identical except two things the cell. division is done in the perspective of the original image no homography is applied to correct for. the perspective and the digits are recognized using structuring elements instead of a neural net. One additional implementation described can be found at 5 where the cell division is done by. detecting the internal grid lines using a Hough transform within the puzzle bounds instead of. assuming a perfect 9x9 grid division, Figure 1 Left a nonplanar puzzle Right screenshot from Sudoku Vision 2 when looking at the puzzle on the left. The potential problem with all these implementations is the assumption that the grid lines. of the puzzle appear straight in the image which is only true if the puzzle surface is planar in the. real world when the image was taken assuming no lens distortion When a puzzle is nonplanar. dividing the puzzle into cells with straight lines may result in a bad partitioning of the puzzle. which will negatively affect the number recognition step In figure 1 above the 9 in the cell. directly below the top right cell of the puzzle has been erroneously determined to be in the top. right cell by the app Note that the top right corner of the bounding quad shown by the app is. much lower than the actual top right corner of the puzzle which is probably the cause of the. misplacement of the 9 since the app thought its location was much closer to the top right. corner than it actually is This motivates a better method of partitioning the cells in the case of. nonplanar puzzles, III Overview of Algorithm, Figure 2 Major steps of the algorithm. Figure 3 Finding four corners of grid by using projections. All the steps except the partitioning of grid cells are very similar to those of the. implementations mentioned in the Previous Work section with a few small modifications and. additional steps The major steps are shown in figure 2 The captured image is binarized using. adaptive thresholding and the largest blob of the binary image is extracted and is assumed to be. the Sudoku grid The four corners of the grid are determined the following way each. foreground pixel in the grid blob will project its coordinates onto the vectors 1 1 and. 1 1 The pixel with the minimum projections and the pixel with the maximum projection. onto 1 1 are assumed to be the top left and bottom right corners of the grid respectively. Similarly the pixels with the min and max projections onto 1 1 are assumed to be the. bottom left and the top right corners of the grid respectively Figure 3 shows a visualization of. this Now using these four corners a homography is calculated to transform the grid from the. binary image to a square A small border is left on all sides of the transformed grid in case the. boundaries of the grid curve outwards Next the centers of each cell are individually estimated. using structuring elements For each cell a square neighborhood of fixed size around each cell. center is cropped out The number of foreground pixels in this neighborhood is calculated if it. doesn t fall within a specified range it s assumed that the cell does not contain a digit If the. number of cells that may contain a digit is less than 17 the supposed minimum number of clues. that a Sudoku must have to ensure a unique solution the algorithm terminates early This check. is usually where the algorithm terminates when the camera image does not contain a Sudoku. puzzle and instead contains some arbitrary scene Now for each viable cell the maximum blob. is extracted and is assumed to be the digit The digit blob is cropped and scaled and compared to. nine templates of the digits 1 through 9 The template producing the least square difference. with the digit blob is selected as the recognized value After all values are recognized a sanity. check is performed to make sure the rules of Sudoku have not been violated i e no digit is. repeated in a row nor in a column nor in any of the nine 3x3 subgrids Then the Sudoku is. solved using backtracing using the code found in 6 Both the detected values and the solution. values are written onto a blank image at the cell centers determined earlier and the image is. transformed back to the perspective of the original image Finally this image is blended into the. original image to produce the output image displayed on the device screen. A couple of the more interesting steps mentioned above will be described in more detail. in the next sections, IV Cell Center Estimation, This step is where this approach differs from most existing Sudoku solvers For. nonplanar grids dividing the grid evenly into 9x9 cells can negatively affect number recognition. In figure 4 a perfect 9x9 grid of squares is overlaid on top of the perspective corrected Sudoku. grid While this particular input may not suffer much from partitioning the grid this way it s. easy to imagine if the grid was more warped causing the partitioning to differ significantly from. the actual grid lines In such a case if the grid is partitioned before digit blob extraction many. digits would be split in between different cells producing a bad input for the recognition step If. the digit blobs are extracted without the grid being partitioned it would still be difficult to tell. which cell that digit belongs to In either case there should be a more accurate way to determine. the cell locations, Figure 4 An even 9x9 partitioning of a nonplanar grid. The method implemented works as follows We will start out with a rough estimate of. the cell center locations We do this by placing them at the centers of the partitions of an even. 9x9 partitioning i e place them at the center of the green cells in Figure 4 Then for each cell. we will refine its cell center position vertically then horizontally. Figure 5 Left the two structuring elements used Right refining a cell center s vertical position using SE A. Figure 6 Refining a cell center s horizontal position starting where vertical refinement left off The final cell center. estimate is shown in the far right image, Figure 5 shows the two structuring elements we ll use When a structuring element is.
centered at its response is defined to be the sum of the values of the pixels within the four. orange rectangles SE A is used to refine the cell center vertically and SE B is used to refine the. cell center horizontally Both SEs are square and sized to be the same size as an evenly. partitioned cell or 1 81 of the area of the grid, To vertically refine a cell center the basic intuition is that we center SE A at the current. cell center estimate and slide it up and down within some predefined range and place it where the. highest number of foreground pixels will fall within the orange areas The right three images of. figure 5 visualize this process where the green dot represents the cell center estimate and the. blue line represents the range in which SE A s center can move The rightmost image in figure 5. shows where the max response will occur when the top and bottom grid lines of the cell. coincide with the top two and bottom two orange areas of SE A This might beg the question. why not just join the top two or bottom two orange areas of SE A into one long thin area. Why have this gap in between The answer is that this configuration reduces the effect that the. number in the cell or in adjacent cells will have on the responses of the SEs If a cell has a. number this gap allows that number to mostly pass through the SE without generating a high. response We re really only looking for the gridline pixels with these SEs so we want the SE s. orange areas to avoid the pixels of the number in the cell After the cell center has been refined. vertically we do the same thing but transposed we slide SE B left and right within a fixed range. of the cell center estimate provided by vertical refinement and move the cell center horizontally. to the location of highest response This is shown in figure 6 There the gap explanation is. more easily seen if SE B were just two long vertical bars instead of 4 shorter ones it will pick. up a strong response when the right vertical bar coincides with the pixels of the 3. Figure 7 Left initial cell center estimates based on even 9x9 division of square boundary Right cell center. estimates after vertical and horizontal refinement. V Number Recognition, Nine templates of 20x20 pixels were used in the number recognition step After the digit. blob is extracted from the square neighborhood of each cell center it s cropped scaled evenly. in width and height and centered in a 20x20 image The templates were constructed from a. training set of 289 images made exclusively of digit blobs produced by this algorithm The. template for a particular digit was set to be the difference between the mean of the training. images of that digit class mean and the mean of all the training images These nine templates. are hard coded into the app During the recognition step the mean of the extracted number. images is calculated test mean To match a number image to a template the test mean is first. subtracted from it Then the mean square error MSE between that image and each of the. template images is calculated The template giving the smallest MSE is selected as the. recognized value of that number, Figure 8 The templates used which are the class mean minus the overall mean of the training set. VI Results, Several methods were tried for digit recognition before settling on using least MSE 370. 20x20 images of digit blobs were extracted by this algorithm from many different images of. Sudoku puzzles found online Of those 289 were used as training data and 81 were used as test. data Three different methods were tried least MSE eigenfaces and fisherfaces To classify a. testing image the calculated descriptor of the test image is used in a Euclidean nearest neighbor. search against the 9 class mean descriptors of the training data The accuracy of classifying the. testing images as well as the training images were determined For eigenfaces the accuracy. seemed to peak when 50 eigenfaces were used so that was used to generate the data below For. fisherfaces 8 fisherfaces generated from the 50 eigenfaces space was used The accuracy of. each of these three methods are shown in Table 1 below. Training Accuracy Test Accuracy, Least MSE 99 65 100.
50 Eigenfaces 99 65 97 53, 8 Fisherfaces 100 97 53. Table 1 Accuracy of digit recognition of the three attempted methods. As seen the accuracy of all three methods are essentially equal The slightly higher test. accuracy of least MSE over the others is probably within the margin of error From these results. least MSE was chosen as the method to implement in the app since it was by far the simplest and. fastest method of the three with seemingly no reduction in accuracy. Figure 9 Some screenshots of the app taken while running. Subjectively the detection results in the final app were very good It was very easy to get. the solution to show up when used on a clean noise free image of a Sudoku with good contrast. Viewing slightly nonplanar Sudoku puzzles did not affect the detection results much as long as. the entire puzzle was in the frame of the camera and took up a large enough portion of the image. the algorithm worked, On images with low contrast or images with a few low contrast areas it was sometimes. difficult to get the solution to show up consistently the solution overlay would occasionally. show an incorrect recognition of a number or two Also there was an unforeseen issue in the. effect of motion blur and focus changes if the device could not be held steady the resulting. motion blur could cause one of the algorithm steps to fail Also when the camera decides to. refocus the temporary blurring of the image will have the same negative effect These effects. made the app slightly less user friendly to use, From a performance standpoint the app displayed around 5 to 10 frames per second on. an Android smartphone with comparable specs to the Samsung Galaxy S5 While this is not a. smooth framerate the speed could still be considered real time. VII Conclusion and Future Work, An algorithm for automatically solving Sudoku puzzles from mobile camera images was. described While many of the steps of the algorithm are very similar to existing Sudoku solvers. the grid partitioning step avoided an even partitioning in favor of using structuring elements to. estimate each cell center individually This change reduces the probability that a digit is broken. up during partitioning or being erroneously assigned to a different cell than the one it actually. resides in The final app was able to correctly extract digits from non planar puzzles and puzzles. viewed from an angle Some possible improvements include. A Freezing the display once a solution has been successfully computed so that the user can. comfortably view it without having to continue holding the camera still. B Improve the performance of the app by utilizing multithreading or GPU operations to improve. the framerate for a smooth viewing experience Another way could be to downsample the input. image first to reduce computation time of the subsequence image processing steps. C Add the ability for the app to give out the solution step by . Sudoku Solver Yixin Wang wangyix stanford edu Abstract An Android app was developed that allows a Sudoku puzzle to be extracted and solved in real time using

Related Books

Understanding Japanese Management Practices

Understanding Japanese Management Practices

just in time and lifetime employment It then provides practical advice on how to successfully enter and position Western products in the Japa nese market Finally it provides an advice on how to negotiate success fully with Japanese business partners and reveals what Western managers can learn from Japanese management practices Japanese management practices have had an enormous influence

The Strategic Marketing Process

The Strategic Marketing Process

The Strategic Marketing Process How to Structure Your Marketing Activities to Achieve Better Results Written by Moderandi Inc creators of the marketing planning and management app at www MarketingMO com Second Edition 2013 Strategy toolS CuStomer aCquiSition The Strategic Marketing Process SaleS ProCeSS CamPaign Planning marKeting Plan Seo amp Sem CuStomer retention online aDVertiSing

Chapter 11 Basics of Semiconductor Lasers

Chapter 11 Basics of Semiconductor Lasers

Chapter 11 Basics of Semiconductor Lasers 11 1 Introduction 11 1 1 Introduction to Semiconductor Lasers In semiconductor optical amplifiers SOAs photons multiplied via stimulated emission In SOAs photons were confined in the dimensions transverse to the waveguide but were allowed to escape from the end of the waveguide We now consider optical cavities in which the photons are confined in

The Seven Challenges Workbook Saylor Academy

The Seven Challenges Workbook Saylor Academy

The Seven Challenges Workbook Cooperative Communication Skills for Success at Home and at Work a structured intensive exploration of seven challenging skills for a lifetime of better communication in work family friendship amp community

Communication Principles for a Lifetime

Communication Principles for a Lifetime

may be reproduced with Communication Principles for a Lifetime Fifth Edition by Steven A Beebe Susan J Beebe and Diana K Ivy provided such reproductions bear copyright notice but may not be reproduced in any form for any other purpose without written permission from the copyright owner To obtain permission s to use material from this work please submit a written request to Pearson

GH3RGPYLRUQUID RWQL

GH3RGPYLRUQUID RWQL

manual is extremely useful and should be read after operating the vehicle for the first time The manual is structured so that it can be used for reference For this reason it should be kept in the vehicle for ready access Options and accessories Optional or accessory equipment described in this manual is indicated by an asterisk

Clutch Systems ZF

Clutch Systems ZF

18 Automated manual transmission Intelligent gear shifting 20 Dual mass flywheel DMF Multi stage vibrational damping 03 The Company 25 The ZF Group 26 Research and development to secure mobility 3 The demands placed on suppliers in the automotive sec tor are changing dramatically Increasingly suppliers are being called upon to integrate components into complex systems a

Automatic transmission 9G TRONIC 725

Automatic transmission 9G TRONIC 725

The automatic transmission 9G TRONIC 725 0 is an entirely new electronically controlled automatic transmission with 9 forward gears and one reverse gear The ratios for the gear stages are achieved by planetary gear sets All the transmis sion functions and control components for this automatic transmission are combined in one assembly module The fully integrated transmission controller unit

MERCEDES JAGUAR shop ukrtrans biz

MERCEDES JAGUAR shop ukrtrans biz

MERCEDES JAGUAR DAIMLER CHRYSLER 722 6 5 Speed AUTOMATIC TRANSMISSION SERVICE GROUP 18639 S W 107 AVENUE CUTLER BAY FLORIDA 33157 305 670 4161 No part of any ATSG publication may be reproduced stored in any retrieval system or transmitted in any form or by any means including but not limited to electronic mechanical photocopying recording or otherwise without written permission

KiesIA 13e SM Ch10 Final National Tsing Hua University

KiesIA 13e SM Ch10 Final National Tsing Hua University

Copyright 2010 John Wiley amp Sons Inc Kieso Intermediate Accounting 13 e Solutions Manual For Instructor Use Only 10 9 Questions Chapter 10 Continued b e