Hello again - rather a newbie here...
I want to work on a sudoku brute-forcer, just for fun.
I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.
'scuse me for being thick - but give me a little pointer and I will do
the rest. 15 3925
anthonyberet wrote: Hello again - rather a newbie here...
I want to work on a sudoku brute-forcer, just for fun.
I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.]
Well, you could do a list of lists, or a tuple of tuples, or a
combination thereof.
For example:
val = matrix[indexA][indexB]
-carl 'scuse me for being thick - but give me a little pointer and I will do the rest.
--
Carl J. Van Arsdall cv*********@mvista.com
Build and Release
MontaVista Software
anthonyberet wrote: Hello again - rather a newbie here...
I want to work on a sudoku brute-forcer, just for fun.
I know what you mean. I wrote one just for fun too.
I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
List of lists.
One list with nine elements, each of which is a list with nine numbers.
[[5,2,7,3,9,8,1,4,6],
[3,1,4,....],
....
]
Cheers,
Carl.
anthonyberet wrote: Hello again - rather a newbie here...
I want to work on a sudoku brute-forcer, just for fun.
I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
'scuse me for being thick - but give me a little pointer and I will do the rest.
Probably the numeric module: http://numeric.scipy.org/
But you can also do nested lists.
Larry Bates
> I want to work on a sudoku brute-forcer, just for fun.
Well, as everybody seems to be doing these (self included...),
the sudoku solver may become the "hello world" of the new world :) What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
Several other answers have crossed the list. I've done it using
a dictionary of tuples:
grid = {}
for row in range(1,10):
for col in range(1,10):
grid[(row,col)] = value
item = grid[(3,2)]
etc.
Seemed fairly quick and worked for me.
-tkc
anthonyberet wrote: Hello again - rather a newbie here...
I want to work on a sudoku brute-forcer, just for fun.
I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
'scuse me for being thick - but give me a little pointer and I will do the rest.
Another approach as already proposed could be, that you define your grid
as a dictionary in a following way:
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[(column, row)] = None
# then you can refer to the cells of the 'array' like:
colNo=5; rowNo=4
valueInCellOfGrid = grid[(colNo, rowNo)]
# and set them like:
grid[(colNo, rowNo)] = 9
print valueInCellOfGrid
print grid[(colNo, rowNo)]
I haven't checked it out, but I can imagine, that this approach could
even have a speed advantage over a list of lists what can become
important in a 'brute-forcer' approach.
Best way is probably to use one of available numeric libraries with
array support, but this is another story.
Claudio
Claudio
Claudio Grondi wrote: Another approach as already proposed could be, that you define your grid as a dictionary in a following way: grid = {} for column in range(1,10): for row in range(1,10): grid[(column, row)] = None # then you can refer to the cells of the 'array' like: colNo=5; rowNo=4 valueInCellOfGrid = grid[(colNo, rowNo)] # and set them like: grid[(colNo, rowNo)] = 9 print valueInCellOfGrid print grid[(colNo, rowNo)]
FWIW, if you leave out the parentheses, it looks more like a genuine 2D
array, which can be nice (actually I think it's the main advantage over
lists of lists):
print grid[colNo, rowNo] Claudio
--Max
Claudio Grondi wrote: anthonyberet wrote: Hello again - rather a newbie here... I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
... define your grid as a dictionary in a following way: grid = {} for column in range(1,10): for row in range(1,10): grid[(column, row)] = None # then you can refer to the cells of the 'array' like: colNo=5; rowNo=4 valueInCellOfGrid = grid[(colNo, rowNo)] # and set them like: grid[(colNo, rowNo)] = 9 print valueInCellOfGrid print grid[(colNo, rowNo)]
Though a couple of people have suggested a dictionary, nobody has
yet pointed out that a[i, j] is the same as a[(i, j)] (and looks
less ugly). So, I'd go with dictionaries, and index them as
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[column, row] = None
...
valueInCellOfGrid = grid[col, row]
grid[col, row] = 9
...
--Scott David Daniels sc***********@acm.org
On 2006-01-26, Larry Bates <la*********@websafe.com> wrote: I want to work on a sudoku brute-forcer, just for fun.
I am considering different strategies, but first I need to decide on the data-structure to use for the progress/solution grid.
This being a square, I would have used a 9x9 2-dimensional array in my teenage years back in the 80's, using BASIC.
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
'scuse me for being thick - but give me a little pointer and I will do the rest.
Probably the numeric module:
http://numeric.scipy.org/
I'd use numeric or numarray. They have built-in notation for
grabbing a row or column.
--
Grant Edwards grante Yow! I appoint you
at ambassador to Fantasy
visi.com Island!!!
Tim Chase wrote: I want to work on a sudoku brute-forcer, just for fun.
Well, as everybody seems to be doing these (self included...), the sudoku solver may become the "hello world" of the new world :)
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
Several other answers have crossed the list. I've done it using a dictionary of tuples:
grid = {} for row in range(1,10): for col in range(1,10): grid[(row,col)] = value
item = grid[(3,2)]
etc.
Seemed fairly quick and worked for me.
Thanks for the advice (to everyone in the thread).
I think I will go with nested lists.
However, I am running into a conceptual problem.
My approach will be firstly to remove all the impossible digits for a
square by searching the row and column for other occurances.
However, I wondering how to approach the search of the nine regions of
the grid. I am thinking of producing another nested list, again 9x9 to
store the contents of each region, and to update this after each pass
through -and update of- the main grid (row and column).
I am not sure how to most efficiently identify which region any given
square on the grid is actually in - any thoughts, for those that have
done this? - I don't want a massive list of IF conditionals if I can
avoid it.
From: anthonyberet
Date: 02/18/06 17:11:01
To: py*********@python.org
Subject: Re: 2-dimensional data structures
I am not sure how to most efficiently identify which region any given
square on the grid is actually in - any thoughts, for those that have
done this? - I don't want a massive list of IF conditionals if I can
avoid it.
Kermit says:
There is a MUCH more efficient way to do this!
If you are doing a 9 by 9 soduku,
Each row and column has exactly the digits 1 through 9
Think of your data as being in a list 81 cells long that is accessed 3
different ways.
As a 9 by 9, row wise,
As a 9 by 9 column wise
As a 3 by 3 by 9 where the first two subscripts identify the region, and
the last identify one of
the 9 values within the region.
And , most important,
To search for a value not yet in a row, column, or region,
Define holding list of length 9.
Suppose a row has 4,2,8 in it,
and the corresponding column has 2,3,1 in it
and the correspond region has 2, 7, 6 in it.
Then you initialize your hold vector to -1,
and set
hold(4) = 4
hold(2) = 1
hold(8) = 1
hold(2) = 1
hold (3) = 1
hold(1) = 1
hold(2) = 1
hold(7) = 1
hold(6) = 1
Then by scaning only the nine elements of hold, you see that
hold(5) = -1, , and hold(9) = -1 are the only values not reset, and
only 5 and 9 are possible choices for the target cell.
> However, I wondering how to approach the search of the nine regions of the grid. I am thinking of producing another nested list, again 9x9 to store the contents of each region, and to update this after each pass through -and update of- the main grid (row and column).
I am not sure how to most efficiently identify which region any given square on the grid is actually in - any thoughts, for those that have done this? - I don't want a massive list of IF conditionals if I can avoid it.
The question is not so much which region a give square is in, but more
which square contains which fields. If we assume that you number your
squares row-wise (top-left zero, top-right 3, bottom-right 9), this
function computes the field indices that a given square is composed of:
def scoords(n):
square_row = n / 3
square_col = n % 3
start_row = square_row * 3 # ( this is _not_ n!!)
start_column = square_col * 3
for x in xrange(start_column, start_column + 3):
for y in xrange(start_row, start_row + 3):
yield (x,y)
print list(coords(4))
Regards,
Diez
Diez B. Roggisch schrieb: The question is not so much which region a give square is in, but more which square contains which fields. If we assume that you number your squares row-wise (top-left zero, top-right 3, bottom-right 9), this function computes the field indices that a given square is composed of:
I'm confusing squares with fields here. What I meant by a square here is
the 3x3 region, of which 9 exist. Each has 3x3=9 cells.
Diez
anthonyberet wrote: Tim Chase wrote: I want to work on a sudoku brute-forcer, just for fun.
Well, as everybody seems to be doing these (self included...), the sudoku solver may become the "hello world" of the new world :)
What is the equivalent way to store data in python? - It isn't obvious to me how to do it with lists.
Several other answers have crossed the list. I've done it using a dictionary of tuples:
grid = {} for row in range(1,10): for col in range(1,10): grid[(row,col)] = value
item = grid[(3,2)]
etc.
Seemed fairly quick and worked for me.
Thanks for the advice (to everyone in the thread). I think I will go with nested lists. However, I am running into a conceptual problem. My approach will be firstly to remove all the impossible digits for a square by searching the row and column for other occurances.
However, I wondering how to approach the search of the nine regions of the grid. I am thinking of producing another nested list, again 9x9 to store the contents of each region, and to update this after each pass through -and update of- the main grid (row and column).
I am not sure how to most efficiently identify which region any given square on the grid is actually in - any thoughts, for those that have done this? - I don't want a massive list of IF conditionals if I can avoid it.
Here's another way:
def region_map():
for row in range(9):
for col in range(9):
region = (row/3,col/3)
print region,
print
def identify_region(cell):
return (cell[0]/3,cell[1]/3)
def create_regions():
regions = {}
for row in range(9):
for col in range(9):
rowcol = (row,col)
reg = (row/3,col/3)
if regions.has_key(reg):
regions[reg].append(rowcol)
else:
regions[reg] = [rowcol]
return regions
grid = [[0,0,6,0,7,0,0,0,0], \
[0,3,5,4,0,0,0,9,0], \
[0,0,0,0,0,6,1,2,0], \
[0,0,0,0,0,3,2,0,8], \
[0,0,0,0,6,0,0,0,0], \
[4,0,7,2,0,0,0,0,0], \
[0,5,2,1,0,0,0,0,0], \
[0,7,0,0,0,5,9,1,0], \
[0,0,0,0,4,0,3,0,0]]
print 'the grid:'
for g in grid: print g
print
print 'the region ids:'
region_map()
print
# create the region dictionary
regions = create_regions()
# pick an arbitrary cell
cell = (5,5)
reg_id = identify_region(cell)
print 'cell:',cell,'is in region:',reg_id
print
print 'region',reg_id,'contains:'
reg_data = regions[reg_id]
for c in reg_data:
print grid[c[0]][c[1]],
"""
the grid:
[0, 0, 6, 0, 7, 0, 0, 0, 0]
[0, 3, 5, 4, 0, 0, 0, 9, 0]
[0, 0, 0, 0, 0, 6, 1, 2, 0]
[0, 0, 0, 0, 0, 3, 2, 0, 8]
[0, 0, 0, 0, 6, 0, 0, 0, 0]
[4, 0, 7, 2, 0, 0, 0, 0, 0]
[0, 5, 2, 1, 0, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 5, 9, 1, 0]
[0, 0, 0, 0, 4, 0, 3, 0, 0]
the region ids:
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)
cell: (5, 5) is in region: (1, 1)
region (1, 1) contains:
0 0 3 0 6 0 2 0 0
"""
anthonyberet wrote: Thanks for the advice (to everyone in the thread). I think I will go with nested lists. However, I am running into a conceptual problem. My approach will be firstly to remove all the impossible digits for a square by searching the row and column for other occurances.
However, I wondering how to approach the search of the nine regions of the grid. I am thinking of producing another nested list, again 9x9 to store the contents of each region, and to update this after each pass through -and update of- the main grid (row and column).
I am not sure how to most efficiently identify which region any given square on the grid is actually in - any thoughts, for those that have done this? - I don't want a massive list of IF conditionals if I can avoid it.
When I wrote my Sudoku solver (a terribly inefficient and naive
recursive algorithm that I originally wrote in C++ and was the first
thing I ever wrote in Python), I used numarray. It allows
two-dimensional slicing:
def inBlock(x, y, val):
blockX = x/size * size
blockY = y/size * size
return val in sudoku[blockX:blockX+size, blockY:blockY+size]
'size' in this example is a global variable equal to the size of the
puzzle, so 3 for a normal puzzle. 'sudoku' is a global two-dimensional
array simply holding the values in the puzzle.
(There are any number of things in this can be improved, such as using
the // floor division operator rather than /, not using global
variables, and so on. What can I say? It was a straight conversion from
C++. I hardly knew what "Pythonic" meant.)
-Kirk McDonald
anthonyberet wrote: I want to work on a sudoku brute-forcer, just for fun. ... Thanks for the advice (to everyone in the thread). I think I will go with nested lists. However, I am running into a conceptual problem. My approach will be firstly to remove all the impossible digits for a square by searching the row and column for other occurances.
However, I wondering how to approach the search of the nine regions of the grid. I am thinking of producing another nested list, again 9x9 to store the contents of each region, and to update this after each pass through -and update of- the main grid (row and column).
I am not sure how to most efficiently identify which region any given square on the grid is actually in - any thoughts, for those that have done this? - I don't want a massive list of IF conditionals if I can avoid it.
Some 'UselessPython' :
import math
def SudokuOrder( length ):
block_length = int(math.sqrt(length))
for block in range(length):
row_offset = block_length * ( block // block_length )
col_offset = block_length * ( block % block_length )
for i in range( block_length ):
for j in range( block_length ):
yield i+row_offset, j+col_offset
grid = list(SudokuOrder(9))
BLOCK1 = grid[:9]
BLOCK2 = grid[9:18]
BLOCK9 = grid[72:81]
print
print 'BLOCK1 ->', BLOCK1
print
print 'BLOCK2 ->', BLOCK2
print
print 'BLOCK9 ->', BLOCK9
BLOCK1 -> [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2,
1), (2, 2)]
BLOCK2 -> [(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2,
4), (2, 5)]
BLOCK9 -> [(6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8,
7), (8, 8)]
Gerard This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Innocence |
last post by:
Hi
I've been considering how to optimize map data structures for a tile
based Python game. However, since I'm a Python newbie I lack
experience with Pythons 'exotic' data types like lists and...
|
by: hzy_104 |
last post by:
Please recommend book on data structures for searching(c++)?
|
by: Amit |
last post by:
Hello,
Can any of you recommend a really good book on data structures and more so,
if it relates to STL data structures, and how they are used to build far
more complex data structures.
...
|
by: el_roachmeister |
last post by:
For being a good web programmer, is a course on data structures
important? It seems php already has built-in functions for what they
teach in a data structures course. On the other hand all...
|
by: Thomas Paul Diffenbach |
last post by:
Can anyone point me to an open source library of /statically
allocated/ data structures?
I'm writing some code that would benefit from trees, preferably self
balancing, but on an embedded system...
|
by: utab |
last post by:
Dear all,
I was reading something on data structures on c++ and in that chapter
it was telling that the same components will be more efficiently
substituted with the STL ones.
So can somebody...
|
by: osp |
last post by:
hi to every one....
i just started out with c++ and i think i am
doing well.i use Robert Laffore to study. which book should i use for
data structures ? please help.
thank you
with regards
...
|
by: efrat |
last post by:
Hello,
I'm planning to use Python in order to teach a DSA (data structures
and algorithms) course in an academic institute. If you could help out
with the following questions, I'd sure...
|
by: Mik0b0 |
last post by:
Hallo to everyone.
This fall I am going to start data structures as a part of C language
course. The problem is I could not find any satisfying tutorial about
structures in C. There are plenty of...
|
by: jehugaleahsa |
last post by:
Hello:
When developing data structures for C#, there is an obvious
performance hit when utilizing primitive types. For instance, a recent
hash table implementation I wrote works exceedingly fast...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |