Prerequisites:<\/h3>\n
1. Python 3.x (we used 3.7.10)
\n2. OpenCV – 4.4.0
\n3. Numpy – 1.19.3
\n4. Tensorflow – 2.5.0
\n5. Imutils – 0.5.4<\/p>\n
Download Sudoku Solver OpenCV Project<\/h3>\n
Download source code of python sudoku solver: Sudoku Solver Project Source Code<\/strong><\/a><\/p>\n Sudoku is a combinational number-placement puzzle. The objective of sudoku is to fill a 9×9 grid with some digits in such a way so that each column, row, and nine 3×3 subgrids contain all of the digits from 0-9.<\/p>\n We\u2019ll use an algorithm called backtracking. Backtracking is an algorithm for finding solutions to some computational problem. It tries to find a solution until it validates all criteria.<\/p>\n In sudoku, the algorithm will put a number in an empty space and then move on to the next empty space, if anywhere some criteria fail then it will turn back to some previous solutions and changes it according to the criteria. It continues until it finds a final solution that matches all the criteria.<\/p>\n solver.py<\/strong><\/p>\n Now the main program where we actually solve and preview the solved sudoku.<\/p>\n 1. Import necessary packages. Sudoku-Solver.py<\/strong><\/p>\n Output:<\/p>\n Output<\/strong>:<\/p>\n But we want to preview the solved board in the main input image. So let’s do that.<\/p>\n Output:<\/strong><\/p>\nWhat is Sudoku?<\/h3>\n
# DataFlair OpenCV Sudoku solver\r\n\r\ndef find_empty(board):\r\n\"\"\"checks where is an empty or unsolved block\"\"\"\r\nfor i in range(len(board)):\r\nfor j in range(len(board[0])):\r\nif board[i][j] == 0:\r\nreturn (i, j) # row, col\r\n\r\nreturn None<\/pre>\n
\n
def valid(board, num, pos):\r\n# Check row\r\nfor i in range(len(board[0])):\r\nif board[pos[0]][i] == num and pos[1] != i:\r\nreturn False\r\n\r\n# Check column\r\nfor i in range(len(board)):\r\nif board[i][pos[1]] == num and pos[0] != i:\r\nreturn False\r\n\r\n# Check box\r\nbox_x = pos[1] \/\/ 3\r\nbox_y = pos[0] \/\/ 3\r\n\r\nfor i in range(box_y*3, box_y*3 + 3):\r\nfor j in range(box_x * 3, box_x*3 + 3):\r\nif board[i][j] == num and (i,j) != pos:\r\nreturn False\r\n\r\nreturn True<\/pre>\n
\n
def solve(board):\r\nfind = find_empty(board)\r\nif not find:\r\nreturn True\r\nelse:\r\nrow, col = find\r\n\r\nfor i in range(1,10):\r\nif valid(board, i, (row, col)):\r\nboard[row][col] = i\r\n\r\nif solve(board):\r\nreturn True\r\nboard[row][col] = 0\r\nreturn False<\/pre>\n
\n
def get_board(bo):\r\nif solve(bo):\r\nreturn bo\r\nelse:\r\nraise ValueError<\/pre>\n
\n
Steps :<\/strong><\/h3>\n
\n2. Find sudoku board in an image.
\n3. Split the board.
\n4. Predict digits of each box.
\n5. Solve the board.<\/p>\n1. Import necessary packages:<\/h4>\n
# DataFlair Sudoku solver\r\n\r\nimport cv2\r\nimport numpy as np\r\nfrom tensorflow.keras.models import load_model\r\nimport imutils\r\nfrom solver import *<\/pre>\n
\n
2. Find sudoku board in an image:<\/h4>\n
# Read image\r\nimg = cv2.imread('sudoku1.jpg')\r\ncv2.imshow(\"Input image\", img)<\/pre>\n\n
def find_board(img):\r\n\"\"\"Takes an image as input and finds a sudoku board inside of the image\"\"\"\r\ngray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)\r\nbfilter = cv2.bilateralFilter(gray, 13, 20, 20)\r\nedged = cv2.Canny(bfilter, 30, 180)\r\nkeypoints = cv2.findContours(edged.copy(), cv2.RETR_TREE,\r\ncv2.CHAIN_APPROX_SIMPLE)\r\ncontours = imutils.grab_contours(keypoints)\r\nnewimg = cv2.drawContours(img.copy(), contours, -1, (0, 255, 0), 3)\r\ncv2.imshow(\"Contour\", newimg)<\/pre>\n
\n
![\"contour\"](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/contour.webp\")
<\/a><\/p>\ncontour.png\r\n\r\ncontours = sorted(contours, key=cv2.contourArea, reverse=True)[:15]\r\nlocation = None\r\n# Finds rectangular contour\r\nfor contour in contours:\r\napprox = cv2.approxPolyDP(contour, 15, True)\r\nif len(approx) == 4:\r\nlocation = approx\r\nbreak\r\nresult = get_perspective(img, location)\r\nreturn result, location<\/pre>\n
\n
def get_perspective(img, location, height = 900, width = 900):\r\n\"\"\"Takes an image and location of an interesting region.\r\nAnd return the only selected region with a perspective transformation\"\"\"\r\npts1 = np.float32([location[0], location[3], location[1], location[2]])\r\npts2 = np.float32([[0, 0], [width, 0], [0, height], [width, height]])\r\n\r\n# Apply Perspective Transform Algorithm\r\nmatrix = cv2.getPerspectiveTransform(pts1, pts2)\r\nresult = cv2.warpPerspective(img, matrix, (width, height))\r\nreturn result<\/pre>\n
\n
![\"perspective](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/sudoku-perspective-transformation.webp\")
<\/a><\/p>\n\n
board, location = find_board(img)\r\ncv2.imshow(\"Board\", board)<\/pre>\n
![\"board\"](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/board.webp\")
<\/a><\/p>\n3. Split the board:<\/h4>\n
# split the board into 81 individual images\r\ndef split_boxes(board):\r\n\"\"\"Takes a sudoku board and split it into 81 cells.\r\neach cell contains an element of that board either given or an empty cell.\"\"\"\r\nrows = np.vsplit(board,9)\r\nboxes = []\r\nfor r in rows:\r\ncols = np.hsplit(r,9)\r\nfor box in cols:\r\nbox = cv2.resize(box, (input_size, input_size))\/255.0\r\ncv2.imshow(\"Splitted block\", box)\r\ncv2.waitKey(50)\r\nboxes.append(box)\r\nreturn boxes<\/pre>\n
\n
gray = cv2.cvtColor(board, cv2.COLOR_BGR2GRAY)\r\nrois = split_boxes(gray)\r\nrois = np.array(rois).reshape(-1, input_size, input_size, 1)<\/pre>\n
4. Predict digits of each box:<\/h4>\n
classes = np.arange(0, 10)\r\n\r\nmodel = load_model('model-OCR.h5')\r\n\r\n# get prediction\r\nprediction = model.predict(rois)\r\n# print(prediction)\r\n\r\npredicted_numbers = []\r\n# get classes from prediction\r\nfor i in prediction:\r\nindex = (np.argmax(i))\r\npredicted_number = classes[index]\r\npredicted_numbers.append(predicted_number)\r\n\r\nprint(predicted_numbers)<\/pre>\n\n
\nmodel.predict(rois) predicts all total 81 digits at once. It returns an array containing 81 predictions. Each prediction array contains 9 elements.<\/li>\n5. Solve the board:<\/h4>\n
# reshape the list\r\nboard_num = np.array(predicted_numbers).astype('uint8').reshape(9, 9)<\/pre>\n\n
# solve the board\r\ntry:\r\nsolved_board_nums = get_board(board_num)<\/pre>\n
\n
def displayNumbers(img, numbers, color=(0, 255, 0)):\r\nW = int(img.shape[1]\/9)\r\nH = int(img.shape[0]\/9)\r\nfor i in range (9):\r\nfor j in range (9):\r\nif numbers[(j*9)+i] !=0:\r\ncv2.putText(img, str(numbers[(j*9)+i]),\r\n(i*W+int(W\/2)-int((W\/4)),int((j+0.7)*H)),\r\ncv2.FONT_HERSHEY_COMPLEX, 2, color,\r\n2, cv2.LINE_AA)\r\nreturn img<\/pre>\n
\n
def get_InvPerspective(img, masked_num, location, height = 900, width = 900):\r\n\"\"\"Takes original image as input\"\"\"\r\npts1 = np.float32([[0, 0], [width, 0], [0, height], [width, height]])\r\npts2 = np.float32([location[0], location[3], location[1], location[2]])\r\n\r\n# Apply Perspective Transform Algorithm\r\nmatrix = cv2.getPerspectiveTransform(pts1, pts2)\r\nresult = cv2.warpPerspective(masked_num, matrix, (img.shape[1],\r\nimg.shape[0]))\r\nreturn result<\/pre>\n
\n
binArr = np.where(np.array(predicted_numbers)>0, 0, 1)\r\nprint(binArr)\r\n# get only solved numbers for the solved board\r\nflat_solved_board_nums = solved_board_nums.flatten()*binArr\r\n# create a mask\r\nmask = np.zeros_like(board)\r\nsolved_board_mask = displayNumbers(mask, flat_solved_board_nums)\r\ncv2.imshow(\"Solved Mask\", solved_board_mask)<\/pre>\n
\n
![\"solved](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/solved-mask.webp\")
<\/a><\/p>\n![\"inverse\"](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/inverse.webp\")
<\/a><\/p>\n![\"opencv](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/10\/opencv-sudoku-solver-output.webp\")
<\/a><\/p>\n