Installed May 2015
This is a slight aside just to explain what we mean when we say an int and string are immutable, but lists and dictonaries are mutable.
The second video goes on to explain how this is relevant when we pass variables into functions.
We need this in our Soduko solver because we will be passing lists around all the time, and it is important to realise we are actually only passing references to the list around and not copying the whole thing. Thus when we change the list in the function, we have actually changed the list in main as well, because it is the same list. !!!! Wow !!!!
The list of lists [ ,,,… ] is used for the board where the first index represents the column and the second the row. However the list above just contains an empty list for each column. We want each column to itself contain a list, with contents for each row.
The problem is what to put in each element of the column list for our initial empty grid.
Initially some cells will contain the known starting values. Other cells will have nothing. However these blank cells will be populated with the range of possible values they could contain, hence another list.
This we end up with the need for a list of list to represent the board, where each element (cell) contains a list of possible values. It is really a list of lists of lists … a, three dimensional array.
One of the first challenges in this type of program is how were are going to represent the board in code.
The board is a grid of 9 columns by 9 rows and each intersection forms a cell.
A cell will contain either,
- A number for a known cell
- A blank or a space
- A range of numbers 1 – 9 of possible values that may be in the cell.
This looks like a 2 dimensional array where we use x,y coordinates to specify a cell. The cell can then contain a list of possible values.
Python uses list for arrays and a list of lists for 2 D arrays. So lets get our mind around that concept 🙂
Cab you now do this to simulate the full Sudoku Board of 9 x 9 grid ?
NOTE – Do not use the grid in the video above as a starting point. It is just for illustration and does not have a solution. (Thanks to Gillian Ward for spotting that one 🙂 )
Before we try to code a problem, we must make sure we really understand what we are trying to accomplish and how we are going to approach it.
Thus in this case it is necessary to have a go at solving a few Sudoku puzzles yourself. There are loads on line. Just keep to the easy ones for now.
You will find yourself applying several strategy simultaneously and being able to flick between scanning rows, columns and squares. When you think how to code this it can feel very daunting. What you need to do is just focus on one strategy and apply it methodically.
Our basic computer strategy will start by taking a grid and filling all the unknown cells, with the full range of numbers 1-9, with the knowledge that one of these in each cell is correct. We then eliminate the numbers one by one from the unknown cells using the rules of Sudoku and logic until there is only one number left in a cell. This MUST then be the number left in the cell.
The first basics strategy is to remove known values from a cell because they are already in the row, column or square to which the cell belongs.
Watch the next video to see it in action.
Sudoku puzzles have been around for some time now and are an excellent way to develop your mind in logical thinking and deduction.
The mathematical nature lends itself to being represented by a computer program and thus be solved using algorithms.
If your new to Sudoku, watch the intro that comes next.
To create code we need to think what we are trying to achieve.
A simple program to get our teeth into is a number guessing game. The computer picks a random number and we try to guess it. The computer tells us if we are too high or too low. When we guess it it tells us we have got it correct
So lets come up with a plan
Lets have a deeper look at the if statements.
Lets code it in scratch to see we have the logic right. This can help with the transition from a drag and drop language to a text based one. Also scratch is a bit like sudo code and allows us to test an idea.
Here is the SCRATCH file
Now we understand the problem, lets code it in Python
OK, It works, but can we improve it ?
Here is the Python File