[PYTHON] I want to solve Sudoku (Sudoku)

Introduction

When I met my father at home after a long time, I was solving Sudoku with a smartphone app. We will do it with Google Colaboratory.

What are the challenges?

If you google with "sudoku", it seems that there is a site like this, so the goal is to solve the problem here. Looking at "Difficulty", it seems that there are the following 4 levels.

I will try to solve one question each.

Implementation

problem

For example, if you have the following problems ... easy.jpg

I will express it as a two-dimensional list as follows. By the way, this problem is an example of easy difficulty.

sudoku.ipynb


# easy
list_sudoku = [
 [0, 4, 8, 0, 9, 0, 0, 5, 0],
 [0, 0, 0, 7, 4, 5, 2, 1, 0],
 [0, 7, 5, 0, 0, 2, 4, 0, 0],
 [0, 0, 0, 0, 7, 0, 0, 0, 2],
 [7, 0, 6, 4, 0, 9, 0, 0, 0],
 [9, 0, 2, 0, 6, 0, 3, 0, 0],
 [0, 0, 0, 6, 1, 0, 8, 2, 7],
 [0, 1, 3, 0, 5, 0, 6, 4, 9],
 [0, 0, 7, 9, 8, 0, 0, 0, 1]]

Function to narrow down candidates

For example, in the upper left cell of the above problem, it is decided that the numbers already in the vertical, horizontal, and block will not be included, so the candidates can be narrowed down to [1,2,3,6]. That's why. Create a function that can do this.

First, let's make the list of candidates 1 to 9 variables.

sudoku.ipynb


list_possible = [i for i in range(1, 10)]

Now let's create a function. First of all, vertical.

sudoku.ipynb


def narrow_ver(x, list_possible, list_sudoku):
  """
Narrow down candidates in the vertical direction
  """
  list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is int]
  return set(list_possible) - set(list_ver)

Then sideways.

sudoku.ipynb


def narrow_hor(y, list_possible, list_sudoku):
  """
Narrow down the candidates in the horizontal direction
  """
  list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is int]
  return set(list_possible) - set(list_hor)

And in the block.

sudoku.ipynb


def narrow_blo(x, y, list_possible, list_sudoku):
  """
Narrow down the candidates in the block
  """
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is int]
  return set(list_possible) - set(list_blo)

Create a function that calls vertically, horizontally, and inside a block ...

sudoku.ipynb


def narrow(x, y, list_possible, list_sudoku):
  """
Narrow down the candidates for the target cell
  """
  list_possible = narrow_ver(x, list_possible, list_sudoku)
  list_possible = narrow_hor(y, list_possible, list_sudoku)
  list_possible = narrow_blo(x, y, list_possible, list_sudoku)
  return sorted(list(list_possible))

Create a function that executes ↑ for all cells. However, cells whose numbers have already been decided are through.

sudoku.ipynb


def apply_narrow(list_sudoku):
  """
Narrow for all cells()To run
  """
  for y in range(9):
    for x in range(9):
      if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
        continue
      elif list_sudoku[y][x] == 0:
        list_sudoku[y][x] = narrow(x, y, list_possible, list_sudoku)
      else:
        list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
        if len(list_sudoku[y][x]) == 1:
          list_sudoku[y][x] = list_sudoku[y][x][0]
  return list_sudoku

Maybe this is all you need to solve? Let's give it a try!

Try to solve Easy

Copy it to temp_sudoku, compare it with the one after executing apply_narrow (), and if there is no change, it will end.

sudoku.ipynb


import copy

list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
  temp_sudoku = copy.deepcopy(list_sudoku)
  count += 1
  list_sudoku = apply_narrow(list_sudoku)
  if temp_sudoku == list_sudoku:
    break
print(count)
list_sudoku

↓ Output result

