| Naive | Start at the beginning (upper left corner) and find the next open cell. Choose one of the possibilities of that cell and place it. Go to the next open cell and backtrack when there are no possibilities for an open cell. |
| Smart | Before solving, place all of the values in the obvious cells (cells with only one possibility) until there are no more obvious cells. Then find the next open cell and pick one of the possibilities into it. This time, after every guess, try to fill in all of the obvious cells. Backtrack condition same as naive solution. |
| Even Smarter | Instead of choosing the next open cell, choose the cell that has the least number of possibilities. As with the smart method, the algorithm will place in values for all of the obvious cells before the start of the search and after every insertion. |
| Notes | I used a single array of length 81 to store my board. My algorithm pushes a dictionary of the entire board, an index of the cell that was just added, and the other possibilities of that cell to the stack for backtracking. A weird thing about my Smart algorithm is that it takes longer than my naive algorithm even though it is backtracking less. |
| Naive | Smart | Even Smarter | |
|---|---|---|---|
| A1 | time = 0.001547 secs, backtracks = 120 | t = 0.001541, b = 0, ratio (Naive/Smart) = ∞ | t = 0.001476, b = 0, r = ∞ |
| A2 | t = 0.199, b = 31381 | t = 0.315, b = 297, r = 105 | t = 0.0291, b = 11, r = 2852 |
| A3 | t = 0.0896, b = 12,787 | t = 0.205, b = 177, r = 72 | t = 0.127, b = 96, r = 133 |
| A4 | t = 0.271, b = 42,170 | t = 0.356, b = 315, r =133 | t = 0.0104, b = 1, r = 42,170 |
| A5 | t = 0.0503, b = 6,286 | t = 0.0196, b = 8, r = 785 | t = 0.0214, b = 7, r = 898 |
| A6 | t = 0.385, b = 61,904 | t = 0.692, b = 811, r = 76 | t = 0.296, b = 239, r = 259 |
| A7 | t = 20.874, b = 2,493,808 | t = 63.647, b = 54,358, r = 45 | t = 8.788, b = 5,318, r = 468 |
| A8 | t = 180.567, b = 18,994,973 | t = 274.148, b = 278,490, r = 68 | t = 8.622, b = 5,523, r = 3439 |