merijn van der leek
asked on
Solving a sudoku
Hey i need to make an algorithm which fills in a sudoku block if there is just one possibility left.
This is how that alghoritm needs to look like:
candidates(x,y) = 1..9 - numbers_row - numbers_col - numbers_block
I need to impliment candidates() like this:
>>> from sudoku import candidates, load
>>> candidates(load("easy/puzz
{2, 3, 4, 5}
So i already made a load function which looks like this:
The output of this code is:
[['7', '9', '0', '0', '0', '0', '3', '0', '1'],
['0', '0', '0', '0', '0', '6', '9', '0', '0'],
['8', '0', '0', '0', '3', '0', '0', '7', '6'],
['0', '0', '0', '0', '0', '5', '0', '0', '2'],
['0', '0', '5', '4', '1', '8', '7', '0', '0'],
['4', '0', '0', '7', '0', '0', '0', '0', '0'],
['6', '1', '0', '0', '9', '0', '0', '0', '8'],
['0', '0', '2', '3', '0', '0', '0', '0', '0'],
['0', '0', '9', '0', '0', '0', '0', '5', '4']]
The file that i am using looks like this:
7,9,0,0,0,0,3,0,1
0,0,0,0,0,6,9,0,0
8,0,0,0,3,0,0,7,6
0,0,0,0,0,5,0,0,2
0,0,5,4,1,8,7,0,0
4,0,0,7,0,0,0,0,0
6,1,0,0,9,0,0,0,8
0,0,2,3,0,0,0,0,0
0,0,9,0,0,0,0,5,4
Can anyone help me write this code?
This is how that alghoritm needs to look like:
candidates(x,y) = 1..9 - numbers_row - numbers_col - numbers_block
I need to impliment candidates() like this:
>>> from sudoku import candidates, load
>>> candidates(load("easy/puzz
{2, 3, 4, 5}
So i already made a load function which looks like this:
def load(filename):
sudoku = []
with open(filename,"r") as sudoku_raw:
for line in sudoku_raw:
line = line.rstrip("\n").replace(" ","")
row = line.split(',')
sudoku.append(row)
return sudoku
load("easy/puzzle1.sudoku")The output of this code is:
[['7', '9', '0', '0', '0', '0', '3', '0', '1'],
['0', '0', '0', '0', '0', '6', '9', '0', '0'],
['8', '0', '0', '0', '3', '0', '0', '7', '6'],
['0', '0', '0', '0', '0', '5', '0', '0', '2'],
['0', '0', '5', '4', '1', '8', '7', '0', '0'],
['4', '0', '0', '7', '0', '0', '0', '0', '0'],
['6', '1', '0', '0', '9', '0', '0', '0', '8'],
['0', '0', '2', '3', '0', '0', '0', '0', '0'],
['0', '0', '9', '0', '0', '0', '0', '5', '4']]
The file that i am using looks like this:
7,9,0,0,0,0,3,0,1
0,0,0,0,0,6,9,0,0
8,0,0,0,3,0,0,7,6
0,0,0,0,0,5,0,0,2
0,0,5,4,1,8,7,0,0
4,0,0,7,0,0,0,0,0
6,1,0,0,9,0,0,0,8
0,0,2,3,0,0,0,0,0
0,0,9,0,0,0,0,5,4
Can anyone help me write this code?
ASKER
Hey good question sorry its hard to explain for me. So i need a programm that checks every sudoku ‘box’ if there is just one possibility left for that box and that needs to repeat till there are no boxes with one possibility left. Example: if a row has the letters 1-8 and there is just one box left then that means the 9 needs be in that box.
Well, what is your problem?
candidates(r, l) :=
take the set of allowed elements, look in row r, remove all found elements, return the reduced set
take the set of allowed elements, look in line l, remove all found elements, return the reduced set
take the set of allowed elements, look in local area (r,l) l, remove all found elements, return the reduced set
return the intersection of those sets
When |candidates(r, l)| = 1, then the element in the candidates set is the solution for that cell.
p.s. your representation of the Sudoku in memory is imho not ideal. Either you use a real 2-dimensional matrix type or a 1-dimensional vector with (r - 1) * row_size + l as address operation.
(cause I don't like jagged arrays).
p.p.s. the above code implies that you think about helper functions like row(r) and line(l) which return the set of used elements.
update: thx @noci, missed the local area/block set.
candidates(r, l) :=
take the set of allowed elements, look in row r, remove all found elements, return the reduced set
take the set of allowed elements, look in line l, remove all found elements, return the reduced set
take the set of allowed elements, look in local area (r,l) l, remove all found elements, return the reduced set
return the intersection of those sets
When |candidates(r, l)| = 1, then the element in the candidates set is the solution for that cell.
p.s. your representation of the Sudoku in memory is imho not ideal. Either you use a real 2-dimensional matrix type or a 1-dimensional vector with (r - 1) * row_size + l as address operation.
(cause I don't like jagged arrays).
p.p.s. the above code implies that you think about helper functions like row(r) and line(l) which return the set of used elements.
update: thx @noci, missed the local area/block set.
ASKER
Hey thanks for the help. How would i make this a 2 dimensional matrix?
Check out functions associated with lists (so you can manage set from set theory).
https://docs.python.org/3/tutorial/datastructures.html
Also you would need a function to extract the partials sets for Rows, Columns and local area.
Your current matrix can be used as a two dimentional matrix with: cell = grid[row][col]
btw: try to create the get all non '0'elements from a row first, then such a routine for column;
get_row(grid,row), get_col(grid,col) both returning a set of number found.
https://docs.python.org/3/tutorial/datastructures.html
Also you would need a function to extract the partials sets for Rows, Columns and local area.
Your current matrix can be used as a two dimentional matrix with: cell = grid[row][col]
btw: try to create the get all non '0'elements from a row first, then such a routine for column;
get_row(grid,row), get_col(grid,col) both returning a set of number found.
Look at NumPy (N-dimensional array object) and read about matrices in Python: Elementary Matrix Operations In Python.
ASKER
Thanks everyone for the tips! Im really struggling with this and u help me alot :)
Whatever you try. Post it here and we can give suggestions of improvement, or point out whether the solution works in all cases or just for a few cases.
you could start writing 3 different functions.
1.) function telling you what numbers are already in row y (0<=y<9) and which positions are still empty
2.) function telling you what numbers are already in column x (0<x<9) and which positions are still empty
3.) function telling you what numbers are already in square s (0<s<9) and which positions are still empty
alternatively write four different functions:
1.) write one function, that returns you all x,y coordinates for all elements in row x
2.) write one function, that returns you all x,y coordinates for all elements in column y
3.) write one function, that returns you all x,y coordinates for all elements in square s
4.) write one function, that returns all numbers showing up in a list of coordinates (result of one of above three functions) and returns the coordinates of the still empty fields.
you could start writing 3 different functions.
1.) function telling you what numbers are already in row y (0<=y<9) and which positions are still empty
2.) function telling you what numbers are already in column x (0<x<9) and which positions are still empty
3.) function telling you what numbers are already in square s (0<s<9) and which positions are still empty
alternatively write four different functions:
1.) write one function, that returns you all x,y coordinates for all elements in row x
2.) write one function, that returns you all x,y coordinates for all elements in column y
3.) write one function, that returns you all x,y coordinates for all elements in square s
4.) write one function, that returns all numbers showing up in a list of coordinates (result of one of above three functions) and returns the coordinates of the still empty fields.
This is a nice technique https://en.wikipedia.org/wiki/Dancing_Links
This question needs an answer!
Become an EE member today
7 DAY FREE TRIALMembers can start a 7-Day Free trial then enjoy unlimited access to the platform.
View membership options
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
Do you mean to write a program, that solves sudoku?
Or do you mean. check all rows, all columns, all squares to find out whether there is just one field missing?
Or do you mean something else?