6
[[2, 4, 8, 1, 9, 6, 7, 5, 3],
 [3, 6, 9, 7, 4, 5, 2, 1, 8],
 [1, 7, 5, 8, 3, 2, 4, 9, 6],
 [4, 5, 1, 3, 7, 8, 9, 6, 2],
 [7, 3, 6, 4, 2, 9, 1, 8, 5],
 [9, 8, 2, 5, 6, 1, 3, 7, 4],
 [5, 9, 4, 6, 1, 3, 8, 2, 7],
 [8, 1, 3, 2, 5, 7, 6, 4, 9],
 [6, 2, 7, 9, 8, 4, 5, 3, 1]]

You've solved it! I did it!

How about Medium?

sudoku.ipynb


# medium
list_sudoku = [
 [9, 0, 0, 8, 1, 0, 0, 0, 0],
 [0, 0, 5, 0, 0, 4, 7, 0, 6],
 [0, 0, 0, 2, 0, 5, 8, 0, 1],
 [0, 9, 0, 7, 4, 0, 5, 0, 0],
 [0, 0, 0, 0, 0, 3, 0, 7, 0],
 [7, 4, 0, 0, 0, 0, 0, 0, 0],
 [3, 0, 0, 9, 5, 0, 6, 0, 0],
 [0, 0, 6, 4, 0, 0, 0, 1, 3],
 [1, 7, 0, 0, 0, 0, 0, 0, 4]]

↓ Result

6
[[9, [3, 6], [2, 3, 7], 8, 1, [6, 7], [3, 4], [3, 4], 5],
 [8, 1, 5, 3, 9, 4, 7, 2, 6],
 [[4, 6], [3, 6], [3, 7], 2, [6, 7], 5, 8, [3, 4, 9], 1],
 [[2, 6], 9, [1, 2, 3, 8], 7, 4, [2, 6], 5, [3, 6], [2, 8]],
 [[2, 6], [5, 6], [1, 2, 8], [1, 5], [2, 6, 8], 3, [1, 4], 7, [2, 8, 9]],
 [7,
  4,
  [1, 2, 3, 8],
  [1, 5],
  [2, 6, 8],
  [2, 6, 9],
  [1, 3],
  [3, 6, 9],
  [2, 8, 9]],
 [3, 2, 4, 9, 5, 1, 6, 8, 7],
 [5, 8, 6, 4, [2, 7], [2, 7], 9, 1, 3],
 [1, 7, 9, 6, 3, 8, 2, 5, 4]]

Is it no good? The 2nd, 7th, and 9th lines are all solved, and the lines are pretty good. Apparently, this alone is not enough to narrow down the candidates.

The table below shows this result. The deficit is a candidate. meduim_in_process.jpg

Well, it's filled up so much that it feels like a breather, but how do you solve it? If you try to solve it yourself ... For example, if it is "46" in the 1st column and 3rd row, there is no other cell in the block that has "4" as a candidate, so the answer is decided to be "4".

A function that finds the answer by comparing it with other cell candidates

After narrowing down the cell candidates, compare them with the cell candidates in the vertical, horizontal, and block. As a result of comparison, if there is a candidate that is not in other cells, create a function that answers it.

It uses itertools, so let's import it.

sudoku.ipynb


import itertools

First from the vertical cell.

sudoku.ipynb


def generate_possible_ver(x, y, list_sudoku):
  """
Collect candidate cells in the vertical direction
  """
  list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is list and i!=y]
  return set(itertools.chain.from_iterable(list_ver))

Then sideways.

sudoku.ipynb


def generate_possible_hor(x, y, list_sudoku):
  """
Collect candidates for horizontal cells
  """
  list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is list and i!=x]
  return set(itertools.chain.from_iterable(list_hor))

And in the block.

sudoku.ipynb


def generate_possible_blo(x, y, list_sudoku):
  """
Collect candidate cells in the block
  """
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is list and (i!=y or j!=x)]
  return set(itertools.chain.from_iterable(list_blo))

Create a function that compares the candidates and assigns them to the cell if there is only one candidate.

sudoku.ipynb


