Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Need help with this question!!

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Novembre

Joined: 24 Apr 2006
Posts: 2
:

Items
PostPosted: Mon Apr 24, 2006 1:59 pm    Post subject: Need help with this question!! Reply with quote

Suppose you are given a two dimensional matrix. For example, 256 by 10000 where 256 is the number of rows and the 10000 is the number of columns. This matrix has the following properties:
1- Each entry is either 0 or 1 only.
2- Each columns must has exactly one 1.
Re-write the structure of the above matrix in a way that minimizes the space as much as you can.

For example:
If you store the 0 as int then the integer will take 4 bytes. If you store it as short integer then it will be 2 bytes. Therefore, you might think of other possible ways. If I were you, I will study the adjacency lists and the sparse matrix. I will try to get rid from the 0s and use the fact that each column has exactly one 1. You are allowed to use anything or any data structure you would like to use. For example, converting the above matrix into one dimensional solution is correct, but you need to check the required storage. Think of the 1s as bits not bytes. Note that total memory size must be as minimum as much as you can.
Back to top
View user's profile Send private message Send e-mail MSN Messenger
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Mon Apr 24, 2006 2:22 pm    Post subject: Reply with quote

Create a one dimensional array of 10,000 unsigned bytes.

Now populate it with ( row_number - 1 ) [0..255] where the 1-bit is set in each column.

Total size = 10,000 bytes = 80,000 bits

(Yeah, I know, someone else will have a smaller solution!)
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 24, 2006 3:36 pm    Post subject: Reply with quote

daj95376 wrote:
Total size = 10,000 bytes = 80,000 bits

(Yeah, I know, someone else will have a smaller solution!)

I don't think so. Indeed, if the process includes "solving the grid", another bit per column would be req'd to keep track of columns with/without a 1s placement.
Back to top
View user's profile Send private message
Novembre

Joined: 24 Apr 2006
Posts: 2
:

Items
PostPosted: Mon Apr 24, 2006 7:08 pm    Post subject: Reply with quote

I thought i can just store a vector of indexes of rows for which the column corresponding to this item index has a "1"... after all, there's just one pero column... ex.: index i of the vector has a j on it if item j,i in the matrix is a "1".

can this do??
Back to top
View user's profile Send private message Send e-mail MSN Messenger
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 24, 2006 7:35 pm    Post subject: Reply with quote

Novembre wrote:
I thought i can just store a vector of indexes of rows for which the column corresponding to this item index has a "1" ... can this do??

Sounds reasonable to me. How many bits does that take?
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Mon Apr 24, 2006 9:55 pm    Post subject: Reply with quote

rkral wrote:
daj95376 wrote:
Total size = 10,000 bytes = 80,000 bits

(Yeah, I know, someone else will have a smaller solution!)

I don't think so. Indeed, if the process includes "solving the grid", another bit per column would be req'd to keep track of columns with/without a 1s placement.


Please re-read his original request. There was no mention of solving the grid and he specifically stated that every column had exactly one occurrence of a 1. I answered his question within the given parameters!
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Tue Apr 25, 2006 1:10 am    Post subject: Reply with quote

daj95376 wrote:
Please re-read his original request. There was no mention of solving the grid and he specifically stated that every column had exactly one occurrence of a 1. I answered his question within the given parameters!

People often don't state the exact scenario, so please re-read my statement and note I said "if" as in "if the process includes solving the grid."
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron