Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Putting 1-9 randomly in 9 3x3 grids; rearranging till valid

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Fyska

Joined: 08 Nov 2005
Posts: 10
:

Items
PostPosted: Tue Nov 08, 2005 8:48 pm    Post subject: Putting 1-9 randomly in 9 3x3 grids; rearranging till valid Reply with quote

Hey

Am writing a Sudoku generator in C#, but am having real problems -

my method to make a generator is to:

Randomly put 1-9 in each 3x3 grid
Move the values around in the grids until the board is valid

Which sounds kind of simple, but I'm really having problems working out how to go about the moving business. I'm trying to look for the duplicates in the rows and swap them with duplicates in other rows, but it's messing up the 1-9 values in the 3x3 grids.

I should add that it ends up in an infinite loop of moving numbers around... I don't particularly want to rewrite the whole thing, the method of solving it by matrices or something crazy I don't understand at all :/

I doubt this is a particularly elegant method. Partly because it doesn't work...

Any suggestions?

Cheers.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Nov 09, 2005 12:49 am    Post subject: Reply with quote

This little piece of C# code
Code:
using System;
using System.Collections;

namespace SudokuGenerator
{
   public enum HouseType
   {
      Row,
      Column,
      Box
   }
   public enum CandidateStatus
   {
      Available,
      Selected,
      Eliminated
   }
   public class Cell
   {
      public House Row;
      public House Column;
      public House Box;
      public int BoxIndex;
      public Candidate[] Candidates;
      public Candidate Selected;
      public int Count;

      public Cell(Grid grid, int r, int c)
      {
         this.Row = grid.Rows[r];
         this.Column = grid.Columns[c];
         this.Box = grid.Boxes[ (r / 3) * 3 + (c / 3)];
         this.BoxIndex = (r % 3) * 3 + (c % 3);
         this.Candidates = new Candidate[9];
         for (int i = 0; i <9; i++) this.Candidates[i] = new Candidate(this,i);
      }
      public string Text
      {
         get
         {
            return "R" + this.Row.Number.ToString() + "C" + this.Column.Number.ToString();
         }
      }
      public void Clear()
      {
         this.Selected = null;
         this.Count = 9;
         foreach (Candidate cd in this.Candidates) cd.Status = CandidateStatus.Available;
      }
   }
   public class House
   {
      public HouseType Type;
      public int Index;
      public int Number;
      public Unit[] Units;

      public House(HouseType type, int index)
      {
         this.Index = index;
         this.Number = index + 1;
         this.Type = type;
         this.Units = new Unit[9];
         for (int i = 0; i <9; i++) this.Units[i] = new Unit(this,i);
      }
   }
   public class Unit
   {
      public House House;
      public int Index;
      public int Digit;
      public Candidate[] Candidates;
      public Candidate Selected;
      public int Count;

      public Unit(House hs, int i)
      {
         this.House = hs;
         this.Index = i;
         this.Digit = i + 1;
         this.Candidates = new Candidate[9];
      }
      public void Clear()
      {
         this.Selected = null;
         this.Count = 9;
      }
   }
   public class Candidate : IComparable
   {
      public Cell Cell;
      public int Index;
      public int Digit;
      public Unit Row;
      public Unit Column;
      public Unit Box;
      public int RandomID;
      public CandidateStatus Status;

      public Candidate(Cell cell, int index)
      {
         this.Cell = cell;
         this.Index = index;
         this.Digit = index + 1;
         this.Row = cell.Row.Units[index];
         this.Column = cell.Column.Units[index];
         this.Box = cell.Box.Units[index];
         this.Row.Candidates[cell.Column.Index] = this;
         this.Column.Candidates[cell.Row.Index] = this;
         this.Box.Candidates[cell.BoxIndex] = this;
      }
      public string Text
      {
         get
         {
            return this.Cell.Text + "D" + this.Digit.ToString();
         }
      }
      public void Select()
      {
         this.Status = CandidateStatus.Selected;
         this.Cell.Selected = this;
         this.Row.Selected = this;
         this.Column.Selected = this;
         this.Box.Selected = this;
      }
      public void Eliminate()
      {
         this.Status = CandidateStatus.Eliminated;
         this.Cell.Count--;
         this.Row.Count--;
         this.Column.Count--;
         this.Box.Count--;
      }
      public int MinSize
      {
         get
         {
            int r = this.Row.Count;
            if (this.Column.Count < r) r = this.Column.Count;
            if (this.Box.Count < r) r = this.Box.Count;
            return r;
         }
      }
      public int CompareTo(object obj)
      {
         Candidate peer = (Candidate)obj;
         if (this.MinSize == peer.MinSize) return this.RandomID.CompareTo(peer.RandomID);
         return this.MinSize.CompareTo(peer.MinSize);
      }
   }
   public class Grid
   {
      public Cell[,] Cells;
      public House[] Rows;
      public House[] Columns;
      public House[] Boxes;

