• Skip to main content
  • Skip to secondary menu
  • Skip to primary sidebar
  • Skip to footer
  • Home
  • Crypto Currency
  • Technology
  • Contact
NEO Share

NEO Share

Sharing The Latest Tech News

  • Home
  • Artificial Intelligence
  • Machine Learning
  • Computers
  • Mobile
  • Crypto Currency

Solving Sudoku Programmatically

December 12, 2020 by systems

Paul Yeo

Terminology:

  • Boxes are individual squares
  • Units are complete rows, columns, and 3×3 squares
  • Peers are boxes that belong to the same unit
rows = 'ABCDEFGHI'
cols = '123456789'
def cross(a, b):
# output = []
# for s in a:
# for t in b:
# output.append(s+t)
# return output
return [s+t for s in a for t in b]
boxes = cross(rows, cols)
row_units = [cross(r, cols) for r in rows]
column_units = [cross(rows, c) for c in cols]
square_units = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]
unitlist = row_units + column_units + square_units
units = dict((s, [u for u in unitlist if s in u]) for s in boxes)
peers = dict((s, set(sum(units[s],[]))-set([s])) for s in boxes)

For unsolved boxes, eliminate solved peer box values from possible values:

def eliminate(values):
for box, val in values.items():
if len(val) == 1:
for peer in peers[box]:
values[peer] = values[peer].replace(val, '')

For unsolved boxes in a unit, if a possible digit appears once in a box, then that box is the only choice for that digit:

def only_choice(values):
for unit in unitlist:
for digit in "123456789":
boxes = [box for box in unit if digit in values[box]]
if len(boxes) == 1:
values[boxes[0]] = digit

Repeatedly reduce possible solutions using these two methods, eliminate and only choice, until no progress is made:

def reduce_puzzle(values):
progress = True
while progress:
# Check how many boxes have a determined value
solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
eliminate(values)
only_choice(values)
# Check how many boxes have a determined value, to compare
solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
# If no new values were added, stop the loop.
progress = solved_values_before != solved_values_after

Once board is reduced as much as possible, get unsolved box with the least number of possible digits and try each digit until board is solved:

def invalid(values):
return len([box for box in values.keys() if len(values[box]) == 0]) != 0
def solved(values):
return len([box for box in values.keys() if len(values[box]) != 1]) == 0
def search(values):
reduce_puzzle(values)
if invalid(values):
return None
if solved(values):
return values
n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
for value in values[s]:
tmp = values.copy()
tmp[s] = value
tmp = search(tmp)
if tmp:
return tmp

Filed Under: Artificial Intelligence

Primary Sidebar

Carmel WordPress Help

Carmel WordPress Help: Expert Support to Keep Your Website Running Smoothly

Stay Ahead: The Latest Tech News and Innovations

Cryptocurrency Market Updates: What’s Happening Now

Emerging Trends in Artificial Intelligence: What to Watch For

Top Cloud Computing Services to Secure Your Data

Footer

  • Privacy Policy
  • Terms and Conditions

Copyright © 2025 NEO Share

Terms and Conditions - Privacy Policy