def find_only_one(x, y, list_possible, list_sudoku):
  """
Compare with the cell candidates in the vertical, horizontal, and block,
If there is a candidate that is not in other cells, answer it
  """
  diff_ver = set(list_possible) - generate_possible_ver(x, y, list_sudoku)
  if len(diff_ver) == 1:
    return list(diff_ver)[0]
  
  diff_hor = set(list_possible) - generate_possible_hor(x, y, list_sudoku)
  if len(diff_hor) == 1:
    return list(diff_hor)[0]

  diff_blo = set(list_possible) - generate_possible_blo(x, y, list_sudoku)
  if len(diff_blo) == 1:
    return list(diff_blo)[0]
  
  return list_possible

Create a function that executes ↑ for all cells. Of course, the one who already has the answer is through.

sudoku.ipynb


def try_solve(list_sudoku):
  """
For cells for which the answer has not yet been determined
  narrow()And find_only_one()To run
  """
  for y in range(9):
    for x in range(9):
      if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
        continue
      else:
        list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
        list_sudoku[y][x] = find_only_one(x, y, list_sudoku[y][x], list_sudoku)
        if type(list_sudoku[y][x]) is list and len(list_sudoku[y][x]) == 1:
          list_sudoku[y][x] = list_sudoku[y][x][0]
  return list_sudoku

Let's try it now!

Try to solve Medium

This time as well, if there is no change compared to temp_sudoku, it will end.

sudoku.ipynb


import copy

list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
  temp_sudoku = copy.deepcopy(list_sudoku)
  count += 1
  list_sudoku = try_solve(apply_narrow(list_sudoku))
  if temp_sudoku == list_sudoku:
    break
print(count)
list_sudoku

↓ Output result

4
[[9, 6, 2, 8, 1, 7, 3, 4, 5],
 [8, 1, 5, 3, 9, 4, 7, 2, 6],
 [4, 3, 7, 2, 6, 5, 8, 9, 1],
 [2, 9, 1, 7, 4, 6, 5, 3, 8],
 [6, 5, 8, 1, 2, 3, 4, 7, 9],
 [7, 4, 3, 5, 8, 9, 1, 6, 2],
 [3, 2, 4, 9, 5, 1, 6, 8, 7],
 [5, 8, 6, 4, 7, 2, 9, 1, 3],
 [1, 7, 9, 6, 3, 8, 2, 5, 4]]

Sounds good. Let's go Hard with this condition.

Try to solve Hard

sudoku.ipynb


# hard
list_sudoku = [
 [1, 3, 0, 6, 0, 0, 0, 8, 0],
 [0, 4, 6, 0, 3, 0, 0, 0, 0],
 [0, 2, 0, 5, 0, 0, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 1, 0, 6],
 [0, 9, 0, 0, 5, 7, 0, 0, 0],
 [8, 0, 0, 0, 0, 0, 0, 4, 5],
 [0, 0, 0, 0, 0, 0, 3, 7, 0],
 [0, 0, 0, 0, 6, 3, 4, 0, 0],
 [0, 0, 0, 0, 0, 0, 5, 0, 1]]

↓ Result

4
[[1, 3, 5, 6, 7, 2, 9, 8, 4],
 [9, 4, 6, 8, 3, 1, 2, 5, 7],
 [7, 2, 8, 5, 4, 9, 6, 1, 3],
 [3, 5, 7, 2, 8, 4, 1, 9, 6],
 [6, 9, 4, 1, 5, 7, 8, 3, 2],
 [8, 1, 2, 3, 9, 6, 7, 4, 5],
 [2, 6, 9, 4, 1, 5, 3, 7, 8],
 [5, 8, 1, 7, 6, 3, 4, 2, 9],
 [4, 7, 3, 9, 2, 8, 5, 6, 1]]

You're done! Maybe all Sudoku in this world can be solved with this logic? Let's try Expert too!

sudoku.ipynb


