Introduction To Artificial Intelligence Program to solve sudoku problems

[qwijibow 0]

This is intended as an introduction to AI.

It covers depth first searches, but not anything too complicated like Neural networks or genetic programming.

 

Exaple code, and the finsihed source code is written in C++, so a basic knoledge of C++ will help.

As will a good understanding of recursive functions.

 

A recursive function is a function that calls itself.

for example, the following function...

 

int factorial(int n) {	if(n==1) { 		 return 1; 	 }	else {		 return n * factorial(n-1);	}}

example, factorial(5) == 5 * 4 * 3 * 2 * 1 = 120.

 

The game of sudoku is very simple, you can read the rules of the game, along with tips on how to solve the game at http://sudoku.com/

 

I picked sudoku as an example, because although the game can be difficult to solve, there is a definate finite number of moves untill the game is over, so the AI will know very quickly wether the game solvable or not, and how close the computer is to fins#ding a solution.

 

games like the rubix cube could go on for hours, with no indication of how close the computer is to finding a solution.

 

If you do not know the rules to sudoku, read up on them now.

 

 

/*****************************************************************************************************

STEP 1: Choosing the best type of AI to solve the problem.

 

This type of problem requires a tree method.

where all possable moves are considered, all good moves are varried out, untill the game is solved.

 

there are two main differant types, BREADTH FIRST and DEPTH FIRST.

 

This is a Breadth first search:

 

KEY:

CIRCLES are game states, variables hodling what game pieces are in what politions, or in sudoku, what numbers aer in which squares.

 

LINES represent a possable move, which would turn the game state from the state at the top of the line, to the state below the line, for example, in chess, quees moves forwards 2 squares, or in sudoku, I place a "3" at coordinate (2,5).

 

NUMBERS within the circles show the order in which the game states were created and examined.

 

This completed tree, shows that in order to complete this puzzle, from the initial game state, the player must make the moves A->B->B in that order. (whre the letters represent a move, e.g. move queen 2 spaces forward)

 

Breadth first search is good in games where we need to find all possable solutions, OR the best solution out of many solutions, OR where the total nuumber of moves to complete the game is un-known.

 

In sudoku, we know the maximum number of moves.. (keep playing untill all squares are not empty),

No Solution is any better than any other solution, and we only need to know one solution.

 

So we will be using a Depth first search.

 

This is a depth first search:

 

In this method, we go deep first, going towards the end game as quickly as possable until we get stuck, Then we go backwards untill we find an earlyer state with possable moves not yet explored, and then explore one of them in the same depth first way.

 

The solution to this problem was A->B->D

 

This all looks complicated, but in fact its incredably simple to program using stacks / lists.

 

here is the pseudo code for breadth first search..

 

// breadth first searchloop {	state = Remove a state from the LEFT side of the list.   	for (all possable moves we can perform to state) {		   new_state = state.Do_Possable_Move	   	   if(new_state == game_over) { finsihed }	   else {			 put new_state to the RIGHT side of the list	   }	}}

To turn this breadth first search into a depth first search, simple change the line

 

state = Remove a state from the LEFT side of the list

to

state = Remove a state from the RIGHT side of the list

Think about that pseudo code, and imagine it going through those trees in the diagram.

Its really quite simple !

 

/*****************************************************************************************************

STEP 2: Creating the STATE class.

 

The state class needs to remember every details about the current state, and be as memory efficiant as possable,

In some types of AI, there will be millions of states created, in sudoku, however, only a few thousand will be used,

and only 40ish will be loaded and in memory at one time, so its not too important.

 

we will need...

1)A char array of 81 (to hold a 9x9 board of numbers)

i use char instead of int, as char uses less memory as an integer, and we only need to hold 0 to 9.

 

2) Copy constructors to make copys of game states from other states, or other char arrays.

 

3) a function to perform a move on the current game state.

 

4) a function to test if a move is legal

 

5) a function to check if the puzzle is completed

 

6) a function to display the current game state graphically. (well.. in an ascii art grid )

 

here is the class prototype...

 

class state {private:	char board[81];	// 9x9 board. coords(x,y) = board[(9*y)+x]	bool legalMoveX(int,char) const;	// (Y,N)  legal to put N into horizontal where line y=Y ?	bool legalMoveY(int,char) const;	// (X,N)  legal to put N into verticle where x = X ?	bool legalMoveB(int,int,char) const;	// (X,Y,N)	legal to put N into 3x3 grid starting at X,Y ?public:	state();	//	  Start with a completely empty board	state(const state &);	  //	  Copy constructor	state(const char *);	  //	  Start with board copyed from chat array	state(const state &, int,int,char);	// (S,X,Y,N)  Copy state S, then put N into coord X,Y	const char *getMemRef() const;  //	  get pointer to baord (for copy constructors use only)	bool legalMove(int,int,char) const;	// (X,Y,N)	legal to put N into coord X,Y ?	bool isComplete()  const;  // is this state the solved puzzle ?	bool isEmpty(int,int)  const;  // (X,Y)  board[(Y*9)+X] == 0 ?	void print() const;	  // Output a graphical rpresentation of the board.};

The full source code to state is

 

http://forums.xisto.com/no_longer_exists/

and

http://forums.xisto.com/no_longer_exists/

 

As this is an AI tutorial, and not a C++ tutorial, i will not be talking through the state class code.

However, i have fully commented the source code, so have a look at state.cpp source code

for explanations of how the state works.. its all very simple really, only a very basic understanding of c++ is needed.

 

 

/*****************************************************************************************************

STEP 3: The AI !!!

 

The last source code file is here (and contains the AI unction expand())

http://forums.xisto.com/no_longer_exists/

 

The AI is all done in the function expand(const state &s);

 

bool expand(const state &S) {	// RECURSIVE FUNCTION !	char x,y,n;	// if this state is complete, print it, and return true.	// returning true at any point will cause all instances of expand() to exit.	if(S.isComplete()) {  cout << "Solution is..." << endl;  S.print();  return true; 	}	// for each square on the board (x,y)	for(y=0; y<9; y++) {  for(x=0; x<9; x++) {	  // for each possable number to put in that square	  for(n=1; n<10; n++) {	// legal to put n into board at coordinate (x,y) ???	if(S.legalMove(int(x),int(y),n)) {		// if yes, perform this move on a new state, and expand it (RECURSE !!!)		if(expand( state( S, int(x), int(y), n) )) {	  // if expanding this function returns true,	  // then a future state of this state has solved the puzzle	  // end the recursice loop, also return true	  return true;		}	}	  }	  // if this square is not solved	  if(S.isEmpty(x,y)) {	// then dont attempt to solve the next one, if its un-solvable now, it will always be so.	// an error hase been made, end this brand of recursion, but not all recursion	return false;	  }  }	}	return false;}

At first, i wrote this code as a loop (no recursion), with a stack holding all the states.

And each state had to remember what possable moves had ben attempted, and which had not yet been attempted.

 

then i realised, that i was simply re-coding exactly what the c++ compiler does with the internal stacks when recursive functions are used.

 

Allowing the c++ compiler to handle all the stack code via a recursive function halfed the size of the expand function, made it a little faster, so i decided to go with recusrion instead of a stack and loop.

 

However recursive runctions can be a little confusing if you are new to them.

 

If you are new to recursion, take a look at this tutorial http://www.cprogramming.com/tutorial/lesson16.html

 

The above function, follows the logic...

 

1) Is this state a finsihed puzzle state.. if yes, exist all recursion and print the sollution, else continue2) are there any possable legal moves that have not yet been expanded ?3) if no, goto 64) if yes, expand one of them as a daughter state, and start again at 1),4) if expand returned true, exit all recursion.5) if expanded returns false, goto  2)6) dead end ! go back ot a parent state, and start again at 1)

read the function code comments for a detailed description of what is happening.

 

NOTE: since this tutorial was posted, i have been working on this program.

it has a Graphical user interface (written in c++) and runs under winows, linux unix and macOSX.

http://forums.xisto.com/no_longer_exists/

 

 

Corrections / Surgestions / Comments, post them here, thanks.