      public override string ToString()
      {
         string s = string.Empty;
         for (int r=0;r<9;r++)
         {
            for (int c=0;c<9;c++) s += this.Cells[r,c].Selected.Digit.ToString();
            s += Environment.NewLine;
         }
         return s;
      }

      public Grid()
      {
         this.Rows = new House[9];
         this.Columns = new House[9];
         this.Boxes = new House[9];
         for (int i = 0; i <9; i++)
         {
            this.Rows[i] = new House(HouseType.Row,i);
            this.Columns[i] = new House(HouseType.Column,i);
            this.Boxes[i] = new House(HouseType.Box,i);
         }
         this.Cells = new Cell[9,9];
         for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) this.Cells[r,c] = new Cell(this,r,c);
      }
      public void Clear()
      {
         foreach (House hs in this.Rows) foreach (Unit u in hs.Units) u.Clear();
         foreach (House hs in this.Columns) foreach (Unit u in hs.Units) u.Clear();
         foreach (House hs in this.Boxes) foreach (Unit u in hs.Units) u.Clear();
         foreach (Cell cel in this.Cells) cel.Clear();
      }
      public void GenerateRandom()
      {
         while (!TryRandom()) {}
      }
      private bool TryRandom()
      {
         Random rnd = new Random();
         this.Clear();
         ArrayList source = new ArrayList(729);
         foreach (Cell cel in this.Cells)
            foreach (Candidate cd in cel.Candidates)
            {
               cd.RandomID = rnd.Next();
               source.Add(cd);
            }
         int Winners = 0;
         while (source.Count > 0)
         {
            source.Sort();
            Candidate winner = (Candidate)source[0];
            if (winner.MinSize == 0) return false;
            winner.Select();
            Winners++;
            if (winner.Cell.Count > 1)
            {
               foreach (Candidate victim in winner.Cell.Candidates)
                  if (victim.Status == CandidateStatus.Available)
                  {
                     victim.Eliminate();
                     source.Remove(victim);
                  }
            }
            if (winner.Row.Count > 1)
            {
               foreach (Candidate victim in winner.Row.Candidates)
                  if (victim.Status == CandidateStatus.Available)
                  {
                     victim.Eliminate();
                     source.Remove(victim);
                  }
            }
            if (winner.Column.Count > 1)
            {
               foreach (Candidate victim in winner.Column.Candidates)
                  if (victim.Status == CandidateStatus.Available)
                  {
                     victim.Eliminate();
                     source.Remove(victim);
                  }
            }
            if (winner.Box.Count > 1)
            {
               foreach (Candidate victim in winner.Box.Candidates)
                  if (victim.Status == CandidateStatus.Available)
                  {
                     victim.Eliminate();
                     source.Remove(victim);
                  }
            }
            source.RemoveAt(0);
         }
         return (Winners == 81);
      }
   }
}

Might generate sudoku grids for you.

Sorry, but I'm too lazy to document my code....

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Nov 09, 2005 12:56 am    Post subject: Reply with quote

And you can use this form to test it:
Code:
using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

namespace SudokuGenerator
{
   public class Form1 : System.Windows.Forms.Form
   {
      private Grid Grid;
      private System.Windows.Forms.Button button1;
      private System.Windows.Forms.Label labelGrid;
      private System.ComponentModel.Container components = null;

      public Form1()
      {
         InitializeComponent();
         this.Grid = new Grid();
      }
      protected override void Dispose( bool disposing )
      {
         if( disposing )
         {
            if (components != null)
            {
               components.Dispose();
            }
         }
         base.Dispose( disposing );
      }
      private void InitializeComponent()
      {
         this.button1 = new System.Windows.Forms.Button();
         this.labelGrid = new System.Windows.Forms.Label();
         this.SuspendLayout();

         this.button1.Location = new System.Drawing.Point(100, 236);
         this.button1.Name = "button1";
         this.button1.Size = new System.Drawing.Size(88, 24);
         this.button1.TabIndex = 0;
         this.button1.Text = "Generate";
         this.button1.Click += new System.EventHandler(this.button1_Click);

         this.labelGrid.Font = new System.Drawing.Font("Courier New", 14.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(0)));
         this.labelGrid.Location = new System.Drawing.Point(56, 12);
         this.labelGrid.Name = "labelGrid";
         this.labelGrid.Size = new System.Drawing.Size(188, 196);
         this.labelGrid.TabIndex = 1;

         this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
         this.ClientSize = new System.Drawing.Size(292, 266);
         this.Controls.Add(this.labelGrid);
         this.Controls.Add(this.button1);
         this.Name = "Form1";
         this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen;
         this.Text = "Sudoku Grid Generator";
         this.ResumeLayout(false);
      }
      [STAThread]
      static void Main()
      {
         Application.Run(new Form1());
      }
      private void button1_Click(object sender, System.EventArgs e)
      {
         this.Grid.GenerateRandom();
         this.labelGrid.Text = this.Grid.ToString();
      }
   }
}
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Nov 09, 2005 6:56 am    Post subject: Reply with quote

you could at least start with a random latin square
http://www.busygin.dp.ua/jacmat.c
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron