[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.

• Easy
• Medium
• Hard
• Expert

I will try to solve one question each.

Implementation

problem

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

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.

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?

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