Sudoku Naive-solver

You'll be creating a program called sudoku-naive.py which will be called with either python or python3 (depending upon the "#!" line) as follows:

python3 sudoku-naive.py  <input-filename> <output-filename>  <ID-of-sudoku-board>

The input-filename will probably be "Sudoku-boards-Master-unsolved.txt".  So, for instance, if the command line was:

python3 sudoku-naive.py Sudoku-boards-1-test.txt first-answer.txt A1-1

... then you should output to "first-answer.txt":

6,9,4,1,8,3,5,2,7
2,1,3,7,9,5,4,6,8
5,8,7,6,2,4,9,3,1
3,5,8,2,7,1,6,9,4
1,2,6,4,3,9,8,7,5
7,4,9,8,5,6,2,1,3
4,7,2,9,1,8,3,5,6
8,3,1,5,6,2,7,4,9
9,6,5,3,4,7,1,8,2

Note that there are no spaces or brackets "[ ]" in the output. Also note that the word "unsolved" in the command-line argument, has been changed to "solved" in the output file

Tips:

• Number the cells, starting at 0 for the upper-left, and then proceeding left-to-right, then down, in normal reading direction, until the bottom-right at cell 80.
  
• I call the groups of cells which have to contain different numbers: "cliques".  For instance, an entire row is a clique, as well as a column, as well as a "box".  Here's the list of the cell positions in all the cliques:

Cliques=[[0,1,2,3,4,5,6,7,8],\
[9,10,11,12,13,14,15,16,17],\
[18,19,20,21,22,23,24,25,26],\
[27,28,29,30,31,32,33,34,35],
[36,37,38,39,40,41,42,43,44],
[45,46,47,48,49,50,51,52,53],\
[54,55,56,57,58,59,60,61,62],\
[63,64,65,66,67,68,69,70,71],\
[72,73,74,75,76,77,78,79,80,],\
[0,9,18,27,36,45,54,63,72],\
[1,10,19,28,37,46,55,64,73],\
[2,11,20,29,38,47,56,65,74],
[3,12,21,30,39,48,57,66,75],\
[4,13,22,31,40,49,58,67,76],\
[5,14,23,32,41,50,59,68,77],\
[6,15,24,33,42,51,60,69,78],\
[7,16,25,34,43,52,61,70,79],\
[8,17,26,35,44,53,62,71,80],\
[0,1,2,9,10,11,18,19,20],\
[3,4,5,12,13,14,21,22,23],\
[6,7,8,15,16,17,24,25,26],\
[27,28,29,36,37,38,45,46,47],\
[30,31,32,39,40,41,48,49,50],\
[33,34,35,42,43,44,51,52,53],\
[54,55,56,63,64,65,72,73,74],\
[57,58,59,66,67,68,75,76,77],\
[60,61,62,69,70,71,78,79,80]
]

• Every cell is a member of 3 cliques.  It will probably be useful to have a dictionary whose key is a cell position, and whose value is the combined list of the positions of all the members of its 3 cliques, without duplication and without the primary cell included.  We can call this the cell's "neighborhood".
  
  
• The naive solver should do the following (as discussed in class): (Imagine that we're in the middle of the algorithm...)
  
  
  1. go to the next open cell.  If there aren't any left, we've found a solution.  Clean up and write out.
     
     
  2. Forced? see if the cell is "forced" into a single number, i.e. its neighbors have 8 numbers used, and one number unused, and therefore this cell must have the unused number.  If so, use that number and go to #1
     
     
  3. Guess next? try guessing "1" and check if invalid with all of the cell's neighbors.  If invalid, then try "2", etc. Let's say "3" works.  Then record that you've used the "3" and the current state of the board, and store (probably in a stack), because we may have to backtrack to here, if  the "3" turns out to be a bad guess.  Then go to #1
     
     
  4. If you've tried all numbers from "1" to "9", and none of them work, then we've reached a contradiction.  Backtrack to the most recent guess, restore its board, and try the next number guess from there.
     
     
• Increment a backtracking counter, to keep track of how many times you've backtracked.  This will eventually measure the goodness of your algorithm
  
• Print out the elapsed time and the number of backtracks (the ProgramTester doesn't care what you print) so that you can eventually compare these stats to your future smarter solver.