Welcome! Log In Create A New Profile

Advanced

suduko

Posted by dve83 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
suduko
February 18, 2011 09:08PM
mmm, seems very quiet here...
question on the suduko:

they ask for the full state diagram, showing only legal states...
if I take the initial state as the 2x2 diagram they provide, and then try to draw out each possible legal state (one move at a time), im going to end up with the combination of the first 11 moves, each followed by a combination of the next 10 moves, 9, 8, 7. Hence a tree structure that has the same number of nodes in each branch... each of which will eventually get to the goal state...

Am I correct? or am i missing something here...

help would be appreciated, finding this kind of difficult.

Danie van Eeden
------------------------
Re: suduko
February 21, 2011 11:43AM
I haven't done this question yet, but I am a Suduko fan,
I don't think every possible move will reach the goal state. And at each stage there will be very few legal moves. As soon as you reach a fail move you stop that branch. So the tree shouldn't actually be all that big.

Anybody else? Come on!!!!! Some of you must be working on this by now and have some thoughts to share, right or wrong.
Re: suduko
February 21, 2011 11:53AM
Hi,

thx again for participating smile smile

see the thing is, they ask ONLY LEGAL moves to be shown in the state space.

thus

As soon as you reach a fail move you stop that branch

in based on that, we can never fail... hence we will never stop in a branch because of an illegal move. We will simply be entering all the legal moves in different combinations.. which to me sounds kind of silly.

Danie van Eeden
------------------------
Re: suduko
February 21, 2011 02:09PM
The way you put it, it does sound kind of silly. I haven't got any other thoughts right now. I'll get back to you when I've had a stab at it myself. Maybe then I will know what I am talking about rather than taking shots in the dark.
JoJ.
Re: suduko
February 22, 2011 04:57PM
to me it seems that we're only to consider states that follow the rules of the game. imagine if we were to exhaust all possible states...we would not finish on time. for question c are we supposed to program?
Re: suduko
February 23, 2011 09:47PM
Hi, for c, I think we have to take your state diagram and indicate graphically how to arrive at the solution with each search algorithm

Danie van Eeden
------------------------
Re: suduko
February 23, 2011 10:00PM
regarding the states

imagine the following

2 1 a b
4 c d e
f g h 4
i j 1 k

this is the initial state,

a possible next state would be

2 1 4 b
4 c d e
f g h 4
i j 1 k

where a = 4
OR even with a = 3 (nothing prohibits this, if this is your first choice - even though you might find it wrong later).

but seeing as though a=3 is NOT the correct state, a=4 is the only option (hence we should only show this state - this is what we are asked to do - to show only legal states)

if so, we could start at any of the possible 11 blank blocks, Enter the correct value, and then follow any of the remaining 10 blocks - entering the value. Then any of the remaining 9 blocks entering the correct value.

eg. two possible initial states

2 1 4 b
4 c d e
f g h 4
i j 1 k

2 1 a 3
4 c d e
f g h 4
i j 1 k

then a possible 2nd state

2 1 4 3
4 c d e
f g h 4
i j 1 k

which would overlap coming from one of the previous two.

Is this what we are aiming at? or am I mad?

Danie van Eeden
------------------------
Re: suduko
March 01, 2011 11:26AM
spoken to the lecturer:

we are suppose to choose a method of solving this thing - not just start at a state and then try and figure out all possible states to follow that selection.

Hence, we choose to solve either LINE by LINE or ROW by ROW - also we are NOT to show any state that resolves to ILLEGAL. hence if you are to insert a 3 somewhere (and that 3 is going to cause it to be ILLEGAL), just skip everything down that path.

basically we are limiting our solution states - eg. by choosing row by row solution - you will have only two states in the first row that are legal. There after, the forst row is considered COMPLETE, then you start with row2.

My mistake was to fill in one value in ROW1, and then try and make up all possible choices in all other rows and columns thereafter. I ended up with 70 states (halfway through the combinations from the 2nd state) and then finally decided that I needed some advice smile

Danie van Eeden
------------------------
Re: suduko
March 10, 2011 05:27PM
Danie I just looked again at my sudoku question and I can see what you were talking about when you said you were freaking out...this state space seems to just explode. Anyway will try again and hopefully get to a solution that is more compact.
Sorry, only registered users may post in this forum.

Click here to login