# expert
list_sudoku = [
 [4, 0, 0, 0, 8, 0, 1, 0, 0],
 [0, 0, 0, 2, 0, 9, 0, 0, 0],
 [0, 0, 0, 7, 3, 0, 0, 0, 0],
 [0, 2, 0, 0, 0, 1, 0, 0, 9],
 [0, 0, 5, 0, 0, 0, 0, 7, 0],
 [0, 9, 0, 0, 0, 0, 0, 5, 0],
 [0, 1, 0, 5, 0, 0, 4, 0, 0],
 [6, 0, 0, 3, 0, 0, 0, 0, 0],
 [0, 0, 4, 0, 0, 7, 6, 0, 3]]

↓ Result

3
[[4, [3, 7], [2, 3, 7, 9], 6, 8, 5, 1, [2, 3, 9], [2, 7]],
 [[3, 5, 7, 8],
  [3, 5, 6, 7, 8],
  [3, 6, 7, 8],
  2,
  1,
  9,
  [3, 5, 7, 8],
  [3, 4, 6, 8],
  [4, 5, 6, 7, 8]],
 [[1, 2, 5, 8, 9],
  [5, 6, 8],
  [1, 2, 6, 8, 9],
  7,
  3,
  4,
  [2, 5, 8, 9],
  [2, 6, 8, 9],
  [2, 5, 6, 8]],
 [[3, 7, 8], 2, [3, 6, 7, 8], [4, 8], 5, 1, [3, 8], [3, 4, 6, 8], 9],
 [[1, 3, 8], 4, 5, 9, [2, 6], [2, 3, 6, 8], [2, 3, 8], 7, [1, 2, 6, 8]],
 [[1, 3, 8],
  9,
  [1, 3, 6, 8],
  [4, 8],
  7,
  [2, 3, 6, 8],
  [2, 3, 8],
  5,
  [1, 2, 4, 6, 8]],
 [[2, 3, 7, 8, 9],
  1,
  [2, 3, 7, 8, 9],
  5,
  [2, 6, 9],
  [2, 6, 8],
  4,
  [2, 8, 9],
  [2, 7, 8]],
 [6, [5, 7, 8], [2, 7, 8, 9], 3, 4, [2, 8], [2, 5, 7, 8, 9], 1, [2, 5, 7, 8]],
 [[2, 5, 8, 9], [5, 8], 4, 1, [2, 9], 7, 6, [2, 8, 9], 3]]

Yes. It didn't work at all. Is it like this in a table?

expert_in_process.jpg

As expected, it is an Expert level. I can't solve it at all. To make matters worse, I don't feel like I can solve it by myself. What to do now?

A function to solve by brute force

I can't help it, so I'll try all of them in order by brute force. It seems that it can be done recursively.

First, the duplicate check function. You can solve it by brute force, but you don't have to try numbers that you already know won't fit.

sudoku.ipynb


def dup_check(x, y, possible, list_sudoku):
  """
In the cells in the vertical, horizontal, and block
Check if there are already duplicate values
  """
  for pos in range(9):
    if list_sudoku[y][pos] == possible or list_sudoku[pos][x] == possible:
      return False
  
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  for pos_y in range(index_y, index_y+3):
    for pos_x in range(index_x, index_x+3):
      if list_sudoku[pos_y][pos_x] == possible:
        return False
  return True

And a function to solve by brute force. If there is an unsolvable problem, it will loop infinitely, so we have set a time limit (60 seconds). The number of seconds is appropriate.

sudoku.ipynb


def brute_force(list_sudoku, list_ans, x=0, y=0):
  """
Try to solve by brute force
If it takes more than 60 seconds, it is judged that it cannot be solved
  """
  if type(list_sudoku[y][x]) is list:
    time_process = time.time()
    if (time_process - time_start) >= 60:
      return False
    for possible in list_sudoku[y][x]:
      if dup_check(x, y, possible, list_ans):
        list_ans[y][x] = possible
        if x <= 7:
          next_x = x + 1
          next_y = y
        elif y <= 7:
          next_x = 0
          next_y = y + 1
        else:
          return True
        if not brute_force(list_sudoku, list_ans, next_x, next_y):
          continue
        else:
          return True
    list_ans[y][x] = []
    return False
  else:
    list_ans[y][x] = list_sudoku[y][x]
    if x <= 7:
      next_x = x + 1
      next_y = y
    elif y <= 7:
      next_x = 0
      next_y = y + 1
    else:
      return True
    return brute_force(list_sudoku, list_ans, next_x, next_y)

Try to solve Expert

How about?

sudoku.ipynb


import copy
import time

time_start = time.time()
temp_sudoku = copy.deepcopy(list_sudoku)
list_ans = [[[] for i in range(9)] for j in range(9)]
result = brute_force(temp_sudoku, list_ans)
print(result)
list_ans

↓ Output result

True
[[4, 7, 9, 6, 8, 5, 1, 3, 2],
 [5, 3, 8, 2, 1, 9, 7, 6, 4],
 [1, 6, 2, 7, 3, 4, 5, 9, 8],
 [7, 2, 6, 8, 5, 1, 3, 4, 9],
 [3, 4, 5, 9, 2, 6, 8, 7, 1],
 [8, 9, 1, 4, 7, 3, 2, 5, 6],
 [9, 1, 3, 5, 6, 8, 4, 2, 7],
 [6, 8, 7, 3, 4, 2, 9, 1, 5],
 [2, 5, 4, 1, 9, 7, 6, 8, 3]]

Solved! I did it!

Finally

I wanted to solve it with logic other than brute force, but I can't solve it normally, so I can't implement it. If you search for "Sudoku, how to solve it, advanced", you will find various things, but you can't solve it even if you refer to any of them. .. I want to do something about it if possible.

reference

For brute force, refer to the following. -Sudoku with Python

By the way

I turned on the screen so that I could try it. SUDOKU SOLVER

Recommended Posts

I want to solve Sudoku (Sudoku)
I tried to let optuna solve Sudoku
I want to solve APG4b with Python (Chapter 2)
I want to understand systemd roughly
I want to scrape images to learn
I want to do ○○ with Pandas
I want to copy yolo annotations
I want to debug with Python
Want to solve a simple classification problem?
I want to detect objects with OpenCV
I want to print in a comprehension
I want to scrape them all together.
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
I want to know how LINUX works!
I want to blog with Jupyter Notebook
I want to use jar from python
I wanted to solve ABC160 with Python
I want to build a Python environment
I want to use Linux on mac
I want to pip install with PythonAnywhere
I want to analyze logs with Python
I want to play with aws with python
I want to use IPython Qt Console
I wanted to solve ABC159 in Python
I want to display the progress bar
I want to make an automation program!
I tried to solve TSP with QAOA
I want to embed Matplotlib in PySimpleGUI
I wanted to solve ABC172 with Python
I want to handle the rhyme part2
I want to develop Android apps on Android
I want CAPTCHA to say HIWAI words
I want to handle the rhyme part5
I want to handle the rhyme part4
I want to make matplotlib a dark theme
I want to connect to PostgreSQL from various languages
I want to do Dunnett's test in Python
I want to have recursion come to my mind
I want to pin Datetime.now in Django tests
I want to analyze songs with Spotify API 2
I want to INSERT a DataFrame into MSSQL
I wanted to solve NOMURA Contest 2020 with Python
I want to memoize including Python keyword arguments
I want to create a window in Python
Anyway, I want to check JSON data easily
[Python] I want to manage 7DaysToDie from Discord! 1/3
I want to perform SageMaker inference from PHP
I want to mock datetime.datetime.now () even with pytest!
I want to knock 100 data sciences with Colaboratory
I want to make a game with Python
I want to visualize csv files using Vega-Lite!
I want to be an OREMO with setParam!
I don't want to take a coding test
I want to store DB information in list
I want to analyze songs with Spotify API 1
I want to merge nested dicts in Python
I want to make fits from my head
I want to manage systemd by time zone! !!
I want to use Temporary Directory with Python2
I want to get League of Legends data ③
I want to get League of Legends data ②