Post date: Aug 27, 2009 9:21:12 AM
Program.cs:
using System;using Sudoku;/* Felstavat mm */namespace Sudoku { class Sudukosolver { static void Main() { Agent agent = new Agent(); if (agent.solveProblem(new Classes.SudokuProblemItem().getProblemStart())) { Console.WriteLine("Yay"); Console.ReadKey(); } else { Console.WriteLine("Nay :("); Console.ReadKey(); } } } }
Agent.cs:
using System;using System.Collections.Generic;using Sudoku.Interfaces;namespace Sudoku { /// <summary> /// The agent will try to solv any problem that implements ISolvableNode, using tree search algorithms. /// </summary> class Agent { private readonly List<ISolvableNode> OPEN; private readonly List<ISolvableNode> CLOSED; private readonly List<ISolvableNode> NODES; private ISolvableNode root; public Agent() { OPEN = new List<ISolvableNode>(); CLOSED = new List<ISolvableNode>(); NODES = new List<ISolvableNode>(); } private bool solve(ISolvableProblemItem solvableProblemItem) { root = solvableProblemItem.getStartNode(); OPEN.Add(root); while (true) { if (OPEN.Count == 0) { Console.WriteLine("Failed after " + CLOSED.Count); return false; } ISolvableNode N = OPEN[0].createCopy(); CLOSED.Add(N.createCopy()); OPEN.RemoveAt(0); if (N.isGoal()) { N.print(); return true; } List<ISolvableNode> tmp = new List<ISolvableNode>(); tmp.Clear(); tmp = N.getChildren(); NODES.Clear(); for (short i = 0; i < tmp.Count; i++) NODES.Add(tmp[i]); for (int i = 0; i < OPEN.Count; i++) { for (int ii = NODES.Count - 1; ii > 0; ii--) { if (OPEN[i].isEqualTo(NODES[ii])) { OPEN[i].print(); NODES[ii].print(); NODES.RemoveAt(ii); } } } for (int i = 0; i < CLOSED.Count; i++) { for (int ii = NODES.Count - 1; ii > 0; ii--) { if ((CLOSED[i]).isEqualTo(NODES[ii])) { CLOSED[i].print(); NODES[ii].print(); NODES.RemoveAt(ii); } } } Expand(NODES); } } private void Expand(IList<ISolvableNode> cNODES) { for (int i = 0; i < cNODES.Count; i++) OPEN.Add(cNODES[i].createCopy()); } public bool solveProblem(ISolvableProblemItem solvableProblemItem) { return solve(solvableProblemItem); } }}
Interfaces used:
namespace Sudoku.Interfaces { interface ISolvableProblemItem { /// <summary> /// Indicates if this Item is the goal of the problem /// </summary> /// <returns></returns> bool isGoal(); /// <summary> /// Should set itself to be the startingpoint of the problem and then return itself or return /// </summary> /// <returns></returns> ISolvableProblemItem getProblemStart(); ISolvableNode getStartNode(); }}using System.Collections.Generic;namespace Sudoku.Interfaces { /// <summary> /// ISolvableNode is a state that can be transformed towards a goal. It is transformed by calling getChildren. /// </summary> interface ISolvableNode { /// <summary> /// Creates a copy of This Solvable Node /// </summary> /// <returns></returns> ISolvableNode createCopy(); /// <summary> /// If needed to initialize the SolvableNode /// </summary> void init(); /// <summary> /// Indicates if this Solvable Node is the solution to the problem. The Solvable Node need to define it's own goal. /// </summary> /// <returns>Should return true if it is the goal, else false</returns> bool isGoal(); /// <summary> /// Prints the current state of the Solvable Node /// </summary> void print(); /// <summary> /// Get all possible transformations of the Solvable Node /// </summary> /// <returns>A list of all possible solvable Nodes that can be transformed from This </returns> List<ISolvableNode> getChildren(); /// <summary> /// Indicates that This have the same state as f /// </summary> /// <param name="f">The other Solvale Node to compare to</param> /// <returns></returns> bool isEqualTo(ISolvableNode f); /// <summary> /// Some value that indicated uniqeness of the Solvable Node /// </summary> /// <returns>A long value</returns> long getChecksum(); ISolvableProblemItem SolvableProblemItem { get; set; } }}
Implementation of those interfaces to solve Sudoku:
using Sudoku.Interfaces;namespace Sudoku.Classes { class SudokuProblemItem : ISolvableProblemItem { private short[,] field; public SudokuProblemItem() { field = new short[9,9]; } public short this[int a, int b] { get { return Field[a, b]; } set { if(Field == null) Field = new short[9,9]; Field[a, b] = value; } } public short[,] Field { get { return field; } set { field = value; } } public bool isGoal() { for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (Field[j, i] == 0) return false; return true; } public ISolvableProblemItem getProblemStart() { Field = new short[9, 9]{ {0, 9, 0, 0, 0, 6, 1, 0, 0}, {0, 0, 0, 5, 0, 0, 0, 3, 2}, {3, 0, 4, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 8, 5, 0, 0, 1, 0}, {9, 5, 0, 6, 0, 0, 0, 8, 0}, {0, 0, 8, 0, 0, 9, 2, 0, 5}, {0, 0, 0, 0, 9, 0, 3, 0, 7}, {4, 0, 3, 2, 0, 0, 0, 0, 0}, {0, 6, 0, 0, 3, 5, 8, 0, 0} }; return this; } public ISolvableNode getStartNode() { return new SudokuNode(getProblemStart()); } }}using System;using System.Collections.Generic;using Sudoku.Interfaces;using Sudoku.Classes;namespace Sudoku { /* * Class Node * * Use as a node in the search tree with lots of fun stuff * * */ class SudokuNode : ISolvableNode { private long checksum; private SudokuProblemItem problemItem; public SudokuNode(ISolvableProblemItem problemItem) { SolvableProblemItem = new SudokuProblemItem(); short[,] cf = ((SudokuProblemItem)problemItem).Field; // Set the values of things ((SudokuProblemItem)SolvableProblemItem).Field = new short[9, 9]; for (int i = 0; i < 9; i++) for (int ii = 0; ii < 9; ii++) ((SudokuProblemItem)SolvableProblemItem)[i, ii] = cf[i, ii]; init(); } public ISolvableProblemItem SolvableProblemItem { get { return problemItem; } set { if(problemItem == null) problemItem = new SudokuProblemItem(); problemItem = (SudokuProblemItem)value; } } public ISolvableNode createCopy() { return new SudokuNode(SolvableProblemItem); } public void init() { calculateChecksum(); } public bool isGoal() // Indicates if this Node is the solution to the problem { //for (int i = 0; i < 9; i++) // for (int j = 0; j < 9; j++) // if (((SudokuProblemItem)SolvableProblemItem)[j, i] == 0) // return false; //return true; return SolvableProblemItem.isGoal(); } public void print() { printShort(); } private void printShort() { Console.WriteLine("Checksum is: " + checksum); for (short i = 0; i < 9; i++) { for (short ii = 0; ii < 9; ii++) Console.Write(" " + ((SudokuProblemItem)SolvableProblemItem)[i, ii]); Console.WriteLine(""); } Console.WriteLine(""); } private void calculateChecksum() { // Calculate the checksum of the Field. checksum = 0; checksum = SolvableProblemItem.GetHashCode(); } /// <summary> /// Get all children that can be transformed from this node. /// </summary> /// <returns></returns> public List<ISolvableNode> getChildren() { // Return all posible children for the 'next' position in the grid int[] next = getNextFreeSpot(); if (next == null) return null; // We could not find a free spot. Thus, we cannot return any children List<ISolvableNode> possible = new List<ISolvableNode>(); int counter = 0; for (short i = 1; i < 10; i++) { if (!(isInCol(i, next) || isInRow(i, next) || isInSquare(i, next))) { possible.Add(new SudokuNode(SolvableProblemItem)); ((SudokuProblemItem)((SudokuNode)possible[counter]).SolvableProblemItem)[next[0], next[1]] = i; possible[counter].init(); counter++; } } return possible; } /// <summary> /// Is this node equal to f? /// </summary> /// <param name="f">The other node to compare to</param> /// <returns></returns> public bool isEqualTo(ISolvableNode f) { calculateChecksum(); f.init(); if (checksum == f.getChecksum()) return true; return false; } /// <summary> /// Returns the checksum, some value that is unique to the current state /// </summary> /// <returns></returns> public long getChecksum() { return checksum; } /// <summary> /// Gets the location of the next free spot in the 9*9 (the big) grid /// </summary> /// <returns></returns> private int[] getNextFreeSpot() { // Finds the next spot in field in wich we can put a number // If this is used those spots who are assigned a number att start will not be evaluated with the getchildren, its ok since it would only have one children. // Save some memory.... // Can this function be altered in a way so that the next spot will be picked at random? And would that increase the overall performance of the solution? for (int i = 0; i < 9; i++) { for (int ii = 0; ii < 9; ii++) { if (((SudokuProblemItem)SolvableProblemItem)[i, ii] == 0) { int[] r = new int[] { i, ii }; return r; } } } Console.WriteLine("Found no spot to put the next number in. Is the playfield full?"); return null; // Found no spot, is it full? } /// <summary> /// Checks if n is in the current Row /// </summary> /// <param name="n">The number to look for</param> /// <param name="pos">The row to search in</param> /// <returns></returns> private bool isInRow(short n, int[] pos) { // true om finns i raden for (int i = 0; i < 9; i++) if (((SudokuProblemItem)SolvableProblemItem)[pos[0], i] == n) return true; return false; } /// <summary> /// Checks if n is in the current column /// </summary> /// <param name="n">The number to look for</param> /// <param name="pos">The row to search in</param> /// <returns></returns> private bool isInCol(short n, int[] pos) { // true om finns i columnen for (int i = 0; i < 9; i++) if (((SudokuProblemItem)SolvableProblemItem)[i, pos[1]] == n) return true; return false; } /// <summary> /// Checks if n is in the current 3*3 square /// </summary> /// <param name="n">The number to search for</param> /// <param name="pos">The square</param> /// <returns></returns> private bool isInSquare(short n, int[] pos) { // true om finns i raden short h = Convert.ToInt16(pos[0] / 3); short b = Convert.ToInt16(pos[1] / 3); for (short x = Convert.ToInt16(3 * b); x < Convert.ToInt16(3 * (b + 1)); x++) for (short y = Convert.ToInt16(3 * h); y < Convert.ToInt16(3 * (h + 1)); y++) if (((SudokuProblemItem)SolvableProblemItem)[y, x] == n) return true; return false; } }}