Sudoku Solved!

I did it! Today I wrote a program using backtracking that will solve any solvable Sudoku puzzle...

wooooooooooooohoooooooooooooooooooooooo


It only uses backtracking.

Most of the time it solved them pretty quickly.
Sometimes with the very very difficult ones it takes up to 5 minutes. (Difficult being those advertised as difficult on websites, boosk etc..)

[update: with the most .most most difficult one's it takes way too long... I started it on one of the minimum 17 hint puzzles 3 hours ago; and its still running and will be for a while.... it definitely needs heuristics... it will be interesting to see how long it takes. I doubt its intractable. I suspect though, if I used the MRC heuristic it would have been solved ages ago... I am going to add that heuristic tonight hopefully...]


When I add in the some of the CSP heuristics I expect it to solve the problems even quicker!!

Here is the link to the GPLd code. I know I know. It needs to be refactored, it needs error handling, yeah yeah....

I am in shock...

I add the MVC heuristic functor...

//    Copyright 2007 Little Me
//    This file is part of Littlemeuko.
//
//    Littlemeuko is free software; you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation; either version 2 of the License, or
//    (at your option) any later version.
//
//    Littlemeuko is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.

//    You should have received a copy of the GNU General Public License
//    along with  Littlemeuko; if not, write to the Free Software
//    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

#include "csp_sudoku.h"

void SelectNaiveUnassignedperator()(worldstate & ws, int & row, int & col)
  {
    ws.SelectUnassigned(row,col);
  }


void SelectMCVUnassignedperator()(worldstate & ws, int & row, int & col) 
{
  
  int count = 0;
  string placeholder;
  for (int posvalue = 1; posvalue<10; posvalue++) {// number of unassigned positions area
    for (int i = 0; i<9; i++) {
      //find most constrained row
      placeholder = ws.GetRow(i);
      for (int j = 0; j<placeholder.size();j++) {
	if (( placeholder[j] - '0'  == 0) count++;
      }
      if (count == posvalue) {	// yay!
	for (int j = 0; j<placeholder.size();j++) {
	  if (( placeholder[j] - '0' == 0 )
	    { row=i;col=j; goto Done; } 		// Goto considered harmful 
	}
      }
      else
	count = 0;
    }
  }
 Done:
  ;
};

I then change the one line of my main code from

 if (solution = recursebacktrack(&neo,SelectNaiveUnassigned())) { ..

to

  if (solution = recursebacktrack(&neo,SelectMCVUnassigned())) {

And the search for my previously pathological case (that took over 12 hours to solve) got solved in..

FIVE SECONDS.

I am giddy.

(And I only checked for the most constrained row - not column or region.. that would even make it faster... so soon to be added.)

Later:

I only moved the worst case to a different problem. But the search time is still reduced jusr not to 5 seconds.

I have now added the shuffling of the order in which values are tried in empty spaces, following Lycium's suggestion.

template <typename Selector>
worldstate * recursebacktrack(worldstate * ws, Selector Select)
{
  int row;
  int col;

  if (SHOWSTAGES) 
    cout << *ws << endl;

  if ((*ws).isSuccess())
    return ws;
  else
    {
       Select(*ws,row,col);
       vector<int> untried;
      for (int i=1; i<10; i++)  //Sudoku Values from 1 to 9
	untried.push_back(i);
      // shuffle values so that worst case scenario is reduced in likelihood.
      // idea suggested to me by T. Ludwig
      srand(time(0));
      random_shuffle(untried.begin(), untried.end());
      vector<int>::iterator itr = untried.begin();
        for (; *itr; itr++) { //Sudoku Values from 1 to 9
	int test_row,test_col;
	test_row = row;
	test_col = col;
     	(*ws).Insert(row,col,*itr);
 
        if ((*ws).isValid()) {
	  while(recursebacktrack(ws,Select))
	    if ((*ws).isSuccess())
	      return ws;
	}
	(*ws).Insert(test_row,test_col,0);   
      }
      return NULL;
    }
};